高維數據組合關聯關系挖掘方法

姜建武, 王博

(1.桂林理工大學測繪地理信息學院，桂林 541004；2.生態時空大數據感知服務重點實驗室，桂林 541004)

關聯規則挖掘(association rule mining,ARM)是數據挖掘的主要任務之一[1]，也是數據挖掘領域最重要、最活躍的研究領域[2]。其中，提高挖掘效率和降低挖掘結果的冗余度是其需要解決的兩個核心問題[3-7]。圍繞以上問題，廣大學者開展了一系列研究。曾子賢等[8]基于Apriori算法提出了改進的MIFP-Apriori(matrix improved frequent pattern-Apriori)算法，從矩陣、改進頻繁模式樹和計算候選集頻數優化策略3個方面入手，解決Apriori算法挖掘效率低，候選集冗余的問題。Rathee等[9]提出了一種基于Spark平臺的分布式關聯規則挖掘算法Adaptive-Miner，該算法是一種動態關聯規則挖掘算法，可以實現對海量事務的關聯規則挖掘。Czibula等[10]提出了一種關系規則挖掘算法CRAR(concurrent relational association rule mining)，通過采用并發技術降低挖掘時間。Yan等[11]提出了一種用于定量關聯規則挖掘的并行粒子群優化(particle swarm optimization,PSO)算法，提供面向粒子和數據兩種不同的并行挖掘方式，并通過實驗驗證了該方法在大型事務數據集中挖掘中更具通用性。楊媛等[12]針對傳統數據挖掘效率低、耗時的問題，提出了一種新的多層次分布式網絡數據挖掘改進方法,并給出了多層次分布式網絡結構。Chiclana等[13]設計了一種新的基于動物遷移優化的挖掘算法ARM-AMO(association rule mining-n animal migration optimization)以減少關聯規則的數量，其原理是從數據中刪除支持度不高且不必要的規則，具體實現是在頻繁規則挖掘時添加適應度函數，用以減少相關模式的生成。Harikumar等[14]通過對Apriori算法進行改進，達到在高維、海量數據上高效挖掘的目的，且能夠從高維數據中找出只與重要屬性相關的關聯規則。現有的關聯規則挖掘算法依賴于基于頻率的規則評估方法[15]，如支持度和置信度[16]，無法為規則評估提供良好的統計或計算方法，并且經常存在大量冗余規則[17-20]。針對該問題，Song等[21]提出了一種基于交叉驗證的可預測性集合類關聯規則挖掘方法，通過實驗驗證，該方法在挖掘到大量有用規則的同時，性能優于現有的一些算法。王京等[22]提出了一種基于相互關聯規則的KAFP-Growth(key attributes frequent pattern growth)算法，通過在FP-Growth(frequent pattern growth)算法的基礎上引入重要屬性概念對挖掘算法進行改進，減少了頻繁項集，提高了計算性能。楊嵐雁等[23]針對MLKNN(multi-label k-nearest neighbor)算法忽略現實世界中標簽之間的相關性問題，基于FP-Growth挖掘標簽之間的相關性進而改進MLKNN算法。廖孟柯等[24]針對傳統Apriori算法時間復雜度高、計算效率低的問題，提出一種基于三維矩陣的Apriori優化算法，通過建立三維矩陣和簡約數據庫的方式較少計算冗余，提升關聯規則的挖掘效率。

但是，以上研究在提升高維數據的挖掘效率和降低規則的冗余度方面還存在一些不足。為解決該問題，提出一種適用于高維數據的組合關聯關系挖掘算法(mining multidimensional association rules by combination, Marc)，在挖掘之初實現對樣本數據的篩選，降低弱樣本的干擾，提升關聯規則挖掘的聚焦度。通過引入數據整體分布的概念，計算分布系數和刪除閾值，增加數據篩選過程，并構建樣本關系表，聯合用戶設置的最小支持度和最小置信度共同對數據進行挖掘。通過構建Marc算法，為海量、高維數據的高效挖掘提供一種新方法。

1 Marc算法原理

Marc算法主要解決高維數據的挖掘問題，與常規算法不同，Marc算法的優點如下。

