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

張 任，王 暉

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

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

張 任，王 暉

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

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

概念漂移;三支決策粗糙集;數(shù)據(jù)挖掘;容錯(cuò)性

0 引言

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

滑動(dòng)窗口技術(shù)[4]作為探測(cè)概念漂移的常用技術(shù)之一，包括固定大小的滑動(dòng)窗口和可變大小的滑動(dòng)窗口。其運(yùn)用的分類技術(shù)主要有單一分類器和集成分類器[5-6]，后者以其分類速度快、分類準(zhǔn)確率高等優(yōu)勢(shì)，在概念漂移探測(cè)領(lǐng)域取得了廣泛了應(yīng)用。

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

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

對(duì)于邊界域的研究是三支決策粗糙集領(lǐng)域的一個(gè)熱點(diǎn)，邊界域代表著不確定性，對(duì)邊界域上的概念漂移情況進(jìn)行研究，就是研究實(shí)際概念的不確定性，這更加切合概念漂移探測(cè)的實(shí)質(zhì)，也更加符合人類的思維模式。

本文主要研究基于三支決策粗糙集的概念漂移探測(cè)，將傳統(tǒng)的基于經(jīng)典粗糙集的概念漂移探測(cè)拓展到了三支決策粗糙集領(lǐng)域，將正域概念漂移探測(cè)的意義推廣到了邊界域上。首先提出了基于三支決策粗糙集探測(cè)概念，在重點(diǎn)關(guān)注邊界域上的概念漂移的同時(shí)，也提出了分別在正域、負(fù)域上概念漂移的度量指標(biāo)及其相關(guān)算法；定義了從整體上綜合了正域、負(fù)域和邊界域上的概念漂移程度的概念漂移確及其算法；通過實(shí)驗(yàn)驗(yàn)證了文中所提方法的可行性?；谌Q策粗糙集的概念漂移探測(cè)符合人類日常處理決策問題時(shí)的思維過程，具有廣泛的代表性。

1 基礎(chǔ)知識(shí)

三支決策是決策粗糙集的核心思想之一，它將傳統(tǒng)的正域、負(fù)域兩支決策語(yǔ)義拓展為正域、負(fù)域和邊界域的三支決策語(yǔ)義，認(rèn)為邊界域決策也是一類可行的決策，這與人類智能在處理決策問題的方法是一致的，也是人們?cè)谔幚頉Q策問題過程中常用的一種策略。例如現(xiàn)實(shí)中醫(yī)生對(duì)疾病進(jìn)行診斷，有時(shí)并不能立即斷定是否患某種疾病，需要更進(jìn)一步的觀察再作出判斷?，F(xiàn)對(duì)三支決策粗糙集理論及其相關(guān)知識(shí)介紹如下。

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

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

由正域中元素導(dǎo)出的規(guī)則表示確定屬于X的規(guī)則，由負(fù)域中元素導(dǎo)出的規(guī)則表示確定不屬于X的規(guī)則，而由邊界域?qū)С龅囊?guī)則表示可能屬于X的規(guī)則。這體現(xiàn)了三支決策的基本思想，但Pawlak粗糙集并沒有考慮到規(guī)則的容錯(cuò)性。

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

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

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

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

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

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

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

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

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

在決策粗糙集理論的(α,β)-三支決策過程中，條件概率Pr(X|[x]R)可完全從信息系統(tǒng)計(jì)算得出，是通過機(jī)器學(xué)習(xí)得到的，是客觀的；閾值α和β是通過行動(dòng)損失參數(shù)計(jì)算得出的，而行動(dòng)損失的大小可由行為學(xué)實(shí)驗(yàn)或?qū)＜业囊庖娊o出，是通過人類經(jīng)驗(yàn)得到的，是主觀的。利用α和β去驗(yàn)證條件概率Pr(X|[x]R)的正確性，利用條件概率Pr(X|[x]R)去指導(dǎo)α和β設(shè)置的合理性，兩者相輔相成，互為補(bǔ)充。因而，三支決策粗糙集體現(xiàn)了一種主觀和客觀相結(jié)合，人機(jī)合一的思想。

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

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

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

基于以上基礎(chǔ)知識(shí)及背景，本文將概念漂移的探測(cè)拓展到三支決策粗糙集領(lǐng)域。首先，對(duì)基于邊界域和負(fù)域的屬性重要度定義如下。

2.1 基于邊界域和負(fù)域的屬性重要度

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

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

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

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

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

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

定理1證畢。

定理2 基于邊界域的屬性重要度和基于負(fù)域?qū)傩灾匾戎辽儆幸粋€(gè)在約簡(jiǎn)時(shí)不隨著屬性個(gè)數(shù)的減少而變?cè)龃蟆?/p>

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

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

