數(shù)據(jù)流分析和挖掘在數(shù)據(jù)挖掘和機器學習領(lǐng)域是一個具有挑戰(zhàn)性的研究，它已經(jīng)受到了計算機智能研究者的廣泛關(guān)注[1-3]。與傳統(tǒng)的靜態(tài)數(shù)據(jù)相比，數(shù)據(jù)流具有動態(tài)性、高維度、實時性、無限性、順序性和高速到達等特點[4]，正是這些特點使得傳統(tǒng)方法難以實現(xiàn)數(shù)據(jù)流的挖掘。而數(shù)據(jù)流分類是數(shù)據(jù)流挖掘的其中一種，它是從大量數(shù)據(jù)樣本中提取知識和信息的過程，而這些樣本中隱含的概念和知識可能隨著時間和環(huán)境不斷的發(fā)生變化，即存在的概念漂移[5]給研究帶來了挑戰(zhàn)。因此，一個高效的數(shù)據(jù)流分類算法需要在有限的時間和內(nèi)存下以相當好的準確度完成任務，并且能夠自適應地處理概念漂移。

　　摘要：當前已有的數(shù)據(jù)流分類模型都需要大量已標記樣本來進行訓練，但在實際應用中，對大量樣本標記的成本相對較高。針對此問題，提出了一種基于半監(jiān)督學習的數(shù)據(jù)流混合集成分類算法SMEClass，選用混合模式來組織基礎分類器，用K個決策樹分類器投票表決為未標記數(shù)據(jù)添加標記，以提高數(shù)據(jù)類標的置信度，增強集成分類器的準確度，同時加入一個貝葉斯分類器來有效減少標記過程中產(chǎn)生的噪音數(shù)據(jù)。實驗結(jié)果顯示，SMEClass算法與最新基于半監(jiān)督學習的集成分類算法相比，其準確率有所提高，在運行時間和抗噪能力方面有明顯優(yōu)勢。

　　關(guān)鍵詞：數(shù)據(jù)流,半監(jiān)督學習,集成分類,概念漂移,混合集成

　　在已有研究中，解決概念漂移問題的方法概括起來有三種[6]：實例選擇、實例加權(quán)和集成學習。近年來研究最熱的當屬集成學習方法[7-9]，它克服了運用滑動窗口方法參數(shù)難以確定的缺陷。盡管集成學習已經(jīng)取得了相當客觀的研究進展，但它是典型的有監(jiān)督學習，需要大量的類標數(shù)據(jù)進行訓練學習。而且標記數(shù)據(jù)是一個耗時又費力的工作，因此便有了近年來半監(jiān)督學習的研究[10-12]，它通過引入未標記數(shù)據(jù)來提高分類器的泛化性能�？梢哉f近年來集成學習和半監(jiān)督學習的研究都有了新的突破，但將兩者融合來改善分類性能的研究還是鳳毛麟角。2002年Bennett等人[13]提出使用標記和未標記數(shù)據(jù)共同構(gòu)造集成分類模型，文中主要運用Boosting方法，它的缺點在于沒有一種機制來控制對無類標數(shù)據(jù)標記的錯誤率；在文獻[14]中Woolam等人融合半監(jiān)督聚類和集成方法先將無類標數(shù)據(jù)進行標記，當標記數(shù)據(jù)占到一定比例時再對數(shù)據(jù)進行聚類，再運用類標傳播技術(shù)為剩余無類標數(shù)據(jù)進行標記，最后更新集成分類器，這樣當數(shù)據(jù)量很大時類標傳播會耗費[Ο（n3）]的時間。

　　基于上述研究中存在的缺陷，該文將集成學習和半監(jiān)督學習有效的融合，提出一種基于半監(jiān)督學習的混合集成分類算法（Semi-SupervisedlearningBasedMixtureEnsembleClassifier，SMEClass），由于引入未標記數(shù)據(jù)，使得集成分類器的準確性和泛化性都得到了改善，而且在對未標記數(shù)據(jù)進行標記時使用集成分類器和在數(shù)據(jù)塊已有的類標數(shù)據(jù)集上訓練的分類器一同進行多數(shù)投票，更增加了被標記數(shù)據(jù)的可信度。同時，在算法中也使用了概念漂移檢測和噪聲過濾的機制，以便能夠更有效的適應含噪音和概念漂移的數(shù)據(jù)流分類。

　　1SMEClass算法模型的訓練和分類的流程

　　數(shù)據(jù)流分類挖掘面臨著兩大難題，一是概念漂移和噪音的影響，二是數(shù)據(jù)流實例標記的高額代價，很少有算法能高效地實現(xiàn)兩者的兼顧，因此在標記樣本少的情況下，既能兼顧概念漂移和噪音影響，又能確保分類的精度將是一個挑戰(zhàn)，SMEClass能夠解決這些問題，它假設數(shù)據(jù)流中的樣本數(shù)據(jù)有一部分是隨機標注的，然后使用我們的集成方法來對這些數(shù)據(jù)中的未標記實例進行標記，以增加分類的性能，而且在訓練過程中進行了漂移監(jiān)測和噪音過濾。

