一种基于聚类提升的不平衡数据分类算法

不平衡数据分类是机器学习研究领域中的一个热点问题。针对传统分类算法处理不平衡数据的少数类识别率过低问题,文章提出了一种基于聚类的改进AdaBoost分类算法。算法首先进行基于聚类的欠采样,在多数类样本上进行K均值聚类,之后提取聚类质心,与少数类样本数目一致的聚类质心和所有少数类样本组成新的平衡训练集。为了避免少数类样本数量过少而使训练集过小导致分类精度下降,采用少数过采样技术过采样结合聚类欠采样。然后,借鉴代价敏感学习思想,对AdaBoost算法的基分类器分类误差函数进行改进,赋予不同类别样本非对称错分损失。实验结果表明,算法使模型训练样本具有较高的代表性,在保证总体分类性能的同时提高了少数类的分类精度。     

基于层次K-均值聚类的支持向量机模型

针对支持向量机SVM分类效率低下的问题,提出一种基于层次K-均值聚类的支持向量机HKSVM(Hierarchical K-means SVM)学习模型。该方法首先对每类样本分别进行K-均值聚类,计算每类中心并训练SVM,得到初始分类器;然后根据超平面与聚类结果的关系,将聚类所得结果划分为活动类集和静止类集,并对超平面附近的活动类集进行深层聚类,以得到更小的类别同时计算类中心来训练新的SVM模型,并校正分类超平面,如此循环往复,直到得到较为精确的分类器为止。采用基于层次K-均值聚类的SVM模型,通过对活动类集进行不断地深层次聚类,从而在分类超平面附近得到较多样本点,而在距离超平面较远处则取少量训练样本,以有效压缩训练集规模,在保持SVM训练精度的同时大幅度提高其学习效率。标准数据集上的实验结果表明,HKSVM方法在大规模数据集上同时得到了较高的分类效率和测试精度。     

提高支持向量机训练速度的CM-SVM方法

针对支持向量机在大规模样本学习时，学习速度慢，需要存储空间大等问题，提出了一种将支持向量机方法与C均值方法结合的CM-SVM方法。在该方法中，先采用C均值方法对训练样本集进行聚类，然后依据聚类域中样本的类型特点确定样本的约简方式。仿真图像实验结果表明，CM—SVM方法提高了支持向量机的学习速度，同时支持向量机的分类精度几乎没有降低，表现出较好的样本约简性能。     

基于商空间理论的非平衡数据集分类算法

在机器学习及其分类问题时经常会遇到非平衡数据集,为了提高非平衡数据集分类的有效性,提出了基于商空间理论的过采样分类算法,即QMSVM算法。对训练集中多数类样本进行聚类结构划分,所得划分结果和少数类样本合并进行线性支持向量机(SVM)学习,从而获取多数类样本的支持向量和错分的样本粒;另一方面,获取少数类样本的支持向量和错分的样本,进行SMOTE采样,最后把上述得到的两类样本合并进行SVM学习,这样来实现学习数据集的再平衡处理,从而得到更加合理的分类超平面。实验结果表明,和其他几种算法相比,所提算法虽在正确分类率上有所降低,但较大改善了g_means值和acc+值,且对非平衡率较大的数据集效果会更好。     

改进的K均值聚类算法在支持矢量机中的应用

将一种改进的K均值聚类算法应用于支持矢量机（SVM）的训练。基于这一改进的聚类算法,设计了SVM的增量式训练步骤,并给出了在训练过程中删除无用样本的的方法。模式分类的实验结果表明,这种改进的K均值聚类算法在SVM中的应用不仅大幅度地缩短了SVM的训练时间,而且进一步提高了它的分类能力。     

基于Kmeans与SVM结合的遥感图像全自动分类方法*

遥感图像分类方法通常采用监督的学习算法,它需要人工选取训练样本,比较繁琐,而且有时很难得到;而非监督学习算法的分类精度通常很难令人满意.针对这些缺陷,提出一种基于K-means与支持向量机(SVM)结合的遥感图像全自动分类方法.首先使用K-means聚类算法对样本进行初始聚类,根据每类中样本数及其稀疏程度选取一些点作为标记的学习样本训练SVM分类器,然后用SVM对原始数据重新分类.Iris数据和遥感数据的实验结果均验证了新方法的有效性.     

利用KKT条件与类边界包向量的SVM增量学习算法