基于三支決策粗糙集的概念漂移探測(cè)增加了探測(cè)算法的容錯(cuò)性。因?yàn)槿Q策粗糙集認(rèn)為具有較高正確可能性的就可以進(jìn)入正域，而不滿足較低劃分閾值的就可以進(jìn)入負(fù)域，介于兩者之間的就會(huì)進(jìn)入邊界域。而傳統(tǒng)的粗糙集要求完全正確或完全屬于的才可以進(jìn)入正域，完全錯(cuò)誤或完全不屬于的就進(jìn)入負(fù)域，介于兩者之間的進(jìn)入邊界域，所以不具有噪聲容忍機(jī)制。例如文獻(xiàn)[11]利用基于正域的屬性重要度去探測(cè)概念漂移，當(dāng)存在噪聲的時(shí)候，正域的劃分將受到影響，從而導(dǎo)致基于正域的屬性重要度的值發(fā)生改變，若以此為依據(jù)來判斷是否存在概念漂移現(xiàn)象，則可能產(chǎn)生誤判。

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

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

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

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

2.2.1 獨(dú)立的概念漂移探測(cè)

傳統(tǒng)的概念漂移研究?jī)H僅關(guān)注概念在正域上的漂移情況，而同一個(gè)概念在不同的情況下不僅在正域上發(fā)生了變化，它在邊界域、負(fù)域上也可能會(huì)發(fā)生變化。三支決策的優(yōu)勢(shì)就是在于它注重決策的容錯(cuò)性，并認(rèn)為邊界域上的決策也是一種可行性決策，從而更加符合人類日常的思考。在考慮屬性的概念漂移時(shí)，不僅要考慮概念在正域上的漂移情況，同樣要考慮屬性在負(fù)域和邊界域的概念漂移情況。下面運(yùn)用屬性重要性的變化情況對(duì)概念漂移進(jìn)行度量，研究概念在正域、負(fù)域以及邊界域上的變化情況，并著重討論概念在邊界域上的漂移情況。它們的定義如下。

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

其中j為屬性a∈A在TB(A,F)中所對(duì)應(yīng)的列。DTk、DTl為F中的兩個(gè)滑動(dòng)窗口。

概念在邊界域上的漂移量的提出，為探測(cè)邊界域上的概念漂移情況提供了指標(biāo)，從而更加切合探測(cè)概念漂移的實(shí)質(zhì)，即對(duì)概念發(fā)生變化的不確定性進(jìn)行度量，也更加符合人類的思維模式。例如：從數(shù)學(xué)上，通過邊界域來描述集合的不確定性，就能更精確地度量知識(shí)的不確定性。

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

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

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

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

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

性質(zhì)1 基于三支決策粗糙集的概念漂移探測(cè)具有容錯(cuò)性。

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

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

已知DRCDP(DTk,DTl)=|γkj-γlj|,DRCDP(DTl,DTk)=|γlj-γkj|,但|γkj-γlj|=|γlj-γkj|，故可知DRCDP(DTk,DTl)滿足對(duì)稱性;又知DRCDN(DTk,DTl)=|γkj-γlj|，則知DRCDP(DTk,DTl)滿足非負(fù)性、三角不等式。

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

證明：假設(shè)當(dāng)DRCDp(DTk,DTl)非零時(shí)，則DRCDN(DTk,DTl)、DRCDB(DTk,DTl)全部為零。由正域、負(fù)域和邊界域的定義及屬性的重要度定義可知,在同一決策表中相同的屬性a中存在γP(d)+γB(d)+γN(d)=1，故在滑動(dòng)窗口DTk、DTl中對(duì)于屬性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 獨(dú)立的概念漂移探測(cè)算法

現(xiàn)在給出具體利用三支決策粗糙集探測(cè)概念獨(dú)立的概念漂移算法，為算法中表達(dá)清楚明白，下面首先給出概念漂移與閾值關(guān)系的定義，只有概念漂移量大于相應(yīng)的閾值時(shí)，才認(rèn)為存在概念漂移。

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

(1)當(dāng)DRCDBND(DTk,DTl)≥ε時(shí)，QBND=1；

(2)當(dāng)DRCDBND(DTk-DTl)<ε時(shí)，QBND=0。

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

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

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

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

第1步：根據(jù)閾值α,β求出每個(gè)滑動(dòng)窗口Si={Ui,d,f,V}(i=1,2,...n)的邊界域?qū)傩灾匾龋?/p>

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

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

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

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

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

(1)當(dāng)DRCDPOSij(DTi-DTi-1)≥δ時(shí)，QPOS=1；

(2)當(dāng)DRCDPOSij(DTi-DTi-1)<δ時(shí)，QPOS=0。

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

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

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

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

