一種基于壓縮矩陣的多值屬性關(guān)聯(lián)規(guī)則改進(jìn)算法

汪峰坤，張婷婷

（安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系，安徽蕪湖，241000）

一種基于壓縮矩陣的多值屬性關(guān)聯(lián)規(guī)則改進(jìn)算法

汪峰坤，張婷婷

（安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系，安徽蕪湖，241000）

針對(duì)經(jīng)典的Apriori算法對(duì)多值屬性數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)效率低下的問題，提出了改進(jìn)算法。算法通過對(duì)屬性值進(jìn)行二進(jìn)制編碼、增加行和屬性值計(jì)數(shù)器等方式，對(duì)數(shù)據(jù)進(jìn)行了壓縮，并針對(duì)壓縮的存儲(chǔ)矩陣使用了新的頻繁集生成算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法相比經(jīng)典Apriori算法執(zhí)行效率更高，所需資源更少。

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；頻繁集；多值屬性

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的重要研究方向。根據(jù)所挖掘數(shù)據(jù)集屬性的特點(diǎn)，這些數(shù)據(jù)集可以分成標(biāo)稱屬性、二元屬性、序數(shù)屬性及數(shù)值型屬性幾大類。對(duì)應(yīng)二元屬性數(shù)據(jù)集的關(guān)聯(lián)規(guī)則稱為布爾關(guān)聯(lián)規(guī)則。標(biāo)稱和序數(shù)屬性數(shù)據(jù)集對(duì)應(yīng)的關(guān)聯(lián)規(guī)則稱為多值屬性關(guān)聯(lián)規(guī)則。

Apriori算法是由Agrawal等人于1993年提出的針對(duì)單維的布爾關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘的方法［1］。該算法通過迭代逐步發(fā)現(xiàn)數(shù)據(jù)中的頻繁集，通過頻繁集來表示數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。

多值屬性的關(guān)聯(lián)規(guī)則最早由Srikant和Agrawal在1996年提出［2］，其主要思想是通過一定的量化規(guī)則將連續(xù)數(shù)值型屬性轉(zhuǎn)換為離散型的單維二元屬性后，再使用經(jīng)典的Apriori算法進(jìn)行挖掘。在多值屬性挖掘的應(yīng)用中，有些應(yīng)用針對(duì)某個(gè)屬性在一條記錄中的取值是唯一的，例如：在某次常規(guī)體檢中，某人的血壓只能是高、中、低三種情況中的任意一種，而不會(huì)同時(shí)是兩種或三種。

根據(jù)這些情況，本文提出了一種基于壓縮矩陣方式的Apriori改進(jìn)算法。此算法充分利用了多值屬性在一條事務(wù)上的取值是唯一的特點(diǎn)，通過構(gòu)造特殊的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和優(yōu)化的剪枝策略，提高算法執(zhí)行的效率。

1 關(guān)聯(lián)規(guī)則的基本概念

關(guān)聯(lián)規(guī)則挖掘的定義如下：設(shè)I=（I1，I2，…，In）是項(xiàng)目的集合，數(shù)據(jù)集（記為D）是數(shù)據(jù)庫(kù)事務(wù)集合，其中每一個(gè)事務(wù)T都是項(xiàng)的集合，且使T屬于I。關(guān)聯(lián)規(guī)則是形式為X=＞Y的蘊(yùn)含式（即如果X為真，則Y也為真），其中X和Y是項(xiàng)集，且X?I，Y?I，X∩Y=?。

項(xiàng)的集合稱為項(xiàng)集，包含k個(gè)項(xiàng)的項(xiàng)集稱為k項(xiàng)集。如果項(xiàng)集的出現(xiàn)頻率大于或等于最小頻度支持度與D中事務(wù)總數(shù)的乘積，則該項(xiàng)集滿足最小頻度支持度m。滿足最小頻度支持度的項(xiàng)集，稱為頻繁集。頻繁k項(xiàng)集的集合記為項(xiàng)集Lk。

數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則主要有兩個(gè)步驟：1）找出所有頻繁集；2）由頻繁集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則［3-4］。其中，1）是核心，決定挖掘關(guān)聯(lián)規(guī)則的總體性能。因此，本文主要針對(duì)1）進(jìn)行算法改進(jìn)。

