劉三民，王忠群，劉　濤，修　宇.安徽工程大學計算機與信息學院，安徽蕪湖4000.安徽工程大學管理工程學院，安徽蕪湖4000

?

融合互近鄰降噪的動態(tài)數(shù)據(jù)流分類研究*

劉三民1+，王忠群2，劉濤1，修宇1
1.安徽工程大學計算機與信息學院，安徽蕪湖241000
2.安徽工程大學管理工程學院，安徽蕪湖241000

* The National Natural Science Foundation of China under Grant Nos. 61300170, 71371012 (國家自然科學基金); the Key Project for Outstanding Young Talents in Higher Education Institutions of Anhui Province under Grant No. 2013SQRL034ZD (安徽省高校優(yōu)秀人才重點項目); the General Project in Education Department of Anhui Province under Grant No. TSKJ2014B10 (安徽省教育廳一般項目); the Natural Science Foundation of Anhui Province under Grant No. 1608085MF147 (安徽省自然科學基金).

Received 2015-04,Accepted 2015-07.

CNKI網(wǎng)絡優(yōu)先出版：2015-08-11, http://www.cnki.net/kcms/detail/11.5602.TP.20150811.1522.006.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0036-07

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：動態(tài)數(shù)據(jù)流分類挖掘應用場景逐漸增多，如何辨識出動態(tài)數(shù)據(jù)流中概念漂移和噪聲信息成為數(shù)據(jù)流分類研究中的重點。因此提出一種具備噪聲檢測能力的動態(tài)數(shù)據(jù)流增量式分類挖掘模型解決此類問題。當動態(tài)數(shù)據(jù)流中出現(xiàn)樣本信息與分類模型概念不相容時，采用互近鄰思想檢測樣本是否為噪聲，在此基礎上用支持向量機作為學習器，通過增量式學習解決數(shù)據(jù)流中概念漂移。在兩種不相容度量標準下，結(jié)合理論分析和實驗，證明了所提的分類方案是有效可行的。

關鍵詞：互近鄰；增量學習；數(shù)據(jù)流分類；不確定性；概念漂移

1　引言

物聯(lián)網(wǎng)、云計算、Web2.0等新興技術的快速發(fā)展和應用需求的推動，數(shù)據(jù)不斷自主產(chǎn)生并以流的形式呈現(xiàn)，使得數(shù)據(jù)流分類成為亟待解決的問題[1]。由于數(shù)據(jù)產(chǎn)生過程出現(xiàn)概念漂移，導致靜態(tài)數(shù)據(jù)挖掘模型無法滿足動態(tài)數(shù)據(jù)流環(huán)境中的分類需求[2-3]。同時由于設備或環(huán)境的影響，數(shù)據(jù)流中不可避免存在噪聲，影響分類挖掘模型的有效性，增加動態(tài)數(shù)據(jù)流分類的復雜性。

針對動態(tài)數(shù)據(jù)流分類問題，國內(nèi)外學者進行了大量研究，并取得進展。在概念漂移檢測方面，文獻[4]把數(shù)據(jù)塊映射成概念向量進行聚類，通過計算數(shù)據(jù)集與對應概念向量之間的距離來判斷概念變化。文獻[5]根據(jù)中心極限定理實現(xiàn)概念漂移檢測模型，該模型不依賴于數(shù)據(jù)分布等先驗信息，具有一定實踐意義。為提高分類模型的準確性，朱群等人[6]提出一種雙層窗口機制數(shù)據(jù)流分類方法，解決單窗口機制難以適應多種類型概念漂移問題，同時抗噪性能顯著提高。文獻[7]結(jié)合集成學習和增量學習方法，解決數(shù)據(jù)流分類問題，實驗顯示該方法具有較高的準確率。文獻[8]融合水平集成和垂直集成分別解決噪聲和概念漂移問題，實驗結(jié)果證明方法可行，不足之處是集成規(guī)模難以控制。文獻[9]針對數(shù)據(jù)流分類中出現(xiàn)概念漂移和類不平衡問題，提出一種在線神經(jīng)網(wǎng)絡集成方法，其難點在于眾多的實驗參數(shù)如何優(yōu)化。文獻[10]從事前和事后兩種角度分析概念漂移發(fā)生特點，提出一種分類挖掘框架。文獻[11]根據(jù)聚類思想，實現(xiàn)一種自適應集成方法解決數(shù)據(jù)流分類問題。在動態(tài)數(shù)據(jù)流分類時集成式解決方案有其優(yōu)勢，但仍存在某些關鍵問題需妥善解決，如子分類器的更新、權重計算和結(jié)果融合等。增量式學習方法能夠解決概念漂移問題，但易受噪聲影響，無法有效分辨數(shù)據(jù)流中的概念漂移樣本和噪聲信息。