第1步： 根據(jù)閾值α,β求出每個(gè)滑動(dòng)窗口Si={Ui,d,f,V}(i=1,2,…，n)的正域?qū)傩灾匾取?/p>

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

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

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

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

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

算法3(略)。

例1 設(shè)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 決策子系統(tǒng)DT2

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

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

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

2.2.3 整體概念漂移探測(cè)

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

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

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

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

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

第2步:計(jì)算QPOS+QBND+QNEG，若結(jié)果為3執(zhí)行第3步，若結(jié)果為0執(zhí)行第4步，若結(jié)果為1執(zhí)行第4步，若結(jié)果為2執(zhí)行第3步；

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

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

該整體概念漂移探測(cè)算法以正域、邊界域、負(fù)域各自表示的實(shí)際語(yǔ)義為依據(jù)，主要分為以下兩種情況：

(1)當(dāng)正域、負(fù)域、邊界域至少兩者發(fā)生概念漂移時(shí)，則稱之單個(gè)屬性發(fā)生全概念漂移；

(2)當(dāng)正域、負(fù)域、邊界域至多一個(gè)發(fā)生概念漂移時(shí)，則稱為屬性不發(fā)生全概念漂移。

3 實(shí)驗(yàn)

在本節(jié)中將通過實(shí)驗(yàn)來驗(yàn)證算法和定義的可行性和有效性。實(shí)驗(yàn)數(shù)據(jù)選擇UCI數(shù)據(jù)集的mushroom數(shù)據(jù)，滑動(dòng)窗口大小為100，相鄰滑動(dòng)窗口間有10%的重復(fù)率，閾值大小從0.01到1，間隔為0.01。

(1)獨(dú)立的屬性概念漂移探測(cè)

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

圖1 基于邊界域的概念漂移總數(shù)與閾值ε之間的關(guān)系

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

圖2 基于正域的概念漂移總數(shù)與閾值δ之間的關(guān)系

圖2中，當(dāng)DRCDPOS(DTi,DTi+1)≥δ時(shí)，表示存在一次概念漂移，實(shí)驗(yàn)結(jié)果顯示閾值大于0.36以后邊界域上幾乎沒有概念漂移的情況，并且圖中曲線變化相比文獻(xiàn)[11]要平緩，原因是本文所依據(jù)的三支決策粗糙集決策規(guī)則的容錯(cuò)性使得基于正域的屬性重要度的變化更加明顯，所定義的基于正域的屬性重要性的概念漂移量的變化范圍更廣，即可以容忍一定噪聲的影響，同樣基于邊界域上的概念漂移探測(cè)也是具有容錯(cuò)性的?；谡虻母拍钇铺綔y(cè)的閾值，通過圖1分析，可以選擇[0.05,0.25],而在文獻(xiàn)[11]閾值選取0.01～0.1，若輕微的噪聲的影響使得它所定義的度量概念漂移的指標(biāo)值為0.01，則會(huì)判斷出屬性存在概念漂移。

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

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

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

圖3 單個(gè)屬性在滑動(dòng)窗口下的整體概念漂移情況

在本次實(shí)驗(yàn)中，實(shí)驗(yàn)數(shù)據(jù)有9個(gè)屬性，論域被劃分為7個(gè)滑動(dòng)窗口，因?qū)γ總€(gè)屬性的實(shí)驗(yàn)結(jié)果相類似，下面選取第4個(gè)屬性來說明概念在整體意義上的概念漂移情況。

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

由此可以更加清晰地判斷概念漂移的程度，若在整個(gè)滑動(dòng)窗口中如3情況出現(xiàn)的次數(shù)過多，那么在后續(xù)基于三支決策的聚類和其他三支決策應(yīng)用中就要對(duì)這個(gè)屬性特別注意，防止由于概念漂移而影響實(shí)際的結(jié)果。

4 結(jié)論

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

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

[2] 王濤, 李舟軍, 顏躍進(jìn), 等. 數(shù)據(jù)流挖掘分類技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 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] 孫岳,毛國(guó)君,劉旭，等.基于多分類器的數(shù)據(jù)流中的概念漂移挖掘[J].自動(dòng)化學(xué)報(bào),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] 王國(guó)胤, 姚一豫, 于洪. 粗糙集理論與應(yīng)用研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2009,32(7): 1229-1246.

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

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

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

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

[13] 劉盾，姚一豫，李天瑞.三支決策粗糙集[J].計(jì)算機(jī)科學(xué)，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] 李華雄，劉盾，周獻(xiàn)中.決策粗糙集模型研究綜述[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版)，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

TP

ADOI： 10.19358/j.issn.1674- 7720.2016.22.015

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

2016-06-16)

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