基于最小距離的多中心向量的增量分類算法

摘要：分類是數(shù)據(jù)挖掘的一項(xiàng)重要研究?jī)?nèi)容。在分析了現(xiàn)有分類方法后，提出了基于最小距離的多中心向量的增量分類算法。該方法首先按照屬性類聚類訓(xùn)練樣本，通過類間調(diào)整，消除類域空間重疊。針對(duì)增量分類，提出了多中心向量的分類算法，通過空間區(qū)域劃分的方法，減少增量分類選取的代表樣本數(shù)量。實(shí)驗(yàn)結(jié)果表明，與文獻(xiàn)[14]提出的增量分類算法相比，分類精度近似相同，但所需時(shí)間復(fù)雜度和存儲(chǔ)空間則有不同程度的下降，這對(duì)大數(shù)據(jù)的處理是具有重要意義的。

關(guān)鍵詞：增量分類；最小距離；多中心向量

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 概述

隨著大數(shù)據(jù)時(shí)代的到來，已有的數(shù)據(jù)挖掘技術(shù)面臨一系列新的挑戰(zhàn)。大數(shù)據(jù)具有數(shù)據(jù)體量巨大，數(shù)據(jù)增量快，數(shù)據(jù)結(jié)構(gòu)復(fù)雜等特點(diǎn)[1]，使得對(duì)大數(shù)據(jù)的挖掘存在許多困難。

分類是數(shù)據(jù)挖掘的重要內(nèi)容之一。目前已有許多分類算法，最小距離分類算法就是其中的一種。該算法擁有計(jì)算簡(jiǎn)單，概念明晰，易于理解，速度較快等優(yōu)點(diǎn)。該文提出了一種基于最小距離增量分類算法，與文獻(xiàn)[14]提出的算法相比，在分類精度大致相同的情況下，算法的復(fù)雜度和存儲(chǔ)開銷均有不同程度的下降，適合于對(duì)大數(shù)據(jù)進(jìn)行分類。

2 相關(guān)研究的工作

目前，增量分類算法有很多。如基于RBF網(wǎng)絡(luò)的增量分類算法[4]，基于支持向量機(jī)的增量分類算法[5]，基于最近鄰方法的增量分類算法，基于決策樹的增量分類算法[6-9]以及基于貝葉斯網(wǎng)絡(luò)的增量分類算法[10]。這些算法主要問題是復(fù)雜度高，要求的存儲(chǔ)空間大。而基于距離的增量分類算法則具有設(shè)計(jì)相對(duì)簡(jiǎn)單，復(fù)雜度低，存儲(chǔ)開銷小等特點(diǎn)，所以有很多基于距離的增量分類算法被提出。例如R.Marin等人提出的距離增量分類算法[11]，該算法首次實(shí)現(xiàn)了基于距離的增量分類；K，yamauchi提出了一種消除訓(xùn)練樣本間相互干擾的方法[12]，它利用已訓(xùn)練樣本進(jìn)行分類訓(xùn)練來消除樣本之間的干擾；Zhao等人提出了增量等距算法[13] ，通過映射新的數(shù)據(jù)點(diǎn)調(diào)整訓(xùn)練結(jié)果，用增量的方法強(qiáng)化分類結(jié)果，最后采用類似滑動(dòng)窗口的方式約束數(shù)據(jù)的增加；桑農(nóng)等提出了一種保留樣本的增量分類方法（ILAMM）[14] ，使用馬氏距離，解決了類域大小不一致影響分類正確率的問題。

基于距離的增量分類算法，不僅要能準(zhǔn)確分類增量樣本，而且要保持對(duì)已訓(xùn)練樣本的分類性能[15-16]。ILAMM算法更加適合于訓(xùn)練樣本和增量樣本數(shù)量級(jí)接近的增量分類情況，在訓(xùn)練樣本遠(yuǎn)大于增量樣本的情況下，分類效率比較低。該文在ILAMM算法的基礎(chǔ)上，提出了基于最小距離的多中心向量的增量分類算法（ICMCVM）。該算法通過將空間區(qū)域劃分為若干區(qū)域，提高了訓(xùn)練樣本比增量樣本大很多的情況下的增量分類效率，因?yàn)樗惴p少了代表樣本的選取數(shù)量，降低了算法的存儲(chǔ)開銷，通過設(shè)置多中心向量，實(shí)現(xiàn)了增量分類。

3 最小距離分類算法

