基于三支決策粗糙集的概念漂移研究

2016-02-23 03:44:48張任，王暉

網絡安全與數據管理 2016年22期

關鍵詞：定義概念

張任，王暉

(浙江師范大學數理與信息工程學院，浙江金華 321004)

基于三支決策粗糙集的概念漂移研究

張任，王暉

(浙江師范大學數理與信息工程學院，浙江金華 321004)

隨著大數據時代的到來，數據挖掘已經成為研究熱點，概念漂移作為數據挖掘領域所面臨的挑戰之一，也越來越受到人們的關注。針對傳統基于經典粗糙集的概念漂移探測研究不關注邊界域上的概念漂移現象、不具有容錯性的問題，提出了基于三支決策粗糙集的概念漂移的探測算法，該算法將概念漂移的探測拓展到了三支決策粗糙集領域，將正域概念漂移探測的意義推廣到了邊界域上，認為邊界域上的概念漂移現象也是值得研究的且具有實際意義的。利用三支決策粗糙集能夠有效模擬人類智能的不確定性和非精確性的特點，增加了該概念漂移算法的容錯性。最后，通過實驗驗證了該算法的可行性。

概念漂移;三支決策粗糙集;數據挖掘;容錯性

0 引言

現實生活中的數據總是按照時間的順序連續不斷地到達，如聲波和信號。連續不斷有序到達的數據就是數據流。由于干擾及噪聲的存在，從數據流中挖掘出有用的數據顯得十分重要。數據挖掘是機器學習的主要應用之一，目前機器學習所面臨的主要挑戰包括概念漂移。概念漂移[1-3]指的是數據及其分布隨時間的推移而變化的現象。

滑動窗口技術[4]作為探測概念漂移的常用技術之一，包括固定大小的滑動窗口和可變大小的滑動窗口。其運用的分類技術主要有單一分類器和集成分類器[5-6]，后者以其分類速度快、分類準確率高等優勢，在概念漂移探測領域取得了廣泛了應用。

粗糙集[7-8]是一種不需要借助外部知識，只需要通過對數據的分析、研究就能發掘數據的潛在的知識和規律的數學工具。目前已有一些利用粗糙集理論對概念漂移進行研究的介紹：文獻[9]利用粗糙集的上近似以及下近似來探測概念漂移，并運用粗糙率來度量概念漂移的程度；文獻[10]的研究建立在F-粗糙集理論之上，并提出了概念漂移探測的一些指標；文獻[11]通過分析并指出了運用數據內部特性——屬性重要度來探測概念漂移的效果優于利用分類準確率的方法；文獻[12]運用F-模糊粗糙集理論及其方法對模糊數據流上的模糊概念漂移進行探測。這些概念漂移的探測沒有關注到邊界域上的概念漂移情況，且不具有容錯性。

三支決策作為決策粗糙集的重要思想之一，有效模擬了人類智能的模糊性和不精準性，并重新探討了經典粗糙集的語義，將可能正確的劃入正域，即接受；可能不正確的劃入負域，即拒絕；介于兩者之間的劃入邊界域，表示需要進一步觀察，即延遲決策，并認為延遲決策是一種可執行決策。三支決策粗糙集[13-14]通過風險值得到的兩個閾值α、β對論域進行劃分從而得到具有某種容錯能力的三個區域，即正域、負域和邊界域，形成了具有容錯性的概率三支決策過程，增加了容錯性，該思想已經被應用在醫學診斷、數據集選擇以及智能學習等領域[15-16]。

對于邊界域的研究是三支決策粗糙集領域的一個熱點，邊界域代表著不確定性，對邊界域上的概念漂移情況進行研究，就是研究實際概念的不確定性，這更加切合概念漂移探測的實質，也更加符合人類的思維模式。

本文主要研究基于三支決策粗糙集的概念漂移探測，將傳統的基于經典粗糙集的概念漂移探測拓展到了三支決策粗糙集領域，將正域概念漂移探測的意義推廣到了邊界域上。首先提出了基于三支決策粗糙集探測概念，在重點關注邊界域上的概念漂移的同時，也提出了分別在正域、負域上概念漂移的度量指標及其相關算法；定義了從整體上綜合了正域、負域和邊界域上的概念漂移程度的概念漂移確及其算法；通過實驗驗證了文中所提方法的可行性。基于三支決策粗糙集的概念漂移探測符合人類日常處理決策問題時的思維過程，具有廣泛的代表性。

