王志剛，徐 越，梁永春，毛亞瓊

(1.青海師范大學(xué), 青海 西寧 810008; 2.華北科技學(xué)院, 河北 廊坊 101601)

0 引 言

關(guān)聯(lián)規(guī)則最先是由Agrawal等人于1994年針對(duì)類似購(gòu)物籃問(wèn)題提出的對(duì)感興趣關(guān)聯(lián)模式挖掘的方法。它包括兩部分內(nèi)容，一部分是頻繁項(xiàng)的挖掘，另一部分是關(guān)聯(lián)規(guī)則的生成。

大數(shù)據(jù)隨著計(jì)算機(jī)硬件與應(yīng)用軟件的不斷更新發(fā)展，能夠在服務(wù)的同時(shí)提供更多的內(nèi)在關(guān)聯(lián)信息，成為了當(dāng)前知識(shí)研究的熱點(diǎn)，如電子商城的興趣推薦、基于用戶行為的安全管理、疾病患者的癥狀預(yù)測(cè)治療等等，而利用頻繁模式的挖掘?qū)?shù)據(jù)有效的利用還沒(méi)有專門的研究。物聯(lián)網(wǎng)采集的監(jiān)測(cè)數(shù)據(jù)為提高數(shù)據(jù)的有效性，目前有很多方法都對(duì)異常數(shù)據(jù)進(jìn)行了清洗工作，如對(duì)空缺值得插補(bǔ)方法，Rubin利用貝葉斯Logistic進(jìn)行多重插補(bǔ)。劉燕提出了基于回歸的近鄰擇優(yōu)補(bǔ)差的方法等。而利用數(shù)據(jù)產(chǎn)生的規(guī)則來(lái)研究數(shù)據(jù)是否存在異常現(xiàn)象具有很大的研究?jī)r(jià)值。

本文第一步針對(duì)數(shù)據(jù)的連續(xù)性與離散型的特點(diǎn)，將特點(diǎn)不同的數(shù)據(jù)進(jìn)行離散化處理，得到模式挖掘的基本條件。文獻(xiàn)[1]對(duì)四種離散化方法進(jìn)行了比較，包括了貪心算法、基于信息熵、基于屬性以及數(shù)據(jù)挖掘的聚類方法。文獻(xiàn)[2]對(duì)聚類方法進(jìn)行了改進(jìn)，采用不完備集雙聚類的方法進(jìn)行數(shù)據(jù)處理。第二步是采用滑動(dòng)窗口的模式對(duì)數(shù)據(jù)進(jìn)行頻繁模式的挖掘。文獻(xiàn)[3]利用了數(shù)據(jù)流任意大小時(shí)間窗口關(guān)聯(lián)規(guī)則挖掘的方法(mining sliding window，MSW)，是將頻繁模式增長(zhǎng)(frequent pattern growth,FP-growth)算法改進(jìn)為頻繁模式樹(shù)算法FP-tree之后進(jìn)行關(guān)聯(lián)規(guī)則的挖掘。第三步是本文提出的對(duì)有效性的計(jì)算與評(píng)估。創(chuàng)新點(diǎn)在于，利用高斯公式對(duì)頻繁模式的衰減因子計(jì)算的方法對(duì)窗口事務(wù)重要性進(jìn)行衰減分析，結(jié)合時(shí)間衰減與窗口化頻繁模式的方法退出對(duì)數(shù)據(jù)屬性在關(guān)聯(lián)規(guī)則基礎(chǔ)上的數(shù)據(jù)可信評(píng)價(jià)的方法。

1 基于時(shí)間滑動(dòng)窗口的頻繁模式挖掘

主要介紹了頻繁項(xiàng)集與關(guān)聯(lián)規(guī)則的基本概念，并對(duì)物聯(lián)網(wǎng)監(jiān)測(cè)數(shù)據(jù)的滑動(dòng)窗口提出物聯(lián)網(wǎng)數(shù)據(jù)流的滑動(dòng)窗口樹(shù)(internet of things sliding window tree,ISW-tree)。

1.1 概念

(1)項(xiàng)、項(xiàng)集與頻繁項(xiàng)集定義：項(xiàng)表示數(shù)據(jù)源監(jiān)測(cè)指標(biāo)的某個(gè)取值或某個(gè)區(qū)間段的統(tǒng)稱；項(xiàng)集是項(xiàng)的集合，包含N個(gè)項(xiàng)的項(xiàng)集稱為N項(xiàng)集；支持度大于最小支持度閾值的項(xiàng)集稱為頻繁項(xiàng)集。

(2)支持度定義：支持度是兩個(gè)項(xiàng)或項(xiàng)集是否頻繁的有效監(jiān)測(cè)指標(biāo)，計(jì)算公式為：

