基于商空间理论的非平衡数据集分类算法文档格式.docx

1、过采样；qmsvm算法 中图分类号: tp311.13 文献标志码:aabstract: the application of data classification is usually confronted with a problem named imbalanced dataset in the machine learning. to improve the performance of imbalanced dataset classification, the over-sampling classification algorithm based on quotient spa

2、ce theory （qmsvm） was proposed. the algorithm partitioned majority data on clustering structure, and combined the results and minority data for linear support vector machine （svm） learning. support vectors and sample of fault of majority data were obtained from those granules. on the other hand, sup

3、port vectors and sample of fault of minority data were obtained and the synthetic minority over-sampling technique （smote） was adopted. thus, two new kinds of samples were merged for svm learning, so as to rebalance the training set and get a more reasonable classification of hyperplanes. the experi

4、mental results show that, in comparison with several other algorithms, the accuracy of the proposed algorithm decreases, but it significantly improves the g_means value and classification accuracy of positives and the effect is better on the imbalance rate of larger datasets.key words: imbalanced da

5、taset; quotient space theory; support vector machine （svm）; over-sampling; qmsvm algorithm0 引言 非平衡数据集的分类问题是机器学习和模式识别领域中新的研究热点，是对传统算法的极大考验，解决它对于完善机器学习体系、提出新的机器学习思想具有很高的理论和应用价值。非平衡数据集是指数据集中某些类的样本比其他类多很多，样本多的类为多数类（即负类），样本少的类为少数类（即正类）1。然而，现实世界中非平衡数据集分类问题随处可见，如疾病诊断、医疗图像中肿瘤识别、信用卡欺诈检测等。这些问题中的少数类样本信息比多数类样本信

6、息还要重要得多，但传统分类器往往把少数样本忽略导致重要信息丢失。 目前国内外学者对非平衡数据集问题的研究已取得大量成果，提出了不同的处理方法，其主要成果表现在两大方面，那就是算法层面和数据处理层面。算法层面上主要是改进算法提高性能，如文献2在支持向量机（support vector machine, svm）基础上，通过优化参数改进svm在非平衡数据集上的性能；wu等也对支持向量机方法进行了改进3；文献4在mpm（minimax probability machine）模型基础上，提出了bmpm（biased minimax probability machine）模型来处理非平衡数据的问题。

7、数据处理层面上主要是过采样和欠采样，如文献5中,采用smote（synthetic minority over-sampling technique）算法人工构造少数类样本来增加正类样本的数量；文献6中，通过粒度对多数类样本压缩减少负类样本的数量，从而减少数据失衡程度，这样压缩很容易使富含重要信息数据丢失。本文在基于商空间理论的支撑背景下，对非平衡学习数据集进行再平衡过程，提出一个新的过采样分类算法。 商空间理论是张铃教授和张钹院士7提出的。商空间理论模型用三元组（x, f,t）描述一个问题,其中：x表示问题的论域； f（）表示论域的属性,可用函数f:xy表示；t为论域结构，指论域x中各元素的

8、相互关系。分析或求解问题（x, f,t）即对论域x及其有关的结构、属性进行分析和研究。对论域x，在其上给定一个等价关系r即一个划分，对应于r的商集为x，得到一个较粗粒度的世界x,然后将x当作新的论域进行分析、研究，也必有一个对应的三元组（x,f,t）称为原问题空间的商空间。由拓扑学的原理知,从商空间的结构可以了解原拓扑空间的某些性质,并有如下的命题。 命题 p：（x,t）（x,t）是自然投影，所以p是连续的。若a x且a是x中的连通集，则p（a）是x中的连通集。 命题表明，若一个问题在原论域x中有解（是连通的），在适当的粗粒度论域x上也有解；反之，若粗粒度论域上无解，则原问题必无解（不连通）。