最小距離分類算法的基本思想[17]：設(shè)有m個(gè)類：[C1，C2，...，Cm]；根據(jù)訓(xùn)練樣本實(shí)例的類別，分別使用算術(shù)平均的計(jì)算方法，計(jì)算出各個(gè)類別的中心向量Uk（k=1，2，3...m；m是樣本類別數(shù)），對(duì)于每一個(gè)待分類的實(shí)例X，計(jì)算出實(shí)例X與中心向量[Uk]的距離d，從而找出距離最近的中心向量Uk，將實(shí)例X分給中心向量Uk代表的類別Ck，其中[X=[x1，x2，...，xn，C]]，[UK=[Lk1，Lk2，...，Lkn，C]] ，C代表所屬類別，Lkn是算術(shù)平均計(jì)算求得的各屬性均值。

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

ICMCVM算法分兩個(gè)階段，第一個(gè)階段通過區(qū)域劃分方法，將空間劃分為穩(wěn)定空間區(qū)域、邊界重疊區(qū)域、未知空間區(qū)域。第二個(gè)階段，通過多中心向量，實(shí)現(xiàn)增量分類。

4.2 不同區(qū)域樣本的不同處理

因?yàn)槁淙氩煌瑓^(qū)域的樣本的價(jià)值是不等價(jià)的[18]，所以處理方法也應(yīng)不同。

邊界重疊區(qū)域的處理方法：該方法通過統(tǒng)計(jì)落入各個(gè)邊界重疊區(qū)域內(nèi)，每一個(gè)類別的實(shí)例數(shù)，用其中最大樣本實(shí)例數(shù)的類別代表該邊界重疊區(qū)域的類別，這樣，當(dāng)有一個(gè)未知類，落入邊界重疊區(qū)域中，可以快速的將該樣本分類給所代表的類別，無論樣本增加多少，總是用統(tǒng)計(jì)中落入各個(gè)邊界重疊區(qū)域的樣本實(shí)例數(shù)最多的類別代表該區(qū)域類別。該方法會(huì)降低了分類的正確率，但是在邊界不清的區(qū)域，正確分類本身就是一件困難的事情，所以該方法依然可以獲得很好的效果。

穩(wěn)定空間區(qū)域的處理方法：在訓(xùn)練樣本空間足夠大的情況下，落入穩(wěn)定空間區(qū)域的樣本，可以直接分類給該穩(wěn)定子集所代表的類域。

未知空間區(qū)域的處理方法：對(duì)于未知空間區(qū)域，該文提出了一種多中心向量的增量處理方法，用來分類落入未知空間區(qū)域的樣本。

4.3 增量分類的算法

定義1：在添加新中心向量時(shí)，該中心向量在現(xiàn)有數(shù)據(jù)集空間上的適應(yīng)度，稱為中心向量適應(yīng)度。中心向量適應(yīng)度計(jì)算方法：中心向量p為類別C的中心向量，分類器正確分類給中心向量p的代表樣本集合為r1，實(shí)例個(gè)數(shù)為k1，錯(cuò)誤分類給中心向量p的代表樣本集合為r2，實(shí)例個(gè)數(shù)為k2，分類器正確分類給中心向量p的訓(xùn)練樣本集合為w1，實(shí)例個(gè)數(shù)為k3，錯(cuò)誤分類給中心向量p的訓(xùn)練樣本集合為w2，實(shí)例個(gè)數(shù)為k4，已訓(xùn)練樣本總數(shù)為N，代表樣本個(gè)數(shù)為n，中心向量適應(yīng)度計(jì)算公式是。

下面詳細(xì)描述ICMCVM算法，算法有5個(gè)步驟：

步驟1 按4.1量化方法，量化增量樣本為數(shù)值類型。

步驟2 用4.1節(jié)生成的分類器分類增量樣本，增量樣本將落入邊界重疊區(qū)域、穩(wěn)定空間區(qū)域、邊界重疊區(qū)域。穩(wěn)定空間區(qū)域和邊界重疊區(qū)域的增量樣本直接分類給區(qū)域代表類，而落入未知空間區(qū)域的的樣本要進(jìn)一步處理。

步驟3 對(duì)于落入未知區(qū)域的樣本集合S，若不是第一次處理，跳轉(zhuǎn)至步驟4，若是第一次處理，則將集合S按照屬性類，根據(jù)最小距離算法的中心向量計(jì)算公式，使用歐式距離作為度量方式（歐式距離公式為[d-sqrt（（X-Uk）2）]其中，Uk為類Ck的中心向量，X為類Ck的實(shí)例），求出中心向量集合P，最小距離算法分類集合S，生成錯(cuò)誤分類集合α，隨機(jī)以集合α中的實(shí)例x為新增加的中心向量，再次分類集合S，若新中心向量的適應(yīng)度Γ>0，則實(shí)例x為新的中心向量，加入集合P，從集合S中去除正確分類的所有實(shí)例，重復(fù)該步驟，直到找出所有的新中心向量。

