一種改進的多值屬性模式聚類算法

王珊珊 梁同樂

?

一種改進的多值屬性模式聚類算法

王珊珊1梁同樂2

（1.廣東輕工職業技術學院 2.廣東郵電職業技術學院）

pCluster算法是面向多值屬性數據的聚類算法，能識別出多值屬性間的相似性。針對模式聚類算法pCluster效率低的問題，提出pCluster的改進算法。實驗證明，該改進算法能更高效地獲得預期聚類結果。

關聯規則；多值屬性；模式聚類

0　引言

實體屬性的關聯規則挖掘是數據挖掘研究的重要方向之一，其目的在于發現數據實體各屬性間隱藏的聚類關系。這種關系具有切實的實踐意義，廣泛應用于醫療數據分析、商業信息推廣和科學實驗結果評價等領域。

實體的屬性分為布爾型屬性和多值屬性。多數學者著重于布爾型屬性關聯規則算法的研究，而多值屬性關聯規則發掘的相關文獻相對較少。多值屬性關聯規則由Srikant R和Agrawal R等于1996年提出[1-2]。挖掘多值屬性關聯規則的算法，通常將每個屬性值范圍映射為布爾型屬性，然后用布爾型屬性的挖掘算法進行關聯規則發現，如Apriori算法。但這會出現2個問題：一是多值屬性轉化為布爾型屬性時導致的數據量迅速膨脹；二是如何量化多值屬性的取值范圍，區間太窄可能造成對應的支持度過低，區間太寬則會出現可信度無法達到閾值的情況。目前，也有一些算法無需將多值屬性向布爾型屬性轉換[3-6]，但這些算法要求龐大的內存空間，以滿足特殊數據結構存儲及操作的需要。同時值得注意的是，維度效應對聚類分析的影響[7]。高維數據分群聚類時，由于數據集的復雜度較高，因此聚類的結果通常帶有不確定性[8]。另外，一些相關研究探討了高維子空間中群的發現[9-11]，然而這些聚類分群法大都是以物理距離作為相似度的計算基礎，在某些情況下這種計算相似度的方式并不合適，例如基因序列中基因對反應的聚類，醫療數據中疾病屬性值關聯性的分析，這些數據往往需要在高維數據空間中尋找具有相關聯意義的部分，進而進行分析?；谝陨闲枨?，模式聚類的概念逐漸在這些應用領域發揮優勢，越來越多的學者開始關注應用模式聚類的概念進行子空間分群[12-14]。

Wang Haixun等在2002年提出了pCluster聚類算法[15]，不同于以往的聚類算法，其更加關注廣泛意義上的屬性子集相似模式，從而發現屬性間的關聯關系。本文提出的pCluster優化算法，致力于提高pCluster聚類算法的收斂速度。

1　相關研究介紹

多數聚類算法是基于距離挖掘相似類別的成員，即通過發現對象在子空間內距離的相近程度來度量。然而，在某些特定的數據集中，相同的簇成員不體現在對象間距離的相近，而是存在一種模式上的相似性。

圖1表示有3個對象10個屬性的數據集。在這3個對象中并不存在明顯的相似模式，但如果將其中部分屬性分離開，就可清晰地看到其中的相似性。例如查看屬性集合｛,,,,｝，如圖2所示，可以直觀地看到它們之間的相似關系。

圖2　對象的屬性子集相似模式

Cheng Y.等在2000年提出了bicluster算法[16]。設為對象的集合，為屬性的集合，令?且?，則（，）表示一個子矩陣，殘差的平方的平均值

當(,)≤（>0）時，稱為一個-bicluster。

Yang Jiong等提出的基于移動的算法[17]能更快地找到-bicluster。首先隨機選擇一個起點，迭代地執行算法以改善聚類分群的質量。該算法能夠同時找到多個分群，且避免了分群間的重疊問題，但它仍然采用平方差作為分群聚類的基礎，當數據集中存在噪聲點時，聚類效果并不理想，同時該算法要求輸入聚類的群數作為輸入參數。

Wang Haixun等[15]使用pScore代替平均平方差，很好地解決了噪聲數據的問題。定義為數據集中的對象子集(?)，為屬性集的子集(?)，(,)對代表一個子矩陣。令,∈，,∈， pScore定義為

其中d代表對象在屬性的取值。

