一种基于层次引力模型的不平衡数据分类方法及其系统

摘要

本发明公开了一种基于层次引力模型的不平衡数据分类方法及其系统，该方法包括以下步骤：S1，获取待分类样本集Z，待分类样本集Z中的样本都包含D个属性，D为正整数；S2，对样本的属性值进行区间划分，每个属性划分为L个区间，L为正整数，样本划分为LD个D维立方体，并计算属性权重；S3，划分特征空间，将待分类样本集Z放入对应的层次D维立方体里，结合引力模型对样本进行标记分类。本发明解决以下问题：针对多层次模型在不同分辨率下对属性进行加权，改善了层次模型的分类性能；通过对属性在不同分辨率下进行划分建立层次分类模型，提高了分类的效率；使用局部引力模型优化了空间重叠区域数据的分类精度。

说明书

技术领域

本发明涉及计算机数据分析与挖掘领域，特别是涉及一种基于层次引力模 型的不平衡数据分类方法及其系统。

背景技术

不平衡数据集,即各个类拥有的样本数量之间有较大差异的数据集。在不平 衡数据集的二分类中,通常把样本数量少的类称为正类,对应的,样本数量多的 类称为负类。数据不平衡性在当前的应用中十分常见,如医疗诊断、入侵检测、 预防诈骗、从卫星图像分辨事物等分类时,正类的分类正确率是我们主要在意的 问题.例如在疾病诊断中,健康者被误诊的情况会在复查时得到解决,然而癌症 患者被误判为正常则可能会引起无法挽回的结果。

由于失衡数据集中数据样本类别分布的特殊性，原本能够很好解决常态数 据分类问题的策略在失衡数据分类问题上却显得力不从心，甚至有些方法给出 的分类结果不能被人们接受。因此，要解决失衡数据分类问题，必须对现有的 分类策略进行改进，这种改进主要可以从数据端和算法端两方面来着手。

从数据端处理失衡数据集就是在尽量不改变原数据集分布规律和信息表达 的基础上，通过增加或删除某类元素，平衡两类数据元素数量，使失衡数据集 变成相对较平衡的数据集，并使用现有的分类算法完成分类任务；从算法端解 决失衡数据集分类问题就是用较小的代价和较小的改动对现有的分类算法进行 改良，通过某些合理的方法使得原本不适合分类失衡数据的分类算法能够较好 的分类失衡数据。

1.从数据端解决失衡数据集问题：

从数据端解决失衡数据集分类问题的常用方法是数据重采样技术。数据重 采样技术是在不改变现有分类算法的基础上，从数据集在数据空间的分布出发， 针对某一类的数据对象进行重采样，从而达到平衡数据失衡比，降低由于样本 分布失衡而对分类器造成不良影响的目的。从采样策略上看，采样可以分为简 单随机采样和启发式采样两种。简单随机采样并不利用数据集中元素的特点和 相关信息，只是随机的增加或删除某些样本。而启发式采样则在采样时充分利 用数据元素所蕴含的信息，有指导的对数据集进行重采样。从采样技术上看， 采样可以分为上采样和下采样，在失衡数据集中，上采样是通过增加正例数据 元素的数量来平衡数据分布的，而下采样则是通过删除反例中的某些数据元素 来平衡数据分布的。

2.从算法端解决失衡数据集问题：

从算法端解决失衡数据集分类问题的常用方法是代价敏感学习和集成学习 算法。在平衡数据分类问题中，人们常常使用分类准确率来评价分类器的分类 性能，这种评价方法是建立在分类器将各类别数据元素错分的代价是相同的。 由于失衡数据集类别分布的特性，使得反例和正例元素的错分意义不同，而代 价敏感学习就是对不同类别数据元素建立不同的错分代价的一种机器学习策 略。集成学习方法是通过组建多个分类器，来克服传统单一分类器分类失衡数 据的瓶颈，通过不同的子分类器训练分类数据，并通过内部的整合机制，综合 地得出最终的分类结果，从而解决失衡数据集分类问题。

另外，基于数据引力和数据引力场，有人提出了一种新的分类方案(DGC)。 这个分类方案的主要思想是：

1)根据训练数据集生成数据粒子训练集。数据粒子的计算遵循一定的原则。

2)测试集的所有测试数据被视为原子数据粒子。数据粒子训练集中的任何 粒子对测试样本中的数据粒子都具有引力。