(1)初讀數據時增加二次篩選，降低弱樣本影響。對原始樣本進行篩選是提升挖掘效率的關鍵步驟[25]。Marc算法引入樣本集分布系數和刪除閾值兩個指標，在數據初次讀取時，根據樣本的分布情況對初始樣本增加二次篩選，保留樣本的出現頻數必須同時滿足大于最小支持度和刪除閾值，該步驟有利于減少弱頻繁項和弱關聯規則的數量，從而提升數據挖掘的效率，降低規則的冗余度。

(2)根據樣本關系表重構樣本組合，降低算法復雜度，提升挖掘效率。與常規關聯規則挖掘算法的挖掘方式不同，Marc算法通過構建樣本關系表，然后根據該關系表對樣本集里的樣本進行全排列組合，從而將樣本間的關聯關系轉換為關系組合，再對組合后的樣本進行挖掘進而獲得關聯規則。經實驗驗證，相較于對比算法，Marc算法在處理高維數據挖掘時占用內存更小，挖掘的復雜度更低，挖掘效率更高。

1.1 算法相關指標

(1)設項集x=[x1,x2,…,xp]代表一組項，I=[I1,I2,…,Im]是一個事務數據集，I中的每個Ii(i∈[1，2，…，m])是包含x中項的一組事務。A和B表示包含x中項的兩個模式。

(2)Supp(支持度)表示同時包含A和B的事務占所有事務的比例，可表示為

(1)

(3)Conf(置信度)表示使用包含A的事務中同時包含B事務的比例，即同時包含A和B的事務占包含A事務的比例，可表示為

(2)

(4)Dist(分布系數)用于標定樣本的離散程度，Marc算法的分布系數采用SigMod對樣本的方差或標準差規劃獲得。

(3)

式(3)中：k為樣本的方差或標準差，具體選用根據實際需要確定。

(5)Trim(刪除閾值)由分布系數Dist與樣本均值E的乘積得到，主要用于去除樣本中的弱頻繁項。

Trim=DistE

(4)

1.2 算法步驟

Marc算法的核心思想是在數據篩選時加入數據整體分布的考量，并構建樣本間的關系表，以該關系表為基礎對樣本數據重新組合，挖掘頻繁項和關聯關系。Marc算法的挖掘流程如圖1所示。

圖1中主要包括樣本二次篩選、樣本頻次統計及排序、樣本關系表生成、樣本全排列組合以及頻繁項和關聯關系生成5個步驟，具體如下。

圖1 Marc算法流程圖

步驟1讀取數據統計樣本頻次，根據最小支持度和計算出的刪除閾值對原始數據集進行篩選，并按照樣本頻次對數據集降序排列，該步驟可以提升因支持度設置不合理引起的挖掘結果冗余。

步驟2對排序后的數據集進行掃描，記錄單個樣本以及單個樣本出現的次數形成樣本頻數集合，接著，將樣本頻數集合里的樣本兩兩組合，分別統計樣本組合的出現次數，將小于最小支持度的樣本組合刪除，形成樣本組合頻數集。

步驟3根據樣本組合頻數集生成樣本關系表。

步驟4掃描第一步生成的排序后數據集，根據樣本關系表將樣本重新全排列組合，形成新的樣本數據集。

步驟5掃描步驟4的數據集，統計組合樣本的頻次，計算組合樣本的支持度和置信度，生成頻繁項和頻繁模式。

Marc算法的詳細步驟如下。

步驟1設定最小支持度為min_support，最小置信度為min_confidence，為便于后續對算法計算過程進行闡述，對2.1節項集x和事務集I做式(5)、式(6)修改。

I=[I1,I2,I3,…,Im]T

(5)

Ii=[xi1,xi2,…,xij]

(6)

式中：1≤i≤m；1≤j≤p。

如式(5)、式(6)所示，將事務數據集I變換為m行p列的數組，Ii中的xij為事務數據集I中第i行的第j個項，xij∈x。

步驟2遍歷樣本集合I，計算樣本集合內每一個樣本xij的頻數Nij(即該樣本在樣本集中的出現次數)，設樣本總數為M。

(7)

(8)

式中：Nij為x中的某個項在事務數據集I中出現的次數；M為x中所有項在事務數據庫I中出現次數之和；Count()為統計函數。

統計每個項出現次數的目的是為了計算后面的分布系數和刪除閾值，去除弱樣本的影響。

如圖2所示，統計事務數據集中每個樣本的出現次數并進行降序排列。

圖2 樣本頻數統計并排序

步驟3計算樣本頻數的平均值E、方差σ2及標準差S，計算公式分別為

(9)

(10)

(11)

