基于最小距离的多中心向量的增量分类算法

摘要：分类是数据挖掘的一项重要研究内容。在分析了现有分类方法后，提出了基于最小距离的多中心向量的增量分类算法。该方法首先按照属性类聚类训练样本，通过类间调整，消除类域空间重叠。针对增量分类，提出了多中心向量的分类算法，通过空间区域划分的方法，减少增量分类选取的代表样本数量。实验结果表明，与文献[14]提出的增量分类算法相比，分类精度近似相同，但所需时间复杂度和存储空间则有不同程度的下降，这对大数据的处理是具有重要意义的。

关键词：增量分类；最小距离；多中心向量

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）04-0070-04

Abstract： Classification is an important research content of data mining. In this paper， a new incremental classification algorithm of multiple center vector base on minimun-distance is presented after analysising the existing methods on incremental classification algorithm of minimun-distance. In the method， first， cluster the training data according to class attribute ，then eliminate the overlap of class space by adjusting the space between classes， finally， incremental classification algorithm of multiple center vector base on minimun-distance is presented to classify incremental training data， reduce the selected number of representative sample. The experiments indicate that compare with the Algorithm from literature[14]，the classification accuracy is basically the same， but the demand of storage space and the time complex decreased in different degree， it is significant for big data classification.

Key words： incremental classification； minimun-distance； multiple center vector

1 概述

随着大数据时代的到来，已有的数据挖掘技术面临一系列新的挑战。大数据具有数据体量巨大，数据增量快，数据结构复杂等特点[1]，使得对大数据的挖掘存在许多困难。

分类是数据挖掘的重要内容之一。目前已有许多分类算法，最小距离分类算法就是其中的一种。该算法拥有计算简单，概念明晰，易于理解，速度较快等优点。该文提出了一种基于最小距离增量分类算法，与文献[14]提出的算法相比，在分类精度大致相同的情况下，算法的复杂度和存储开销均有不同程度的下降，适合于对大数据进行分类。

2 相关研究的工作

目前，增量分类算法有很多。如基于RBF网络的增量分类算法[4]，基于支持向量机的增量分类算法[5]，基于最近邻方法的增量分类算法，基于决策树的增量分类算法[6-9]以及基于贝叶斯网络的增量分类算法[10]。这些算法主要问题是复杂度高，要求的存储空间大。而基于距离的增量分类算法则具有设计相对简单，复杂度低，存储开销小等特点，所以有很多基于距离的增量分类算法被提出。例如R.Marin等人提出的距离增量分类算法[11]，该算法首次实现了基于距离的增量分类；K，yamauchi提出了一种消除训练样本间相互干扰的方法[12]，它利用已训练样本进行分类训练来消除样本之间的干扰；Zhao等人提出了增量等距算法[13] ，通过映射新的数据点调整训练结果，用增量的方法强化分类结果，最后采用类似滑动窗口的方式约束数据的增加；桑农等提出了一种保留样本的增量分类方法（ILAMM）[14] ，使用马氏距离，解决了类域大小不一致影响分类正确率的问题。

基于距离的增量分类算法，不仅要能准确分类增量样本，而且要保持对已训练样本的分类性能[15-16]。ILAMM算法更加适合于训练样本和增量样本数量级接近的增量分类情况，在训练样本远大于增量样本的情况下，分类效率比较低。该文在ILAMM算法的基础上，提出了基于最小距离的多中心向量的增量分类算法（ICMCVM）。该算法通过将空间区域划分为若干区域，提高了训练样本比增量样本大很多的情况下的增量分类效率，因为算法减少了代表样本的选取数量，降低了算法的存储开销，通过设置多中心向量，实现了增量分类。

3 最小距离分类算法

最小距离分类算法的基本思想[17]：设有m个类：[C1，C2，...，Cm]；根据训练样本实例的类别，分别使用算术平均的计算方法，计算出各个类别的中心向量Uk（k=1，2，3...m；m是样本类别数），对于每一个待分类的实例X，计算出实例X与中心向量[Uk]的距离d，从而找出距离最近的中心向量Uk，将实例X分给中心向量Uk代表的类别Ck，其中[X=[x1，x2，...，xn，C]]，[UK=[Lk1，Lk2，...，Lkn，C]] ，C代表所属类别，Lkn是算术平均计算求得的各属性均值。

4 基于最小距离的多中心向量的增量分类算法