3)训练数据粒子和测试数据粒子之间的引力服从数据引力定律。

4)一旦训练数据粒子集合被建立，数据空间的数据的引力场也被建立，并 且数据空间任何位置的引力场强度可以计算。

5)一个测试数据对某个类的归属程度是由该数据类在该数据所在位置的引 力场大小所决定的。

现有的不均衡数据分类技术，存在诸多不足,现就传统DGC(英文全称)算 法的不足进行分析：

DGC的一个重要过程就是创建数据质点。创建数据质点的最简单方法是将数 据空间中每个单独的数据作为一个数据质点。用这种方法，训练数据集中的每 个样本都形成一个数据质点，所以，原始训练集中有多少个样本，就形成多少 个训练数据质点。显然，这种方法非常简单而且易于实现，另外，用这种方法 建立的训练数据质点集来计算数据引力场，可以取得比较高的精度。但是这种 方法的缺点也是显而易见的：随着训练数据集规模的增大，数据质点集的规模 也就随之增大，分类的计算量也就要增大，这就不可避免地影响分类效率。

另一种创建数据质点的方法是最大距离原理(MDP，英文全称)。MDP方法能 将训练集中对数据引力场影响相近的元素归并到一起，显然这样做大大减少了 分类计算量，提高了分类效率。但这种方法影响了数据引力场的计算精度，特 别是在数据质点的质心附近，因为在数据质点质心的邻域内，由于原始数据比 较密集，该区域的数据引力场梯度变化比较快，场比较复杂，而数据质点创建 后，根据数据质点计算的数据引力场则丢失了原引力场的一些信息，因此这就 必然会影响分类精度。

另外，DGC算法对特征的加权相当敏感，选择有效的特征权重不仅能大大提 高DGC算法分类效率，甚至能提高其分类精度。

发明内容

本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种 基于层次引力模型的不平衡数据分类方法及其系统。

为了实现本发明的上述目的，本发明提供了一种基于层次引力模型的不平 衡数据分类方法，包括以下步骤：

S1，获取待分类样本集Z，所述待分类样本集Z中的样本都包含D个属性， 所述D为正整数；

S2，对样本的属性值进行区间划分，每个属性划分为L个区间，所述L为正 整数，样本划分为L^D个D维立方体，并计算在不同分辨率下属性的权重；

S3，划分特征空间，将所述待分类样本集Z放入对应的D维立方体里，利用 空间自然领域，结合引力模型对样本进行标记分类。在使用引力模型时只计算 周围相邻D维立方体内样本的引力，可以提高局部的分类精度，同时提高分类 速度。

本发明旨在根据样本的分布情况，在不同分辨率下对样本进行分类，以提 高分类速度。同时，在分辨率较高时使用引力模型，可以解决在正负样本空间 重叠时样本难以划分的问题，提高分类的准确率。

在本发明的一种优选实施方式中，步骤S2包括以下步骤：

S21，设置初始分辨率s和终止分辨率e，并设置当前分辨率l；

S22，统计每个样本第j个属性值，并选出第j个属性值中的最大值Max_j和 最小值Min_j，其中1≤j≤D且j为正整数，所述D为属性个数且D为正整数；

S23，将每个属性值划分为L个区间，每个区间长度为(Max_j-Min_j)/L，则样 本空间O_L划分为L^D个D维立方体，所述L为正整数，且L＝l；

S24，计算正类样本和负类样本分布在每个区间上的样本的个数X_+i和X_-i， 所述X_+i表示在第i个区间上的正类样本的个数，所述X_-i表示在第i个区间上的负 类样本的个数；

S25，计算正类样本和负类样本在每个属性上的距离；

S26，计算属性权重。

在本发明的一种优选实施方式中，在步骤S25中，距离的计算方法为：

$d_j=\sqrt{\underset{i=1}{\overset{L}{\Sigma }}\frac{\left|X_{+i}\right|}{\left|X_{+}\right|}-\frac{\left|X_{-i}\right|}{\left|X_{-}\right|}},$

其中X_+i、X_-i、X₊和X_-分别依次表示为分辨率l下第i个区间上的正类样本 的个数、第i个区间上负类样本的个数、所有正类样本的个数和所有负类样本的 个数，L为属性划分的区间个数。