9、 定义 设（x,t）为原拓扑空间，（x,t）是其相应划分的商空间。在（x,t）中 x,yx，且x和y相容度为1，如果x,yx，则称此划分是相容性划分；在（x,t）中 x， y x，且x和y相容度近似为1，如果x,yx，则称此划分是近似相容性划分。 相容性划分能保持不同粒度之间信息完全传递，但这种划分很难得到，于是提出近似相容性划分，尽量保持不同粒度之间信息的传递。 1 算法设计 传统支持向量机处理非平衡数据集问题时，往往由于数据不平衡，把很多少数类样本归于多数类，甚至使所有样本被分到多数类，忽略了数据集本该存在的重要信息。为了避免此种情况出现，本文对多数类样本进行相容或近似相容划分，通过自然映

10、射构造新的数据空间即商空间。具体做法如下。 对多数类样本即负类x -进行k-均值聚类，聚类后把每个类中所有样本自然投影到它相应的聚类中心上，即是商空间x -中的一个元素，这样便得到商空间x -。图1是某地区50位男性和50位女性身高体重数据分布图，星号代表男性，点代表女性。图2是图1数据通过聚类划分与原来数据比较，“ o ”代表聚类中心，聚成两类后每个类中所有样本自然投影到它相应的聚类中心。 这样便得到商空间x -，接着把商空间x -和少数类x +样本进行线性 svm 训练， 删去那些远离超平面且分类正确的多数类样本，认为它们是安全的信息，把支持向量中多数类样本和错分的多数类样本留下来，认为它

11、们是活跃的信息，把留下的多数类样本释放，而对留下的少数类样本进行smote过采样以期达到两类数据平衡，smote采样技术是chawla等5提出的一种采样方法，主要思想是在相距较近的少数类之间线性插入人为样本。具体算法如下。 对留下少数类每个样本x，在少数样本x +中找出与样本x距离最近x，再在x和x之间进行随机线性插值，人造出一个新的少数类样本x_xin，即： x_xin=x+ rand （0,1）x1+ rand （0,1）（1） 其中 rand （0,1）是0至1之间的一个随机实数。如 rand （0, 1）= 12，则x_xin=x+12x1+12，如果对每个样本x插入两个数据时，就在少

12、数样本x +中找出与样本x距离最近x1和第二近的x2，再在x和x1、x2之间进行随机线性插值，人造出一个新的少数类样本x_xin1、x_xin2，以此类推得到更多的少数类人造样本。最后对所得新的样本进行 svm 训练，这样可使分类结果精度不会太低而且更好地将少数类正确分类。 qmsvm算法主要步骤如下： 步骤1 输入非平衡数据集x； 步骤2 对训练集中的多数类样本x -进行相容或近似相容划分得到商集x -，商集的势为少数类样本个数； 步骤3 把商集x -和训练集中的少数类样本x +合并,进行线性 svm 训练； 步骤4 找出支持向量中多数类样本和错分的多数类样本，并释放记为x1 -； 步骤5

13、找出步骤3中支持向量中少数类样本和错分的少数类样本x1 +，利用 smote 采样技术对每个x1 +及它x +中的样本进行采样，得到新的少数类样本x1 +（采样使x1 +和x1 -达到平衡）； 步骤6 把x1 +和x1 -合并再进行 svm 训练，得到合理的超平面； 步骤7 算法结束，输出结果。 2 非平衡数据分类评价指标 2.1 正确分类率 正确分类率（accuracy）能准确反映学习器的泛化性能，其定义为： accuracy=tp+tntp+fp+tn+fn（2） 其中：tp（true positives）代表正确分类的正类的个数，tn（true negatives）代表正确分类的负类的个

14、数，fp（false positives）代表负类错误分成正类的个数，fn（false negatives）代表正类错误分成负类的个数。而对于非平衡数据，这一指标实际意义并不大，因为它反映的是多数类样本的分类测试结果，所以本文还采用以下两类指标。 2.2 g_means 文献8中提出的g_means值是非平衡数据集常采用的衡量指标，它可以有效地衡量非平衡数据的分类精度，一般g_means值越大分类效果越好。g_means的定义为： g_means=tptp+fntntn+fp（3） 2.3 正类分类的准确率（ acc +） 为了更进一步考虑非平衡数据中的少数类样本， 除g_means值外，还有

