一種改進(jìn)的多值屬性模式聚類算法

王珊珊 梁同樂(lè)

?

一種改進(jìn)的多值屬性模式聚類算法

王珊珊1梁同樂(lè)2

（1.廣東輕工職業(yè)技術(shù)學(xué)院 2.廣東郵電職業(yè)技術(shù)學(xué)院）

pCluster算法是面向多值屬性數(shù)據(jù)的聚類算法，能識(shí)別出多值屬性間的相似性。針對(duì)模式聚類算法pCluster效率低的問(wèn)題，提出pCluster的改進(jìn)算法。實(shí)驗(yàn)證明，該改進(jìn)算法能更高效地獲得預(yù)期聚類結(jié)果。

關(guān)聯(lián)規(guī)則；多值屬性；模式聚類

0　引言

實(shí)體屬性的關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的重要方向之一，其目的在于發(fā)現(xiàn)數(shù)據(jù)實(shí)體各屬性間隱藏的聚類關(guān)系。這種關(guān)系具有切實(shí)的實(shí)踐意義，廣泛應(yīng)用于醫(yī)療數(shù)據(jù)分析、商業(yè)信息推廣和科學(xué)實(shí)驗(yàn)結(jié)果評(píng)價(jià)等領(lǐng)域。

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

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

1　相關(guān)研究介紹

多數(shù)聚類算法是基于距離挖掘相似類別的成員，即通過(guò)發(fā)現(xiàn)對(duì)象在子空間內(nèi)距離的相近程度來(lái)度量。然而，在某些特定的數(shù)據(jù)集中，相同的簇成員不體現(xiàn)在對(duì)象間距離的相近，而是存在一種模式上的相似性。

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

圖2　對(duì)象的屬性子集相似模式

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

當(dāng)(,)≤（>0）時(shí)，稱為一個(gè)-bicluster。

Yang Jiong等提出的基于移動(dòng)的算法[17]能更快地找到-bicluster。首先隨機(jī)選擇一個(gè)起點(diǎn)，迭代地執(zhí)行算法以改善聚類分群的質(zhì)量。該算法能夠同時(shí)找到多個(gè)分群，且避免了分群間的重疊問(wèn)題，但它仍然采用平方差作為分群聚類的基礎(chǔ)，當(dāng)數(shù)據(jù)集中存在噪聲點(diǎn)時(shí)，聚類效果并不理想，同時(shí)該算法要求輸入聚類的群數(shù)作為輸入?yún)?shù)。

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

其中d代表對(duì)象在屬性的取值。

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

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

最后將余下的o-pair MDS插入一個(gè)以屬性為路徑的前綴樹(shù)，相應(yīng)的對(duì)象存放在結(jié)點(diǎn)中，再對(duì)所有結(jié)點(diǎn)，利用對(duì)應(yīng)路徑屬性對(duì)的MDS刪除結(jié)點(diǎn)中保存的多余對(duì)象，并將該結(jié)點(diǎn)中對(duì)象加入其父節(jié)點(diǎn)，刪除此結(jié)點(diǎn)，重復(fù)此過(guò)程直到?jīng)]有深度大于的結(jié)點(diǎn)存在。后序遍歷該前綴樹(shù)以得到最終的pCluster結(jié)果。

2　改進(jìn)的pCluster算法

pCluster算法中MDS剪枝操作占用了算法的絕大部分運(yùn)行開(kāi)銷。當(dāng)數(shù)據(jù)集對(duì)象或?qū)傩詳?shù)目增加時(shí)，MDS剪枝耗時(shí)也將隨著MDS候選元組數(shù)的上升而急劇增加。于是一些文獻(xiàn)針對(duì)MDS剪枝問(wèn)題的改進(jìn)進(jìn)行了嘗試。李健億等人[18]提出了pCluster的改進(jìn)算法pCluster+，通過(guò)犧牲額外的存儲(chǔ)空間對(duì)MDS相關(guān)信息進(jìn)行計(jì)數(shù)，從而提高剪枝效率。pCluster算法的核心是MDS的相互剪枝過(guò)程。

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

假設(shè)現(xiàn)有5×5數(shù)據(jù)集（5個(gè)對(duì)象，5個(gè)屬性）如表1所示。

表1　5×5數(shù)據(jù)集

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

令= 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數(shù)據(jù)集中存在的MDS

