基于頻繁模式的數(shù)據(jù)有效性評估研究

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

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

0 引 言

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

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

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

1 基于時間滑動窗口的頻繁模式挖掘

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

1.1 概念

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

(2)支持度定義：支持度是兩個項或項集是否頻繁的有效監(jiān)測指標，計算公式為：

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

(3)置信度(Confidence)定義：置信度是衡量兩個項或項集之間的關聯(lián)程度的有效監(jiān)測指標。

Confidence(X?Y)

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

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

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

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

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

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

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

1.3 滑動窗口內的頻繁模式

采用基于數(shù)據(jù)流的滑動窗口對頻繁模式的挖掘，利用對頻繁模式樹結構算法FP-tree的改進和利用提出的滑動窗口樹結構ISW-tree ，更新了存儲結構，具體有以下兩點不同：

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

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

2 衰減模型的應用

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

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

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

表1 規(guī)則示例表

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

圖1 頻繁模式樹

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

利用ISW-tree通過構造滑動窗口的樹結構將項集列出來，首先找出所有的頻繁模式，然后利用本研究所需的對某一指標的置信度需求，找出所有支持Xi的所有條件集合，且數(shù)量總數(shù)記為m。

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

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

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

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

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

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

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

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

4 結束語

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