易 黎 胡雅萌,2 彭艷兵

1(南京烽火軟件科技有限公司 江蘇 南京 210019) 2(武漢郵電科學(xué)研究院 湖北 武漢 430074)

探索關(guān)聯(lián)規(guī)則可視化的結(jié)構(gòu)化關(guān)聯(lián)映射圖

易 黎1胡雅萌1,2彭艷兵1

1(南京烽火軟件科技有限公司 江蘇 南京 210019)2(武漢郵電科學(xué)研究院 湖北 武漢 430074)

對(duì)于大量的高維度的交易數(shù)據(jù)，利用關(guān)聯(lián)規(guī)則進(jìn)行數(shù)據(jù)挖掘，用戶難以進(jìn)行解釋和利用。主要兩個(gè)原因：常規(guī)關(guān)聯(lián)規(guī)則挖掘算法可產(chǎn)生大量關(guān)聯(lián)規(guī)則；一些關(guān)聯(lián)規(guī)則可部分重疊。若用戶能自主選擇，在關(guān)聯(lián)規(guī)則挖掘中所使用的相關(guān)項(xiàng)集，則可解決該問題。提出一種新的視覺探索工具，結(jié)構(gòu)化關(guān)聯(lián)映射圖，使用戶能夠以視覺方式找到相關(guān)項(xiàng)集的組。該方法使用健康檢查結(jié)果數(shù)據(jù)集進(jìn)行驗(yàn)證，并且實(shí)驗(yàn)結(jié)果表明具有最高2×2規(guī)則貢獻(xiàn)的和值的結(jié)構(gòu)化關(guān)聯(lián)映射圖有助于顯著減少關(guān)聯(lián)分析的復(fù)雜性，并且能夠集中于搜索空間的特定區(qū)域關(guān)聯(lián)規(guī)則挖掘，同時(shí)避免不相關(guān)的關(guān)聯(lián)規(guī)則。

可視化 關(guān)聯(lián)規(guī)則挖掘 分層聚類 結(jié)構(gòu)化關(guān)聯(lián)映射圖

0 引 言

隨著生活水平的提高，預(yù)防保健成為公眾關(guān)注的焦點(diǎn)，Boulware等[1]認(rèn)為大眾健康檢查(MHE)在監(jiān)測(cè)和評(píng)估個(gè)人健康水平方面發(fā)揮了重要作用，Kweon等[2]也提到MHE結(jié)果數(shù)據(jù)為在國(guó)家和個(gè)人層面制定衛(wèi)生政策或戰(zhàn)略提供了堅(jiān)實(shí)的基礎(chǔ)。邊根慶等[3]表明了數(shù)據(jù)挖掘能為我們提供有價(jià)值的重要信息或知識(shí)，從而產(chǎn)生不可估計(jì)的經(jīng)濟(jì)效益。李春青[4]認(rèn)為關(guān)聯(lián)規(guī)則算法是數(shù)據(jù)挖掘算法中重要的分析方法，能夠挖掘數(shù)據(jù)中各項(xiàng)關(guān)聯(lián)。然而，分析從大眾健康檢查收集來的數(shù)據(jù)集相當(dāng)困難，因?yàn)樗鼈儼ㄔS多相關(guān)變量，探索高維交易數(shù)據(jù)內(nèi)的關(guān)聯(lián)規(guī)則時(shí)，數(shù)據(jù)過于復(fù)雜抽象，因而難以被直觀的展示出來。

肖晗等[5]提出通過數(shù)據(jù)挖掘產(chǎn)生的關(guān)聯(lián)規(guī)則會(huì)存在大量無用和不感興趣的規(guī)則，同時(shí)劉曉蔚[6]提到傳統(tǒng)的類關(guān)聯(lián)規(guī)則挖掘算法在挖掘完整的規(guī)則數(shù)據(jù)集時(shí)往往需要消耗很長(zhǎng)的時(shí)間。此外，Yang[7]提到關(guān)聯(lián)規(guī)則的前提和后果是在所有項(xiàng)的集合的冪集上定義的，并且它們項(xiàng)之間表現(xiàn)出了多對(duì)多的關(guān)系。而Ferreira等[8]提出可視化技術(shù)可以處理大量而復(fù)雜的規(guī)則。

