基于頻繁模式的數據有效性評估研究

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

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

0 引 言

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

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

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

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

主要介紹了頻繁項集與關聯規則的基本概念，并對物聯網監測數據的滑動窗口提出物聯網數據流的滑動窗口樹(internet of things sliding window tree,ISW-tree)。

1.1 概念

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

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

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

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

Confidence(X?Y)

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

1.2 離散化數據

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

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

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

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

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

1.3 滑動窗口內的頻繁模式

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

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

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

2 衰減模型的應用

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

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

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

表1 規則示例表

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

圖1 頻繁模式樹

3 關聯規則的有效可信系數的劃分與規則可信評估

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

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

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

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

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

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

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

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

那么，監測指標X的整體基于關聯規則的有效可信度結果表示為：

4 結束語

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