由于该距离对数据的不平衡不敏感，所以，该计算方法可以很好的适应数 据不平衡的情况。

在本发明的一种优选实施方式中，在步骤S26中，属性权重的计算方法为：

$w_j=\frac{d_j}{{\Sigma }_{i=1}^D{d}_i}$

d_j表示正类样本和负类样本在分辨率l下第j个属性上的距离，D为属性个 数。

在本发明的一种优选实施方式中，步骤S3包括如下步骤：

S31，若l＝s，将样本集Z中的样本放入对应的D维立方体里；否则将分辨 率为l/2时，未划分的样本集合Z′_l/2里的样本放入对应的D维立方体里，根据当前 分辨率l和D维立方体的位置生成D维立方体的标识：

$(p_{1l_1}{p}_{1l_2}...p_{1l_j}...p_{1l},p_{2l_1}{p}_{2l_2}...p_{2l_j}...p_{2l},p_{{\mathrm{il}}_1}{p}_{{\mathrm{il}}_2}...p_{{\mathrm{il}}_j}...p_{il},p_{{\mathrm{Dl}}_1}{p}_{{\mathrm{Dl}}_2}...p_{{\mathrm{Dl}}_j}...p_{Dl}),$

其中，表示D维立方体在分辨率l_j下第i个属性上的位置，l为当前分辨 率，D为属性个数；

S32，扫描当前分辨率的所有D维立方体，若对于任意D维立方体x属于样 本空间O_L，如果D维立方体x中的样本个数不为0,则D维立方体x为l下的有效 的D维立方体；

S33，若D维立方体x在分辨率为l/2时标记为+(或-)，则D维立方体x在 分辨率为l时，同样标记为+(或-)；

若D维立方体x为未划分的样本集合Z′_l/2内的D维立方体，若对于任意属于D 维立方体x的样本的类标签相同且为+(或-)，则将D维立方体标记为+(或-)， 否则标记为*；

S34，对任意D维立方体x，x的标记记为L(x)；x相邻的任意D维立方体y， y的标记记为L(y)：

若L(x)为*，则将x放入上一分辨率2/l无法分类的样本集合Z_l'中，Z_l'为分 辨率l下要进行分类的样本，令分辨率l＝2×l，执行步骤S35；

若L(x)为+(或-)且满足L(y)＝L(x)，则x最终标记为+或(-)，表示x标 记完成，不必进入下一分辨率处理，退出程序；l＝2×l

若L(x)为+(或-)且L(y)不为*,且存在L(y)与L(x)不相同，则使用引力模 型计算x相邻D维立方体内样本对x内样本的引力，并根据正负引力的值对x内 样本分类，若每个样本分类结果与x的标签均相同，则x最终标记为+或(-)， 否则标记为*，将x放入Z_l'，令分辨率l＝2×l，执行步骤S35；

若存在L(y)为*，则将x放入Z_l'，令分辨率l＝2×l，执行步骤S35；

S35，若满足l＝e，划分结束；若不满足，返回步骤S22。

在本发明的一种优选实施方式中，引力模型的计算方法为：

对于待分类样本t，计算其所在的D维立方体的相邻D维立方体内正类样本 和负类样本对其引力F₊和F_-：

若F₊≥F_-,则t标记为+，否则标记为-；

若相邻D维立方体内都不包含样本，则计算分辨率为l/2时，t所在D维立 方体周围的D维立方体内样本对其的引力。

在本发明的一种优选实施方式中，负类样本对待分类样本t的引力计算方法 为：

$F_{-}=F(i_{-},t)=\frac{1}{d^2(i_{-},t)},d^2(i_{-},t)=\underset{k=1}{\overset{D}{\Sigma }}{(\frac{A_{i_{-}k}-A_{tk}}{{\mathrm{Max}}_k-{\mathrm{Min}}_k}\times w_k)}^2;$

正类样本对待分类样本t的引力计算方法为：

$F_{+}=F(i_{+},t)=\frac{n(-)/n(+)}{d^2(i_{+},t)},d^2(i_{+},t)=\underset{k=1}{\overset{D}{\Sigma }}{(\frac{A_{i_{+}k}-A_{tk}}{{\mathrm{Max}}_k-{\mathrm{Min}}_k}\times w_k)}^2;$