步驟4計算分布系數Dist。采用SigMod函數對標準差或者方差進行規劃，計算公式為

(12)

式(12)中：Index∈(S,σ2)。

由于方差和標準差反映了樣本的離散程度，因此可以以此為指標對原始樣本進行篩選，通過SigMod進行規劃的目的是將該樣本的離散度規劃為[0,1]，這樣在求解刪除閾值時更加方便。具體選用何種指標計算分布系數，可根據實際情況確定。需要注意的是，由于SigMod的變量取值范圍較小，如圖3所示，當變量值小于-6或者大于6時其結果都非常接近1，因此為了更好地篩選樣本，當樣本方差較大時，建議選擇方差，當樣本方差較小時選擇標準差。

圖3 SigMod函數變化曲線

步驟5計算刪除閾值Trim，將樣本集合中所有Nij小于Trim的樣本刪除，得到新的樣本集合I′。

Trim=EDist

(13)

步驟6遍歷樣本集合I′，計算樣本內每一個樣本xij的出現次數N′ij，形成樣本頻數集Samples，設不同樣本xij的總數為M′，由于刪除了一些樣本數據，因此此時的樣本數和維度均小于或等于原樣本數和維度，新的樣本數記為m′，維度記為p′。

(14)

式(14)中：1≤i≤m′；1≤j≤p′。

(15)

Samples=[{s1:c1},{s2:c2},…,{si:ci}]

(16)

式(16)中：si為第i個樣本；ci為第i個樣本的頻數，1≤i≤p′。

步驟7將Samples集合中的樣本進行兩兩組合形成新的集合，記為S′amples，并統計組合樣本在集合I′中共同出現的頻數，將頻數小于最小支持度的樣本組合刪除。

S′amples=[{si1:ci1},{si2:ci2},…,{sij:cij}]

(17)

式(17)中：sij為第i個樣本與第j個樣本組合；cij為第i個樣本與第j個樣本共同出現的頻數，1≤i≤p′,1≤j≤p′,i≠j。

步驟8根據S′amples集合，生成樣本關系表Relations，具體生成方法是以組合樣本中某一個樣本為基礎，找出所有與之相關的樣本即在S′amples集合中存在，可表示為

Relations={s1:[s2,s3,…,si],s2:[s1,s3,…,si],…,si:[s1,s2,…,si-1]}

(18)

步驟9根據樣本關系表Relations對I′中的每一組樣本進行全排列組合，具體方法是以I′中的某一樣本為基礎，遍歷I′中的其他樣本，若樣本在基礎樣本的關系表中，則進行組合，循環I′中所有樣本，形成全排列集合I″，此時I′中的每一組數據的維度可能會急劇擴大，設此時樣本的數量為m″，維度為p″，新樣本集合可表示為

I″=[I″1,I″2,…,I″m]T

(19)

I″i=[x′i1,x′i2,…,x′ij]

(20)

式(20)中：1≤i∈m″；1≤j≤p″。

x′ij=[xi1,xi2,…,xip′]

(21)

即此時的x′ij是由多個xij組成的，m″=m′，p″≥p′。

步驟10遍歷樣本集合I″，計算樣本內每一個樣本x′ij的出現次數N″ij，形成新的樣本頻數集S′amples。

(22)

式(22)中：1≤i≤m″；1≤j≤p″。

(23)

S′amples=[{s′1:c′1},{s′2:c′2},…,{s′i:c′i}]

(24)

式(24)中:1≤i≤p″。

步驟11根據S′amples計算I″中每個新樣本x′ij出現的概率，記為Pij，計算不同樣本間組合的支持度記為Supportij、置信度記為Confidenceij，將小于最小支持度和最小置信度的樣本刪除。

步驟12生成頻繁項集合關聯關系集，按照支持度、置信度降序排列。

以上步驟即為Marc算法關聯規則挖掘的流程，其總體示意圖如圖4所示。

X1～X5為樣本集中5個不同的樣本；N1～N5為X1～X5在樣本集中出現的次數；P為概率

時間復雜度是評價算法效率的重要參數，根據1.2節算法的過程，分析本文算法的復雜度如下。

(1)定義包含n個樣本的集合I，時間為1。

(2)第一次遍歷樣本I計算頻數，時間為n。

(3)計算刪除閾值后對低于閾值的樣本進行刪除，形成新的樣本集合I′，時間為n。