1 基礎知識

三支決策是決策粗糙集的核心思想之一，它將傳統的正域、負域兩支決策語義拓展為正域、負域和邊界域的三支決策語義，認為邊界域決策也是一類可行的決策，這與人類智能在處理決策問題的方法是一致的，也是人們在處理決策問題過程中常用的一種策略。例如現實中醫生對疾病進行診斷，有時并不能立即斷定是否患某種疾病，需要更進一步的觀察再作出判斷。現對三支決策粗糙集理論及其相關知識介紹如下。

定義1 假設U是一個有限的非空子集，R是定義在U上的一種等價關系，記apr=(U,R)，為近似空間，U在等價關系R下的劃分記為U/R={[x]R|x∈U}，[x]R是包含x的等價類。?X?U，其下、上近似集定義為：

上、下近似集將論域分為三個部分，即正域POS(X)、邊界域BND(X)和負域NEG(X)，其定義分別為：

由正域中元素導出的規則表示確定屬于X的規則，由負域中元素導出的規則表示確定不屬于X的規則，而由邊界域導出的規則表示可能屬于X的規則。這體現了三支決策的基本思想，但Pawlak粗糙集并沒有考慮到規則的容錯性。

定義2 假設S=(U,A,V,f)是一個信息表，R是定義在U上的等價關系，?x∈U，X?U，記

Pr(X|[x]R)=|[x]R∩X|/|[x]R|

其中，|·|表示集合中元素的基數；Pr(X|[x]R)表示分類條件概率。

定義3 假設S=(U,A,V,f)是一個信息表，?X?U，0≤β<α≤1，則(α,β)-下近似集、(α、β)-上近似集可分別定義為：

同樣地，(α,β)-上、下近似集將論域分為三個部分，即(α,β)-正域POS(α,β)(X)、(α,β)-邊界域BND(α,β)(X)和(α,β)-負域NEG(α,β)(X)，其定義分別為：

POS(α,β)(X)={x∈U|Pr(X|[x]R)≥α}