當(,)對中任意2×2子矩陣均滿足pScore() ≤時，(,)為一個-pCluster。設=(,)是一個-pCluster，定義是的最大維度集（maximum dimension sets，MDS），當且僅當不存在任意?，使得(,)也是一個-pCluster。pCluster算法需對每2個對象及每對屬性進行比較，產生MDS。這時將對象對產生的MDS稱為o-pair MDS，屬性對產生的MDS稱為c-pair MDS。由數據集產生的所有MDS中，包含了可能構成pCluster的全部信息。

接下來對o-pair MDS和c-pair MDS進行相互剪枝操作。MDS的剪枝過程是pCluster算法的重要組成部分。假設T是對象和的MDS，O是屬性和對應的MDS。對任意一個TMDS中的屬性，計算O的MDS中包含{,}的個數，當個數小于-1時（是pCluster要求的最小屬性數），則將屬性從T中去除，如果剪枝后的|T| <，則移除整個T。該過程即為使用c-pair MDS對o-pair MDS剪枝。反之亦然，只需將替換為（pCluster要求的最小對象數）。反復使用c-pair MDS與o-pair MDS相互剪枝，直至沒有任何MDS可被刪除為止。

最后將余下的o-pair MDS插入一個以屬性為路徑的前綴樹，相應的對象存放在結點中，再對所有結點，利用對應路徑屬性對的MDS刪除結點中保存的多余對象，并將該結點中對象加入其父節點，刪除此結點，重復此過程直到沒有深度大于的結點存在。后序遍歷該前綴樹以得到最終的pCluster結果。

2　改進的pCluster算法

pCluster算法中MDS剪枝操作占用了算法的絕大部分運行開銷。當數據集對象或屬性數目增加時，MDS剪枝耗時也將隨著MDS候選元組數的上升而急劇增加。于是一些文獻針對MDS剪枝問題的改進進行了嘗試。李健億等人[18]提出了pCluster的改進算法pCluster+，通過犧牲額外的存儲空間對MDS相關信息進行計數，從而提高剪枝效率。pCluster算法的核心是MDS的相互剪枝過程。

本文提出改進的pCluster算法，通過在MDS相互剪枝過程中加入存儲檢驗容器Checkbox，在每次c-pair MDS與o-pair MDS的遍歷檢查過程中用于存放那些導致被檢查的T或O被刪除的記錄行號。因為Checkbox所存儲的行中必然包含被刪除記錄中的前2個元素，且該記錄已被刪除，則這2個元素的出現頻率也將降低，于是Checkbox所存儲的行在下一次剪枝過程中被移除的可能性將大于其它記錄，如果對Checkbox中記錄的行優先進行檢查，就可以避免由于檢查記錄過多而導致的算法效率緩慢。

假設現有5×5數據集（5個對象，5個屬性）如表1所示。

表1　5×5數據集

原始數據中存在5項o-pair MDS，6項c-pair MDS。在本文的改進算法中，加入了一個Checkbox檢驗存儲容器，用于輔助MDS剪枝過程。對于o-pair MDS中(O, O) à {C, C, C}，在c-pair MDS中查找包含(O,O)的項，并將其行號加入preCheckbox中。若最終(O, O) à {C, C, C}由于屬性頻率或個數未達到閾值被刪除，則將preCheckbox中的行號轉錄至Checkbox，同時清空preCheckbox。在接下來的c-pair MDS遍歷中，僅需對Checkbox中記錄的c-pair MDS行號進行掃描。同樣地，對于記錄(C,C) à {O,O,O}，在o-pair MDS中查找包含(C,C)的項，并將其行號加入preCheckbox中。若最終(C,C) à {O,O,O}被刪除，則將preCheckbox中行號加入Checkbox，并清空preCheckbox。反復進行這樣的操作，直至在完整的一輪檢驗過程中（o-pair MDS與c-pair MDS相互剪枝）都沒有記錄被刪除。

令= 3，= 3，= 1。首先找到全部MDS，如圖3所示。

(1,3)→(1,2,3)

(1,4) →(3,4,5)

(1,5) →(3,4,5)

(2,3)→(1,2,3)

(4,5) →(3,4,5)

(a) o-pair MDS

(1,2) →(1,2,3)

(1,3) →(2,3,4)

(2,3) →(2,3,5)

(3,4) →(1,4,5)

(3,5) →(1,4,O)

(4,5) →(1,4,O)

(b) c-pair MDS

圖3數據集中存在的MDS