式中，Support(X?Y)表示X,Y同時(shí)發(fā)生的支持度，Support_count(X∩Y)表示X,Y一起出現(xiàn)的記錄數(shù)量，Total_count表示數(shù)據(jù)記錄總數(shù)。

(3)置信度(Confidence)定義：置信度是衡量?jī)蓚€(gè)項(xiàng)或項(xiàng)集之間的關(guān)聯(lián)程度的有效監(jiān)測(cè)指標(biāo)。

Confidence(X?Y)

有效關(guān)聯(lián)規(guī)則的提取是需要事先確認(rèn)最小支持度min_sup與最小置信度min_con。并且在數(shù)據(jù)有效性可信度分析中，監(jiān)測(cè)指標(biāo)的各個(gè)項(xiàng)都是非空值，因?yàn)檫@在常規(guī)的數(shù)據(jù)異常處理都會(huì)填充可信任數(shù)值或者直接判斷為無(wú)效數(shù)據(jù)。

1.2 離散化數(shù)據(jù)

利用關(guān)聯(lián)規(guī)則無(wú)法直接處理連續(xù)型數(shù)據(jù)，若為連續(xù)型數(shù)據(jù)則需要對(duì)此類數(shù)據(jù)進(jìn)行離散化處理。有行業(yè)規(guī)則的根據(jù)行業(yè)規(guī)則對(duì)指標(biāo)區(qū)間符號(hào)化，無(wú)行業(yè)規(guī)則數(shù)據(jù)需要進(jìn)一步探索來(lái)劃分。聚類算法可以適用于大部分?jǐn)?shù)據(jù)源分類情況，優(yōu)點(diǎn)是能夠根據(jù)需求聚類出相似相近的數(shù)據(jù)集合。采用K-means聚類算法計(jì)算每個(gè)數(shù)據(jù)區(qū)間的權(quán)重，算法步驟如下：

第一步，將監(jiān)測(cè)指標(biāo)X的取值劃分為K個(gè)數(shù)據(jù)區(qū)間，即將指標(biāo)離散化為{X1,X2,…,Xi…XK}，由K個(gè)指標(biāo)項(xiàng)組成的建模數(shù)據(jù)。

第二步，從某指標(biāo)整體數(shù)據(jù)中隨機(jī)找出K個(gè)數(shù)據(jù)做為K個(gè)數(shù)據(jù)初始區(qū)間的重心；再根據(jù)這些重心的歐幾里得距離對(duì)所有對(duì)象聚類；如果數(shù)據(jù)x距重心Xi最近，將x歸為Xi所代表的那個(gè)區(qū)間，并記為xiTi，據(jù)值j是對(duì)應(yīng)每一次出現(xiàn)的數(shù)據(jù)標(biāo)號(hào)，范圍為[0,n]。

第三步，重新計(jì)算各區(qū)間的重心，并利用新的重心重新聚類所有樣本。

第四步，數(shù)據(jù)源中的數(shù)值xiTi表示在Xi這個(gè)離散化區(qū)間的某一個(gè)數(shù)。那么分布在Xi這個(gè)區(qū)間的數(shù)量為num(Xi)，Sum(Xi)為數(shù)據(jù)源的數(shù)據(jù)落在監(jiān)測(cè)指標(biāo)X的所有區(qū)間的總數(shù)量：

1.3 滑動(dòng)窗口內(nèi)的頻繁模式

采用基于數(shù)據(jù)流的滑動(dòng)窗口對(duì)頻繁模式的挖掘，利用對(duì)頻繁模式樹(shù)結(jié)構(gòu)算法FP-tree的改進(jìn)和利用提出的滑動(dòng)窗口樹(shù)結(jié)構(gòu)ISW-tree ，更新了存儲(chǔ)結(jié)構(gòu)，具體有以下兩點(diǎn)不同：

(1)在頻繁模式FP-tree上包括根節(jié)點(diǎn)(Root)、單獨(dú)事務(wù)(item)、事務(wù)數(shù)(count)，現(xiàn)在此基礎(chǔ)上增加時(shí)間戳的記錄標(biāo)識(shí)(TID)；(2)在FP-tree樹(shù)結(jié)構(gòu)節(jié)點(diǎn)都按照事務(wù)的支持?jǐn)?shù)的采用降序排列，針對(duì)傳統(tǒng)物聯(lián)網(wǎng)數(shù)據(jù)采集指標(biāo)的特殊性，ISW-tree采用的排列方式即指標(biāo)列表的固定排序方式。