BND(α,β)(X)={x∈U|β

NEG(α,β)(X)={x∈U|Pr(X|[x]R)≤β}

當α=1，β=0時，該模型轉化成Pawlak粗糙集模型；當α=β=0.5時，上述模型轉化成0.5-概率粗糙集模型。然而，Pawlak粗糙集模型和0.5-概率粗糙集模型只是兩種特殊情況下的三支決策模型，大多概率粗糙集在參數α和β的選取上都缺乏對實際語義的思考。Yao等的決策粗糙集理論是將Bayes決策過程引入概率粗糙集模型，為概率粗糙集模型給出了語義上的一種解釋。

在決策粗糙集理論的(α,β)-三支決策過程中，條件概率Pr(X|[x]R)可完全從信息系統計算得出，是通過機器學習得到的，是客觀的；閾值α和β是通過行動損失參數計算得出的，而行動損失的大小可由行為學實驗或專家的意見給出，是通過人類經驗得到的，是主觀的。利用α和β去驗證條件概率Pr(X|[x]R)的正確性，利用條件概率Pr(X|[x]R)去指導α和β設置的合理性，兩者相輔相成，互為補充。因而，三支決策粗糙集體現了一種主觀和客觀相結合，人機合一的思想。

定義4 假設S=(U,C∪d,V,f)是一個決策表，α∈[0,1]為條件概率閾值,a∈C為單個屬性，則屬性a的α-正域全局重要度定義為：

三支決策作為決策粗糙集的重要思想之一，有效地模擬了人類智能的模糊性和不精準性，對于邊界域的研究是三支決策粗糙集領域的一個熱點，邊界域代表著不確定性，對概念在邊界域上的漂移進行研究，就是研究實際概念的不確定性，這更加切合概念漂移探測的實質，也更加符合人類的思維模式。

2 基于三支決策粗糙集的概念漂移

基于以上基礎知識及背景，本文將概念漂移的探測拓展到三支決策粗糙集領域。首先，對基于邊界域和負域的屬性重要度定義如下。

2.1 基于邊界域和負域的屬性重要度

傳統的關于屬性重要度的研究只集中在正域上，幾乎沒有研究是基于邊界域和基于負域的屬性重要度。基于邊界域的屬性重要度可以刻畫出屬性在邊界域上的變化情況，這為更好地研究延遲決策提供了依據，其相應的定義如下。

定義5(基于邊界域的屬性重要度) 已知S={U,C∪d,f,V}一決策表,0≤β<α≤1,α、β為概率閾值,a∈C為單個屬性,則決策屬性集D(這里簡記為d)相對于條件屬性a的(α,β)-邊界域全局重要度定義為：

定義6 (基于負域的屬性重要度) 已知S={U,C∪d,f,V}一決策表,0≤β<α≤1,β為概率閾值,a∈C為單個屬性,則決策屬性d相對于條件屬性a的(α,β)-負域全局重要度定義為：

定理1 決策屬性d對同一條件屬性a下的基于正域的屬性重要度、基于負域的屬性重要度以及基于負域的屬性重要度之和為定值1。

證明：由定義4～6可知γp(d)、γB(d)、γN(d)具體意義，在此不在贅述。

γp(d)+γB(d)+γN(d)=

定理1證畢。

定理2 基于邊界域的屬性重要度和基于負域屬性重要度至少有一個在約簡時不隨著屬性個數的減少而變增大。

證明：由文獻[13-14] 可知基于正域的屬性重要度不具有單調性，并且由定理1可知三個屬性重要度之間存在線性關系，故若基于邊界域的屬性重要度和基于負域的屬性重要度都存在著單調性，則基于正域的屬性重要度也必然存在單調性，故定理2成立。

2.2 基于三支決策粗糙集的概念漂移探測

基于三支決策粗糙集的概念漂移探測增加了探測算法的容錯性。因為三支決策粗糙集認為具有較高正確可能性的就可以進入正域，而不滿足較低劃分閾值的就可以進入負域，介于兩者之間的就會進入邊界域。而傳統的粗糙集要求完全正確或完全屬于的才可以進入正域，完全錯誤或完全不屬于的就進入負域，介于兩者之間的進入邊界域，所以不具有噪聲容忍機制。例如文獻[11]利用基于正域的屬性重要度去探測概念漂移，當存在噪聲的時候，正域的劃分將受到影響，從而導致基于正域的屬性重要度的值發生改變，若以此為依據來判斷是否存在概念漂移現象，則可能產生誤判。

本節主要研究基于三支決策粗糙集探測概念漂移，分別給出了基于邊界域、負域、正域的屬性重要性向量、基于三支決策的正域、邊界域和負域全局屬性重要度的概念漂移確指標定義，以及相關基于三支決策的概念漂移的探測算法(注：滑動窗口視為數據流決策系統的決策子表，兩者可等同看待)。

定義7(基于三支決策的邊界域全局屬性重要度矩陣) 已知Si={Ui,C∪D,f,V}(i=1,2,…，n)是數據流決策系統DS=(U,A,d)的滑動窗口，F是若干個滑動窗口的集合，則屬性A關于F基于三支決策的邊界域全局屬性重要度矩陣TB(A,F)可以定義為：

定義8(基于三支決策的正域全局屬性重要度矩陣)已知Si={Ui,C∪D,f,V}(i=1,2,…，n)是數據流決策系統DS=(U,A,d)的決策子表(滑動窗口)，F是若干個滑動窗口的集合，則屬性A關于F基于三支決策的正域全局屬性重要度矩陣TP(A,F)可以定義為：

定義9(基于三支決策的負域全局屬性重要度矩陣) 已知Si={Ui,C∪D,f,V}(i=1,2,…，n)是數據流決策系統DS=(U,A,d)的滑動窗口，F是若干個滑動窗口的集合，則屬性A關于F基于三支決策的負域全局屬性重要度矩陣TN(A,F)可以定義為：

2.2.1 獨立的概念漂移探測

傳統的概念漂移研究僅僅關注概念在正域上的漂移情況，而同一個概念在不同的情況下不僅在正域上發生了變化，它在邊界域、負域上也可能會發生變化。三支決策的優勢就是在于它注重決策的容錯性，并認為邊界域上的決策也是一種可行性決策，從而更加符合人類日常的思考。在考慮屬性的概念漂移時，不僅要考慮概念在正域上的漂移情況，同樣要考慮屬性在負域和邊界域的概念漂移情況。下面運用屬性重要性的變化情況對概念漂移進行度量，研究概念在正域、負域以及邊界域上的變化情況，并著重討論概念在邊界域上的漂移情況。它們的定義如下。

定義10(基于三支決策的邊界域全局屬性重要度概念漂移量) 在基于三支決策的邊界域全局屬性重要度矩陣TB(A,F)中，單個屬性a∈A在邊界域上的屬性重要度的概念漂移量定義為：

其中j為屬性a∈A在TB(A,F)中所對應的列。DTk、DTl為F中的兩個滑動窗口。

概念在邊界域上的漂移量的提出，為探測邊界域上的概念漂移情況提供了指標，從而更加切合探測概念漂移的實質，即對概念發生變化的不確定性進行度量，也更加符合人類的思維模式。例如：從數學上，通過邊界域來描述集合的不確定性，就能更精確地度量知識的不確定性。

同樣可以得到基于正域及負域的概念漂移量。

定義11(基于三支決策的正域全局屬性重要度概念漂移量) 在基于三支決策的正域全局屬性重要度矩陣TP(A,F)中，單個屬性a∈A在正域上的屬性重要度的概念漂移量定義為：

其中j為屬性a∈A在TP(A,F)中所對應的列。

定義12(基于三支決策的負域全局屬性重要度概念漂移量) 在基于三支決策的負域全局屬性重要度矩陣TN(A,F)中，單個屬性a∈A在負域上的屬性重要度的概念漂移量定義為：

其中j為屬性a∈A在TN(A,F)中所對應的列。

性質1 基于三支決策粗糙集的概念漂移探測具有容錯性。

定理3 基于三枝決策的屬性重要性的概念漂移量DRCDp(DTk,DTl)、DRCDB(DTk,DTl)DRCDN(DTk,DTl)滿足對稱、非負、三角不等式。

證明：因證明過程類似，這里只證明DRCDP(DTk,DTl)滿足對稱、非負、三角不等式。

定理4 基于三枝決策正域全局屬性重要性的概念漂移量DRCDp(DTk,DTl)非零時，則DRCDN(DTk,DTl)、DRCDB(DTk,DTl)中至多有一個為零。

證明：假設當DRCDp(DTk,DTl)非零時，則DRCDN(DTk,DTl)、DRCDB(DTk,DTl)全部為零。由正域、負域和邊界域的定義及屬性的重要度定義可知,在同一決策表中相同的屬性a中存在γP(d)+γB(d)+γN(d)=1，故在滑動窗口DTk、DTl中對于屬性a分別有γPk(d)+γBk(d)+γNk(d)=1，γPl(d)+γBl(d)+γNl(d)=1成立。若DRCDN(DTk,DTl)、DRCDB(DTk,DTl)都為零則可以知道|γBk-γBl|=|γNk-γNl|=0，即γBk=γBl，γNk=γNl，則γPk=γPl，那就可知DRCDP=|γPk-γPl|=0，與DRCDp(DTk,DTl)非零相矛盾，故原命題得證。

2.2.2 獨立的概念漂移探測算法

現在給出具體利用三支決策粗糙集探測概念獨立的概念漂移算法，為算法中表達清楚明白，下面首先給出概念漂移與閾值關系的定義，只有概念漂移量大于相應的閾值時，才認為存在概念漂移。

定義13(基于三支決策的邊界域全局屬性重要度概念漂移確) 設TB(A,F)是若干個滑動窗口Si(i=1,2,3,…，n)的基于三支決策的邊界域全局屬性重要度矩陣，ε為一個給定的閾值，DRCDBND(DTk,DTl)為基于三支決策的邊界域全局屬性重要度概念漂移量，則基于三支決策的邊界域全局屬性重要度概念漂移確QBND∈{0,1}：

(1)當DRCDBND(DTk,DTl)≥ε時，QBND=1；

(2)當DRCDBND(DTk-DTl)<ε時，QBND=0。

基于三支決策的邊界域全局屬性重要度概念漂移探測算法如下。

算法1 基于三支決策的邊界域全局屬性重要度概念漂移探測算法

輸入：若干個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)，閾值α,β∈[0,1]；

