馬憲敏

(黑龍江外國語學院 信息工程系， 哈爾濱 150025)

0 引言

在社會計算方面，需要提供認為最適合用戶當前場景的某種服務[1]。本文研究從大量用戶數(shù)據(jù)中提取出規(guī)則。近年來，社會計算受到廣泛應用，包括醫(yī)療保健系統(tǒng)和智能車輛系統(tǒng)均是這方面的應用典范。實施過程中，關鍵一點在于從大數(shù)據(jù)中準確、快速地提取有用規(guī)則，并高效地處理用戶所處環(huán)境以便為用戶提供最好的服務[2]。

實踐中，社會計算系統(tǒng)往往需要滿足實時性。因此，重要的是通過應用可簡化關聯(lián)規(guī)則數(shù)目的方案減少運算數(shù)據(jù)量；從而縮短數(shù)據(jù)處理時間。規(guī)則簡化方案保證數(shù)據(jù)完整性和較高的時間效率，為現(xiàn)實環(huán)境中部署社會計算提供了關鍵因素[3]。

規(guī)格簡化方案所適用的數(shù)據(jù)很特別地存在二進制屬性。先后有人提出了利用數(shù)據(jù)二進制屬性來挖掘關聯(lián)規(guī)則的各種算法，如直接散列，修剪，劃分法和動態(tài)項目集計數(shù)法。這些方法普遍用來增強挖掘效果，減少數(shù)據(jù)庫掃描次數(shù)及降低候選數(shù)據(jù)集數(shù)目。此外，有人提出了利用屬性分類或用戶屬性約束來挖掘廣義關聯(lián)規(guī)則的方法；通過借助于直方圖和樣本，找到不相關項目來挖掘負關聯(lián)規(guī)則的技術。對目標數(shù)據(jù)的關聯(lián)性進行分析所采用的基礎方法，其目的在于找出交易中頻繁出現(xiàn)的次數(shù)高于下限值的項目。由于所采用的數(shù)據(jù)結構較簡單，且結果存在確定性，故基于頻率的方法已得到廣泛應用。但是，隨著項目數(shù)不斷增多，計算時間急速增加，提取不頻繁出現(xiàn)的數(shù)據(jù)規(guī)則方面的信息就變得困難[4-5]。

為克服已有算法對大數(shù)據(jù)關聯(lián)規(guī)則挖掘存在的弊端，本文提出以二進制數(shù)字形式來表示數(shù)據(jù)集，對每個項目分配一個權重的WTabular算法。而且，利用奎因-麥克拉斯基算法[6]將邏輯函數(shù)簡化成一個算法。本文算法可減少不必要的規(guī)則，改善關聯(lián)規(guī)則的挖掘效率。實驗表明，無論是實用性和有效性還是規(guī)則簡化率和處理時間，本文算法較APRIORI算法[7]和FP增長算法[8]這兩種代表性算法均表現(xiàn)更佳。本文算法更適用于要求對大數(shù)據(jù)及時處理的社會計算領域。

1 相關研究工作

關聯(lián)規(guī)則是許多交易進行累積后交易與數(shù)據(jù)庫之間關聯(lián)性挖掘過程的結果；通過統(tǒng)計方法可以找到存在關聯(lián)的項目之間的規(guī)則性。例如，它們之間存在關聯(lián)：“如果發(fā)生了事故，其他事故也會發(fā)生”。

通過搜集大量交易，一個項目集與另一個項目集之間的關聯(lián)可以提取到，表明它們之間存在相似性或一個模式。關聯(lián)規(guī)則的基本特性是：對于一組交易表示為I，如果非空集合X和Y滿足XI和YI，表明當事故X發(fā)生后，事故Y也會發(fā)生。

規(guī)則的關聯(lián)等級由支持度和置信度來衡量。給定兩個數(shù)據(jù)集A和B，支持度S決定一條規(guī)則如何頻繁應用到給定的數(shù)據(jù)集；置信度C決定隸屬于B的項目在A中出現(xiàn)的次數(shù)。這兩個指標分別定義，如式(1)、(2)。

支持度：

(1)

置信度：

(2)

其中，σ(A)表示A含有的項目個數(shù)；支持度用來衡量關聯(lián)規(guī)則的有用性。一個非常低的“支持”的規(guī)則可以被判斷為偶爾發(fā)生，因此很難說這條規(guī)則是有用的。置信度衡量一個規(guī)則推理的有效性，

可以說給定規(guī)則A→B的可靠性越高，B在A中出現(xiàn)的概率就越大。因此，置信度界定B對A的條件概率。

從數(shù)據(jù)庫找到關聯(lián)規(guī)則分兩步：(1)尋找頻繁項；(2)生成關聯(lián)規(guī)則。

步驟1: 尋找頻繁項