用于表示大量關(guān)聯(lián)規(guī)則的最常見和簡(jiǎn)單的方法是表格。由于其簡(jiǎn)單性，基于表格的視圖用于許多常規(guī)數(shù)據(jù)挖掘軟件中，并且這種表格中的規(guī)則通常通過諸如置信度或提升的興趣度度量排序。然而，Sekhavat等[9]提出若發(fā)現(xiàn)太多關(guān)聯(lián)規(guī)則，分析器在解釋列表和從表中找到有趣的規(guī)則仍有困難。

本文介紹了一種稱為結(jié)構(gòu)化關(guān)聯(lián)圖的新型可視化方法，是關(guān)聯(lián)規(guī)則集合簇?zé)釄D的變體，用于總結(jié)高維交易數(shù)據(jù)中二元變量之間的關(guān)系。所提出的方法基于關(guān)聯(lián)規(guī)則挖掘和聚類分析的常規(guī)數(shù)據(jù)挖掘技術(shù)，并且其使得用戶能夠容易地找到由一組相關(guān)聯(lián)的二進(jìn)制變量形成的感興趣區(qū)域，這個(gè)區(qū)域可構(gòu)成感興趣的許多關(guān)聯(lián)規(guī)則。由于結(jié)構(gòu)化關(guān)聯(lián)映射圖是基于矩陣的方法，它很容易實(shí)現(xiàn)和解釋。與基于經(jīng)典矩陣的技術(shù)相比，結(jié)構(gòu)化關(guān)聯(lián)映射圖更適合于解釋給定項(xiàng)集間的多對(duì)多關(guān)系。

1 研究方法

1.1 挖掘過程

圖1 基于結(jié)構(gòu)化關(guān)聯(lián)映射圖的關(guān)聯(lián)規(guī)則挖掘過程

圖1描述了基于結(jié)構(gòu)化關(guān)聯(lián)映射圖的關(guān)聯(lián)規(guī)則挖掘過程，上半部分描述其構(gòu)建階段，下半部分總結(jié)其利用階段。在構(gòu)建階段，矩陣與以不同方式構(gòu)造的兩個(gè)樹形圖組合，獲得結(jié)構(gòu)化關(guān)聯(lián)映射圖。創(chuàng)建后，結(jié)構(gòu)化關(guān)聯(lián)映射圖用于可視化識(shí)別感興趣的區(qū)域和組，感興趣組由關(guān)聯(lián)規(guī)則挖掘算法探索。

1.2 行項(xiàng)集(因素項(xiàng))分析

行項(xiàng)集分析的目的是通過對(duì)因子項(xiàng)應(yīng)用層次聚類算法來生成因子項(xiàng)樹形圖。Michael等[10]提出式(1)中的親和度是兩個(gè)項(xiàng)集a和b的相似性度量，而式(2)中的Jaccard距離可以用于測(cè)量它們之間的距離，其中sup(X)表示項(xiàng)集集合X。在本文中，式(2)中的距離度量用于生成因子項(xiàng)集樹形圖。

(1)

Jd(a,b)=1-A(a,b)

(2)

DF因子項(xiàng)的平方距離矩陣可如式(3)獲得，其中mf是因子項(xiàng)的數(shù)量，并且dfij=Jd(Fi，F(xiàn)j)，F(xiàn)i和Fj為因子項(xiàng)集。 注意，如果i=j且dfij=dfji，則dfij=0。

(3)

在本文中，凝聚層次聚類算法應(yīng)用于距離矩陣DF，以生成樹形圖。聚集聚類算法需要確定兩個(gè)聚類(項(xiàng)集)之間的距離的鏈接標(biāo)準(zhǔn)。Tan等[11]提出常用的鏈接標(biāo)準(zhǔn)是單鏈(SL)、完全鏈(CL)、平均鏈(AL)和Ward’s標(biāo)準(zhǔn)(WC)。本文通過對(duì)比四種標(biāo)準(zhǔn)，找出最優(yōu)值。而用于對(duì)樹形圖的子樹進(jìn)行排序的方法使用基于支持度量(OM)，這是一個(gè)簡(jiǎn)單的自上而下排序方法，從最高合并點(diǎn)開始。在每個(gè)合并點(diǎn)，此方法查找哪個(gè)子樹具有支持最高的項(xiàng)集，并將其放在樹形圖的左側(cè)(上側(cè))。

1.3 列項(xiàng)(響應(yīng)項(xiàng))分析

通過層次聚類算法獲得響應(yīng)項(xiàng)DR的距離矩陣，來生成響應(yīng)項(xiàng)樹形圖。