其中,n(+)表示所有正类样本的个数,n(-)表示所有负类样本的个数，表 示负类样本i的第k个属性值，表示正类样本i的第k个属性值，Max_k和Min_k依 次表示第k个属性的最大值和最小值，w_k为第k个属性的属性权重，A_tk表示待分 类样本t的第k个属性值。

本发明还公开了一种基于层次引力模型的不平衡数据分类系统，包括：样 本获取模块、属性划分加权模块和标记分类模块；

所述样本获取模块获取待分类样本集Z并传输给所述属性划分加权模块，所 述待分类样本集Z中的样本都包含D个属性，所述D为正整数；

所述属性划分加权模块根据权利要求2-4之一所述的方法对属性划分和加 权，将每个属性划分为L个区间，所述L为正整数，样本划分为L^D个D维立方体， 并计算属性权重；

标记分类模块将所述待分类样本集Z放入对应的D维立方体里，根据权利要 求5-7之一所述的方法对样本进行标记分类。

综上所述，由于采用了上述技术方案，本发明的有益效果是：本发明解决 了以下问题：1)针对多层次模型在不同分辨率下对属性进行加权，改善了算法 的分类性能；2)通过对属性在不同分辨率下进行划分建立层次分类模型，提高 了分类的效率；3)使用局部引力模型优化了数据的分类精度；4)选择合适的 分层依据，确保了分层的有效性和合理性；5)自适应的利用不同分辨率下的样 本空间中的自然近邻样本辅助分类，克服了传统近邻算法中k值难以确定的问 题。

附图说明

图1是本发明流程示意图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自 始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元 件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能 理解为对本发明的限制。

本发明提供了一种基于层次引力模型的不平衡数据分类方法，包括以下步 骤：

第一步，获取待分类样本集Z，待分类样本集Z中的样本都包含D个属性， D为正整数。

第二步，对样本的属性值进行区间划分，每个属性划分为L个区间，L为正 整数，样本划分为L^D个D维立方体，并计算在不同分辨率下属性的权重，即计 算每个分辨率下的属性的权重。在本实施方式中，具体包括以下步骤：

S21，设置初始分辨率s和终止分辨率e，并设置当前分辨率l；

S22，统计每个样本第j个属性值，并选出第j个属性值中的最大值Max_j和 最小值Min_j，其中1≤j≤D且j为正整数，D为属性个数且D为正整数；

S23，将每个属性值划分为L个区间，每个区间长度为(Max_j-Min_j)/L，则样 本空间O_L划分为L^D个D维立方体，L为正整数，且L＝l；

S24，计算正类样本和负类样本分布在每个区间上的样本的个数X_+i和X_-i， X_+i表示在第i个区间上的正类样本的个数，X_-i表示在第i个区间上的负类样本的 个数；

S25，计算正类样本和负类样本在每个属性上的距离；在本实施方式中，距 离的计算方法为：

$d_j=\sqrt{\underset{i=1}{\overset{L}{\Sigma }}\frac{\left|X_{+i}\right|}{\left|X_{+}\right|}-\frac{\left|X_{-i}\right|}{\left|X_{-}\right|}},$

其中X_+i、X_-i、X₊和X_-分别依次表示为分辨率l下第i个区间上的正类样本 的个数、第i个区间上负类样本的个数、所有正类样本的个数和所有负类样本的 个数，L为属性划分的区间个数。

S26，计算属性权重。在本实施方式中，属性权重的计算方法为：

$w_j=\frac{d_j}{{\Sigma }_{i=1}^D{d}_i}$

d_j表示正类样本和负类样本在分辨率l下第j个属性上的距离，D为属性个 数。

第三步，划分特征空间，将待分类样本集Z放入对应的D维立方体里，结合 引力模型对样本进行标记分类。在本实施方式中，具体包括如下步骤：

S31，若l＝s，将样本集Z中的样本放入对应的D维立方体里；否则将分辨 率为l/2时，未划分的样本集合Z′_l/2里的样本放入对应的D维立方体里，根据当前 分辨率l和D维立方体的位置生成D维立方体的标识：

$(p_{1l_1}{p}_{1l_2}...p_{1l_j}...p_{1l},p_{2l_1}{p}_{2l_2}...p_{2l_j}...p_{2l},p_{{\mathrm{il}}_1}{p}_{{\mathrm{il}}_2}...p_{{\mathrm{il}}_j}...p_{il},p_{{\mathrm{Dl}}_1}{p}_{{\mathrm{Dl}}_2}...p_{{\mathrm{Dl}}_j}...p_{Dl}),$