正是由于這種固定的節(jié)點(diǎn)排序方式，使得節(jié)點(diǎn)之間的排列數(shù)序固定不變。這對(duì)基于時(shí)間的物聯(lián)網(wǎng)監(jiān)測(cè)的數(shù)據(jù)流來(lái)說(shuō)，能夠保證不用維護(hù)像FP-tree樹(shù)結(jié)構(gòu)基于節(jié)點(diǎn)支持?jǐn)?shù)采用流動(dòng)窗口時(shí)需要不斷變化動(dòng)態(tài)結(jié)構(gòu)，因此ISW-tree能夠更好地減少不斷改變結(jié)構(gòu)付出的代價(jià)。其次，雖然FP-tree的結(jié)構(gòu)在尋找頻繁項(xiàng)集上比Apriori更少地對(duì)數(shù)據(jù)庫(kù)進(jìn)行掃描，但對(duì)于龐大的數(shù)據(jù)來(lái)說(shuō)，掃描兩次數(shù)據(jù)庫(kù)仍然會(huì)對(duì)系統(tǒng)帶來(lái)很大的負(fù)荷，而ISW-tree由于固定指標(biāo)節(jié)點(diǎn)順序，為此可立即將新的數(shù)據(jù)流加載到滑動(dòng)窗口。

2 衰減模型的應(yīng)用

依據(jù)數(shù)據(jù)流的動(dòng)態(tài)特性特點(diǎn)，傳統(tǒng)的挖掘方法并不能適應(yīng)于這樣的流環(huán)境中[2]，有以下三點(diǎn)原因：(1)處理數(shù)據(jù)的設(shè)備內(nèi)存空間有限，數(shù)據(jù)量很大就不能實(shí)現(xiàn)將所有的頻繁模式都挖掘出來(lái)；(2)不能體現(xiàn)實(shí)時(shí)性，數(shù)據(jù)量的大小不能合理控制，導(dǎo)致精度和自適應(yīng)能力差；(3)不能夠獲得數(shù)據(jù)流的先驗(yàn)?zāi)Ｊ?，不具有模式指?dǎo)意義。因此要通過(guò)窗口與時(shí)間衰減模型的結(jié)合來(lái)適應(yīng)在動(dòng)態(tài)環(huán)境下的高效挖掘方法。

采用時(shí)間衰減模型TDM(time decay model)對(duì)窗口的舊事務(wù)的支持?jǐn)?shù)占有的權(quán)重進(jìn)行衰減操作，以此來(lái)降低歷史事務(wù)對(duì)產(chǎn)生新模式支持?jǐn)?shù)的影響。當(dāng)任意單位時(shí)間內(nèi)的事務(wù)到達(dá)窗口時(shí)，其單位時(shí)間內(nèi)的衰減程度系數(shù)用f(拉姆達(dá))來(lái)表示，范圍為(0,1]。那么模式P在任意時(shí)間點(diǎn)到達(dá)的支持度計(jì)數(shù)可以表示為fre(P,Ti),此時(shí)當(dāng)?shù)趇個(gè)事務(wù)到達(dá)窗口時(shí)，新的模式支持度計(jì)數(shù)可以用下面式子表示，即：

衰減因子的確定關(guān)系到衰減程度的大小，是基于時(shí)間滑動(dòng)窗口篩選頻繁項(xiàng)集確定支持度計(jì)數(shù)的重點(diǎn)。文獻(xiàn)[4]中對(duì)比了目前的衰減因子不同計(jì)算方法的優(yōu)劣，并且得出采用高斯函數(shù)的方法最能強(qiáng)調(diào)最近事務(wù)的重要性，并分析了高斯函數(shù)中參數(shù)的設(shè)置方法，為此采用高斯衰減因子fg滿足物聯(lián)網(wǎng)采集數(shù)據(jù)有效規(guī)則分析的實(shí)時(shí)性要求。如表1與圖1是關(guān)聯(lián)規(guī)則樹(shù)結(jié)構(gòu)ISW-tree算法示例：

表1 規(guī)則示例表

Itemscountx11.8x22.0406y13.541824y21z12.44z22.2096

圖1 頻繁模式樹(shù)

3 關(guān)聯(lián)規(guī)則的有效可信系數(shù)的劃分與規(guī)則可信評(píng)估

利用ISW-tree通過(guò)構(gòu)造滑動(dòng)窗口的樹(shù)結(jié)構(gòu)將項(xiàng)集列出來(lái)，首先找出所有的頻繁模式，然后利用本研究所需的對(duì)某一指標(biāo)的置信度需求，找出所有支持Xi的所有條件集合，且數(shù)量總數(shù)記為m。