頻繁項的最大數(shù)即項目集的冪集的大小。如果用戶感興趣的項目個數(shù)增加，項目集也呈幾何級數(shù)增長。掃描數(shù)據(jù)庫，計算每個項目的支持度，從而找到頻繁項。

步驟2: 生成關聯(lián)規(guī)則

1.1 APRIORI算法

APRIORI算法應用于候選項目。首先計算每個候選項目的頻率[8]；再根據(jù)數(shù)據(jù)集的最小支持度確定頻繁項；算法過程如下：

APRIORI算法

L1={Large-itemsets};

For(k=2;Lk-1=0;k++) do begin;

Ck=Apriori-gen(Lk-1);

For all transactionst∈Ddo begin;

Ct=subset(Ck,t);

For all candidatesc∈Ctdo

c.count++;

End

Lk={c∈Ct|c.count≥minsup};

End;

首先，生成包含了候選頻繁項C1；然后，對屬于C1的每個候選頻繁項的數(shù)據(jù)庫進行掃描；計算每個元素的支持度值；接下來，選出支持度值滿足置信度要求的項目，作為一個集合L1；對兩個元素的各子集進行上述操作；因為每個子集的元素個數(shù)會逐個增加，該過程需重復下去，直至不再有滿足要求的元素出現(xiàn)。

APRIORI算法生成由支持度大于最小置信度的項目構成的候選項目集；從而縮小搜索空間。但是，隨著滿足最小支持度的項目數(shù)量增多，會有大量要求重復掃描數(shù)據(jù)庫的候選集產(chǎn)生。要生成候選集，所有項目集的冪集生成為候選集且候選集的每個元素的頻率通過掃描數(shù)據(jù)庫可得到。這么做會導致產(chǎn)生并不存在的項目，充當交易數(shù)據(jù)里的候選集，浪費時間和空間。

1.2 FP樹算法

另一個將與本文算法對比的FP增長算法將含有頻繁項的數(shù)據(jù)庫壓縮成FP樹，生成條件模式樹，采用分而治之方法對與每個項目關聯(lián)的樹進行挖掘，同時挖掘關聯(lián)規(guī)則。

給定一個FP樹R，按照支持度升序方式對R里的每個頻繁項構建隨后的FP樹。[9]找出樹里頻繁項的所有出現(xiàn)次數(shù)；對每次出現(xiàn)，確定到達根部的路徑。記錄下每條路徑上項目的支持度值；將該路徑插入新構建的樹Rx，其中X是對項目加以前綴P后獲取到的項目集。插入路徑時，Rx上每個節(jié)點的權重隨著項目-i的路徑支持度pathsup(i)而增長；之后，遞歸調用FP增長函數(shù)，Rx與X作為參數(shù)。當輸入FP樹是單路徑時，存在一個基本情況：窮舉路徑子集的所有項目集來處理單路徑FP樹，以這樣的項目集的支持度值作為其中的最小頻繁項。

由于FP增長算法不生成候選集，也不共享頻繁集，所以比APRIORI算法浪費空間較小。它在速度方面也很出色，因為數(shù)據(jù)庫掃描只進行兩次。不過，F(xiàn)P增長算法要求對樹結構進行壓縮以對關聯(lián)規(guī)則進行快速挖掘，導致新數(shù)據(jù)添加困難。

1.3 奎因-麥克拉斯基算法

奎因-麥克拉斯基算法使布爾函數(shù)最小化。功能上它與卡諾映射大同小異，只是其制表形式效率高，所以經(jīng)常作為作計算機算法。該算法采用一種確定性方式來檢查布爾函數(shù)是否達到極小形式。有時可稱為制表法。此法分兩步：

1. 尋找函數(shù)的所有主蘊含項

2. 從主蘊含項圖表里，找到函數(shù)的必要主蘊含項

例如，假設減少方程的功能如式(3)。

f(A,B,C,D)=∑(4,8,9,10,11,12,14,15)

(3)

通過對最小項求和，可以形成式(4)乘積和正準表現(xiàn)式。

fA,B,C,D=A′BC′D′+AB′C′D′+AB′C′D+AB′CD′+AB′CD+ABC′D′+ABCD′+ABCD

(4)

式(4)不是最小的。為了使函數(shù)最小化，將所有評估成1的最小項首先以最小項形式按表格排列，然后與其他最小項合并。如果兩個項目相差只有一個單位數(shù)，用連接符“-”取代它，表明它無足輕重。

繼續(xù)操作直至不再有項目可以合并，至此創(chuàng)建主要的主蘊含項表格。

2 本文研究方法