以上述原始數據舉例，先用c-pair MDS對o-pair MDS進行檢驗，第一項(1,3) à {1,2,3}，在c-pair MDS中包含(1,3)的項中僅在第1行，屬性1，2，3出現頻率為（1，1，0），于是刪除(1,3) à {1,2,3}，并將c-pair MDS行號1加入Checkbox；下一步只檢驗c-pair MDS的第1行(1,2) à {1,2,3}，包含(1,2)的o-pair MDS僅有(2,3) à {1,2,3}，{1,2,3}頻率不滿足閾值-1，因此刪除該記錄，并將o-pair MDS行號3加入Checkbox，至此第一輪剪枝完成。后續剪枝規則相同。當Checkbox為空時，遍歷相應MDS中的所有項，否則只需檢查Checkbox中記錄的行號即可。對于給定的數據集（表1），需進行3輪剪枝過程，如圖4所示。

Roud 1: Checkbox = NULL

Part 1:

(1,3) →(1,2,3) ×

(1,4) → (3,4,5)

(1,5) → (3,4,5)

(2,3) → (1,2,3)

(4,5) → (3,4,5)

Checkbox = [1]

Part 2:

(1,2) → (1,23)×

(1,3) → (2,3,4)

(2,3) → (2,3,5)

(3,4) → (1,4,5)

(3,5) → (1,4,5)

(4,5) →(1,4,5)

Checkbox = [3]

Roud 2: Checkbox = [3]

Part 1:

(1,4) →(3,4,5)

(1,5) →(3,4,5)

(2,3) →(1,2,3)×

(4,5) → (3,4,5)

Checkbox = [1, 2]

Part 2:

(1,3) →(2,3,4)×

(2,3) → (2,3,5)×

(3,4) → (1,4,5)

(3,5) → (1,4,5)

(4,5) → (1,4,5)

Checkbox = NULL

Roud 3: Checkbox = NULL

Part 1:

(1,4) →(3,4,5)

(1,5) →(3,4,5)

(4,5) →(3,4,5)

Checkbox = NULL

Part 2:

(3,4) →(1,4,5)

(3,5) →(1,4,5)

(4,5) →(1,4,5)

Checkbox = NULL

圖4改進的MDS剪枝過程

比較過程：第一輪，c-pair MDS對o-pair MDS剪枝，Checkbox為空，比較次數5×6，Checkbox=[1]；o-pair MDS只需對c-pair MDS第1行檢驗是否需要剪枝，比較次數1×4，Checkbox=[3]。第二輪，使用c-pair MDS對o-pair MDS第3行檢驗，比較次數1×5，Checkbox=[1，2]；o-pair MDS 對c-pair MDS第1行和第2行檢驗是否需要剪枝，比較次數2×3，Checkbox為空。第三輪，c-pair MDS與o-pair MDS相互檢驗，比較次數3×3×2，沒有記錄被刪除。MDS剪枝結束?？偙容^次數為63。原pCluster MDS剪枝過程如下：第一輪c-pair MDS對o-pair MDS剪枝，比較次數為5×6，刪除o-pair MDS第一行記錄；o-pair MDS對c-pair MDS剪枝，比較次數為6×4，刪除c-pair MDS的第1、2、3條記錄。第二輪使用c-pair MDS對o-pair MDS進行檢驗，比較次數為3×4，刪除o-pair MDS第三行記錄；o-pair MDS對c-pair MDS剪枝，比較次數為3×3，無記錄刪除。第三輪，c-pair MDS與o-pair MDS相互檢驗，比較次數3×3×2?？偙容^次數93。

算法優化了pCluster核心部分，改進了MDS剪枝過程，在保持算法準確性的基礎上使算法效率得到顯著提高。在改進后的剪枝過程中，利用存儲檢驗容器Checkbox記錄下更有可能被剪枝的MDS。使用Checkbox中記錄項作為優先檢驗對象，從而大幅縮小待檢查的MDS范圍，避免了原算法中每輪剪枝都必須檢查全部MDS的繁瑣步驟，同時當Checkbox首次為空時，執行一次MDS全面覆蓋相互篩查，以保證剪枝結果的正確性，有效避免漏檢情況的發生。這樣既保證了MDS剪枝的完整性，同時也使算法耗時大幅減少。

改進的pCluster算法：

begin

for each,∈,≠

find c-pair MDSs;

end

for each,∈,≠

find o-pair MDSs;

end

Checkbox = NULL;

do

if Checkbox is empty