多值屬性關(guān)聯(lián)規(guī)則挖掘算法的主要性質(zhì)［5-7］是：每條交易所包含的屬性數(shù)目相同，即每個(gè)交易的長(zhǎng)度相同，并且某一屬性的不同的屬性值不會(huì)出現(xiàn)在同一個(gè)頻繁屬性集中。

2 改進(jìn)算法

2.1 數(shù)據(jù)結(jié)構(gòu)

將屬性值轉(zhuǎn)換為等長(zhǎng)二進(jìn)制串，需構(gòu)建屬性值變換的哈希表H。哈希表中元素的鍵是連接屬性名和屬性值的字符串，元素的值是屬性值的新編碼。

定義矩陣S用來存儲(chǔ)數(shù)據(jù)庫(kù)中所有記錄項(xiàng)。若挖掘數(shù)據(jù)庫(kù)有M維，則S就有M列，其每行都表示數(shù)據(jù)庫(kù)中的一條記錄，每列表示記錄中的一維數(shù)據(jù)。S中每個(gè)元素對(duì)應(yīng)數(shù)據(jù)集中相應(yīng)行和列的屬性值。

定義行計(jì)數(shù)矩陣R，使S中的每行記錄在R中都有一個(gè)相應(yīng)的值，用來表示相同行在數(shù)據(jù)集中出現(xiàn)的次數(shù)。

定義列屬性計(jì)數(shù)矩陣C。C的內(nèi)容是S中列的屬性的所有取值在數(shù)據(jù)集中出現(xiàn)的次數(shù)。

2.2 算法流程

（1）掃描事務(wù)數(shù)據(jù)集D，對(duì)屬性值進(jìn)行變換，生成表H，同時(shí)構(gòu)建矩陣S。在掃描過程中對(duì)相同的事務(wù)進(jìn)行計(jì)數(shù)，把矩陣中相同的數(shù)據(jù)行壓縮成一行，并保證沒有重復(fù)值的行。建立用于表示行個(gè)數(shù)的數(shù)組M，數(shù)組下標(biāo)對(duì)應(yīng)的是數(shù)據(jù)行的順序，數(shù)組的值為數(shù)據(jù)行出現(xiàn)的次數(shù)。另外，建立列屬性計(jì)數(shù)矩陣C。

（2）遍歷屬性計(jì)數(shù)矩陣C，如果C中的某個(gè)值，即屬性取值在數(shù)據(jù)集中出現(xiàn)的次數(shù)不小于最小支持計(jì)數(shù)，則將此屬性值加入1階頻繁集。

（3）檢查矩陣S中每一列，如果某列的值都小于最小支持計(jì)數(shù)，則刪除此列。

（4）連接n-1階頻繁項(xiàng)生成n階頻繁候選集。遍歷矩陣S，將每個(gè)n-1階頻繁候選項(xiàng)都與S中每一對(duì)應(yīng)列做“邏輯與”操作。如果結(jié)果為“0”，則支持度加上行計(jì)數(shù)矩陣R相應(yīng)行的數(shù)目；如支持度大于最小頻度支持度，則此頻繁候選項(xiàng)是頻繁項(xiàng)。

（5）遍歷矩陣S，去除未包含m階頻繁項(xiàng)的行。

（6）重復(fù)步驟（3）和（5），直到某階頻繁項(xiàng)小于2或S行數(shù)小于最小支持計(jì)數(shù)時(shí)，算法終止，最終生成k階頻繁項(xiàng)。

2.3 算法改進(jìn)

相對(duì)于Apriori算法，本算法優(yōu)化部分如下。

（1）經(jīng)典的Apriori算法要多次掃描數(shù)據(jù)庫(kù)，性能低下。本算法只需掃描并讀取數(shù)據(jù)庫(kù)中的記錄一次，通過“屬性轉(zhuǎn)換為二進(jìn)值和對(duì)相同行計(jì)數(shù)”等壓縮方法，將用于挖掘的數(shù)據(jù)集轉(zhuǎn)換為內(nèi)存中的數(shù)據(jù)矩陣S，之后的所有掃描只針對(duì)數(shù)據(jù)矩陣S，從而有效地提高了運(yùn)行效率，節(jié)約了存儲(chǔ)空間。

