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

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

《基于商空间理论的非平衡数据集分类算法文档格式.docx》由会员分享，可在线阅读，更多相关《基于商空间理论的非平衡数据集分类算法文档格式.docx（5页珍藏版）》请在冰点文库上搜索。

过采样；

qmsvm算法中图分类号:

tp311.13文献标志码:

aabstract:

theapplicationofdataclassificationisusuallyconfrontedwithaproblemnamedimbalanceddatasetinthemachinelearning.toimprovetheperformanceofimbalanceddatasetclassification,theover-samplingclassificationalgorithmbasedonquotientspacetheory（qmsvm）wasproposed.thealgorithmpartitionedmajoritydataonclusteringstructure,andcombinedtheresultsandminoritydataforlinearsupportvectormachine（svm）learning.supportvectorsandsampleoffaultofmajoritydatawereobtainedfromthosegranules.ontheotherhand,supportvectorsandsampleoffaultofminoritydatawereobtainedandthesyntheticminorityover-samplingtechnique（smote）wasadopted.thus,twonewkindsofsamplesweremergedforsvmlearning,soastorebalancethetrainingsetandgetamorereasonableclassificationofhyperplanes.theexperimentalresultsshowthat,incomparisonwithseveralotheralgorithms,theaccuracyoftheproposedalgorithmdecreases,butitsignificantlyimprovestheg_meansvalueandclassificationaccuracyofpositivesandtheeffectisbetterontheimbalancerateoflargerdatasets.keywords:

imbalanceddataset;

quotientspacetheory;

supportvectormachine（svm）;

over-sampling;

qmsvmalgorithm0引言非平衡数据集的分类问题是机器学习和模式识别领域中新的研究热点，是对传统算法的极大考验，解决它对于完善机器学习体系、提出新的机器学习思想具有很高的理论和应用价值。

非平衡数据集是指数据集中某些类的样本比其他类多很多，样本多的类为多数类（即负类），样本少的类为少数类（即正类）［1］。

然而，现实世界中非平衡数据集分类问题随处可见，如疾病诊断、医疗图像中肿瘤识别、信用卡欺诈检测等。

这些问题中的少数类样本信息比多数类样本信息还要重要得多，但传统分类器往往把少数样本忽略导致重要信息丢失。

目前国内外学者对非平衡数据集问题的研究已取得大量成果，提出了不同的处理方法，其主要成果表现在两大方面，那就是算法层面和数据处理层面。

算法层面上主要是改进算法提高性能，如文献［2］在支持向量机（supportvectormachine,svm）基础上，通过优化参数改进svm在非平衡数据集上的性能；

wu等也对支持向量机方法进行了改进［3］；

文献［4］在mpm（minimaxprobabilitymachine）模型基础上，提出了bmpm（biasedminimaxprobabilitymachine）模型来处理非平衡数据的问题。

数据处理层面上主要是过采样和欠采样，如文献［5］中,采用smote（syntheticminorityover-samplingtechnique）算法人工构造少数类样本来增加正类样本的数量；

文献［6］中，通过粒度对多数类样本压缩减少负类样本的数量，从而减少数据失衡程度，这样压缩很容易使富含重要信息数据丢失。

本文在基于商空间理论的支撑背景下，对非平衡学习数据集进行再平衡过程，提出一个新的过采样分类算法。

商空间理论是张铃教授和张钹院士［7］提出的。

商空间理论模型用三元组（x,f,t）描述一个问题,其中：

x表示问题的论域；

f（）表示论域的属性,可用函数f:

x→y表示；

t为论域结构，指论域x中各元素的相互关系。

分析或求解问题（x,f,t）即对论域x及其有关的结构、属性进行分析和研究。

对论域x，在其上给定一个等价关系r即一个划分，对应于r的商集为［x］，得到一个较粗粒度的世界［x］,然后将［x］当作新的论域进行分析、研究，也必有一个对应的三元组（［x］,［f］,［t］）称为原问题空间的商空间。

由拓扑学的原理知,从商空间的结构可以了解原拓扑空间的某些性质,并有如下的命题。

命题p：

（x,t）→（［x］,［t］）是自然投影，所以p是连续的。

若ax且a是x中的连通集，则p（a）是［x］中的连通集。

命题表明，若一个问题在原论域x中有解（是连通的），在适当的粗粒度论域［x］上也有解；

反之，若粗粒度论域上无解，则原问题必无解（不连通）。

定义设（x,t）为原拓扑空间，（［x］,［t］）是其相应划分的商空间。

在（x,t）中x,y∈x，且x和y相容度为1，如果x,y∈［x］，则称此划分是相容性划分；

在（x,t）中x，y∈x，且x和y相容度近似为1，如果x,y∈［x］，则称此划分是近似相容性划分。

相容性划分能保持不同粒度之间信息完全传递，但这种划分很难得到，于是提出近似相容性划分，尽量保持不同粒度之间信息的传递。

1算法设计传统支持向量机处理非平衡数据集问题时，往往由于数据不平衡，把很多少数类样本归于多数类，甚至使所有样本被分到多数类，忽略了数据集本该存在的重要信息。

为了避免此种情况出现，本文对多数类样本进行相容或近似相容划分，通过自然映射构造新的数据空间即商空间。

具体做法如下。

对多数类样本即负类x-进行k-均值聚类，聚类后把每个类中所有样本自然投影到它相应的聚类中心上，即是商空间［x-］中的一个元素，这样便得到商空间［x-］。