針對上述問題，本文提出了一種融合噪聲檢測的增量式動態(tài)數(shù)據(jù)流分類處理方案。該方案未采用先概念漂移檢測后更新訓練學習模型的傳統(tǒng)思路，而是針對當前不相容的樣本進行噪聲檢測來判斷樣本是否適合作為增量學習樣本。該方案的優(yōu)勢在于，避免通過數(shù)理統(tǒng)計推斷的方法來檢測概念漂移時因噪聲樣本的影響而降低準確性。

2　動態(tài)數(shù)據(jù)流中噪聲檢測

2.1基本概念

為便于描述，首先給出本文所用到的兩個基本概念：

定義1（數(shù)據(jù)流）形如{…，(xi?1，yi?1)，(xi，yi)，(xi＋1，yi＋1)，…}，其中xi表示特征屬性信息，yi表示對應類別信息。

基于數(shù)據(jù)流概念可以描述動態(tài)數(shù)據(jù)流中概念漂移現(xiàn)象。

定義2（概念漂移）是指在相鄰時間段內(nèi)，數(shù)據(jù)產(chǎn)生的聯(lián)合概率分布函數(shù)不一致現(xiàn)象，即pt(x，y)≠pt＋1(x，y)。

由上述定義可知，一旦數(shù)據(jù)流中產(chǎn)生概念漂移現(xiàn)象，基于歷史樣本獲得的分類模型在概念表示上將與新樣本不相容，這種不相容現(xiàn)象表現(xiàn)為對新樣本類別預測錯誤，或者是對新樣本的類別信息預測具有較大的不確定性。噪聲樣本在外部表現(xiàn)上與新概念樣本相似，因此在具有噪聲的動態(tài)數(shù)據(jù)流分類時應該對噪聲樣本與新概念樣本進行甄別。

2.2基于互近鄰的噪聲檢測

根據(jù)聚類思想可知相鄰樣本具有較高的相似性，即兩者之間概念相似的概率非常大?；诖擞^點本文提出了互近鄰的噪聲消除方法，基本思想是當樣本與互近鄰集合中樣本概念多數(shù)不一致時，即判斷為噪聲。

設樣本集S＝{(xi，yi)，i＝1，2，…，n}，其中xi是由特征屬性構(gòu)成的矢量，yi代表類別信息。在此樣本集上，可以給出相應概念的描述。

定義3（k-近鄰）指樣本xi在集合S中距離最近的k個樣本集合，本文記為Nk(xi)。