本文提出一種新的挖掘方法，它有效減少大數(shù)據(jù)的關聯(lián)規(guī)則數(shù)目，同時具有較高的置信度和支持度。從大規(guī)模數(shù)據(jù)庫的數(shù)據(jù)里找到置信度高的規(guī)則，是包括社會化計算在內(nèi)諸多領域里的一項非常重要的工作，其中主要涉及對大數(shù)據(jù)的高效處理問題。因此，本文提出WTabular算法，它以二進制數(shù)字形式來表現(xiàn)交易數(shù)據(jù)集；通過與奎因-麥克拉斯基法和權重分配法結合，提高了關聯(lián)規(guī)則的挖掘效率。

2.1 基本運算

本文提出的WTabular算法以二進制數(shù)字形式表達數(shù)據(jù)集以及將權重與奎因-麥克拉斯基法相結合來簡化挖掘過程，有效改善了數(shù)據(jù)挖掘的效率。該過程由兩部分構成：(1)預處理：分3步；(2)后處理：分4步。前3步預處理環(huán)節(jié)去除疊加或不必要的數(shù)據(jù)并將數(shù)據(jù)轉化為適合分析的格式；具體步驟如下：

步驟1：先行部分的規(guī)則由小到大依次按1進行排列；

步驟2：從數(shù)據(jù)庫的規(guī)則里，找出先行部分之后部分的值為1的規(guī)則；

步驟3：計算步驟2找到的規(guī)則的權重；剔除權重值小于預設值的那些規(guī)則；

步驟4：通過預處理方式生成的數(shù)據(jù)相互比較，然后再進行簡化；

步驟5：通過比較數(shù)目1為i及i+1的項目將其進行簡化；

步驟6：重復步驟4和5步對初次簡化的結果進一步簡化； 如果沒有更多的減少是可能的，就停止工作；

步驟7：刪除重疊的規(guī)則。

2.2 分配權重到關聯(lián)規(guī)則

隨機生成的數(shù)據(jù)集用來解釋文中算法，如表1所示。

表1 輸入數(shù)據(jù)集

S1-S4表示傳感器；根據(jù)給定規(guī)則，將它所獲取到的數(shù)據(jù)轉化為二進制數(shù)據(jù)；F事件在二進制數(shù)據(jù)里出現(xiàn)情況(1：出現(xiàn)；0：未出現(xiàn))，取決于S的值。

本文算法進行預處理后對表2數(shù)據(jù)進行挖掘得到的結果，如表2所示。

表2 預處理的數(shù)據(jù)值為1

利用表2里F值為1的行而形成的數(shù)據(jù)集；APRIORI概率PPij，PPij由表2的數(shù)據(jù)得到如表3所示。

表3 表2數(shù)據(jù)的先驗概率

PPij表示Sj的APRIORI概率Di。APRIORI概率是傳感器值的百分比。例如，表2有7行，每一行都存在0值；所以S1的0值百分比計算為5/7=0.7；0.3是1值的百分比。同樣，S2的0值是3/7=0.4。

根據(jù)貝葉斯理論，將后驗權重分配給表3的數(shù)據(jù)。由式(5)可得到Di的后驗權重Wi。

(5)

在式(5)，n表示傳感器的數(shù)目；Wi是Di的平均后驗概率。由式(5)得到的權重，如表4所示。

表4 表3數(shù)據(jù)的權重

因為其權重小于最小權重0.5，所以要刪除D3，才能保證關聯(lián)規(guī)則簡化所需的置信度和支持度。

2.3 規(guī)則的簡化

采用本文的WTabular算法對規(guī)則進行簡化。在移除權重低于最小權重的規(guī)則后得到的規(guī)則，如表5所示。

表5 簡化后的規(guī)則

當表5中，數(shù)據(jù)f=1時，應用后處理環(huán)節(jié)步驟4的初次簡化；初次簡化后得到的結果，如表6所示。

表6 初次簡化的結果

在初次簡化之后，反復采用后處理環(huán)節(jié)的步驟5和步驟6直至不能簡化。表7給出二次簡化后的結果，如表7所示。

表7 二次簡化后的結果

最后得到的關聯(lián)規(guī)則，如表8所示。

表8 最后關聯(lián)規(guī)則

2.4 關聯(lián)規(guī)則的評價

根據(jù)式(1)和式(2)定義的方程，假設存在規(guī)則，表7的{S4}→f，其支持度和置信度均為100%。利用APRIORI算法，可計算{S4}→f滿足表1最小支持度20%的支持度和置信度，分別是38%和87%。APRIORI算法和WTabular算法的簡化率分別大約是69%和92%。由上述例子可知，本文提出的WTabular算法無論在支持度和置信度還是規(guī)則的簡化率方面都要優(yōu)于APRIORI算法。

3 實驗結果與討論

本文采取計算機模擬實驗來評估本文算法的性能。實驗采用的系統(tǒng)是INTER2.8Ghz酷睿2四核CPU，8GB RAM，32位Windows7；模擬代碼是Visual studio 2010的C++語言。

