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

?

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

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

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

Received 2015-04,Accepted 2015-07.

CNKI網(wǎng)絡(luò)優(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ù)流分類挖掘應(yīng)用場景逐漸增多，如何辨識出動態(tài)數(shù)據(jù)流中概念漂移和噪聲信息成為數(shù)據(jù)流分類研究中的重點(diǎn)。因此提出一種具備噪聲檢測能力的動態(tài)數(shù)據(jù)流增量式分類挖掘模型解決此類問題。當(dāng)動態(tài)數(shù)據(jù)流中出現(xiàn)樣本信息與分類模型概念不相容時(shí)，采用互近鄰思想檢測樣本是否為噪聲，在此基礎(chǔ)上用支持向量機(jī)作為學(xué)習(xí)器，通過增量式學(xué)習(xí)解決數(shù)據(jù)流中概念漂移。在兩種不相容度量標(biāo)準(zhǔn)下，結(jié)合理論分析和實(shí)驗(yàn)，證明了所提的分類方案是有效可行的。

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

1　引言

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

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

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

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

2.1基本概念

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

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

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

定義2（概念漂移）是指在相鄰時(shí)間段內(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)為對新樣本類別預(yù)測錯(cuò)誤，或者是對新樣本的類別信息預(yù)測具有較大的不確定性。噪聲樣本在外部表現(xiàn)上與新概念樣本相似，因此在具有噪聲的動態(tài)數(shù)據(jù)流分類時(shí)應(yīng)該對噪聲樣本與新概念樣本進(jìn)行甄別。

2.2基于互近鄰的噪聲檢測

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

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

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

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

定義4（k-互近鄰）若樣本xi∈Nk(xj)，且同時(shí)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ì)，這是本文基于互近鄰進(jìn)行噪聲檢測的基礎(chǔ)。

性質(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-近鄰的近鄰關(guān)系。

證明設(shè)樣本xi∈Mk(x)，由定義2可知xi∈Nk(x) 與x∈Nk(xi)是同時(shí)成立的。又由樣本xi的任意性可知性質(zhì)2是成立的。□

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

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

算法1 NEA

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

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

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

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

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

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

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

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

3.1支持向量機(jī)

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

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

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

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

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

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

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

其中，pi表示樣本屬于第i類的后驗(yàn)概率。

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

Fig.1 Flowchart of incremental learning圖1　增量式學(xué)習(xí)流程

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

算法2 SUNEIL

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

輸出：分類模型φ。

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

2. For i＝2 to|DS |

3.For j＝1 to|DBi|

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

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

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

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

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

算法3 ESNEIL

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

輸出：分類模型φ。

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

2. For i＝2 to|DS |

3.For j＝1 to|DBi|

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

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

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

4　仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

4.2實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

Table 1 Mean and standard deviation of accuracy表1　準(zhǔn)確率的平均值和標(biāo)準(zhǔn)差

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

5　結(jié)束語

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

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.

附中文參考文獻(xiàn)：

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

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

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

[12]劉三民,孫知信,劉濤.基于樣本不確定性的增量式數(shù)據(jù)流分類研究[J].小型微型計(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—），男，安徽安慶人，安徽工程大學(xué)副教授、博士，主要研究領(lǐng)域?yàn)槟Ｊ阶R別，機(jī)器學(xué)習(xí)，數(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—），男，安徽蕪湖人，安徽工程大學(xué)教授，主要研究領(lǐng)域?yàn)檐浖こ?，信息管理與信息系統(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—），女，安徽六安人，安徽工程大學(xué)副教授，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)與信息安全等。

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—），男，山東單縣人，安徽工程大學(xué)講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，機(jī)器學(xué)習(xí)等。

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

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP311

doi:10.3778/j.issn.1673-9418.1504009