for each o-pair MDS

use c-pair MDSs to prune columns in;

if ||<

eliminate MDS({,},);

store sequence number of c-pair MDS in Checkbox;

end

end

if Checkbox is empty

for each c-pair MDS

use o-pair MDSs to prune objects in;

if ||<

eliminate MDS({,},);

store sequence number of c-pair MDS in Checkbox;

end

end

else if Checkbox is not empty

check every c-pair MDS which is recorde-d in Checkbox;

eliminate MDS({,},) and store the sequence number in Checkbox, if ||<;

end

else if Checkbox is not empty

check every o-pair MDS which is recorded in Checkbox;

eliminate MDS({,},) and store the sequence number in Checkbox, which ||<;

end

if no pruning takes place

mutual prune both o-pair MDSs and c-pair MDSs;

end

while pruning takes place

insert all o-pair MDSs({,},) into the prefix tree;

make a post-order traversal of the tree;

do

:= objects in node;

:= columns represented by node;

for each,∈

find c-pair MDSs;

remove fromthose objects not contained in any MDS

end

while no node whose depth > nc exists

end

3　仿真實驗與結果分析

對改進的pCluster及原算法進行仿真實驗，并對算法效率進行分析與比較。實驗平臺為處理器Intel(R) core(TM)2 Duo CPU 2.26 GHz，3 G內存，Vista操作系統。實驗分別采用人工數據集、經典數據集以及實際采集的醫療數據作為測試數據，不同數據集仿真實驗結果均表明改進的pCluster算法較原算法在聚類效率上有顯著的提高。

3.1人工數據集

測試數據采用人工數據集，矩陣元素為隨機生成的1～100數字。屬性個數固定為30，對象個數分別設為10、20、30、50、100。此外，pCluster中最小對象數設為3，最小屬性數設為2，閾值為3。原算法與改進算法的運行時間比較如表2所示。第1行表示數據集大小，即對象數×屬性數。從表2可以看出，數據集規模較小時，例如10×15，改進算法與原算法耗時幾乎相同，隨著數據集規模的增大，改進的pCluster算法優勢逐漸顯現，在對象數為20、30、50的數據集中，改進算法耗時較原算法減少了一個數量級。數據集大小為100×15時，CPU耗時減少了72.94%。

表2　人工數據集仿真結果

3.2酵母菌基因序列數據

測試數據采用經典的數據集酵母菌基因序列片段[19]，數據集中包含2884個基因在17種條件下的記錄數據。數據集以矩陣形式顯示，每行代表1種基因，每列代表1類環境條件。矩陣中的值由原始數據值采用比例縮放或取對數方式使其數值呈現在0到600之間。生物學家的目標是尋找在相同條件下產生共同趨勢的基因組。其中，pCluster最小對象數設為40，最小屬性數設為7，閾值為2。2種模式聚類算法對該數據集的測試結果如表3所示?？梢钥闯觯璸Cluster算法剪枝輪數較少，但耗時集中；改進后的pCluster算法剪枝輪數增加了一倍，但剪枝所需總時間有所減少，較改進前提高了12.04%。

表3　酵母菌基因數據集仿真結果

3.3醫療數據

采用某醫院的醫療數據，數據集中包含560名受訪者21種癥狀程度的記錄。數據集以矩陣形式存儲，每行代表1名受訪者，每列代表1類癥狀。其中，為數據集樣本數。pCluster最小屬性數設為13，最小對象數設為0.1，閾值為1。2種模式聚類算法對該數據集的測試結果如表4所示。第1行表示數據集大小，即對象數×屬性數。實驗結果表明，改進的pCluster算法較原算法在效率上有明顯的提升。樣本數超過200時，改進算法的CPU耗時提高了兩個數量級。醫療數據改進的pCluster與原pCluster算法效率比較如圖5所示。

表4　醫療數據集仿真結果

圖5 醫療數據改進的pCluster與原pCluster算法效率比較

4　結語

本文提出一種pCluster改進算法，優化了pCluster算法的核心部分—MDS剪枝過程，使發現對象和屬性間的相似模式更具效率。改進算法分別在人工數據集和2組真實數據集上進行了仿真實驗，測試結果均表明改進的pCluster算法較原算法耗時更少，聚類效率更高。同時，相似模式聚類算法具有廣泛的實際應用價值，例如醫療數據分析、商業信息推廣、化學結構評價等等，這也是筆者未來工作的方向。