图1是某地区50位男性和50位女性身高体重数据分布图，星号代表男性，点代表女性。

图2是图1数据通过聚类划分与原来数据比较，“o”代表聚类中心，聚成两类后每个类中所有样本自然投影到它相应的聚类中心。

这样便得到商空间［x-］，接着把商空间［x-］和少数类x+样本进行线性svm训练，删去那些远离超平面且分类正确的多数类样本，认为它们是安全的信息，把支持向量中多数类样本和错分的多数类样本留下来，认为它们是活跃的信息，把留下的多数类样本释放，而对留下的少数类样本进行smote过采样以期达到两类数据平衡，smote采样技术是chawla等［5］提出的一种采样方法，主要思想是在相距较近的少数类之间线性插入人为样本。

具体算法如下。

对留下少数类每个样本x，在少数样本x+中找出与样本x距离最近x′，再在x和x′之间进行随机线性插值，人造出一个新的少数类样本x_xin，即：

x_xin=x+rand（0,1）×

x′1+rand（0,1）

（1）其中rand（0,1）是0至1之间的一个随机实数。

如rand（0,1）=12，则x_xin=x+12×

x′1+12，如果对每个样本x插入两个数据时，就在少数样本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找出步骤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（truepositives）代表正确分类的正类的个数，tn（truenegatives）代表正确分类的负类的个数，fp（falsepositives）代表负类错误分成正类的个数，fn（falsenegatives）代表正类错误分成负类的个数。

而对于非平衡数据，这一指标实际意义并不大，因为它反映的是多数类样本的分类测试结果，所以本文还采用以下两类指标。

2.2g_means文献［8］中提出的g_means值是非平衡数据集常采用的衡量指标，它可以有效地衡量非平衡数据的分类精度，一般g_means值越大分类效果越好。

g_means的定义为：

g_means=tptp+fn×

tntn+fp（3）2.3正类分类的准确率（acc+）为了更进一步考虑非平衡数据中的少数类样本，除g_means值外，还有一个重要指标：

正类分类的准确率acc+，一般acc+越大说明正类样本分类准确率越大。

acc+定义为：

acc+=tptp+fn（4）3实验验证及分析3.1数据集说明为了验证qmsvm算法的性能，采用人造数据集和典型uci数据库集（如表1），人造数据集是随机产生了两组正态分布均值为00和1.21.2，协方差矩阵均为0.2000.2的二维数据点，样本大小为1000和20,平衡率为50∶1。

3.2实验验证及分析采用10-折交叉的方法，把所有样本随机分成10份，并且保持每份样本和原来样本平衡率大致一样。

每次取其中9份作为训练集，剩下的1份作为测试集，计算测试集的各项评价指标值，然后把10次值的平均值作为本算法的评价指标值。

在人造数据集中（如表2）,使用本文的qmsvm算法比单纯的svm算法、支持聚类机（clusteringbasedsupportvectormachine,csvm）算法和文献［6］中的gsvm（granularsupportvectormachine）算法除accuracy值外结果都要好些。

在uci数据集中（如表3~5），qmsvm算法在g_means值除数据blood-transfusion外都优越其他3种算法，acc+值比svm算法和csvm算法也要好得多。

实验结果表明，非平衡率越大，数据集的属性越少，本文qmsvm算法性能较其他3种算法就越好，表3~4充分说明了这一点。

4结语本文针对当前机器学习和模式识别中研究比较热的非平衡数据集分类问题，在商空间理论基础上提出了qmsvm算法。

实验表明该算法对非平衡率较大的数据集分类问题有较好的结果，对少数类样本的分辨率较高。

在未来工作中，可以考虑如何选取更科学的商集，使非平衡数据集分类效率进一步提高。

参考文献:

[1]weissgm.miningwithrarity:

aunifyingframework［j］.acmsigkddexplorationsnewsletter-specialissueonlearningfromimbalanceddatasets,2004,6

（1）:

7-19.[2]蒋莎,张晓龙.一种用于非平衡数据的svm学习算法［j］.计算机工程,2008,34（20）:

198-199.[3]wug,change.class-boundaryalignmentforimbalanceddatasetlearning［c］//thetwentiethinternationalconferenceonmachinelearningworkshoponlearningfromimbalanceddatasets.washington,dc:

aaaipress,2003:

786-795.[4]huangkaizhu,yanghaiqin,kingi,etal.imbalancedlearningwithabiasedminimaxprobabilitymachine［j］.ieeetransactionsonsystems，man，andcybernetics,2006,36（4）:

913-923.[5]chawlanv,bowyerkw,halllo,etal.smote:

syntheticminorityover-samplingtechnique［j］.journalofartificialintelligenceresearch,2002,16

（1）:

321-357.[6]郭虎,升亓慧,王文剑.处理非平衡数据的粒度svm学习算法［j］.计算机工程,2010,36

（2）:

181-183.[7]张钹,张铃.问题求解理论及应用［m］.北京:

清华大学出版社,1990.[8]kubatm,matwins.addressingthecurseofimbalancedtrainingsets:

one-sidedselection［c］//proceedingsofthe14thinternationalconferenceonmachinelearning.sanfrancisco:

morgankaufmann,1997:

179-186.[9]边肇祺,张学工.模式识别［m］.2版.北京:

清华大学出版社,2000.[10]blakec,merzc.ucirepositoryofmachinelearningdatabases［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-），男，安徽合肥人，硕士研究生，主要研究方向：

金融数据挖掘。