其中，表示D维立方体在分辨率l_j下第i个属性上的位置，l为当前分辨 率，D为属性个数；

S32，扫描当前分辨率的所有D维立方体，若对于任意D维立方体x属于样 本空间O_L，如果D维立方体x中的样本个数不为0,则D维立方体x为l下的有效 的D维立方体；

S33，若D维立方体x在分辨率为l/2时标记为+(或-)，则D维立方体x在 分辨率为l时，同样标记为+(或-)；

若D维立方体x为未划分的样本集合Z′_l/2内的D维立方体，若对于任意属于D 维立方体x的样本的类标签相同且为+(或-)，则将D维立方体标记为+(或-)， 否则标记为*；

S34，对任意D维立方体x，x的标记记为L(x)；x相邻的任意D维立方体y， y的标记记为L(y)：

若L(x)为*，则将x放入上一分辨率无法分类的样本集合Z_l'，该Z_l'也是分辨 率l下要进行分类的样本，令分辨率l＝2×l，执行步骤S35；

若L(x)为+(或-)且满足L(y)＝L(x)，则x最终标记为+或(-)，表示x标 记完成，不必进入下一分辨率处理；

若L(x)为+(或-)且L(y)不为*,且存在L(y)与L(x)不相同，则使用引力模 型计算x相邻D维立方体内样本对x内样本的引力，并根据正负引力的值对x内 样本分类，若每个样本分类结果与x的标签均相同，则x最终标记为+或(-)， 否则标记为*，将x放入Z_l'，令分辨率l＝2×l，执行步骤S35；在本实施方式中， 引力模型的计算方法为：

对于待分类样本t，计算其所在的D维立方体的相邻D维立方体内正类样本 和负类样本对其引力F₊和F_-：

若F₊≥F_-,则t标记为+，否则标记为-；

若相邻D维立方体内都不包含样本，则计算分辨率为l/2时，t所在D维立 方体周围的D维立方体内样本对其的引力。

在本发明的一种优选实施方式中，负类样本对待分类样本t的引力计算方法 为：

$F_{-}=F(i_{-},t)=\frac{1}{d^2(i_{-},t)},d^2(i_{-},t)=\underset{k=1}{\overset{D}{\Sigma }}{(\frac{A_{i_{-}k}-A_{tk}}{{\mathrm{Max}}_k-{\mathrm{Min}}_k}\times w_k)}^2;$

正类样本对待分类样本t的引力计算方法为：

$F_{+}=F(i_{+},t)=\frac{n(-)/n(+)}{d^2(i_{+},t)},d^2(i_{+},t)=\underset{k=1}{\overset{D}{\Sigma }}{(\frac{A_{i_{+}k}-A_{tk}}{{\mathrm{Max}}_k-{\mathrm{Min}}_k}\times w_k)}^2;$

其中,n(+)表示所有正类样本的个数,n(-)表示所有负类样本的个数，表 示负类样本i的第k个属性值，表示正类样本i的第k个属性值，Max_k和Min_k依 次表示第k个属性的最大值和最小值，w_k为第k个属性的属性权重，A_tk表示待分 类样本t的第k个属性值。

若存在L(y)为*，则将x放入Z_l'，令分辨率l＝2×l，执行步骤S35；

S35，若满足l＝e，划分结束；若不满足，返回步骤S22。

本发明还公开了一种基于层次引力模型的不平衡数据分类系统，包括：样 本获取模块、属性划分加权模块和标记分类模块。其中，样本获取模块获取待 分类样本集Z并传输给属性划分加权模块，待分类样本集Z中的样本都包含D个 属性，D为正整数，属性划分加权模块对属性划分和加权，将每个属性划分为L 个区间，L为正整数，样本划分为L^D个D维立方体，并计算属性权重。标记分类 模块将待分类样本集Z放入对应的D维立方体里，利用空间自然邻域，结合引力 模型对样本进行标记分类。具体的引力模型、属性划分、加权以及样本的标记 分类方法都在方法部分描述，在此不作赘述。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、 “具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特 征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明 书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描 述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中 以合适的方式结合。

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解： 在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、 替换和变型，本发明的范围由权利要求及其等同物限定。