　　由于數(shù)據(jù)流的特性，在此算法中使用C4.5和Na?veBayes作為基礎分類器來構(gòu)建混合集成模型，在每個數(shù)據(jù)塊上使用類似于self-training的方法來進行半監(jiān)督學習。

　　首先對方法中涉及到的符號進行說明：如表1所示。

　　2SMEClass算法

　　2.1算法的合理性論證

　　數(shù)據(jù)塊到達后，用其中的有標記數(shù)據(jù)訓練一個C4.5分類器，使用這個分類器和集成分類器一同對未標記數(shù)據(jù)進行預測，如果預測錯誤率小于隨機錯誤率，則將這個預測類標作為此數(shù)據(jù)的類標記。在最壞的情況下，當有噪音實例時，如果擁有足夠的類標數(shù)據(jù)，就能降低分類的錯誤率，為了達到這樣的效果，借鑒了文獻[16]中的思想。

　　2.2算法的執(zhí)行過程

　　3數(shù)據(jù)流變化的檢測和識別

　　3.1概念漂移的檢測

　　3.2噪聲數(shù)據(jù)的過濾

　　為了降低噪音數(shù)據(jù)對概念漂移檢測的影響，集成模型中增加了一個樸素貝葉斯分類器，這是因為Na?veBayes算法簡單、速度快、準確率高，還有一個重要的特性就是對噪音數(shù)據(jù)相當敏感，利用它的統(tǒng)計特性，能夠及時地發(fā)現(xiàn)數(shù)據(jù)中的噪音，以達到噪音過濾的效果。

　　使用這個計算方法，在[K+1]個分類器進行投票時，如果實例被一半以上的決策樹分類器和Na?veBayes分類器同時分類錯誤，那么概念就存在潛在的漂移，將分類錯誤的實例放入緩沖區(qū)；反之，認為是噪音，不用其構(gòu)建新的分類器，這樣就減少了那些噪音數(shù)據(jù)對漂移檢測的影響。

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

　　基于人工數(shù)據(jù)集、UCI提供的真實數(shù)據(jù)集和已有的半監(jiān)督集成分類方法SEClass[15]進行對比測試。分別從算法的準確率、運行時間和可擴展性三個方面驗證SMEClass方法的有效性。實驗運行環(huán)境為：1.73GHz英特爾奔騰雙核PC機，1GB內(nèi)存，WindowsXP操作系統(tǒng)。

　　為了實現(xiàn)算法，在實驗中使用MOA平臺，SMEClass的參數(shù)設置如下：[K=8]（基分類器個數(shù)），[d=5000]（數(shù)據(jù)塊大小）；SEClass參數(shù)如下：[L=8]（基分類器個數(shù)），[K=50]（微簇個數(shù)），[M=5000]，[e=0.9]。采用先測試再訓練的順序，這樣可以有效顯示模型的泛化能力。人工數(shù)據(jù)集包括HyperPlane、RandomRBF、RandomTree、SEA和Waveform。具體構(gòu)造見文獻[9]，真實數(shù)據(jù)集采用UCI提供的ForestCovertype。

　　表2顯示了數(shù)據(jù)集的相關(guān)信息，這里對數(shù)據(jù)集分成大小固定為1000的數(shù)據(jù)塊，使他們分批到達來模擬數(shù)據(jù)流的特性。

　　4.1算法準確率分析

　　算法的準確率如表3所示，由于現(xiàn)實生活中獲得已標記數(shù)據(jù)代價太大，在實驗數(shù)據(jù)集中我們只利用[20%]的已標記數(shù)據(jù)，其余[80%]的數(shù)據(jù)是未標記的，而且在實驗過程中增加了噪音數(shù)據(jù)和噪音屬性，以測試SMEClass算法對噪音數(shù)據(jù)的過濾能力和對含噪音屬性數(shù)據(jù)集的學習能力。

　　由于文獻[15]中有兩個屬性權(quán)值處理方式，SEClass-I在訓練中不調(diào)整屬性權(quán)值，SEClass-II在訓練迭代過程中動態(tài)調(diào)整屬性權(quán)值，通過對比實驗結(jié)果可以發(fā)現(xiàn)SMEClass和SEClass-II的準確率較高，由于SEClass-II動態(tài)調(diào)整屬性權(quán)值可以減少噪音屬性的影響，而SMEClass是采用的C4.5決策樹分類模型，也能實現(xiàn)這一點，葉節(jié)點在分裂的過程中會選擇具有最大增益率的屬性進行分裂，這樣每次都能選擇最重要的屬性。而且SMEClass采用的貝葉斯分類器還能夠有效降低噪音數(shù)據(jù)對準確度的影響，而SEClass沒有考慮噪音數(shù)據(jù)的影響，因此在同時含有噪音屬性和噪音數(shù)據(jù)的情況下，SMEClass的分類準確率要略勝一籌。