基于k-近鄰思想廣泛應用于分類和聚類學習中，實現(xiàn)過程中由于樣本過分依賴于近鄰信息來確定自己的類別情況，可能會出現(xiàn)誤判斷現(xiàn)象，即偽近鄰效應，也就是樣本的近鄰并沒有把該樣本作為它的近鄰。為避免偽近鄰現(xiàn)象導致的誤判斷，本文引出互近鄰的概念解決相應問題?；ソ徃拍顝娬{(diào)信息的對稱性，即真正近鄰是互相承認的近鄰關系。

定義4（k-互近鄰）若樣本xi∈Nk(xj)，且同時xj∈Nk(xi)成立，則稱樣本xi、xj為k-互近鄰。

根據(jù)定義4可知在樣本集合S中，樣本x的k-互近鄰集合可記為Mk(x)＝{xi∈S|xi∈Nk(x)∩x∈Nk(xi)}。結(jié)合k-近鄰和k-互近鄰的定義歸納出兩條有用的性質(zhì)，這是本文基于互近鄰進行噪聲檢測的基礎。

性質(zhì)1給定樣本集，樣本x的k-互近鄰是k-近鄰的子集，即Mk(x)?Nk(x)。

證明根據(jù)k-互近鄰的定義形式化Mk(x)＝{xi∈S| xi∈Nk(x)∩x∈Nk(xi)}可直接證明性質(zhì)1是成立的?！?/p>

性質(zhì)1保證通過求樣本的近鄰信息來獲得互近鄰信息是完備的。

性質(zhì)2給定近鄰k的參數(shù)值，樣本x與其互近鄰集合中的所有樣本必然滿足互為k-近鄰的近鄰關系。

證明設樣本xi∈Mk(x)，由定義2可知xi∈Nk(x) 與x∈Nk(xi)是同時成立的。又由樣本xi的任意性可知性質(zhì)2是成立的?！?/p>

性質(zhì)2保證所求近鄰信息是真正近鄰，提高基于互近鄰進行噪聲檢測的可靠性。

根據(jù)上述分析，本文的噪聲檢測算法（noisy elimination algorithm，NEA）描述如下所示。

算法1 NEA

輸入：S表示樣本集，x為待測樣本，k表示近鄰數(shù)。

輸出：待測樣本是否為噪聲信息。

1.求樣本x的k-近鄰，遍歷k-近鄰中每個樣本求其k-近鄰，凡滿足{xi∈S|xi∈Nk(x)∩x∈Nk(xi)}的樣本并入Mk(x)中。

2. If Mk(x)＝?返回樣本x是噪聲。

3. else統(tǒng)計Mk(x)中與樣本x類別相同的互近鄰個數(shù)count值

4. If count＜Mk(x)/2，返回樣本x是噪聲。

3　具有噪聲消除的動態(tài)數(shù)據(jù)流增量式分類

鑒于集成學習尚存在某些問題需要解決，本文采用增量式學習來適應數(shù)據(jù)流概念的動態(tài)變化。由于支持向量機具備出色的泛化性能而備受青睞，而且通過支持向量集進行樣本數(shù)量歸約，能夠降低增量學習時樣本復雜性，因此本文采用支持向量機算法作為增量學習器。

3.1支持向量機

支持向量機的實現(xiàn)本質(zhì)是求解能夠正確劃分樣本集的最優(yōu)分類超平面，當在原樣本空間線性不可分時，通過核映射把線性不可分問題轉(zhuǎn)化至高維空間實現(xiàn)線性可分，而且無需掌握映射函數(shù)信息。最優(yōu)超平面求解可以通過如下最優(yōu)化問題求解：

其中，C是懲罰因子，表示對錯分樣本的關注程度；ξi表示樣本松弛變量。根據(jù)拉格郎日最優(yōu)化方法，上式可轉(zhuǎn)化成下式易于求解的最優(yōu)化問題：

其中，K(xi，xj)為核函數(shù)。通過最優(yōu)化求解可得相應的分類函數(shù)：

在分類函數(shù)中，αi是拉格朗日乘子。由式（3）可知，最優(yōu)分類面是由乘子αi非零樣本構(gòu)成，這些樣本稱為支持向量（support vector，SV）。

3.2增量式數(shù)據(jù)流分類模型

在動態(tài)數(shù)據(jù)流分類中，增量式學習關鍵是從數(shù)據(jù)流中選出代表概念變化的樣本進行更新學習。由前文可知，當數(shù)據(jù)流出現(xiàn)概念漂移時，分類器具有較高概率錯分樣本或者分類結(jié)果呈現(xiàn)較大的不確定性，即此時出現(xiàn)分類器知識與樣本概念不相容現(xiàn)象。因此本文后續(xù)研究將在兩種概念不相容的度量基礎上進行分析。

文獻[12]對樣本不確定性進行詳細的分析，本文將采用相同的樣本不確定性概念，即樣本不確定性是指基于當前分類器關于樣本類別隨機變量的后驗概率信息熵的大小。本文僅討論兩分類問題，故樣本不確定性計算公式如下：

其中，pi表示樣本屬于第i類的后驗概率。

綜上可得動態(tài)數(shù)據(jù)流增量式學習分類流程，如圖1所示。

Fig.1 Flowchart of incremental learning圖1　增量式學習流程

基于圖1可以給出基于樣本不確定性的噪聲消除增量式數(shù)據(jù)流分類算法，文中記為SUNEIL（sample uncertainty based noisy elimination incremental learning algorithm）。

算法2 SUNEIL

輸入：DS＝{…，DBt?1，DBt，DBt＋1，…}，其中DBt表示固定大小的數(shù)據(jù)塊；支持向量機學習算法L；不確定性閾值θ；增量集IDS。

輸出：分類模型φ。

1.訓練初始分類模型(φ，sv)＝L(DB1)，其中sv表示支持向量

2. For i＝2 to|DS |

3.For j＝1 to|DBi|

4.用分類模型φ預測數(shù)據(jù)塊中樣本sj的后驗概率，并根據(jù)式（4）求不確定性值u

5.If (u＞θ)成立，則調(diào)用噪聲檢測算法NEA (DBi，sj，k)

6.如果樣本sj為非噪聲，則IDS＝IDS∪sj

7. (φ，sv)＝L(IDS∪sv)

類似可得基于錯誤樣本的增量式學習算法，文中記為ESNEIL（error sample based noisy elimination incremental learning algorithm）。

算法3 ESNEIL

輸入：DS＝{…，DBt?1，DBt，DBt＋1，…}，其中DBt表示固定大小的數(shù)據(jù)塊；支持向量機學習算法L；增量集IDS。

輸出：分類模型φ。

1.訓練初始分類模型(φ，sv)＝L(DB1)，其中sv表示支持向量

2. For i＝2 to|DS |

3.For j＝1 to|DBi|

4.用分類模型φ預測數(shù)據(jù)塊中樣本sj的類別，當預測錯誤時調(diào)用噪聲檢測算法NEA (DBi，sj，k)

5.如果樣本sj為非噪聲，則有IDS＝IDS∪sj

6.(φ，sv)＝L(IDS∪sv)

4　仿真實驗及結(jié)果分析

仿真數(shù)據(jù)流源于大型在線仿真平臺MOA[13]中的移動超平面數(shù)據(jù)流，在3種不同噪聲比率的數(shù)據(jù)流環(huán)境進行實驗，對比3種實驗方案，即基于不確定性增量式數(shù)據(jù)流分類（sample uncertainty based incremental learning algorithm，SUIL）、基于不確定性的噪聲消除增量式數(shù)據(jù)流分類（SUNEIL）和基于錯分樣本的噪聲消除增量式數(shù)據(jù)流分類（ESNEIL）。

4.1移動超平面數(shù)據(jù)流

移動超平面數(shù)據(jù)流[14]仿真生成辦法可以表示成m維超平面，其中特征值xi在區(qū)間（0，1）上隨機生成。當滿足時，由各特征值構(gòu)成的樣本(x1，x2，…，xm)代表正類樣本，否則為負類樣本，即，其中。在MOA平臺上通過調(diào)節(jié)參數(shù)生成不同的實驗數(shù)據(jù)集：噪聲參數(shù)n用來隨機改變樣本類別的概率大小，表示數(shù)據(jù)集中噪聲比；幅度調(diào)節(jié)參數(shù)m表示權值的變化量大??；參數(shù)s∈{?1，1}表示a方向改變情況，即按照設置的概率把s變成?s。研究目標是解決噪聲環(huán)境下動態(tài)數(shù)據(jù)流分類問題，因此生成3組實驗數(shù)據(jù)集(H1，H2，H3)，每個實驗數(shù)據(jù)集包含20 000條樣本信息，每個樣本由5個特征屬性構(gòu)成，其中2個特征屬性發(fā)生漂移，參數(shù)m取值0.1，參數(shù)s為10%。為分析基于互近鄰的噪聲檢測性能，分別往3個數(shù)據(jù)集H1、H2、H3中加入類噪聲25%、30%、35%。

4.2實驗結(jié)果分析

實驗環(huán)境基于Matlab7.1平臺，結(jié)合LibSVM[15]軟件包完成，實驗時支持向量機相關參數(shù)均按缺省值設置。結(jié)合文獻[12]，本文的近鄰參數(shù)k值和樣本不確定性閾值依據(jù)經(jīng)驗設置，分別為3和0.66。數(shù)據(jù)流按照固定數(shù)據(jù)塊大?。?00）進行批量處理，采用先測試后增量更新分類模型的方法，通過記錄準確率反映各種方案在噪聲環(huán)境中的動態(tài)數(shù)據(jù)流分類性能。圖2～圖4分別表示不同的噪聲數(shù)據(jù)流中3種實驗方案的變化曲線。

Fig.2 Accuracy of data block with 25% noisy圖2　含25%噪聲的數(shù)據(jù)塊準確率

Fig.3 Accuracy of data block with 30% noisy圖3　含30%噪聲的數(shù)據(jù)塊準確率

Fig.4 Accuracy of data block with 35% noisy圖4　含35%噪聲的數(shù)據(jù)塊準確率

由圖2～圖4中的準確率變化曲線可知，本文的分類方案是可行的。通過互近鄰辦法能夠發(fā)現(xiàn)動態(tài)數(shù)據(jù)流環(huán)境中的噪聲信息，利用增量式學習解決概念漂移問題。通過對比實驗曲線可知，僅依賴于樣本不確性進行增量學習（SUIL）隨著噪聲比例增加，準確性將急劇下降。而且在3種噪聲環(huán)境中，隨著數(shù)據(jù)塊的不斷處理，準確率曲線呈下降趨勢明顯，這是由于噪聲數(shù)據(jù)被認為是概念漂移樣本加入增量學習當中，導致學習器概念無法收斂。對比融入互近鄰的噪聲消除增量式學習方法可知，進行噪聲檢測在一定程度上緩解了噪聲樣本的影響，準確率曲線變化相對較為平緩，且平均值也高于SUIL分類方案。通過上述3個圖形準確率曲線可知，基于錯分樣本的噪聲消除增量學習方案（ESNEIL）較好。特別是當噪聲增加時，隨著數(shù)據(jù)塊處理ESNEIL的準確性很快就優(yōu)于其他兩種方案，且越來越明顯。通過實驗觀察發(fā)現(xiàn)，ESNEIL在整個處理過程中，效率較高，支持樣本數(shù)量明顯偏少，是另外兩種方案的一半左右。這說明在具備噪聲的動態(tài)數(shù)據(jù)流分類過程中，在表征分類器與樣本概念不相容時用錯分樣本較好，在此基礎上再進行噪聲檢測是較優(yōu)的處理方案。

Table 1 Mean and standard deviation of accuracy表1　準確率的平均值和標準差

表4中的統(tǒng)計量值也再次證實了上述相關結(jié)論，在3種噪聲環(huán)境下，ESNEIL的標準差是最小的，而且平均準確率相比也是最好的。采用增加了互近鄰的噪聲消除方法后，SUNEIL和ESNEIL準確率在相同的情況下均比SUIL要好，而且標準差值要小。這說明噪聲消除能夠辨識出概念變化樣本和噪聲樣本，特別是當噪聲增加時，其相關準確性和健壯性均能得到顯著提升。

5　結(jié)束語

針對噪聲環(huán)境中動態(tài)數(shù)據(jù)流分類問題，本文提出了一種噪聲消除的增量式學習方案。通過實驗數(shù)據(jù)證明了所設計的方案能夠解決所提出的問題，而且通過相關性質(zhì)說明了噪聲消除方案是可靠的。在研究過程中發(fā)現(xiàn)，基于錯分樣本的增量式學習方案支持向量集規(guī)模增長較為平緩，而基于樣本不確定性的增量式學習方案面臨支持向量集規(guī)模增大的困境，影響分類效率。后續(xù)研究將在概念傾斜的框架上，通過雙懲罰因子的支持向量機解決此問題。

References:

[1] Sun Dawei, Zhang Guangyan, Zheng Weimin. Big data stream computing: technologies and instances[J]. Journal of Software, 2014, 25(4): 839-862.

[2] Zliobaite I. Learning under concept drift: an overview[R]. Vilnius, Lithuania: Faculty of Mathematics and Informatics, Vilnius University, 2009.

[3] He Qing, Li Ning, Luo Wenjuan, et al. A survey of machine learning algorithms for big data[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(4): 327-336.

[4] Katakis I, Tsoumakas G, Vlahavas I. Tracking recurring contexts using ensemble classifiers: an application to email filtering[J]. Knowledge and Information Systems, 2010, 22(3): 371-391.

[5] Alippi C, Boracchi G, Roveri M. An effective just-in-time adaptive classifier for gradual concept drifts[C]//Proceedings of the 2011 International Joint Conference on Neural Networks, San Jose, USA, Jul 31-Aug 5, 2011. Piscataway, USA: IEEE, 2011: 1675-1681.

[6] Zhu Qun, Zhang Yuhong, Hu Xuegang, etal.Adouble-windowbased classification algorithm for concept drifting data streams[J].Acta Automatica Sinica, 2011, 37(9): 1078-1083.

[7] Flwell R, Polikar R. Incremental learning of concept drift in nonstationary environments[J]. IEEE Transactions on Neural Networks, 2011, 22(10): 1517-1531.

[8] Zhang Peng, Zhu Xingquan, Shi Yong, et al. Robust ensemble learning for mining noisy data streams[J]. Decision Support Systems, 2011, 50(2): 469-479.

[9] Ghazikhani A, Monsefi R, Yazdi H S. Ensemble of online neural networks for nonstationary and imbalanced data streams[J]. Neurocomputing, 2013, 122: 535-544.

[10] Hofer V, Georg K. Drift mining in data: a framework for addressing drift in classification[J]. Computational Statistics and Data Analysis, 2013, 57(1): 377-391.

[11] Dewan M F, Zhang Li, Alamgir H, et al. An adaptive ensemble classifier for mining concept drifting data streams[J]. Expert Systems with Applications, 2013, 40(15): 5895-5906.

[12] Liu Sanmin, Sun Zhixin, Liu Tao. Research of incremental data stream classification based on sample uncertainty[J]. Journal of Chinese Computer Systems, 2015, 36(2): 193-196.

[13] Holmes G, Kirkby R, Pfahringer B. MOA: massive onlineanalysis[EB/OL]. (2010)[2015-03-09]. http://sourceforge.net/ projects/moa-datastream.

[14] Hulten G, Spencer L, Domingos P. Mining time changing data streams[C]//Proceedings of the 2001 ACM International Conference on Knowledge Discovery and Data Mining, San Francisco, USA, 2001. New York, USA: ACM, 2001: 97-106.

[15] Chang C C, Lin C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 27(2): 1-27.

附中文參考文獻：

[1]孫大為,張廣艷,鄭緯民.大數(shù)據(jù)流式計算:關鍵技術及系統(tǒng)實例[J].軟件學報, 2014, 25(4): 839-862.

[3]何清,李寧,羅文娟,等.大數(shù)據(jù)下的機器學習算法綜述[J].模式識別與人工智能, 2014, 27(4): 327-336.

[6]朱群,張玉紅,胡學鋼,等.一種基于雙層窗口的概念漂移數(shù)據(jù)流分類算法[J].自動化學報, 2011, 37(9): 1077-1084.

[12]劉三民,孫知信,劉濤.基于樣本不確定性的增量式數(shù)據(jù)流分類研究[J].小型微型計算機系統(tǒng), 2015, 36(2): 193-196.

LIU Sanmin was born in 1978. He is an associated professor and Ph.D. at Anhui Polytechnic University. His research interests include pattern recognition, machine learning and data mining, etc.

劉三民（1978—），男，安徽安慶人，安徽工程大學副教授、博士，主要研究領域為模式識別，機器學習，數(shù)據(jù)挖掘等。

WANG Zhongqun was born in 1965. He is a professor at Anhui Polytechnic University. His research interests include software engineering, information management and information system, etc.

王忠群（1965—），男，安徽蕪湖人，安徽工程大學教授，主要研究領域為軟件工程，信息管理與信息系統(tǒng)等。

LIU Tao was born in 1973. She is an associated professor at Anhui Polytechnic University. Her research interests include network and information security, etc.

劉濤（1973—），女，安徽六安人，安徽工程大學副教授，主要研究領域為網(wǎng)絡與信息安全等。

XIU Yu was born in 1976. He is a lecturer at Anhui Polytechnic University. His research interests include data mining and machine learning, etc.

修宇（1976—），男，山東單縣人，安徽工程大學講師，主要研究領域為數(shù)據(jù)挖掘，機器學習等。

Research on Dynamic Data Streams Classification with Noise Elimination Using Mutual Nearest Neighbor*

LIU Sanmin1+, WANG Zhongqun2, LIU Tao1, XIU Yu1
1. College of Computer and Information,Anhui Polytechnic University, Wuhu,Anhui 241000, China
2. College of Management Engineering,Anhui Polytechnic University, Wuhu,Anhui 241000, China
+ Corresponding author: E-mail: aqlsm@163.com

LIU Sanmin, WANG Zhongqun, LIU Tao, et al. Research on dynamic data streams classification with noise elimination using mutual nearest neighbor. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：36-42.

Abstract:Application scenarios of dynamic data streams classification are increasing, and it is very important to discriminate concept drift from noisy information in data streams classification. This paper proposes an incremental classification model with noisy elimination for dynamic data streams classification to solve this problem. When dynamic data streams sample is incompatible with the concept of classifier model, the mutual nearest neighbor is used to detect noisy sample. Based on it, support vector machine is used as learner, and then concept drift in data streams is solved by incremental learning. Under two different metrics about incompatibility, classification schema is effective through the theory analysis and simulation experiment.

Key words:mutual nearest neighbor; incremental learning; data streams classification; uncertainty; concept drift

文獻標志碼：A

中圖分類號：TP311

doi:10.3778/j.issn.1673-9418.1504009