同時對APRIORI算法和FP增長算法進行評估；將它們與文中WTabular算法在數(shù)據(jù)規(guī)模不斷變化情況下對置信度、支持度、規(guī)則簡化率和數(shù)據(jù)處理速度的表現(xiàn)進行比較。

實驗數(shù)據(jù)庫取自人體感知的數(shù)據(jù)，隨機創(chuàng)建而成，具有7個預處理和兩個后處理屬性。每個數(shù)據(jù)項以二進制來表示，如果比閾值大,值就是1；否則為0。例如，如果權重正常，是0；否則是1。實驗用到的數(shù)據(jù)集大小從10萬逐漸擴大到100萬。

選擇規(guī)則{S5}→f1時，數(shù)據(jù)規(guī)模不同情況下三種算法的支持度和置信度比較結果，如圖2、圖3所示。

圖2 三種算法的支持度比較結果

圖3 三種算法的置信度比較結果

由圖2可知文中算法的支持度和置信度均優(yōu)于另兩種算法；而且，本文算法的規(guī)則簡化率最高，如圖4所示。

圖4 規(guī)則簡化率比較

所以，本文算法適合于通過快速對比最小數(shù)據(jù)，并且又保持較高置信度來提供準確服務社會化計算領域。

不同數(shù)據(jù)規(guī)模情況下規(guī)則挖掘次數(shù)的對比結果，如圖5所示。

當數(shù)據(jù)相對較小在50萬以下時，文中算法用時比FP增長算法稍長；但對更大規(guī)模的數(shù)據(jù)運算更快。所以我們認為

文中算法更適合用來處理大數(shù)據(jù)。

圖5 數(shù)據(jù)處理時間比較

4 總結

對給定數(shù)據(jù)集的關聯(lián)規(guī)則進行簡化是處理大規(guī)模數(shù)據(jù)的社會化計算領域一個非常重要的問題。目前，已有許多研究提出利用屬性分類學和負關聯(lián)規(guī)則的做法來有效簡化數(shù)據(jù)并找出關聯(lián)規(guī)則。本文提出WTabular算法是通過去除不滿足最小權重的數(shù)據(jù)并利用奎因-麥克拉斯基簡化方法來達到對關聯(lián)規(guī)則的數(shù)目進行刪減的目的。通過計算機模擬實驗，發(fā)現(xiàn)本文算法的支持度、置信度、規(guī)則簡化率和數(shù)據(jù)處理時間都較現(xiàn)有方法有所改善。

今后研究的重心在于該算法對流動數(shù)據(jù)的實時處理方面。關注傳感器實時收集無格式的流數(shù)據(jù)。因此，有必要對關聯(lián)規(guī)則簡化方面的方法論進行研究，以便不需要將無格式數(shù)據(jù)轉化為二進制數(shù)據(jù)而直接進行處理。而且，還要考慮通過語義傳感器網(wǎng)提前建立傳感器之間的關聯(lián)來提高關聯(lián)規(guī)則簡化的效果；并在多種領域和不同規(guī)模數(shù)據(jù)集方面對其進行驗證。

[1] 程學旗,靳小龍,王元卓,等. 大數(shù)據(jù)系統(tǒng)和分析技術綜述[J]. 軟件學報,2014,09:1889-1908.

[2] 張峰. 基于網(wǎng)絡化數(shù)據(jù)分析的社會計算關鍵問題研究[D].北京：北京郵電大學,2014.

[3] 陳翔,徐佳,吳敏,等. 基于社會行為分析的群智感知數(shù)據(jù)收集研究[J].計算機應用研究,2015,12:3534-3541.

[4] 陳愛東,劉國華,費凡,等. 滿足均勻分布的不確定數(shù)據(jù)關聯(lián)規(guī)則挖掘算法[J]. 計算機研究與發(fā)展,2013,S1:186-195.

[5] 張璽. 數(shù)據(jù)挖掘中關聯(lián)規(guī)則算法的研究與改進[D].北京郵電大學,2015.

[6] Chiu H P, Tang Y T, Hsieh K L. Applying clusterbased fuzzy association rules mining framework into EC environment[J]. Applied Soft Computing, 2012,12(8): 2114-2122.

[7] Sun D, Teng S, Wei Zhang, Haibin Zhu. An Algorithm to Improve the Effectiveness of Apriori[C]∥International Conference on Cognitive Informatics, 2007:385-390.

[8] Zhang W, Liao H, Zhao N. Research on the FP Growth Algorithm about Association Rule Mining[J].International Seminar Business and Information Management, 2008:315-318.

[9] Nelson V P, Nagle H T. Digital Logic Circuit Analysis and Design[M]. Prentice Hall, 1995.