例，集合U是上述示例數(shù)據(jù)源7條基于時(shí)間序列的項(xiàng)集，求X1在Y1Z1條件下的可信度：

U1={(x11y11z11)，(x12y12z12)，(x13y13z13)，(x21y14z14)}，此時(shí)X2Y1的衰減支持?jǐn)?shù)為最新的計(jì)數(shù)1.64，Z2支持?jǐn)?shù)1，從而置信度為：

這就是求得的一條規(guī)則的置信度結(jié)果，而在大量數(shù)據(jù)中會(huì)出現(xiàn)多個(gè)支持規(guī)則Z2的集合，單個(gè)集合表示為Uk，若總共有m個(gè)，下面將對(duì)這m個(gè)規(guī)則不同置信度結(jié)果進(jìn)行可信系數(shù)的劃分。

首先對(duì)置信度的區(qū)間進(jìn)行劃分，求得的置信度范圍在區(qū)間[0,1]，將此區(qū)間再劃分為三個(gè)區(qū)間，即不可信區(qū)間UI(Untrusted interval)，弱可信區(qū)間WCI(Weak confidence interval)，可信區(qū)間CI(Confidence interval)。根據(jù)不同用戶對(duì)置信度的要求高低，可對(duì)置信度區(qū)間取值范圍進(jìn)行伸縮設(shè)置。

可信系數(shù)定義，即根據(jù)項(xiàng)集規(guī)則挖掘時(shí)置信度的結(jié)果不同，對(duì)支持某個(gè)監(jiān)測(cè)指標(biāo)出現(xiàn)在三個(gè)不同置信區(qū)間時(shí)進(jìn)行系數(shù)劃分，得到的系數(shù)即為可信系數(shù)CC(Confidence coefficient)，取值范圍為[-1,1]。利用可信系數(shù)的正負(fù)值劃分來(lái)進(jìn)一步確認(rèn)指標(biāo)有效的可信程度。

單個(gè)項(xiàng)集的可信系數(shù)用CC來(lái)表示。因此，當(dāng)規(guī)則存在于可信區(qū)間CI時(shí)，且置信度越高， 越接近1。反之，在UI區(qū)間時(shí)，得到的可信系數(shù)越接近-1，對(duì)即將計(jì)算的有效可信度也越低。對(duì)于處于弱可信區(qū)間WCI的收集規(guī)則數(shù)據(jù)來(lái)說(shuō)，大多接近于0，可信度在模糊區(qū)間，因此需要用其它方法來(lái)進(jìn)一步驗(yàn)證有效性。

利用CC表示某一指標(biāo)值下所有支持該指標(biāo)值的集合的可信系數(shù)，那么區(qū)間數(shù)據(jù)的可信系數(shù)和SOC(Sum of Coefficients)可表示為：

那么，監(jiān)測(cè)指標(biāo)X的整體基于關(guān)聯(lián)規(guī)則的有效可信度結(jié)果表示為：

4 結(jié)束語(yǔ)

通過(guò)頻繁項(xiàng)集的引入，利用數(shù)據(jù)關(guān)聯(lián)規(guī)則的可信度來(lái)對(duì)數(shù)據(jù)關(guān)聯(lián)關(guān)系有效性評(píng)估進(jìn)行研究。重點(diǎn)利用了對(duì)采集物聯(lián)網(wǎng)數(shù)據(jù)的滑動(dòng)窗口ISW-tree以及在流動(dòng)的時(shí)間序列下的采用高斯函數(shù)的衰減支持度計(jì)數(shù)方法，對(duì)物聯(lián)網(wǎng)數(shù)據(jù)有效內(nèi)在隱性規(guī)律挖掘。本理論依然具有可拓展性和進(jìn)一步探索的方向，一是對(duì)數(shù)據(jù)關(guān)聯(lián)規(guī)則的研究可拓展到多個(gè)鄰居節(jié)點(diǎn)或者是邏輯相鄰節(jié)點(diǎn)進(jìn)行研究；二是在可信區(qū)間劃分并沒(méi)有確切可靠的區(qū)間定位，往往由專業(yè)人員根據(jù)需求輔助確定，也可通過(guò)機(jī)器學(xué)習(xí)以及博弈論等方法對(duì)不同領(lǐng)域?qū)^(qū)間提出劃分方法，權(quán)衡付出的代價(jià)和得到的收益并進(jìn)一步計(jì)算出最優(yōu)結(jié)果，提高數(shù)據(jù)有效性。數(shù)據(jù)有效性是提高數(shù)據(jù)質(zhì)量的基礎(chǔ)，數(shù)據(jù)只有在較高的可信度和可靠度的情況下才能為社會(huì)帶來(lái)巨大的效益。