參考文獻

[1] Srikant R, Agrawal R. Mining quantitative association rules in large relational tables[C]. Montreal: in Proc. of the ACM SIGMOD International Conference on Management of Data, 1996, 25: 1-12.

[2] Agrawal R, Imielinski T, Swami A. Mining association rules between sets of items in large databases[C]. Washington: in Proc. of the ACM SIGMOD International Conference on Management of Data, 1993, 22:207-216.

[3] 李國雁,沈炯夏.一種基于矩陣的多值關聯規則的挖掘算法[J].計算機工程與科學,2008,30(5):72-74,77.

[4] 賀志,田盛豐,黃厚寬.一種挖掘數值屬性的二維優化關聯規則方法[J].軟件學報,2007,18(10):2528-2537.

[5] 陳文.基于位矩陣的加權頻繁項集生成算法[J].計算機工程,2010,36(5):54-56.

[6] 姜麗莉,孟凡榮,周勇.多值屬性關聯規則挖掘的Q-Apriori算法[J].計算機工程,2011,37(9):81-83.

[7] Donoho David L. High-dimentional data analysis: The curses and blessings of dimensionality [R]. Los Angeles, 2000.

[8] Beyer K, Goldstein J, Ramakrishnan R, et al. When is nearest neighbors meaningful[C]. Jerusalem: in Proc. of the International Conference Database Theories, 1999: 217-235.

[9] Agrawal R, Gehrke J, Gunopulos D, et al. Authomatic subspace clustering of high dimensional data for data mining applications[C]. New York: Proc of ACM SIGMOD International Conference on Management of Data, 1998, 27: 94-105.

[10] Aggarwal C C, Yu P S. Finding generalized projected clusters in high dimensional spaces[C]. Dallas: Proc of ACM SIGMOD International Conference on Management of Data, 2000, 29: 70-81.

[11] 宗瑜,李明楚,徐貫東,等.局部顯著單元高維聚類算法[J].電子與信息學報,2010,32(11):2107-2712.

[12] Liu Qingbao, Dong Guozhu. CPCQ: Contrast pattern based clustering quality index for categorical data[J]. Pattern Recognition, 2012 ,45 (4): 1739-1748.

[13] Poon Leonard K M, Zhang Nevin L, Liu Tengfei, et al. Model-based clustering of high-dimensional data: Variable selection versus facet determination[OL]. http://www. sciencedirect.com/science/article/pii/S0888613X12001429. 2012.8.

[14] Browne R P, McNicholas P D. Model-based clustering, classification, and discriminant analysis of data with mixed type[J]. Journal of Statistical Planning and Inference, 2012, 142 (11): 2976-2984.

[15] Wang Haixun, Wang Wei, Yang Jiong, et al. Clustering by pattern similarity in large data sets[C]. Madison: in Proc. Of ACM SIGMOD International Conference on Management of Data, 2002:394-405.

[16] Cheng Y, Church G. Biclustering of expression data[C]. San Diego: In Proc. Of 8th International Conference on Intelligent System of Molecular Biology, 2000:93-103.

[17] Yang Jiong, Wang Wei, Wang Haixun, et al. δ-clusters: Capturing subspace correlation in a large data set[C]. San Jose: ICDE, 2002: 517-528.

[18] 李健億,黃乙展,吳崢榕.新的pCluster方法：pCluster+與incremental pCluster[C].臺中:National Computer Symposium ,2003:1114-1121.

[19] Tavazoie S, Hughes J, Campbell M, et al. Yeast micro data set[OL]. http://arep.med.harvard.edu/biclustering/yeast.matrix, 2012.5.

An Improved Pattern Cluster Algorithm for Quantitative Attributes

Wang Shanshan1Liang Tongle2

(1.Department of Computer Engineering, Guangdong Industry Technical College 2. Department of Computer, Guangdong Vocational Technical College of Posts and Telecom)

pCluster is a kind of cluster algorithm for the numeric attributes, which could identify the similar trend among several attributes, but it is less than satisfactory in algorithm efficiency. In this paper, an improved pCluster algorithm was presented, the expected cluster results could be produced more efficient.

Association Rule; Quantitative Attribute; Pattern Cluster

王珊珊，女，1984年生，碩士，助教，主要研究方向：數據挖掘。E-mail: 2014106061@gditc.edu.cn

梁同樂，男，1984年生，學士，助教，主要研究方向：智能信息處理、大數據分析等。