(4)遍歷新的樣本集合I′，統計新集合的樣本頻次，形成樣本頻數集Samples，時間為n。

(5)將Samples集合中的樣本進行兩兩組合形成新的集合，記為S′amples，并統計組合樣本在集合中共同出現的頻數，時間為n2。

(6)根據S′amples集合，生成樣本關系表Relations，由于每一個要素都需要與其他要素進行組合，因此時間為n2。

(7)根據樣本關系表Relations對I′中的每一組樣本進行全排列組合，形成樣本集合I″，時間為n。

(8)根據S′amples計算I″中每個新樣本x′ij出現的概率，時間為n。

綜上所述，本文算法的時間總耗時為

T(n)=1+n+n+n+n2+n2+n+n

=1+5n+2n2

(25)

因此，本文算法的時間復雜度為O(n2)。

2 實驗分析

2.1 實驗環境及評價指標

2.1.1 實驗環境

本實驗選取的Python版本為3.8.5，實驗平臺的配置如表1所示。

表1 實驗設備配置

為方便數據挖掘，本實驗以支持度數代替支持度。本實驗設置的最小支持度數為5，最小置信度為0.5。

2.1.2 評價指標

為驗證所提算法在高緯數據關聯規則挖掘時的效率提升及關聯規則冗余度降低方面的優勢，通過設計Marc與Apriori、FP-Growth和Eclat算法的對比試驗，選取挖掘時間、內存消耗、產生的頻繁項數量和關聯規則數量4個指標評價所提算法的優略。

2.2 實驗數據

關聯規則挖掘的核心是從不規律的樣本中挖掘出其蘊含的隱式關聯關系。通過構建不同維度和事務數的數據集進行4種算法的對比實驗，為充分對比分析四類算法在不同數據集上的表現，共構建對比數據集60組，數據集的具體構建方法如下。

2.2.1 數據集構建策略

為了使實驗事務數據集中的項構成的關聯規則模式聚焦，其生成遵循以下規則：①假設事務中下標奇數項與奇數項，偶數項與偶數項是相關的，生成事務集時按奇、偶交替生成；②設定事務集中包含的做多項數為dimension，每個事務中具有的項總個數最多為dimension個；③每個事務的噪聲項個數為noise個，noise值隨機設定且在0～3，噪聲項的選取規則是當生成奇數項時噪聲樣本為偶數項，當生成偶數項時噪聲樣本為奇數項；④同一事務中包含的項是唯一的。

2.2.2 數據集構建與分片

定義樣本集中每一行為一個事務，每個事務中包含的要素數為事務的維度。所構建的數據集最大維度為25，最多包含300個事務項。為了保證實驗數據集中關聯規則模式的一致性，首先按照2.2.1節所述的規則分別生成維度為10、15、20、25的包含300個事務項的數據集，然后按照每20個事務項對前面生成的數據集進行切片，即每個維度都包含事務項20～300的15個數據集。

2.3 實驗結果與分析

采用2.1節所述的4個指標對所提算法與Apriori、FP-Growth和Eclat進行對比分析。實驗結果如下。

2.3.1 挖掘耗時分析

四類算法在維度為25，事務項數量為300時的耗時如表2所示，不同維度和事務項數量下的挖掘耗時對比結果如圖5所示。

表2 挖掘耗時

通過對表2和圖5進行分析，可得出如下結論：①總體上四類算法的挖掘時間與維度和事務項數量成正比，且維度對挖掘時間的影響較大；②Marc算法較其他三類算法的挖掘耗時遠遠低于對比模型，且事務項數量越多，維度越高，Marc算法的時間優勢越明顯；③在挖掘時間隨事務項數量和維度變化的增長率方面，Marc算法的增長率較對比算法是最小的。Marc算法和Apriori算法的挖掘時間增長率較FP-Growth和Eclat更為平穩，FP-Growth和Eclat隨著事務項數量和維度的提升顯著增加了挖掘時間，且波動性較大，表明在高維數據挖掘時，兩類算法的穩定性較Marc和Apriori差。

圖5 挖掘耗時對比圖

2.3.2 內存消耗分析

四類算法在維度為25，事務項數量為300時的內存消耗如表3所示，不同維度和事務項數量下的內存消耗對比結果如圖6所示。