ICMCVM算法分两个阶段，第一个阶段通过区域划分方法，将空间划分为稳定空间区域、边界重叠区域、未知空间区域。第二个阶段，通过多中心向量，实现增量分类。

4.2 不同区域样本的不同处理

因为落入不同区域的样本的价值是不等价的[18]，所以处理方法也应不同。

边界重叠区域的处理方法：该方法通过统计落入各个边界重叠区域内，每一个类别的实例数，用其中最大样本实例数的类别代表该边界重叠区域的类别，这样，当有一个未知类，落入边界重叠区域中，可以快速的将该样本分类给所代表的类别，无论样本增加多少，总是用统计中落入各个边界重叠区域的样本实例数最多的类别代表该区域类别。该方法会降低了分类的正确率，但是在边界不清的区域，正确分类本身就是一件困难的事情，所以该方法依然可以获得很好的效果。

稳定空间区域的处理方法：在训练样本空间足够大的情况下，落入稳定空间区域的样本，可以直接分类给该稳定子集所代表的类域。

未知空间区域的处理方法：对于未知空间区域，该文提出了一种多中心向量的增量处理方法，用来分类落入未知空间区域的样本。

4.3 增量分类的算法

定义1：在添加新中心向量时，该中心向量在现有数据集空间上的适应度，称为中心向量适应度。中心向量适应度计算方法：中心向量p为类别C的中心向量，分类器正确分类给中心向量p的代表样本集合为r1，实例个数为k1，错误分类给中心向量p的代表样本集合为r2，实例个数为k2，分类器正确分类给中心向量p的训练样本集合为w1，实例个数为k3，错误分类给中心向量p的训练样本集合为w2，实例个数为k4，已训练样本总数为N，代表样本个数为n，中心向量适应度计算公式是。

下面详细描述ICMCVM算法，算法有5个步骤：

步骤1 按4.1量化方法，量化增量样本为数值类型。

步骤2 用4.1节生成的分类器分类增量样本，增量样本将落入边界重叠区域、稳定空间区域、边界重叠区域。稳定空间区域和边界重叠区域的增量样本直接分类给区域代表类，而落入未知空间区域的的样本要进一步处理。

步骤3 对于落入未知区域的样本集合S，若不是第一次处理，跳转至步骤4，若是第一次处理，则将集合S按照属性类，根据最小距离算法的中心向量计算公式，使用欧式距离作为度量方式（欧式距离公式为[d-sqrt（（X-Uk）2）]其中，Uk为类Ck的中心向量，X为类Ck的实例），求出中心向量集合P，最小距离算法分类集合S，生成错误分类集合α，随机以集合α中的实例x为新增加的中心向量，再次分类集合S，若新中心向量的适应度Γ>0，则实例x为新的中心向量，加入集合P，从集合S中去除正确分类的所有实例，重复该步骤，直到找出所有的新中心向量。

步骤4 判断落入未知区域空间的实例总数SUM是否达到预设的样本总数阀值Φ，若达到，落入未知空间区域的实例总数SUM=0，按ILAMM算法增量样本的分类方法，增量分类代表样本集合J，重新区域划分，结果加入分类器。若没有达到阀值Φ，重新计算落入未知空间区域的实例总数SUM，在已有的中心向量集合P基础上，分类集合L，得到错误分类集合β，将代表样本集合加入新训练集合，随机以集合β中的实例x作为新增加的中心向量，再次分类新训练样本，若实例x的中心向量适应Γ>0，则实例x作为新的中心向量加入集合P，重复该步骤，直到找出所有的新中心向量。

步骤5 经过上述步骤后，落入边界重叠区域，落入稳定空间区域，落入未知空间区域的样本都可以分类，按ILAMM算法的代表样本获取方法，重新从落入未知空间区域的样本，选取代表样本，最后保留代表样本。

5 实验模拟

为了验证ICMCVM算法的有效性，该文实验比较了ICMCVM算法与ILAMM算法的时间、空间开销和算法的分类精度。实验使用C++语言在编译环境VS2010下编写，在CPU为IntelT6500，2GB内存的PC机上运行。