为实现对历史训练数据有选择地遗忘,并尽可能少地丢失训练样本集中的有用信息,分析了KKT条件与样本分布间的关系并得出了结论,给出了增量训练中当前训练样本集的构成.为了提高SVM增量训练速度,进一步利用训练样本集的几何结构信息对当前训练样本集进行约减,用约减后的当前训练样本集进行SVM增量训练,从而提出一种利用KKT务件与类边界包向量的快速SVM增量学习算法.实验结果表明,该算法在保持较高分类精度的同时提高了SVM增量学习速度.     

基于代价敏感思想和自适应增强集成的SVM多分类算法

针对数据识别分类在传统的支持向量机(SVM)个体分类器上正确识别率不理想的问题，提出一种基于代价敏感思想(cost-sensitive)和自适应增强(AdaBoost)的SVM集成数据分类算法(CAB-SVM)。在自适应增强算法每次迭代训练SVM弱分类器之前，根据样本总数设置初始样本权值，并抽取样本组成临时训练集训练SVM弱分类器。其中在权重迭代更新阶段，赋予被分错样本更高的误分代价，使得被分错样本权重增加更快，有效地减少了算法迭代次数。同时，算法迭代过程极大地优化了个体分类器的识别鲁棒性能，使得提出的CAB-SVM算法获得了更优越的数据分类性能。利用UCI数据样本集的实验结果表明CAB-SVM分类算法的正确识别率高于SVM和SVME算法。     

基于混合采样的非平衡数据集分类研究

针对传统的过采样算法在增加样本的同时可能使决策域变小和噪声点增加的问题进行了研究,提出了一种基于错分的混合采样算法。该算法是以SVM为元分类器,Ada Boost算法进行迭代,对每次错分的样本点根据其空间近邻关系,采取一种改进的混合采样策略:对噪声样本直接删除;对危险样本约除其近邻中的正类样本;对安全样本则采用SMOTE算法合成新样本并加入到新的训练集中重新训练学习。在实际数据集上进行实验,并与SMOTE-SVM和Ada Boost-SVM-OBMS算法进行比较,实验结果表明该算法能够有效地提高负类的分类准确率。     

基于支持向量机与极端保守在线算法相结合的多类分类器

本文给出了一种将SVM和极端保守在线算法相结合的通用多类分类算法,算法利用最大置信度原则将离线训练的多个SVM组合成一个多类分类器.为了提高在线学习过程的实时性,同时保证分类器的推广能力,我们将K.Cramer等人提出的极端保守在线算法思想引入到分类器修正过程当中,修正过程中采用对应SVM的支持向量和错分样本作为训练集.实验表明,算法具有良好的实时性能,且具有良好的推广能力.     

一种SOM和GRNN结合的模式全自动分类新方法

非监督学习算法的分类精度通常很难令人满意,而监督的学习算法需要人工选取训练样本,这有时很难得到,并且其分类精度直接依赖于所选取的学习样本。针对这些缺陷,提出一种非监督自组织神经网络(SOMNN)和监督的广义回归网络(GRNN)结合的全自动模式分类新方法。新方法首先通过SOMNN将原始数据进行自动聚类,再用所得的聚类中心以及中心邻近数据点训练GRNN,然后根据GRNN的分类结果重新计算聚类中心,再根据新的聚类中心和中心邻近点训练GRNN,如此反复,直至得到稳定的中心为止。Iris数据,Wine数据的实验结果都验证了新方法的可行性。     

基于分类的半监督聚类方法

提出一种基于分类的半监督聚类算法。充分利用了数据集中的少量标记对象对原始数据集进行粗分类,在传统k均值算法的基础上扩展了聚类中心点的选择方法;用k-meansGuider方法对数据集进行粗聚类,在此基础上对粗聚类结果进行集成。在多个UCI标准数据集上进行实验,结果表明提出的算法能有效改善聚类质量。     

基于多维网格空间的改进K-means聚类算法

K-means算法是被广泛使用的一种聚类算法,传统的K-means算法中初始聚类中心的选择具有随机性,易使算法陷入局部最优,聚类结果不稳定。针对此问题,引入多维网格空间的思想,首先将样本集映射到一个虚拟的多维网格空间结构中,然后从中搜索出包含样本数最多且距离较远的子网格作为初始聚类中心网格,最后计算出各初始聚类中心网格中所包含样本的均值点来作为初始聚类中心。此法选择出来的初始聚类中心与实际聚类中心拟合度高,进而可据此初始聚类中心稳定高效地得到最终的聚类结果。通过使用计算机模拟数据集和UCI机器学习数据集进行测试,结果表明改进算法的迭代次数和错误率比较稳定,且均小于传统K-means算法测试结果的平均值,能有效避免陷入局部最优,并且聚类结果稳定。     