輸出：若干個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)有沒有發生邊界域概念漂移；

第1步：根據閾值α,β求出每個滑動窗口Si={Ui,d,f,V}(i=1,2,...n)的邊界域屬性重要度；

第2步：求出每個屬性在每個滑動窗口中的基于三支決策的邊界域的全局屬性重要度，并分別生成基于三支決策的邊界域全局屬性重要度矩陣TB(A,F)；

第3步：分別在這個矩陣中計算相鄰兩行之間對應元素之差，即基于邊界域的概念漂移量DRCDBND(DTi,DTi-1)；

第4步：計算基于三支決策的邊界域全局屬性重要度概念漂移確，即QBND；

輸出若干個滑動窗口Si={U,C∪D,f,V}(i=1,2,…，n)沒有發生邊界域概念漂移，結束程序。

定義14(基于三支決策的正域全局屬性重要度概念漂移確) 設TP(A,F)是若干個滑動窗口Si(i=1,2,3,…，n)的基于三支決策的正域全局屬性重要度矩陣，δ為一個給定的閾值，DRCDPOS(DTk,DTl)為基于三支決策的正域全局屬性重要度概念漂移量，則基于三支決策的正域全局屬性重要度概念漂移確QPOS∈{0,1}：

(1)當DRCDPOSij(DTi-DTi-1)≥δ時，QPOS=1；