從表3和圖6可以看出：①Marc挖掘時消耗的內存遠遠小于Apriori、FP-Growth和Eclat算法，且樣本維度越高，Marc算法內存優勢越明顯；②在低維度數據挖掘時，由于Marc會生成樣本關系表和全關系組合，因此會耗費更多的內存，高維度數據挖掘時，其他三種算法的數據組織形式耗費的內存遠遠高于Marc算法的關系表和全關系組合的數據格式，表明本文算法對于高維數據的挖掘在內存消耗上更有優勢；③Marc算法的內存消耗增長率遠小于其他三類算法，且隨著樣本維度和事務項數量的增加，Marc算法的內存消耗增長率趨于穩定，表明Marc算法在內存耗費方面較對比算法[如圖6(d)所示，Eclat和FP-Growth算法的內存消耗波動較大]更穩定。

表3 內存消耗

圖6 內存消耗對比

2.3.3 頻繁項數量分析

四類算法在維度為25，事務項數量為300時生成的頻繁項數如表4所示，不同維度和事務項數量下生成的頻繁項數對比結果如圖7所示。

表4 頻繁項數量

通過對表4和圖7進行對比分析可知：①四類算法挖掘出的頻繁項數量隨著樣本的維度和事務項數量的增加而增加，Marc算法挖掘出的頻繁項個數較對比算法更少，挖掘結果更加聚焦；②同一維度下，隨著事務項數量的增加，Marc算法挖掘出的頻繁項個數趨于穩定，由于構建的數據集只有25個維度，因此Marc算法挖掘出的頻繁項結果更符合數據集情況。

圖7 頻繁項數量對比

2.3.4 關聯規則個數分析

四類算法在維度為25，事務項數量為300時生成的關聯規則數如表5所示，不同維度和事務項數量下產生的關聯規則數量的對比如圖8所示。

表5 關聯規則數量

由表5和圖8可知，Marc算法在同一緯度下隨著事務項數量的增加挖掘出的關聯規則數量趨于穩定，較對比算法更加符合數據集的情況，Marc算法顯著降低了關聯規則的生成數量，且樣本數量越多，挖掘出的關聯關系越穩定。

2.4 挖掘精度評價

以上實驗從挖掘時間、內存消耗、頻繁項和關聯規則數量4個方面評價了所提算法的優劣性，但是未對挖掘精度進行評價，因此，通過構建全關系樣本驗證隨提方法的挖掘精度。所謂全關系樣本是指每個事務項包含的維度和要素都一致的樣本，構建的驗證數據集每個事務項包含X1～X5維度，共5個事務項。設置最小支持度數為10，最小置信度為0.5。由于是全關系樣本，因此所有關聯關系的支持度和置信度都是1。實經實驗驗證，Marc挖掘出的頻繁項數為31，關聯規則數為128，且頻繁項和關聯規則與樣本真實情況一致，挖掘精度為100%。

3 結論

Marc關聯規則挖掘算法主要面向高維數據挖掘場景，經實驗驗證和對比分析，得出如下結論。

(1)Marc通過在數據初次篩選時引入分布系數和刪除閾值指標，在挖掘的初期即簡化了挖掘任務的時間和空間復雜度，大大提升挖掘算法的挖掘效率，節省了內存空間。

(2)Marc以樣本關系表為基礎構建樣本全關系組合，簡化了挖掘過程中維護的復雜度，提升了頻繁項和關聯關系的挖掘效率。

(3)Marc算法在挖掘效率、消耗內存方面都優于Apriori、FP-Growth和Eclat算法，生成的頻繁項和關聯關系更加貼近樣本和應用實際，且緯度越高優勢越明顯，更加適用于海量高維數據挖掘。

(4)Marc算法挖掘的頻繁項和關聯規則關系的精度為100%。

(5)在高維數據挖掘時FP-Growth和Eclat算法的挖掘效率低于Apriori。

目前分布系數是通過SigMoid函數對樣本的標準差或方差進行規劃所得到的，刪除系數則是由根據樣本均值E與分布系統相乘所得。根據標準差和方差的定義，當樣本數據分布較為集中時，方差和標準差較小，經SigMoid函數規劃后分布系數接近于0，刪除系數也接近于0，數據降維效果差；反之，當數據較為離散時，方差和標準差較大，分布系數接近于1，刪除系數接近于E，數據降維過多，造成部分關聯規則丟失，不利于關聯規則的挖掘，因此如何尋找合適的樣本分布指標和規劃函數計算分布系數是我們下一步將要研究的工作。