在本文中，響應(yīng)項(xiàng)Rj的定義如下：

PF(Rj)=[L1j,L2j,…,Lmj j]

(4)

式中：Lij是Fi對(duì)Rj的影響。規(guī)則“{Fi}→{Rj}”的興趣度量用Lij表示，并且本文通過使用升力測(cè)量來計(jì)算Lij如下：

(5)

考慮因子項(xiàng)的影響的分布，Rj和Rk之間的距離drjk計(jì)算如下：

(6)

式中：PF(Rj)·PF(Rk)是兩個(gè)輪廓向量PF(Rj)和PF(Rk)的內(nèi)積，|PF(Rj)| 是PF(Rj)的長(zhǎng)度。

1.4 結(jié)構(gòu)化關(guān)聯(lián)映射圖的評(píng)價(jià)

本文引用一種基于興趣的評(píng)估方法，即2×2規(guī)則貢獻(xiàn)的和，由“相鄰”項(xiàng)組成的概念。

如下計(jì)算2×2規(guī)則貢獻(xiàn)的和測(cè)量：

(7)

式中：CN({F(i)，F(xiàn)(i + 1)}→{R(j)，R(j + 1)})是{F(i)，F(xiàn)(i + 1)}→{R(j)，R(j + 1)}的規(guī)則。 如果先導(dǎo)和后繼項(xiàng)集都連接到縮減的結(jié)構(gòu)化關(guān)聯(lián)映射圖的樹形圖中，則該規(guī)則被關(guān)閉，并且其貢獻(xiàn)計(jì)算如下：

CN(closedrule)=LIFT(closedrule)

(8)

式 (8)中的CN(closedrule)表示閉合規(guī)則應(yīng)當(dāng)具有高興趣度值，因此分析器傾向于期望它們是有趣的規(guī)則。

如果在縮減結(jié)構(gòu)化關(guān)聯(lián)映射圖的樹形圖中既沒有連接先導(dǎo)項(xiàng)也沒有連接后繼項(xiàng)，則打開關(guān)聯(lián)規(guī)則，并且如下獲得其貢獻(xiàn)：

CN(openedrule)=

(9)

式(9)中的CN(openedrule)意味著打開的規(guī)則具有低興趣度值。因此，打開的規(guī)則的貢獻(xiàn)是其升力的倒數(shù)，如果它具有正升力值。如果打開規(guī)則的提升為0，則規(guī)則的貢獻(xiàn)被設(shè)置為任意值M，并且本文中M=1。

1.5 結(jié)構(gòu)化關(guān)聯(lián)映射圖利用率

結(jié)構(gòu)化關(guān)聯(lián)映射圖用于可視化探索給定事務(wù)數(shù)據(jù)內(nèi)的二進(jìn)制變量之間的關(guān)系。并且，結(jié)構(gòu)化關(guān)聯(lián)映射圖通過應(yīng)用關(guān)聯(lián)規(guī)則挖掘算法幫助用戶更深入地找到要研究的感興趣區(qū)域。

設(shè)S(a，b，p，q)表示由代表F(a)，F(xiàn)(a + 1)，…，F(xiàn)(a + p-1)的行和代表R(b)、R(b + 1)、R(b + q-1)的列，當(dāng)p,q≥2時(shí)，組成的結(jié)構(gòu)化關(guān)聯(lián)映射圖的p×q子矩陣。如果滿足以下兩個(gè)條件，則將S(a，b，p，q)稱為感興趣區(qū)域：

(1)S(a，b，p，q)中的幾乎所有eijs指示F(i)和R(j)之間的正相關(guān)，或eijs指示F(i)和R(j)之間的負(fù)相關(guān)(a≤i≤a+p-1，b≤j≤b+q-1)。

(2)F(a)，F(xiàn)(a + 1)，…，F(xiàn)(a + p-1)在要素項(xiàng)集樹形圖中以較低的級(jí)別合并，且R(b)、R(b + 1)、R(b + q-1)在響應(yīng)項(xiàng)樹形圖中的較低級(jí)合并。

如果S(a，b，p，q)是感興趣區(qū)域，則與該子矩陣G(a，b，p，q)相關(guān)的項(xiàng)集合被稱為感興趣組。

G(a,b,p,q)= {F(a),F(a+1),…,F(a+p-1)}∪

{R(b),R(b+1),…,R(b+q-1)}