(2)當DRCDPOSij(DTi-DTi-1)<δ時，QPOS=0。

基于三支決策的正域全局屬性重要度概念漂移探測算法如下。

算法2 基于三支決策的正域全局屬性重要度概念漂移探測算法

輸入：若干個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)，閾值α,β∈[0,1]；

輸出：若干個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)有沒有發生正域概念漂移；

第1步：根據閾值α,β求出每個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)的正域屬性重要度。

第2步：求出每個屬性在每個滑動窗口中的基于三支決策的正域的全局屬性重要度，并分別生成基于三支決策的正域全局屬性重要度矩陣TP(A,F)；

第3步：分別在這個矩陣中計算相鄰兩行之間對應元素之差，即基于正域的概念漂移量DRCDPOS(DTi,DTi-1)(1≤i≤n)；

第4步：計算基于三支決策的正域全局屬性重要度概念漂移確，即QPOS；

輸出若干個滑動窗口Si={U,C∪D,f,V}(i=1,2,…，n)沒有發生正域概念漂移，結束程序。

相應地，也可以得到屬性在負域上的概念漂移算法(算法3)，但篇幅原因，在此就不詳細敘述，記φ、QNES∈{0,1}為與基于負域的概念漂移量相對應得閾值和概念漂移確。

算法3(略)。

例1 設F={DT1,DT2}，如表1、表2所示，其論域U1={e1,e2,e3,e4,e5}，U2={e4,e5,e6,e7,e8},條件屬性集C={Headache,Muscle-pain,Temperature}，決策條件屬性d={Flu}。

表1 流感診斷決策表DT1

表2 決策子系統DT2

通過計算可得F的基于正域、邊界域、負域的屬性重要性矩陣TP(A,F)、TB(A,F)與TN(A,F)分別為：

DT1與DT2之間的概念漂移為：

如果ε、δ、φ均取0.3，那么相對于單個屬性a在正域、負域上具有概念漂移，在邊界域上就不具有概念漂移；相對于單個屬性b在邊界域、負域上具有概念漂移具有概念漂移，在正閾上就不具有概念漂移；相對于單個屬性c在正域、負域上具有概念漂移，在邊界域上不具有概念漂移。

2.2.3 整體概念漂移探測

下面探討整體上來探討概念漂移的程度。以上的研究只是在獨立的研究屬性在正閾、負域、邊界域是否存在概念漂移，沒有將正域、負域、邊界域上的概念漂移綜合起來研究屬性的概念漂移，不僅要單一地研究屬性的概念漂移，而且要整體上結合正域、負域、邊界域上的概念漂移來研究屬性的概念漂移，這樣更符合人們認識客觀世界的思維邏輯，從局部和整體上去認識事物。基于三支決策的整體概念漂移探測算法如下。

算法4 基于三支決策的整體概念漂移探測算法

輸入：若干個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)，閾值α,β∈[0,1]；

輸出：若干個滑動窗口Si={Ui,d,f,V}(i=1,2,…，n)有沒有發生整體概念漂移；

第1步:調用算法1、算法2、算法3分別計算基于三支決策的正域、邊界域、負域全局屬性重要度概念漂移確，即QPOS、QBND、QNEG；

第2步:計算QPOS+QBND+QNEG，若結果為3執行第3步，若結果為0執行第4步，若結果為1執行第4步，若結果為2執行第3步；