15、一个重要指标：正类分类的准确率acc +，一般acc +越大说明正类样本分类准确率越大。acc +定义为： acc +=tptp+fn（4） 3 实验验证及分析 3.1 数据集说明 为了验证qmsvm算法的性能，采用人造数据集和典型uci数据库集（如表1），人造数据集是随机产生了两组正态分布均值为0 0和1.2 1.2，协方差矩阵均为0.20 00.2的二维数据点，样本大小为1 000和20,平衡率为501。 3.2 实验验证及分析 采用10-折交叉的方法，把所有样本随机分成10份，并且保持每份样本和原来样本平衡率大致一样。每次取其中9份作为训练集，剩下的1份作为测试集，计算测试集的各项评价指

16、标值，然后把10次值的平均值作为本算法的评价指标值。 在人造数据集中（如表2）,使用本文的qmsvm算法比单纯的svm算法、支持聚类机（clustering based support vector machine, csvm）算法和文献6中的gsvm（granular support vector machine）算法除 accuracy 值外结果都要好些。在uci数据集中（如表35），qmsvm算法在 g_means 值除数据blood-transfusion外都优越其他3种算法， acc +值比svm算法和csvm算法也要好得多。 实验结果表明，非平衡率越大，数据集的属性越少，本文qms

17、vm算法性能较其他3种算法就越好，表34充分说明了这一点。 4 结语 本文针对当前机器学习和模式识别中研究比较热的非平衡数据集分类问题，在商空间理论基础上提出了qmsvm算法。实验表明该算法对非平衡率较大的数据集分类问题有较好的结果，对少数类样本的分辨率较高。在未来工作中，可以考虑如何选取更科学的商集，使非平衡数据集分类效率进一步提高。 参考文献: 1weiss g m. mining with rarity: a unifying framework j. acm sigkdd explorations newsletter-special issue on learning from im

18、balanced datasets, 2004, 6（1）: 7-19. 2蒋莎,张晓龙.一种用于非平衡数据的svm学习算法j.计算机工程,2008,34（20）:198-199. 3wu g, chang e. class-boundary alignment for imbalanced dataset learning c/ the twentieth international conference on machine learning workshop on learning from imbalanced datasets. washington, dc: aaai press,

19、 2003: 786-795. 4huang kaizhu, yang haiqin, king i, et al. imbalanced learning with a biased minimax probability machine j. ieee transactions on systems， man， and cybernetics, 2006, 36（4）: 913-923. 5chawla n v, bowyer k w, hall l o, et al. smote: synthetic minority over-sampling technique j. journal

20、 of artificial intelligence research, 2002, 16（1）: 321 -357. 6郭虎,升亓慧,王文剑.处理非平衡数据的粒度svm学习算法j.计算机工程,2010,36（2）:181-183. 7张钹,张铃.问题求解理论及应用m.北京:清华大学出版社,1990. 8kubat m, matwin s. addressing the curse of imbalanced training sets: one-sided selection c/ proceedings of the 14th international conference on ma

21、chine learning. san francisco: morgan kaufmann, 1997: 179-186. 9边肇祺,张学工.模式识别m.2版.北京:清华大学出版社,2000. 10blake c,merz c. uci repository of machine learning data bases eb/ol. 2011-03-25. http:/www.ics.uci.edu/mlearn/mlrepository.html.收稿日期:2011-07-18;修回日期:2011-09-21。基金项目:国家自然科学基金资助项目（71071002）；安徽省教育厅自然科学基金资助项目（05010428）；安徽大学人才队伍建设项目；安徽大学学术创新团队项目（kjtd001b）。 作者简介:张健（1981-），男，安徽安庆人，硕士研究生，主要研究方向：机器学习、模式识别； 方宏彬（1972-），男，安徽池州人，副教授，博士，主要研究方向：智能计算、信息融合； 孙启林（1982-），男，安徽合肥人，硕士研究生，主要研究方向：金融数据挖掘。