（2）由n-1階頻繁項(xiàng)生成n階頻繁項(xiàng)時(shí)，使用優(yōu)化的剪枝策略是：1）n-1階頻繁項(xiàng)自身進(jìn)行組合得到n階頻繁項(xiàng)的候選集，判斷組合的合法性；2）遍歷S，增加一個(gè)變量用來保存已遍歷的矩陣行數(shù)。如果n-1階項(xiàng)頻繁次數(shù)-行數(shù)＜最小頻度支持度，則停止對(duì)矩陣的掃描，這是因?yàn)榫仃囍惺Ｓ嘈兄蓄l繁次數(shù)不可能大于最小頻度支持度。

（3）在生成頻繁項(xiàng)候選集時(shí)，經(jīng)典的Apriori算法是通過字符串比較來判斷矩陣的某一行是否包括頻繁項(xiàng)候選項(xiàng)的。本算法則是構(gòu)造二進(jìn)制串，將候選項(xiàng)二進(jìn)制串與矩陣S中每一行二進(jìn)制串進(jìn)行邏輯與運(yùn)算，如果結(jié)果是0，則表示該行中包括候選項(xiàng)。

3 實(shí)例分析

3.1 改進(jìn)算法示例

設(shè)某事務(wù)數(shù)據(jù)庫(kù)D中有10個(gè)事務(wù)，每個(gè)事務(wù)固定有5個(gè)屬性，如表1所示。其中屬性TⅠD表示事務(wù)的唯一編號(hào)，其他4個(gè)屬性每個(gè)屬性都有若干取值。

表1 多值屬性數(shù)據(jù)示例

假設(shè)最小頻度支持度m=30%，即最小支持計(jì)數(shù)為N=m×|D|=30%×10=3。

掃描事務(wù)數(shù)據(jù)庫(kù)D，對(duì)屬性值進(jìn)行變換生成H，H=｛“BMI.超重”：0000，“BMI.正?！保?001，“BMI.肥胖”：0010”“空腹血糖.受損”：0011，“空腹血糖.糖尿病”：0100，“空腹血糖.正?！保?101，“鍛煉.不鍛煉”：0110，“鍛煉.經(jīng)常”：0111，“鍛煉.很少”：1000”“脂肪肝.否”：1001，“脂肪肝.是”：1010｝，同時(shí)構(gòu)建表示矩陣S、R和C。第一遍掃描結(jié)束時(shí)，相應(yīng)的數(shù)據(jù)結(jié)構(gòu)內(nèi)容為

根據(jù)最小支持計(jì)數(shù)N，得到1階頻繁集｛0000，0001，0011，0111，0101，0111，1000，1001，1010｝。

由1階頻繁集生成2階頻繁集時(shí)，通過連接操作生成的2階頻繁候選項(xiàng)較多，且每個(gè)候選項(xiàng)都要掃描S，效率很低。本算法在此處進(jìn)行了優(yōu)化，思路是：在對(duì)2階頻繁候選項(xiàng)出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)時(shí)，增加一個(gè)計(jì)數(shù)器，記錄S中2階頻繁候選項(xiàng)出現(xiàn)的總個(gè)數(shù)t，如果此總個(gè)數(shù)滿足候選項(xiàng)分項(xiàng)支持度-t＜N，則此候選項(xiàng)分項(xiàng)的其他連接就不用再掃描。使用此優(yōu)化方法，掃描S的次數(shù)減少了，算法運(yùn)行速度提高了。例如：對(duì)于0000項(xiàng)，其2階頻繁候選項(xiàng)組合有｛0000，0011｝，｛0000，0100｝，…，｛0000，1010｝8項(xiàng)。如果不進(jìn)行優(yōu)化，則要8次掃描S；而通過算法優(yōu)化，只需掃描2次。第一次掃描，組合｛0000，0011｝出現(xiàn)次數(shù)為1次，組合｛0000，0100｝出現(xiàn)次數(shù)為3次。1階頻繁項(xiàng)“0000”共出現(xiàn)了5次，而其他包含“0000”的組合項(xiàng)最多只有5-1-3=1次，小于N，不包含“0000”項(xiàng)的2階頻繁候選項(xiàng)一定不會(huì)是2階頻繁集，關(guān)于“0000”項(xiàng)的2階頻繁集搜索結(jié)束。對(duì)于本例，2階頻繁集最終是｛（0000，1001，4），（0000，0100，3），（0000，0111，3），（1001，0100，3），（1001，0001，3），（1001，0101，3），（1001，1000，4），（0001，1000，3）｝。

根據(jù)2階頻繁集，掃描矩陣S，去除在2階頻繁集中不存在的屬性，然后連接2階頻繁項(xiàng)得到3階頻繁候選項(xiàng)集，掃描矩陣S，最后得到3階頻繁集｛（1001，0001，1000，3）｝。