第3步：Si={U,C∪D,f,V}(i=1,2,…，n)發生了概念漂移，結束程序；

第4步：輸出若干個滑動窗口Si={U,C∪D,f,V}(i=1,2,…，n)沒有發生概念漂移，結束程序。

該整體概念漂移探測算法以正域、邊界域、負域各自表示的實際語義為依據，主要分為以下兩種情況：

(1)當正域、負域、邊界域至少兩者發生概念漂移時，則稱之單個屬性發生全概念漂移；

(2)當正域、負域、邊界域至多一個發生概念漂移時，則稱為屬性不發生全概念漂移。

3 實驗

在本節中將通過實驗來驗證算法和定義的可行性和有效性。實驗數據選擇UCI數據集的mushroom數據，滑動窗口大小為100，相鄰滑動窗口間有10%的重復率，閾值大小從0.01到1，間隔為0.01。

(1)獨立的屬性概念漂移探測

圖1和圖2分別顯示在所有滑動窗口下基于邊界域和正域的概念漂移情況。

圖1 基于邊界域的概念漂移總數與閾值ε之間的關系

圖1中DRCDBND(DTi,DTi+1)≥ε，表示在邊界域上存在一次概念漂移，通過圖1分析可知，概念在邊界域的確存在概念漂移的情況，并且不同的閾值會有相應的概念漂移情況產生，當閾值大于0.36以后邊界域上幾乎沒有概念漂移的情況。

圖2 基于正域的概念漂移總數與閾值δ之間的關系

圖2中，當DRCDPOS(DTi,DTi+1)≥δ時，表示存在一次概念漂移，實驗結果顯示閾值大于0.36以后邊界域上幾乎沒有概念漂移的情況，并且圖中曲線變化相比文獻[11]要平緩，原因是本文所依據的三支決策粗糙集決策規則的容錯性使得基于正域的屬性重要度的變化更加明顯，所定義的基于正域的屬性重要性的概念漂移量的變化范圍更廣，即可以容忍一定噪聲的影響，同樣基于邊界域上的概念漂移探測也是具有容錯性的。基于正域的概念漂移探測的閾值，通過圖1分析，可以選擇[0.05,0.25],而在文獻[11]閾值選取0.01～0.1，若輕微的噪聲的影響使得它所定義的度量概念漂移的指標值為0.01，則會判斷出屬性存在概念漂移。

基于負域的概念漂移與閾值φ之間的關系，同邊界域、正域相類似，在此就不再贅述。

(2)綜合意義下的概念漂移探測

下面來探討整體上來探討概念漂移的程度。以上的研究只是在獨立的研究屬性在正域、負域、邊界域是否存在概念漂移，沒有將正閾、負域、邊界域綜合起來研究屬性的概念漂移，不僅要單一地研究屬性的概念漂移，而且要整體、綜合研究概念漂移，圖3是根據概念漂移確來研究的綜合上探測概念漂移的情況。

圖3 單個屬性在滑動窗口下的整體概念漂移情況

在本次實驗中，實驗數據有9個屬性，論域被劃分為7個滑動窗口，因對每個屬性的實驗結果相類似，下面選取第4個屬性來說明概念在整體意義上的概念漂移情況。

在第1、3、4相鄰的滑動窗口下，屬性在整體上存在概念漂移的情況，特別在第3個相鄰的滑動窗口間，整體意義上的概念漂移情況更明顯。2中不存在單獨及整體上的概念漂移，5、6中在邊界域、負域上也存在整體意義的概念漂移。

由此可以更加清晰地判斷概念漂移的程度，若在整個滑動窗口中如3情況出現的次數過多，那么在后續基于三支決策的聚類和其他三支決策應用中就要對這個屬性特別注意，防止由于概念漂移而影響實際的結果。

4 結論

針對傳統基于經典粗糙集的概念漂移探測研究不關注邊界域上的概念漂移現象和不具有容錯性的問題，本文提出了基于三支決策粗糙集的概念漂移的探測算法。實驗結果表明該算法比傳統的概念漂移算法更具容錯性。但是，在處理具有大量屬性的概念在邊界域上的漂移探測問題上，仍然有可能存在時間復雜度過高的問題。將并行計算的思想結合到基于三支決策的概念漂移探測中，在探測之前對冗余屬性進行刪除，從而降低處理算法的時間復雜度，這將是下一步的研究方向。