步驟4 判斷落入未知區(qū)域空間的實(shí)例總數(shù)SUM是否達(dá)到預(yù)設(shè)的樣本總數(shù)閥值Φ，若達(dá)到，落入未知空間區(qū)域的實(shí)例總數(shù)SUM=0，按ILAMM算法增量樣本的分類方法，增量分類代表樣本集合J，重新區(qū)域劃分，結(jié)果加入分類器。若沒有達(dá)到閥值Φ，重新計(jì)算落入未知空間區(qū)域的實(shí)例總數(shù)SUM，在已有的中心向量集合P基礎(chǔ)上，分類集合L，得到錯(cuò)誤分類集合β，將代表樣本集合加入新訓(xùn)練集合，隨機(jī)以集合β中的實(shí)例x作為新增加的中心向量，再次分類新訓(xùn)練樣本，若實(shí)例x的中心向量適應(yīng)Γ>0，則實(shí)例x作為新的中心向量加入集合P，重復(fù)該步驟，直到找出所有的新中心向量。

步驟5 經(jīng)過上述步驟后，落入邊界重疊區(qū)域，落入穩(wěn)定空間區(qū)域，落入未知空間區(qū)域的樣本都可以分類，按ILAMM算法的代表樣本獲取方法，重新從落入未知空間區(qū)域的樣本，選取代表樣本，最后保留代表樣本。

5 實(shí)驗(yàn)?zāi)M

為了驗(yàn)證ICMCVM算法的有效性，該文實(shí)驗(yàn)比較了ICMCVM算法與ILAMM算法的時(shí)間、空間開銷和算法的分類精度。實(shí)驗(yàn)使用C++語言在編譯環(huán)境VS2010下編寫，在CPU為IntelT6500，2GB內(nèi)存的PC機(jī)上運(yùn)行。

數(shù)據(jù)1 使用UCI網(wǎng)站上的Adult數(shù)據(jù)集，數(shù)據(jù)集擁有實(shí)例個(gè)數(shù)為48842個(gè)，有兩種類別，分別為收入大于50k和收入小于等于50k，每個(gè)實(shí)例擁有14個(gè)屬性，包括年齡、工種、教育、每周工作時(shí)間、種性別等，屬性的數(shù)據(jù)類型有兩種，連續(xù)型和離散型。實(shí)驗(yàn)1首先去除了Adult數(shù)據(jù)集中不完整屬性值的數(shù)據(jù)實(shí)例18680個(gè)，然后將剩下的30162個(gè)數(shù)據(jù)實(shí)例分為已訓(xùn)練樣本和增量訓(xùn)練樣本2個(gè)部分，已訓(xùn)練樣本的選取方法是，通過對(duì)數(shù)據(jù)集，采用未增量的分類算法分類，選取能夠正確分類的20162樣本為已訓(xùn)練樣本，余下的實(shí)例作為增量訓(xùn)練樣本，用來驗(yàn)證算法的增量效果。

6 結(jié)束語

本文提出了一種基于最小距離的增量分類算法ICMCVM，該算法劃分區(qū)域分治分類樣本，設(shè)置多中心向量，實(shí)現(xiàn)了增量分類，與ILAMM相比，減少了代表樣本的選取數(shù)量，降低了存儲(chǔ)開銷。

ICMCVM算法面對(duì)數(shù)據(jù)空間有較多邊界重疊區(qū)時(shí)，分類正確率會(huì)下降，因此提高數(shù)據(jù)的邊界重疊區(qū)的分類正確率將是一個(gè)研究方向，同時(shí)，標(biāo)量和字符串屬性的量化方法，也是進(jìn)一步可以研究的內(nèi)容。

參考文獻(xiàn)：

[1] 孟小峰，慈祥.大數(shù)據(jù)管理[J].概念、技術(shù)與挑戰(zhàn).計(jì)算機(jī)研究與發(fā)展，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] 桑農(nóng)，張榮，張?zhí)煨?一類改進(jìn)的最小距離分類器的增量學(xué)習(xí)算法[J].模式識(shí)別與人工智能，2007，20（3）：358-364.

[15] Schlimmer J C，F(xiàn)isher 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.