根據(jù)2.2中的步驟（6），由于3階頻繁項(xiàng)個(gè)數(shù)為1，小于2，滿足算法終止條件，算法結(jié)束。

3.2 性能比較

改進(jìn)算法與基本的多值A(chǔ)priori算法的性能比較如下。

實(shí)驗(yàn)條件：雙核筆記本計(jì)算機(jī)，主頻2.1 GHz，內(nèi)存4 GB，操作系統(tǒng)為Win7 64位；編程語(yǔ)言為C#；測(cè)試數(shù)據(jù)為某醫(yī)院健康體檢數(shù)據(jù)，共有9個(gè)屬性，每個(gè)屬性有3～5個(gè)屬性值；最小頻度支持度為10%；數(shù)據(jù)量從1 000條增加到100 000條。運(yùn)行結(jié)果如圖1所示。

由圖1可見，由于在連接時(shí)和剪枝時(shí)進(jìn)行了優(yōu)化，隨著數(shù)據(jù)量增大，效果愈加明顯，改進(jìn)算法的性能優(yōu)于基本的Apriori算法。

圖1 運(yùn)行時(shí)間和數(shù)據(jù)量關(guān)系

圖2是在不同的最小頻度支持度下，對(duì)50 000條記錄進(jìn)行處理后的Apriori算法和改進(jìn)算法的性能比較。從圖2可以看出，在最小頻度支持度比較小時(shí)，改進(jìn)算法的性能遠(yuǎn)遠(yuǎn)優(yōu)于Apriori算法。

圖2 運(yùn)行時(shí)間和最小頻度支持度關(guān)系

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

針對(duì)多維多值關(guān)聯(lián)規(guī)則的Apriori算法執(zhí)行效率較低和存儲(chǔ)空間較大的缺點(diǎn)，提出了基于壓縮矩陣和相應(yīng)的頻繁集的改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)算法減少了數(shù)據(jù)存儲(chǔ)和搜索所需的空間，性能相對(duì)于經(jīng)典Apriori算法有顯著的提高。

［1］AGRAWALR，IMIELINSKIT，SWAMIA.Mining Association Rules Between Sets ofItems in Large Databases［J］.ACM SIGMOD Record，1993，22（2）：207-216.

［2］陳文.基于位矩陣的加權(quán)頻繁k項(xiàng)集生成算法［J］.計(jì)算機(jī)工程，2010（5）：54-56.

［3］崔貫勛，李梁，王柯柯，等.基于改進(jìn)Apriori算法的入侵檢測(cè)系統(tǒng)研究［J］.計(jì)算機(jī)工程與科學(xué)，2011（4）：40-44.

［4］姜麗莉，孟凡榮，周勇，等.多值屬性關(guān)聯(lián)規(guī)則挖掘的QApriori算法［J］.計(jì)算機(jī)工程，2011（9）：81-83.

［5］付沙，周骯軍.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)［J］.微電子學(xué)與計(jì)算機(jī)，2013（9）：110-114.

［6］張?jiān)茲?，于治樓，張化?關(guān)聯(lián)規(guī)則中頻繁集高效挖掘的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011（3）：139-141.

［7］李曉虹，尚晉.一種改進(jìn)的新Apriori算法［J］.計(jì)算機(jī)科學(xué)，2007（4）：196-198.

【責(zé)任編輯 梅欣麗】

An Improved Algorithm of Quantitative Association Rules Based on Compressed Matrix

WANG Fengkun，ZHANG Tingting
（Information Engineering Department，Anhui Technical College of Mechanical and Electrical Engineering，Wuhu 241000，China）

Aiming at the problem of low efficiency of mining quantitative association rules with the classical apriori algorithm，an improved algorithm was proposed.The improved algorithm compressed data by using binary encoding of attribute values，adding rows and attribute value counters.A new algorithm for generating frequent itemsets was used for the compressed matrix.Experimental results showed that the improved algorithm was more efficient and less spaced than the classical apriori algorithm.

data mining；quantitative association rules；frequent itemsets

TP301.6

A

2095-7726（2015）12-0033-04

2015-09-01

安徽省高校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目（KJ2014A038）

汪峰坤（1978-），男，安徽霍邱人，講師，碩士，研究方向：數(shù)據(jù)挖掘和大數(shù)據(jù)處理。