本发明涉及不平衡数据的分类技术领域，具体是一种边界合成、混合采样、异常检测算法及数据分类方法。
背景技术：
分类是数据挖掘和机器学习中重要的知识获取手段之一，经典的分类算法通常是基于数据集平衡这一假设而提出的，而在实际应用中，许多数据集是不平衡的，并且少数类数据有时更重要，将其错分要付出更大的代价，如信用卡欺诈检测、医疗诊断、垃圾邮件判别等。因此，以总体分类精度为学习目标的传统分类算法并不适用于不平衡数据的分类，研究如何提高分类器对不平衡数据的分类效果有着重要的意义。
近年来，许多学者在多个领域如文本分类、欺诈检测、故障诊断、无线传感器入侵检测、医疗诊断、推荐系统中根据用户点击进行分析等方面研究了不平衡数据的分类问题。目前，主要有两个方法去解决这一问题，第一种方法是从数据的角度出发，对原始的训练数据进行重采样，使数据分布较为平衡；第二种是从分类算法的角度出发，考虑分类器对不平衡数据分类的缺陷和误分类的代价对分类算法进行改进，使得新的分类算法可以在不平衡数据集上取得较好的分类效果。
重采样技术分为欠采样(undersampling)和过采样(oversampling)。欠采样通过筛选多数类数据来平衡数据集，最简单的欠采样方法是随机欠采样rus(randomundersampling)，rus从原始多数类数据集中随机筛选数据，使整体数据集较为平衡，但这种方式可能删除一些有代表性的多数类数据，使分类器无法完整的学习数据中隐含的规则。为了克服rus的这一缺点，很多学者进而提出其它的欠采样方法，如tomeklinks算法，邻域清理法ncl(neighborhoodcleaning)算法，最近邻规则欠采样enn(editednearestneighbor)算法，基于knn算法的knn欠采样算法等。另外也有学者提出利用聚类算法对多数类样本进行聚类，按比例抽取多数类样本，使新的数据集与原数据集有相似的样本分布。孟晓龙则是通过使用逻辑回归算法对多数类样本进行预测，并按概率抽取样本。
与欠采样相似，最简单的过采样方法是随机过采样ros(randomoversampling)，ros通过复制少数类样本使原始数据集较为平衡，但这种方法可能会导致过拟合。chawla等人提出的smote算法通过分析少数类样本特征空间，生成与少数类样本相似的样本来使数据集平衡。bsmote算法则是寻找处于不同类别数据的边界数据，进而对少数类边界数据过采样。杨毅等人提出了精化边界的smote算法，其根据边界样本的分布，对少数类样本设置不同的过采样倍率。为了减少smote算法在合成少数类样本的随机性，也有学者提出了smote-d算法。还有学者提出对不同的少数类样本寻找适合的k值进行新的数据合成。而c_smote算法则是不需要定义smote算法的k值，而是围绕少数类样本的重心合成新的数据。
除了欠采样和过采样分别使用的方法，学者们又相继提出组合采样方法和集成采样方法，例如将smote算法与enn算法与tomeklinks算法相结合。有学者提出了easyensemble算法和balancecascad算法，这两种算法都是利用集成学习的机制，通过多次随机抽取多数类样本与原少数类样本共同构建平衡数据子集去训练多个分类器，这种方法降低丢失多数类数据中的信息的可能。也有学者提出了一种以集成学习方式来处理企业信用评估不平衡问题，它采用不同的过采样率进行多次对少数类样本过采样与多次随机欠采样相结合构建数据集。
在算法层面，通常是针对不平衡数据的特点改进原有的分类算法或者是构造新算法。如集成学习分类方法、基于单类学习的方法、基于代价敏感学习的方法和基于核方法的分类算法等。由于不平衡数据分类时对少数类样本错分要付出更高的代价，因此使用在评价中引入代价的代价敏感学习，此时的分类目标不是为了降低分类的错误率，而是为了降低整体分类的代价。刘东启等人采用过采样技术与不同错误代价相结合的技术对支持向量机算法进行改进以适应不平衡数据的分类。
集成学习是处理不平衡数据分类问题的主要手段之一，集成学习的几种典型的方法有：bagging,boosting,adaboost,随机森林等。陈启伟等人提出了结合代价敏感与集成学习的信用评分模型。周志华等人提出了基于有排除的结合策略的选择性集成算法gasen。
总体的来说，就是目前以总体分类精度为学习目标的传统分类算法并不适用于不平衡数据的分类，基于此，本申请提出了一种边界合成、混合采样、异常检测算法及数据分类方法。
技术实现要素：
本发明的目的在于提供一种边界合成、混合采样、异常检测算法及数据分类方法，以解决上述背景技术中提出的问题。
为实现上述目的，本发明提供如下技术方案：
一种边界合成算法，包括以下步骤：
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n；
步骤一，通过bsmote算法将正类样本集为p分成噪声样本集、边界样本集和安全样本集；
步骤二，在给定过采样率ratio的情况下，训练数据集需合成新样本的数量g得以确定，为每个正类边界样本赋予采样权值ωj，由ωj与g得到每一个正类边界样本应合成新样本的数目gj；
步骤三，将步骤二所得的gj个新样本与噪声样本集、安全样本集和负类样本集共同组成平衡的训练数据集。
作为本发明进一步的方案：所述采样权值ωj为：
式中，dsumpj为正类边界样本到它m最近邻中各个正类样本距离之和，m为正类样本在原始训练数据集d中的最近邻数量，m'为正类样本最近邻中负类样本的数量。
一种混合采样算法，包括以下步骤：
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n；
步骤一，使用欠采样方法和如上述所述的自适应边界合成算法分别对负类样本集和正类样本集进行重新采样；
步骤二，得到若干个平衡数据子集；
步骤三，以adaboost算法为基分类器gt(x)，对若干个平衡数据子集进行处理，并为基分类器引入关于f1值的分类误差率εt'，并以分类误差率εt'计算基分类器gt(x)的权值αt；
步骤四，将若干个平衡数据子集的处理结果汇总与原始训练数据集合并后输出。
作为本发明再进一步的方案：所述分类误差率εt'为：
εt'＝εt*(1-f1t)，式中，f1t为第t次迭代时基分类器gt(x)分类后的f1值。
作为本发明再进一步的方案：所述基分类器gt(x)的权值αt为：
作为本发明再进一步的方案：步骤三中，在f1值迭代过程中，更新基分类器gt(x)的权值αt。
作为本发明再进一步的方案：在t 1次迭代时，权值ωt 1,i与t次迭代时的权值ωti的关系为：
其中zt是规范因子，使得
一种异常检测算法，其包括以下步骤：
步骤一，设置好参数，对数据进行预处理；
步骤二，将步骤一所得的数据利用iforest算法进行处理，滤除其中平均分割路径长度小于设定阈值的数据，保留平均分割路径长度不小于设定阈值的数据作为正常数据子集；
步骤三，利用lof算法对步骤二中滤除的、平均分割路径长度小于设定阈值的数据进行处理，剔除其中不符合要求的数据作为异常数据子集，其余数据作为正常数据子集。
本发明的另一目的在于提供一种数据分类方法，包括以下步骤：
通过bsmote算法将正类样本集p分成噪声样本集、边界样本集和安全样本集；
在给定过采样率ratio的情况下，训练数据集需合成新样本的数量g得以确定，为每个正类边界样本赋予采样权值ωj，由ωj与g得到每一个正类边界样本应合成新样本的数目gj；
将所得的gj个新样本与噪声样本集、安全样本集和负类样本集共同组成平衡的训练数据集；
分别对负类样本集和正类样本集进行重新采样，得到若干个平衡数据子集；
以adaboost算法为基分类器gt(x)，对若干个平衡数据子集进行处理，并为基分类器引入关于f1值的分类误差率εt'，并以分类误差率εt'计算基分类器gt(x)的权值αt；
将若干个平衡数据子集的处理结果汇总与原始训练数据集合并后输出；
设置好参数，对所得数据进行预处理；
将所得的数据利用iforest算法进行处理，滤除其中平均分割路径长度小于设定阈值的数据，保留平均分割路径长度不小于设定阈值的数据作为正常数据子集；
利用lof算法对滤除的、平均分割路径长度小于设定阈值的数据进行处理，剔除其中不符合要求的数据作为异常数据子集，其余数据作为正常数据子集。
与现有技术相比，本发明的有益效果是：通过bsmote算法将正类样本分为噪声样本，边界样本和安全样本，并对对边界样本赋予权值以合成新的正类样本，这样可以在边界上更好的区分正负类样本，同时可以避免正类样本中的噪声合成更多新的样本影响分类效果；通过对基分类器的权值进行迭代更新，可以减缓样本错分时的权值增长速度，也可以使样本正确分类时权值减小速度变缓，保证正确率。
附图说明
图1为一种边界合成算法的流程图。
图2为一种边界合成算法的流程图。
图3为一种异常检测算法的流程图。
具体实施方式
这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本公开相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本实施例公开的一些方面相一致的装置和方法的例子。
实施例1
请参阅图1，本发明实施例中，一种边界合成算法。
此处，首先对现有的bsmote算法进行介绍。
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n，负类样本数目为nnum，p＝{p1,p2,…,ppnum}，n＝{n1,n2,…,nnnum}，bsmote算法的具体过程描述如下：
(1)对于每一个正类样本pi(i＝1,2,…,pnum)，在原始训练数据集为d中使用knn算法计算其m最近邻，在这m个最近邻中负类样本的数目为m'(0≤m'≤m)；
(2)若m'＝m，说明这个正类样本pi的m最近邻都是负类样本，将其视为噪声样本；
若m/2≤m'＜m，说明这个正类样本pi的m最近邻中负类样本数目大于正类样本数目，将其视为边界样本；
若0≤m'＜m/2，说明这个正类样本pi的m最近邻中正类样本数目大于负类样本数目，则将其视为安全样本；
(3)所有边界样本都属于正类样本，设正类边界样本为p'，正类边界样本数目为bnum(0≤bnum≤pnum)，p'＝{p1',p2',…,pbnum'}，对于每一个正类边界样本：
pj'(j＝1,2,…,bnum)，在正类样本集p中使用knn算法计算它的k最近邻；
(4)对于每一个正类边界样本pj'，从上述步骤中得到它在正类样本中的k最近邻，在这k个样本中随机选择sj(1≤sj≤k)个样本，在pj'与sj个样本之间使用smote算法合成新的正类样本，正类边界样本集中所有样本共合成
(5)新合成的正类样本与原始训练数据集d共同构成平衡数据集d'。
smote算法和bsmote算法都是对于一个正类样本从它的k最近邻样本中随机选择s个样本，之后在这个正类样本和s个样本之间合成新的正类样本，这两种算法对于每个正类样本需合成新的正类样本的数目都是随机选择的，没有考虑到正类样本彼此之间存在着差异，从而存在一定的盲目性。
因此，本实施例基于此问题拟提出自适应边界合成少数类过采样算法。该算法对正类边界样本加以区分，根据正类边界样本的学习难易程度自适应计算其应合成新的正类样本的数目，并使用smote算法进行合成。为了实现此目的首先要完成正类边界样本采样权值的确定。
具体的，一种边界合成算法，其包括以下步骤：
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n；
步骤一，通过bsmote算法将正类样本集为p分成噪声样本集、边界样本集和安全样本集；
步骤二，在给定过采样率ratio的情况下，训练数据集需合成新样本的数量g得以确定，为每个正类边界样本赋予采样权值ωj，由ωj与g得到每一个正类边界样本应合成新样本的数目gj；
步骤三，将步骤二所得的gj个新样本与噪声样本集、安全样本集和负类样本集共同组成平衡的训练数据集。
而对于采样权值ωj的确定方式，具体如下：
采样权值ωj是根据正类边界样本的学习难易度而确定的，对于所有正类边界样本，难分类的样本即是靠近负类样本或者是远离其它正类样本的样本，由于难分类的样本合成新的样本数量应该更多，所以它的采样权值ωj更大，反之，采样权值ωj较小。
对于上述bsmote算法中，由于其对于每一个正类样本pi需要在原始训练数据集d上找到它的m最近邻，在这m个最近邻中负类样本的数目为m'，边界样本的m'的范围或取值为m/2≤m'＜m。
在这样的前提条件下，本实施例中，考虑到正类边界样本pj'的m'越大时，说明此正类边界样本pj'较为靠近负类样本并远离其它的正类边界样本，
当不同正类边界样本pj'的m'相等时，可选择此正类边界样本到它m最近邻中各个正类样本距离之和dsumpj或到它m最近邻中各个负类样本距离之和dsumnj作为判断依据。当dsumpj较大时，则说明此正类边界样本pj'较为远离其它的正类样本；当dsumnj较小时，则说明此正类边界样本pj'较为靠近负类样本；
当m'不同时，仅用dsumpj或dsumnj两个值将无法进行判断，若dsumpj值较大时，可能是此正类边界样本pj'其它正类样本，也可能是由于它的m最近邻中正类样本更多导致的；反之，当dsumnj较小时，可能是此正类边界样本pj'较为靠近负类样本，也可能是由于它的m最近邻中负类样本较少导致。因此当综合考虑m'、dsumpj和dsumnj时，则需考虑平均距离
即：正类边界样本pj'到它最近邻中各个正类样本的平均距离
总得来说，确定每个正类边界样本pj'的采样权值ωj的确定条件如下：
比较pj'的m'，若m'越大则采样权值ωj越大；
当pj'的m'相等时，dsumpj越大，采样权值ωj越大；dsumnj越小，采样权值ωj越大；
当pj'的m'不等时，
综上所述，综合考虑m'和平均距离，为了使难分类的正类边界样本权重较大，提出了公式来计算正类边界样本采样权值ωj：
实施例2
请参阅图2，本发明实施例中，一种混合采样算法，包括以下步骤：
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n；
步骤一，使用欠采样方法和如实施例1所述的自适应边界合成算法分别对负类样本集和正类样本集进行重新采样；
步骤二，得到若干个平衡数据子集，从图2可以看出，平衡数据子集的编号从1至m；
步骤三，以adaboost算法为基分类器gt(x)，对若干个平衡数据子集进行处理，并为基分类器引入关于f1值的分类误差率εt'，并以分类误差率εt'计算基分类器gt(x)的权值αt，且在f1值迭代过程中，更新基分类器gt(x)的权值αt；
步骤四，将若干个平衡数据子集的处理结果汇总与原始训练数据集合并后输出。
f1值通常作为分类器对不平衡数据的分类效果的评价标准，定义f1值的分类误差率为εt'：
εt'＝εt*(1-f1t)
其中，f1t为第t次迭代时基分类器gt(x)分类后的f1值(εt代表何意义)；
根据f1值的分类误差率εt'计算基分类器gt(x)的权值αt；
f1值是小于1的值，f1值越大，表示基分类器gt(x)对不平衡数据的分类效果越好，反之，则越差。
当εt相同时，f1t越小，则εt'越大，即当基分类器gt(x)对不平衡数据分类效果不好时，分类误差率εt'增加。当εt'越大时，αt则越小，即当εt相同时，基分类器gt(x)分类后的f1值越小将导致该基分类器gt(x)的权值αt越小；换言之，基分类器gt(x)对不平衡数据的分类效果越差，将导致它在最终分类器中的重要性越低。
由于对基分类器gt(x)的权值αt更新过程进行了改进，使得f1t越大时，εt'会更小导致基分类器gt(x)权值αt相对更大，将导致分错的样本在下一次迭代的权值ωt 1,i增长过快，夸大了基分类器gt(x)错分样本的问题。因此本实施例还提出了在f1值迭代过程中，更新基分类器gt(x)的权值αt，具体的：
更新第t 1次迭代的训练数据集中每个样本的权值ωt 1,i为：
其中zt是规范因子，使得
其中p为调节参数，取值为[1,10]之间的整数，当样本被错误分类时，由于αt＞0，所以
实施例3
请参阅图3，本发明实施例中，一种异常检测算法，其包括以下步骤：
步骤一，设置好参数，对数据进行预处理(此处的参数，是指在借鉴后面的lof算法时，对其模型参数需要作出适应性改变)；
步骤二，将步骤一所得的数据利用iforest算法进行处理，滤除其中平均分割路径长度小于设定阈值的数据，保留平均分割路径长度不小于设定阈值的数据作为正常数据子集；
步骤三，利用lof算法对步骤二中滤除的、平均分割路径长度小于设定阈值的数据进行处理，剔除其中不符合要求的数据作为异常数据子集，其余数据作为正常数据子集。
异常检测的目标是寻找与数据集中大部分数据不同的异常数据，这些异常数据被称为异常点。异常点定义为：相对于数据集中其它数据，异常点是使用不同的机制产生的且数量上相对较少的数据。简言之，异常点是“少而不同”的。
实施例4
本发明实施例提供了一种数据分类方法，包括以下步骤：
通过bsmote算法将正类样本集p分成噪声样本集、边界样本集和安全样本集；
在给定过采样率ratio的情况下，训练数据集需合成新样本的数量g得以确定，为每个正类边界样本赋予采样权值ωj，由ωj与g得到每一个正类边界样本应合成新样本的数目gj；
将所得的gj个新样本与噪声样本集、安全样本集和负类样本集共同组成平衡的训练数据集；
分别对负类样本集和正类样本集进行重新采样，得到若干个平衡数据子集；
以adaboost算法为基分类器gt(x)，对若干个平衡数据子集进行处理，并为基分类器引入关于f1值的分类误差率εt'，并以分类误差率εt'计算基分类器gt(x)的权值αt；
将若干个平衡数据子集的处理结果汇总与原始训练数据集合并后输出；
设置好参数，对所得数据进行预处理；
将所得的数据利用iforest算法进行处理，滤除其中平均分割路径长度小于设定阈值的数据，保留平均分割路径长度不小于设定阈值的数据作为正常数据子集；
利用lof算法对滤除的、平均分割路径长度小于设定阈值的数据进行处理，剔除其中不符合要求的数据作为异常数据子集，其余数据作为正常数据子集。
本实施例借鉴了过滤的设计思想，将不同的算法视为不同粒度的过滤器，尤其适用于处理数据候选集与推荐结果数量相差过多的情况。具体是将前一个算法过滤后的结果作为输入递交给后一个算法，通过这样的层层筛选，候选结果在此过程中会被逐步过滤，最终得到一个精度较高的结果。通常将时间复杂度较低，区分度较差的算法放在前面，将时间复杂度较高，区分度较强的算法放在后面，这样的优点在于可充分运用不同算法的区分度，将宝贵的运算资源集中应用在质量较高的候选集上。
由于iforest算法时间复杂度低，lof算法时间复杂度高，且后者对局部异常数据的区分精度高于前者。考虑到iforest算法是根据计算每个数据的异常分数判断数据是否异常，而异常分数是一个全局概念，很多局部异常点的异常分数不会超过0.5，将该算法作为一个过滤器，以平均分割路径长度为阈值判断依据，将平均分割路径长度小于阈值l的数据集放入候选异常子集并作为下一个算法的输入，将平均分割路径长度大于等于阈值l的数据集放入正常数据子集。这样会在一定程度上减少传递给下一个算法的数据量。
基于平均路径的iforest算法过滤了一部分正常数据，使得接下来使用lof算法时正常数据被判断为异常数据的数目减少，降低了lof算法的假正率；又因为候选异常子集中数据的数目明显少于原数据集中数据的数目，降低了lof算法的时间复杂度。文献[44]提出了用于空间异常点挖掘的slof算法，该算法在求邻域距离时使用了剔除平均的思想，本项目将借鉴该思想对lof算法进行改进，继续降低假正率，得到更为精确的异常数据。
本领域技术人员在考虑说明书及实施例处的公开后，将容易想到本公开的其它实施方案。本申请旨在涵盖本公开的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本公开的一般性原理并包括本公开未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本公开的真正范围和精神由权利要求指出。
应当理解的是，本公开并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。本公开的范围仅由所附的权利要求来限制。
1.一种边界合成算法，其特征在于，包括以下步骤：
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n；
步骤一，通过bsmote算法将正类样本集p分成噪声样本集、边界样本集和安全样本集；
步骤二，在给定过采样率ratio的情况下，训练数据集需合成新样本的数量g得以确定，为每个正类边界样本赋予采样权值ωj，由ωj与g得到每一个正类边界样本应合成新样本的数目gj；
步骤三，将步骤二所得的gj个新样本与噪声样本集、安全样本集和负类样本集共同组成平衡的训练数据集。
2.根据权利要求1所述的一种边界合成算法，其特征在于，所述采样权值ωj为：
式中，dsumpj为正类边界样本到它m最近邻中各个正类样本距离之和，m为正类样本在原始训练数据集d中的最近邻数量，m'为正类样本最近邻中负类样本的数量。
3.一种混合采样算法，其特征在于，包括以下步骤：
设原始训练数据集为d，正类样本集为p，正类样本数目为pnum，负类样本集为n；
步骤一，使用欠采样方法和如上述所述的自适应边界合成算法分别对负类样本集和正类样本集进行重新采样；
步骤二，得到若干个平衡数据子集；
步骤三，以adaboost算法为基分类器gt(x)，对若干个平衡数据子集进行处理，并为基分类器引入关于f1值的分类误差率εt'，并以分类误差率εt'计算基分类器gt(x)的权值αt；
步骤四，将若干个平衡数据子集的处理结果汇总与原始训练数据集合并后输出。
4.根据权利要求3所述的一种混合采样算法，其特征在于，所述分类误差率εt'为：
εt'＝εt*(1-f1t)，式中，f1t为第t次迭代时基分类器gt(x)分类后的f1值。
5.根据权利要求4所述的一种混合采样算法，其特征在于，所述基分类器gt(x)的权值αt为：
6.根据权利要求5所述的一种混合采样算法，其特征在于，在t 1次迭代时，权值ωt 1,i与t次迭代时的权值ωti的关系为：
其中zt是规范因子，使得
7.一种异常检测算法，其特征在于，包括以下步骤：
步骤一，设置好参数，对数据进行预处理；
步骤二，将步骤一所得的数据利用iforest算法进行处理，滤除其中平均分割路径长度小于设定阈值的数据，保留平均分割路径长度不小于设定阈值的数据作为正常数据子集；
步骤三，利用lof算法对步骤二中滤除的、平均分割路径长度小于设定阈值的数据进行处理，剔除其中不符合要求的数据作为异常数据子集，其余数据作为正常数据子集。
8.一种数据分类方法，其特征在于，包括以下步骤：
通过bsmote算法将正类样本集p分成噪声样本集、边界样本集和安全样本集；
在给定过采样率ratio的情况下，训练数据集需合成新样本的数量g得以确定，为每个正类边界样本赋予采样权值ωj，由ωj与g得到每一个正类边界样本应合成新样本的数目gj；
将所得的gj个新样本与噪声样本集、安全样本集和负类样本集共同组成平衡的训练数据集；
分别对负类样本集和正类样本集进行重新采样，得到若干个平衡数据子集；
以adaboost算法为基分类器gt(x)，对若干个平衡数据子集进行处理，并为基分类器引入关于f1值的分类误差率εt'，并以分类误差率εt'计算基分类器gt(x)的权值αt；
将若干个平衡数据子集的处理结果汇总与原始训练数据集合并后输出；
设置好参数，对所得数据进行预处理；
将所得的数据利用iforest算法进行处理，滤除其中平均分割路径长度小于设定阈值的数据，保留平均分割路径长度不小于设定阈值的数据作为正常数据子集；
利用lof算法对滤除的、平均分割路径长度小于设定阈值的数据进行处理，剔除其中不符合要求的数据作为异常数据子集，其余数据作为正常数据子集。
技术总结