一种用于文本分类的语义SVM及其在线学习算法

该文利用SVM在小训练样本集条件下仍有高泛化能力的特性,结合文本分类问题中同类别文本的特征在特征空间中具有聚类性分布的特点,提出一种使用语义中心集代替原训练样本集作为训练样本和支持向量的SVM:语义SVM。文中给出语义中心集的生成步骤,进而给出语义SVM的在线学习(在线分类知识积累)算法框架,以及基于SMO算法的在线学习算法的实现。实验结果说明语义SVM及其在线学习算法具有巨大的应用潜力:不仅在线学习速度和分类速度相对于标准SVM及其简单增量算法有数量级提高,而且分类准确率方面具有一定优势。     

Optimality and stability of the K-hyperline clustering algorithm

K-hyperline clustering is an iterative algorithm based on singular value decomposition and it has been successfully used in sparse component analysis. In this paper, we prove that the algorithm converges to a locally optimal solution for a given set of training data, based on Lloyd’s optimality conditions. Furthermore, the local optimality is shown by developing an Expectation-Maximization procedure for learning dictionaries to be used in sparse representations and by deriving the clustering algorithm as its special case. The cluster centroids obtained from the algorithm are proved to tessellate the space into convex Voronoi regions. The stability of clustering is shown by posing the problem as an empirical risk minimization procedure over a function class. It is proved that, under certain conditions, the cluster centroids learned from two sets of i.i.d. training samples drawn from the same probability space become arbitrarily close to each other, as the number of training samples increase asymptotically.     

高度不平衡数据的代价敏感随机森林分类算法

在处理高度不平衡数据时,代价敏感随机森林算法存在自助法采样导致小类样本学习不充分、大类样本占比较大、容易削弱代价敏感机制等问题.文中通过对大类样本聚类后,多次采用弱平衡准则对每个集群进行降采样,使选择的大类样本与原训练集的小类样本融合生成多个新的不平衡数据集,用于代价敏感决策树的训练.由此提出基于聚类的弱平衡代价敏感随机森林算法,不仅使小类样本得到充分学习,同时通过降低大类样本数量,保证代价敏感机制受其影响较小.实验表明,文中算法在处理高度不平衡数据集时性能较优.     

用于文本分类的改进KNN算法

采用灵敏度方法对距离公式中文本特征的权重进行修正;提出一种基于CURE算法和Tabu算法的训练样本库的裁减方法,采用CURE聚类算法获得每个聚类的代表样本组成新的训练样本集合,然后用Tabu算法对此样本集合进行进一步维护(添加或删除样本),添加样本时只考虑增加不同类交界处的样本,添加或删除样本以分类精度最高、与原始训练样本库距离最近为原则。     

PAKDD’12 best paper: generating balanced classifier-independent training samples from unlabeled data

We consider the problem of generating balanced training samples from an unlabeled data set with an unknown class distribution. While random sampling works well when the data are balanced, it is very ineffective for unbalanced data. Other approaches, such as active learning and cost-sensitive learning, are also suboptimal as they are classifier-dependent and require misclassification costs and labeled samples, respectively. We propose a new strategy for generating training samples, which is independent of the underlying class distribution of the data and the classifier that will be trained using the labeled data. Our methods are iterative and can be seen as variants of active learning, where we use semi-supervised clustering at each iteration to perform biased sampling from the clusters. We provide several strategies to estimate the underlying class distributions in the clusters and to increase the balancedness in the training samples. Experiments with both highly skewed and balanced data from the UCI repository and a private data set show that our algorithm produces much more balanced samples than random sampling or uncertainty sampling. Further, our sampling strategy is substantially more efficient than active learning methods. The experiments also validate that, with more balanced training data, classifiers trained with our samples outperform classifiers trained with random sampling or active learning.     

一种基于morlet小波核的约简支持向量机

针对支持向量机（SVM）的训练数据量仅局限于较小样本集的问题，结合Morlet小波核函数，提出了一种基于Morlet小波核的约倚支持向量机（MWRSVM—DC）．算法的核心是通过密度聚类寻找聚类中每个簇的边缘点作为约倚集合，并利用该约倚集合寻找支持向量．实验表明，利用小波核，该算法不仅提高了分类的准确率，而且提高了整体分类效率．