[1]KUNCHEVALI.Classifierensemblesforchangingenvironments[C].ProceedingsoftheFifthWorkshoponMultipleClassifierSystems.Cagliari,Italy, 2004: 1-15.

[2] 王濤, 李舟軍, 顏躍進, 等. 數據流挖掘分類技術綜述[J]. 計算機研究與發展, 2007, 44(11): 1809-1815.

[3]HOENSTR,POLIKARR,CHAWLANV.Learningfromstreamingdatawithconceptdriftandimbalance:anoverview[J].ProgressinArtificialIntelligence, 2011: 1-13.

[4]BABCOCKB,BABUS,DATERM,etal.Modelsandissuesindatastreamsystems[C].Proceedingsofthe19thACM

SIGACT-SIGMOD-SIGARTSymposiumonPrinciplesDatabaseSystems,Madison,USA, 1802.

[5] 孫岳,毛國君,劉旭，等.基于多分類器的數據流中的概念漂移挖掘[J].自動化學報,2008, 34(1): 93-96.

[6]WangHaixun,FanWei,YUPS,etal.Miningconcept-driftingdatastreamsusingensembleclassifiers[C].Proceedingsofthe9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,Washington,USA, 2003:226-235.

[7]PAWLAKZ.Roughsets-theoreticalaspectofreasoningaboutdata[M].KluwerAcademicPublishers,Dordrecht, 1991.

[8] 王國胤, 姚一豫, 于洪. 粗糙集理論與應用研究綜述[J]. 計算機學報, 2009,32(7): 1229-1246.

[9]CaoFuyuan,HUANGJZ.Aconcept-drftingdetectionalgorithmforcategoricalevolvingdata[C].LectureNotesinComputerScience, 2013: 485-496.

[10] 鄧大勇, 裴明華, 黃厚寬.F-粗糙集方法對概念漂移的度量[J].浙江師范大學學報(自然科學版), 2013, 36(3): 303-308.

[11] 鄧大勇,徐小玉. 黃厚寬.基于并行約簡的概念漂移探測[J].計算機研究與發展, 2015,58(5):582-587.

[12] 張任.基于模糊并行約簡的模糊概念漂移探測[J]. 微型機與應用，2016,35(12):55-58.

[13] 劉盾，姚一豫，李天瑞.三支決策粗糙集[J].計算機科學，2011，38(1)：245-250.

[14]YaoYiyu.Probabilisticroughsetapproximations[J].InternationalJournalofApproximateReasoning,2008,49:255-271.

[15]LiuDun,LiHuaxiong,ZhouXxianzhong.Twodecades’researchondecision-theoreticroughsets[C].Proceedingof9thIEEEInternationalConferenceonCognitiveInformatics,2010.

[16] 李華雄，劉盾，周獻中.決策粗糙集模型研究綜述[J]. 重慶郵電大學學報(自然科學版)，2010，22(5)：624-630.

An implementation of Cloud-based video image recognition system

ZhangRen,WangHui

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

Asthetimeforbigdataiscoming,thedatamininghasbeenahottopic.Theconceptdriftingisoneofchallengeswhichthedataminingfaces,andmoreandmorepeoplefocusonit.Amingattheproblemsthattheresearchontheconceptdriftingbasedontheclassicalroughsettheorydoesn’thavefault-toleranceandpaysnoattentiontotheconceptdriftingonboundaryregion,thispaperproposesdetectionalgorithmofconceptdriftingbasedonthree-waydecisionroughset,whichextendsthedetectionoftheconceptdriftingtothefieldofthree-waydecisionroughsetanddetectionofconceptdriftingonpositiveregiontotheoneonboundaryregion,andregardsthedecisiononboundaryregionasafeasibleandvaluableone.Thefault-toleranceisaddedtothealgorithmbyusingthecharacteristicthatthethree-waydecisionroughsetcanimitatetheindeterminacyandinaccuracyofhumanintelligence.Finallythefeasibilityofthealgorithmisvalidatedthroughtheexperiment.

theconceptdrifting;three-waydecisionroughset;datamining;fault-tolerance

ADOI： 10.19358/j.issn.1674- 7720.2016.22.015

張任，王暉. 基于三支決策粗糙集的概念漂移研究[J].微型機與應用，2016,35(22)：54-60.

2016-06-16)

張任(1989-)，男，碩士研究生，主要研究方向：人工智能、數據挖掘。