(10)

2 應(yīng)用實(shí)例

2.1 大眾健康檢查結(jié)果數(shù)據(jù)集

原始數(shù)據(jù)從韓國(guó)278個(gè)青少年的大眾健康檢查收集。其中，兩類變量表示受試者的身體狀況或病史，由專職醫(yī)務(wù)人員檢查。其他類別中的變量表示主觀癥狀和個(gè)人生活方式，基于受試者對(duì)感知健康狀況的陳述。圖2為大眾健康檢查結(jié)果數(shù)據(jù)集的項(xiàng)集分類。

圖2 大眾健康檢查結(jié)果數(shù)據(jù)集的項(xiàng)集分類

通過使用結(jié)構(gòu)化關(guān)聯(lián)映射圖來探尋個(gè)人牙齒健康可視化變量之間的關(guān)系。本文選擇生活方式變量作為因子項(xiàng)，主觀癥狀和牙科疾病變量作為響應(yīng)項(xiàng)，分析形式“{Ilife}→{Isymptom∪Idisease}”的關(guān)聯(lián)規(guī)則。

2.2 結(jié) 論

一旦項(xiàng)集被分類，下一步是生成因子項(xiàng)集樹形圖。為此，凝聚層次聚類算法應(yīng)用于因子項(xiàng)的距離矩陣DF，通過使用式(2)獲得。

然后，我們可以通過使用式(4)-式(6)生成響應(yīng)項(xiàng)，并且這些響應(yīng)項(xiàng)用于計(jì)算響應(yīng)項(xiàng)DR的距離矩陣。同樣，響應(yīng)項(xiàng)樹形圖通過應(yīng)用層次聚類算法獲得。

由于我們有4個(gè)因素項(xiàng)集樹狀圖和相同數(shù)量的響應(yīng)項(xiàng)集樹狀圖，可以構(gòu)造4個(gè)不同的結(jié)構(gòu)化關(guān)聯(lián)映射圖?？梢酝ㄟ^使用式(8)-式(10)中描述的2×2規(guī)則貢獻(xiàn)的和測(cè)量來評(píng)價(jià)它們的性能，評(píng)價(jià)結(jié)果總結(jié)在表1中。在表1中，每行指示因子項(xiàng)集樹形圖的排序方法和鏈接標(biāo)準(zhǔn)，而每一列指定響應(yīng)項(xiàng)集樹形圖的排序方法和鏈接標(biāo)準(zhǔn)。

表1 不同結(jié)構(gòu)化關(guān)聯(lián)映射的2×2規(guī)則貢獻(xiàn)的和值

圖3 2×2規(guī)則貢獻(xiàn)的和值的分布

圖4 結(jié)構(gòu)化關(guān)聯(lián)映射圖與最高2×2規(guī)則貢獻(xiàn)的和(結(jié)構(gòu)化關(guān)聯(lián)映射圖與OM-WCOM-AL)

表1的第i行和第j列中的元素表示通過組合第i個(gè)因子項(xiàng)集樹形圖和第j個(gè)響應(yīng)項(xiàng)集樹形圖構(gòu)建的結(jié)構(gòu)化關(guān)聯(lián)映射圖的2×2規(guī)則貢獻(xiàn)的和值，并且可以看出結(jié)構(gòu)化關(guān)聯(lián)映射圖的性能根據(jù)組合樹形圖的結(jié)構(gòu)而顯著變化，如圖3所示。在表1中列出的16個(gè)不同的結(jié)構(gòu)化關(guān)聯(lián)映射圖中，我們必須選擇具有WC/AL的結(jié)構(gòu)化關(guān)聯(lián)映射圖(因子項(xiàng)集樹形圖結(jié)構(gòu)/響應(yīng)項(xiàng)集樹狀圖結(jié)構(gòu))，因?yàn)樗?×2規(guī)則貢獻(xiàn)的和測(cè)量的值最大化。因此，我們可以獲得如圖4所示的優(yōu)化的結(jié)構(gòu)化關(guān)聯(lián)映射圖。其中每個(gè)方塊eij根據(jù)關(guān)聯(lián)規(guī)則“{F(i)}→{R(j)}”的提升值被著色，如下：① 方塊內(nèi)含三角指示升力值高于1(正相關(guān))，而普通方塊意味著升力值低于1(負(fù)相關(guān))。② 較深色的瓷磚表示較強(qiáng)的相關(guān)性，無色瓷磚表示升力值約為1(F(i)和R(j)之間的周相關(guān)性)。