数据1 使用UCI网站上的Adult数据集，数据集拥有实例个数为48842个，有两种类别，分别为收入大于50k和收入小于等于50k，每个实例拥有14个属性，包括年龄、工种、教育、每周工作时间、种性别等，属性的数据类型有两种，连续型和离散型。实验1首先去除了Adult数据集中不完整属性值的数据实例18680个，然后将剩下的30162个数据实例分为已训练样本和增量训练样本2个部分，已训练样本的选取方法是，通过对数据集，采用未增量的分类算法分类，选取能够正确分类的20162样本为已训练样本，余下的实例作为增量训练样本，用来验证算法的增量效果。

6 结束语

本文提出了一种基于最小距离的增量分类算法ICMCVM，该算法划分区域分治分类样本，设置多中心向量，实现了增量分类，与ILAMM相比，减少了代表样本的选取数量，降低了存储开销。

ICMCVM算法面对数据空间有较多边界重叠区时，分类正确率会下降，因此提高数据的边界重叠区的分类正确率将是一个研究方向，同时，标量和字符串属性的量化方法，也是进一步可以研究的内容。

参考文献：

[1] 孟小峰，慈祥.大数据管理[J].概念、技术与挑战.计算机研究与发展，2013，50（1）：146-169.

[2] Last M.Online classification of nonstationary data streams[J].Intelligent Data Analysis，2002，6（2）：129-147.

[3] Jin R，Agrawal G.Efficient decision tree construction on streaming data[C]//Proceeding of the ACM SIGKDD，2003：571-576.

[4] Okamato K，Ozawa S，Abe S.A fast incremental learning algorithm of RBF networks with long-term memory[C].Proc. of the Intl Joint Conf.on Neural Networks，2003：102?107. http：//www2.kobe-u.ac.jp/～ozawasei/pub/ijcnn03a.pdf.

[5] Crammer K，Singer Y.Ultraconservative online algorithms for multiclass problems[C].Journal of Machine Learning Research，2003，3：951-991.

[6] Utgoff P E，Berkman N C，Clouse J A.Decision tree induction based on efficient tree restructuring[C].Machine Learning，1997，29：5-44.

[7] Luo B，Zhou Z H，Chen Z Q，et al.Induce： An incremental decision tree algorithm[J].Journal of Computer Research and Development， 1999，36（5）：518-522.

[8] Wang T，Li Z J，Hu X H，et a；.An incremental fuzzy decision tree classification method for data streams mining based on threaded binary search trees[J].Chinese Journal of Computers， 2007，30（8）：1244-1250.

[9] del Campo-?vila J，Ramos-Jiménez G，Gama J，et al.Improving prediction accuracy of an incremental algorithm driven by error margins[J].Intelligent Data Analysis， 2008，12（3）：305-318.

[10] Friedman N，Goldszmidt M.Sequential update of Bayesian network structure[C]. Proc. of the 13th Conf. on Uncertainty in Artificial Intelligence.1997：165?174. http：//www.cs.huji.ac.il/～nir/Papers/FrG4.pdf.

[11] Marin R，Sanchez J S，Sanz P J.ObjectRecognition and Incremental Learning Algorithms for a Web-Based Telerobotic System[C]//Proc of the IEEE International Conference on Robotics and Automation. Washington， USA，2002，III：2719-2724.

[12] Yamauchi K，Yamauchi N，Ishii N.Incremental Learning Methods with Retrieving of Interfered Patterns[J].IEEE Trans on Neural Networks，1999，10（6）：1351-1365.

[13] Zhao Dongfang，Yang Li.Incremental isometric embedding of high-dimensional data using connected neighborhood graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（1）： 86-98.

[14] 桑农，张荣，张天序.一类改进的最小距离分类器的增量学习算法[J].模式识别与人工智能，2007，20（3）：358-364.

[15] Schlimmer J C，Fisher D H.A case study of incremental concept induction[C].Proc. of the 5th National Conf. on Artificial Intelligence Philadelphia. Morgan Kaufmann Publishers，1986：496?501.https：//www.aaai.org/Papers/AAAI/1986/AAAI86-083.pdf.

[16] Quinlan J R.C4.5： Programs for Machine Learning[M].Morgan Kaufmann Publishers，1993.

[17] Anil K，Robert P，Duin W，et al.Statistical Pattern Recognition：A Review[J].IEEE Transactions on Patterm Analysis and Machine Intelligence，2000，22（1）：4-37.

[18] Angiulli F.Fast Nearest Neighbor Condensation for Large Data SetsClassification[J].IEEE Trans on Knowledge and Data Engineering，2007，19（11）：1450-1464.