　　4.2算法的運行時間和可擴展性

　　在人工數(shù)據(jù)集RandomRBF上測試SMEClass算法和SEClass算法，改變數(shù)據(jù)集的屬性維度[d]來測試兩個算法在高維數(shù)據(jù)情況下的運行時間，從而檢驗算法的可擴展性。實驗結(jié)果如圖2所示，縱坐標代表算法訓練時間和測試時間之和。

　　觀察實驗結(jié)果，兩個算法的運行時間都隨屬性量的增加呈線性增長趨勢，這是因為在訓練基本分類器和測試過程中他們都是和屬性數(shù)量成線性關(guān)系的，但SMEClass的時間明顯少于SEClass，這是因為SEClass算法在聚類過程中需要頻繁計算實例間的距離，浪費了大量的時間，而SMEClass算法不存在這樣的問題，因此在時間上有明顯優(yōu)勢。這說明SMEClass算法在處理高維數(shù)據(jù)流時比較穩(wěn)定，具有良好的可擴展性。

　　5結(jié)束語

　　針對數(shù)據(jù)流類標數(shù)據(jù)獲取困難這一現(xiàn)狀，該文提出將集成學習和半監(jiān)督學習有效結(jié)合的一種分類算法SMEClass，算法在數(shù)據(jù)塊上采用類似于self-training的學習方法將置信度高的無類標數(shù)據(jù)賦予標記后加入類標集來改善基分類器的性能，由于在標記過程中使用了集成分類器的多數(shù)投票機制，這使加入的無類標數(shù)據(jù)更加可靠，而且增加了一個Na?veBayes分類器用來去除數(shù)據(jù)所含噪音，及時更新集成分類器以適應概念漂移。

　　實驗表明，與基于聚類的半監(jiān)督數(shù)據(jù)流集成分類算法SEClass相比，SMEClass算法具有更高的準確度和較強的抗噪性，而且免去了存儲大量微簇的空間，且運行時間隨屬性維度的增加呈現(xiàn)線性增長，具有一定的可擴展性，因此本文的算法能夠用于高維數(shù)據(jù)流分類問題。

　　參考文獻：

　　[1]LiaoSH，ChuPH，HsiaoPY.Dataminingtechniquesandapplications-Adecadereviewfrom2000to2011[J].ExpertSystemswithApplications，2012，39（12）：11303–11311.

　　[2]ReadJ，BifetA，HolmesG，PfahRINGERB.Scalableandefficientmulti-labelclassificationforevolvingdatastreams[J].MachineLearning，2012，88（1-2），243–272.

　　[3]白雪冰，王寶軍.數(shù)據(jù)流分類算法分析[J].電腦知識與技術(shù)，2012，8（11）：2445-2446.

　　[4]ZliobaiteI.Learningunderconceptdrift：anoverview[R/OL].Technicalreport，VilniusUniversity，2009.http：//arxiv.org/pdf/1010.4784v1pdf.

　　[5]WidmerG，KubatM.Learninginthepresenceofconceptdriftandhiddencontexts[J].MachineLearning，1996，23（1）：69-101.

　　[6]HoS-s，WechslerH.AMartingaleframeworkfordetectingchangesindatastreamsbytestingexchangeability[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2010，32（12）：2113-2127.

　　[7]ScholzM，KlinkenbergR.AnEnsembleClassifierforDriftingConcepts[C]//Proceedingsofthe2ndInternationalWorkshoponKnowledgeDiscoveryinData

　　Streams.Portugal：Porto，2005：53-64.

　　[8]AggarwalCC，HanJ，WangJY，etal.AFrameworkforOn-DemandClassificationofEvolvingDataStreams[J].IEEETransactionsonKnowledgeandDataEngineering，2006，18（5）：577-589.[9]BieftA，HolmesG，PfahringerB，etal.NewEnsembleMethodsforEvolvingDataStreams[C]//Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMing.France：Paris，2009：139-148.

　　[10]ChapelleO，ScholkopfB，ZienA，editors.Semi-SupervisedLearning[M].Cambridge：MITPress，2006.

　　[11]ZhuX.Semi-supervisedlearningliteraturesurvey[R/OL].TechnicalReport1530，DepartmentofComputerSciences，UniversityofWisconsinatMadison，2006.http：//www.cs.wisc.edu/jerryzhu/pub/ssl_survey.pdf.

　　[12]ZhouZH，LiM.Semi-supervisedlearningbydisagreement[J].KnowledgeandInformationSystems，2010，24（3）：415-439.

　　[13]BennettK，DemirizA，MaclinR.Exploitingunlabeleddatainensemblemethods[C]//Proceedingsofthe8thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.Canada：Edmonton，2002：289–296.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/dianzijishulw/28954.html