3 結(jié) 語

本文提出了一種稱為結(jié)構(gòu)化關(guān)聯(lián)映射圖的新型可視化方法，精心設(shè)計(jì)來表示大型交易數(shù)據(jù)中項(xiàng)集之間的復(fù)雜關(guān)系。其與經(jīng)典簇?zé)釄D相似，因?yàn)榫仃嚺c兩個(gè)樹形圖組合。然而，結(jié)構(gòu)化關(guān)聯(lián)映射的樹形圖以更復(fù)雜的方式構(gòu)建，以避免對(duì)多對(duì)多關(guān)聯(lián)規(guī)則的誤解。優(yōu)化了之前工作中引入的結(jié)構(gòu)化關(guān)聯(lián)映射的抽象概念，并開發(fā)了構(gòu)建優(yōu)化其詳細(xì)概念和增強(qiáng)的過程。

[1] Boulware L E,Barnes G J,Wilson R F,et al.Value of the periodic health evaluation[J].Evidence Report/technology Assessment,2006(136):1.

[2] Kweon S,Kim Y,Jang M J,et al.Data resource profile:the Korea National Health and Nutrition Examination Survey (KNHANES)[J].International Journal of Epidemiology,2014,43(1):69-77.

[3] 邊根慶,王月.一種基于矩陣和權(quán)重改進(jìn)的Apriori算法[J].微電子學(xué)與計(jì)算機(jī),2017,34(1):136-140.

[4] 李春青.基于關(guān)聯(lián)規(guī)則算法的數(shù)據(jù)挖掘研究[J].軟件導(dǎo)刊,2017,16(2):147-149.

[5] 肖晗,黃誠(chéng).基于量化關(guān)聯(lián)規(guī)則的敏感性分析[J].計(jì)算機(jī)應(yīng)用,2017,37(S1):1-6.

[6] 劉曉蔚.基于等價(jià)類規(guī)則樹的高效關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(1):313-319.

[7] Yang L.Pruning and visualizing generalized association rules in parallel coordinates[J].IEEE Transactions on Knowledge & Data Engineering,2005,17(1):60-70.

[8] Ferreira d O M C,Levkowitz H.From visual data exploration to visual data mining:a survey[J].Visualization & Computer Graphics IEEE Transactions on,2003,9(3):378-394.

[9] Sekhavat Y A,Hoeber O.Visualizing Association Rules Using Linked Matrix,Graph,and Detail Views[J].International Journal of Intelligence Science,2013,3(1):34-49.

[10] Hahsler M,Buchta C,Gruen B,et al.Mining Association Rules and Frequent Itemsets[EB/OL].2017.https://cran.r-project.org/web/packages/arules/arules.pdf.

[11] Tan P N,Steinbach M,Kumar V.Introduction to Data Mining,(First Edition)[M].Addison-Wesley Longman Publishing Co.Inc.2005.

EXPLORINGSTRUCTUREDASSOCIATIONMAPOFASSOCIATIONRULESVISUALIZATION

Yi Li1Hu Yameng1,2Peng Yanbing1

1(FiberHomeStarrySkyCo.,Ltd.,Nanjing210019,Jiangsu,China)2(WuhanResearchInstituteofPostsandTelecommunications,Wuhan430074,Hubei,China)

The users often face difficulties in interpreting and exploiting the association rules extracted from large transaction data with high dimensionality. There are two main reasons. Firstly, too many association rules can be produced by the conventional association rule mining algorithms, and secondly, some association rules can be partly overlapped. This problem can be solved if the users can select the relevant items to be used in association rule mining. In this context, this paper aims to propose a new visual exploration tool, structured association map, which enables the users to find the group of the relevant items in a visual way. For illustration, this procedure is applied to a mass health examination result data set, and the experiment results demonstrate that structured association map with maximum sums of 2×2 regular contributions value helps to reduce the complexities of association analysis significantly and it enables to focus on the specific region of the search space of association rule mining while avoiding the irrelevant association rules.

Visualization Association rule mining Hierarchical clustering Structured association mapping

2017-05-15。易黎，工程師，主研領(lǐng)域：大數(shù)據(jù)分析。胡雅萌，碩士生。彭艷兵，教授級(jí)高級(jí)工程師。

TP391.4

A

10.3969/j.issn.1000-386x.2017.12.013