以上述原始數(shù)據(jù)舉例，先用c-pair MDS對(duì)o-pair MDS進(jìn)行檢驗(yàn)，第一項(xiàng)(1,3) à {1,2,3}，在c-pair MDS中包含(1,3)的項(xiàng)中僅在第1行，屬性1，2，3出現(xiàn)頻率為（1，1，0），于是刪除(1,3) à {1,2,3}，并將c-pair MDS行號(hào)1加入Checkbox；下一步只檢驗(yàn)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行號(hào)3加入Checkbox，至此第一輪剪枝完成。后續(xù)剪枝規(guī)則相同。當(dāng)Checkbox為空時(shí)，遍歷相應(yīng)MDS中的所有項(xiàng)，否則只需檢查Checkbox中記錄的行號(hào)即可。對(duì)于給定的數(shù)據(jù)集（表1），需進(jìn)行3輪剪枝過(guò)程，如圖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改進(jìn)的MDS剪枝過(guò)程

比較過(guò)程：第一輪，c-pair MDS對(duì)o-pair MDS剪枝，Checkbox為空，比較次數(shù)5×6，Checkbox=[1]；o-pair MDS只需對(duì)c-pair MDS第1行檢驗(yàn)是否需要剪枝，比較次數(shù)1×4，Checkbox=[3]。第二輪，使用c-pair MDS對(duì)o-pair MDS第3行檢驗(yàn)，比較次數(shù)1×5，Checkbox=[1，2]；o-pair MDS 對(duì)c-pair MDS第1行和第2行檢驗(yàn)是否需要剪枝，比較次數(shù)2×3，Checkbox為空。第三輪，c-pair MDS與o-pair MDS相互檢驗(yàn)，比較次數(shù)3×3×2，沒(méi)有記錄被刪除。MDS剪枝結(jié)束?？偙容^次數(shù)為63。原pCluster MDS剪枝過(guò)程如下：第一輪c-pair MDS對(duì)o-pair MDS剪枝，比較次數(shù)為5×6，刪除o-pair MDS第一行記錄；o-pair MDS對(duì)c-pair MDS剪枝，比較次數(shù)為6×4，刪除c-pair MDS的第1、2、3條記錄。第二輪使用c-pair MDS對(duì)o-pair MDS進(jìn)行檢驗(yàn)，比較次數(shù)為3×4，刪除o-pair MDS第三行記錄；o-pair MDS對(duì)c-pair MDS剪枝，比較次數(shù)為3×3，無(wú)記錄刪除。第三輪，c-pair MDS與o-pair MDS相互檢驗(yàn)，比較次數(shù)3×3×2。總比較次數(shù)93。

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

改進(jìn)的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　仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1人工數(shù)據(jù)集

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

表2　人工數(shù)據(jù)集仿真結(jié)果

3.2酵母菌基因序列數(shù)據(jù)

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

表3　酵母菌基因數(shù)據(jù)集仿真結(jié)果

3.3醫(yī)療數(shù)據(jù)

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

表4　醫(yī)療數(shù)據(jù)集仿真結(jié)果

圖5 醫(yī)療數(shù)據(jù)改進(jìn)的pCluster與原pCluster算法效率比較

4　結(jié)語(yǔ)

本文提出一種pCluster改進(jìn)算法，優(yōu)化了pCluster算法的核心部分—MDS剪枝過(guò)程，使發(fā)現(xiàn)對(duì)象和屬性間的相似模式更具效率。改進(jìn)算法分別在人工數(shù)據(jù)集和2組真實(shí)數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn)，測(cè)試結(jié)果均表明改進(jìn)的pCluster算法較原算法耗時(shí)更少，聚類效率更高。同時(shí)，相似模式聚類算法具有廣泛的實(shí)際應(yīng)用價(jià)值，例如醫(yī)療數(shù)據(jù)分析、商業(yè)信息推廣、化學(xué)結(jié)構(gòu)評(píng)價(jià)等等，這也是筆者未來(lái)工作的方向。

參考文獻(xiàn)

[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] 李國(guó)雁,沈炯夏.一種基于矩陣的多值關(guān)聯(lián)規(guī)則的挖掘算法[J].計(jì)算機(jī)工程與科學(xué),2008,30(5):72-74,77.

[4] 賀志,田盛豐,黃厚寬.一種挖掘數(shù)值屬性的二維優(yōu)化關(guān)聯(lián)規(guī)則方法[J].軟件學(xué)報(bào),2007,18(10):2528-2537.

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

[6] 姜麗莉,孟凡榮,周勇.多值屬性關(guān)聯(lián)規(guī)則挖掘的Q-Apriori算法[J].計(jì)算機(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].電子與信息學(xué)報(bào),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].臺(tái)中: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年生，碩士，助教，主要研究方向：數(shù)據(jù)挖掘。E-mail: 2014106061@gditc.edu.cn

梁同樂(lè)，男，1984年生，學(xué)士，助教，主要研究方向：智能信息處理、大數(shù)據(jù)分析等。