魏振鋼， 鄭東輝， 魏兆強

(中國海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266100)

聚類結(jié)果的好壞與原始數(shù)據(jù)集的相關(guān)屬性具有一定關(guān)系，而聚類得到的相關(guān)數(shù)據(jù)都是一些不容易理解的數(shù)字信息，很難從中得到數(shù)據(jù)簇拆分重組、數(shù)量變化、聚類結(jié)果穩(wěn)定性等信息。研究聚類結(jié)果的可視化方法能夠發(fā)現(xiàn)聚類過程中的相關(guān)規(guī)律，對數(shù)據(jù)挖掘和聚類的相關(guān)研究具有重要意義。

然而，目前聚類相關(guān)研究仍然依靠單純的數(shù)據(jù)集的聚類結(jié)果數(shù)據(jù)分析，難以發(fā)現(xiàn)其中的相關(guān)規(guī)律和內(nèi)在聯(lián)系。文獻(xiàn)[1-3]中對聚類結(jié)果的分析比較詳細(xì)，但是很難發(fā)現(xiàn)聚類結(jié)果的穩(wěn)定性與數(shù)據(jù)集中的維度關(guān)系。文獻(xiàn)[4]中提出了一種聚類結(jié)果可視化的分析方法，是一種基于matlab中dendrogram而改進的方法，可以看出聚類變化的過程，但是不能發(fā)現(xiàn)聚類結(jié)果與維度的關(guān)系、數(shù)據(jù)簇數(shù)量的變化，本質(zhì)上還是一種dendrogram。目前的可視化方法主要缺點[5-11]：(1)無法顯式表現(xiàn)數(shù)據(jù)集聚類結(jié)果穩(wěn)定性與數(shù)據(jù)屬性的關(guān)系；(2)無法展示數(shù)據(jù)簇在聚類過程中數(shù)量變化。如圖1所示，dendrogram只能表現(xiàn)出數(shù)據(jù)集聚類過程中數(shù)據(jù)簇重組情況，無法表現(xiàn)聚類結(jié)果與數(shù)據(jù)屬性的內(nèi)在聯(lián)系以及數(shù)量的變化。

本文提出的PC方法，能夠提供一種顯式的方法對聚類結(jié)果進行分析，容易表現(xiàn)數(shù)據(jù)集聚類變化過程、數(shù)據(jù)簇的數(shù)量變化，發(fā)現(xiàn)聚類結(jié)果與數(shù)據(jù)屬性的內(nèi)在聯(lián)系。即PC方法能夠很好的記錄和表現(xiàn)聚類過程中數(shù)據(jù)簇的數(shù)量變化、拆分和重組等情況，對聚類研究具有重要作用。

圖1 matlab中dendrogram

1 PC聚類結(jié)果可視化分析方法

PC方法的基本思想是記錄數(shù)據(jù)集聚類過程中的一系列矩陣，利用圖的形式直觀的表現(xiàn)出聚類結(jié)果與某個屬性的關(guān)系和聚類過程中數(shù)據(jù)簇的變化，圖中矩形塊的長度表示聚類結(jié)果中數(shù)據(jù)簇的數(shù)量，相近類別的矩形塊之間的連線表示數(shù)據(jù)簇的拆分和重組關(guān)系以及變化過程。數(shù)據(jù)簇拆分后組成其他數(shù)據(jù)簇，然后從不同的數(shù)據(jù)簇分出一部分組成新數(shù)據(jù)簇，這種情形越多，PC圖中交叉現(xiàn)象就越嚴(yán)重，說明聚類結(jié)果的穩(wěn)定性越差。通過這種直觀的描述，根據(jù)數(shù)據(jù)簇的拆分重組情況，評價聚類結(jié)果穩(wěn)定性與某個屬性是否有一定的關(guān)系。

通過對不同聚類數(shù)k下聚類結(jié)果的分析，得到一個原始數(shù)據(jù)的分類矩陣，該矩陣包含了每個原始數(shù)據(jù)被分到了相應(yīng)類別的信息，然后將此分類矩陣通過PC技術(shù)以更加直觀的圖表方式表現(xiàn)出來。具體實現(xiàn)如下：

輸入：數(shù)據(jù)集X={x1,x2,x3,…,xn}；

輸出：聚類結(jié)果的PC圖。

①通過調(diào)用聚類算法，得到數(shù)據(jù)集聚類結(jié)果的類別矩陣

(1)

式中：k=1,2,3,…,7,代表對數(shù)據(jù)集聚類數(shù)目；1～k數(shù)據(jù)集中這一條記錄屬于1～k中的某一類；n代表數(shù)據(jù)集記錄的數(shù)量。

②把得到的類別矩陣合并為一個矩陣

首先初始化HB矩陣：

(2)

經(jīng)過k次聚類，然后通過公式合并矩陣

(3)

式中，n代表數(shù)據(jù)集數(shù)據(jù)的數(shù)量，n≥0且n為整數(shù)。

③通過HB矩陣統(tǒng)計目前k聚類結(jié)果與k-1聚類結(jié)果的對應(yīng)關(guān)系，存儲聚類過程的矩陣記為重組矩陣

初始化矩陣TJX，如下：

(4)

式中k代表聚類的類別數(shù)。

然后運用下面公式計算TJX矩陣。

(5)

式中n為HB矩陣中的行數(shù)。

④利用HB矩陣統(tǒng)計矩陣中的相同數(shù)值，計算統(tǒng)計矩陣

(6)

式中k代表聚類的類別數(shù)。

⑤計算聚類數(shù)目為i時矩形條的高度的一半

(7)

式中：GD為設(shè)定的值，代表數(shù)據(jù)集記錄數(shù)量，值越大，PC尺寸越大；i為此時的聚類數(shù)目。

⑥初始化存儲此前矩形塊的坐標(biāo)和長度矩陣

(8)

式中，H為矩陣TJ的行數(shù)。

⑦循環(huán)畫出代表每簇數(shù)據(jù)的矩陣塊,并記錄此次循環(huán)的相關(guān)數(shù)據(jù)，計算矩陣塊的長度

(j-1)×0.5，

(9)

式中，j為此前的聚類數(shù)目，j=1,2,…，H。

使用matlab自帶的rectangle公式畫出矩形塊

rectangle(′Position′,[0.95+(i-1)×1.0,JS,

(10)

式中i為此時的聚類數(shù)目。

利用ZBH矩陣存儲此時的矩形塊的長度和坐標(biāo)

ZBH(j,1)=JS，

(11)

(12)

⑧循環(huán)畫出矩形塊之間的變化過程：

根據(jù)TJX矩陣計算矩形塊之間的變化數(shù)量

(13)

式中：m=1,2,…,H；n=1,2,…,i；CH為HB矩陣的記錄數(shù)量。

調(diào)用matlab中l(wèi)ine函數(shù)畫出數(shù)據(jù)簇之間的變化過程

line([1.05+(i-2)×1.0,0.95+(i-1)×1.0],[ZBQ(n,1)+ZBQ(n,2),ZBH(m,1)+ZBH(m,2)])，

(14)

line([1.05+(i-2)×1.0,0.95+(i-1)×1.0],[ZBQ(n,1)+ZBQ(n,2),ZBH(m,1)+ZBH(m,2)-SGD])，

(15)

ZBQ(n,2)=ZBQ(n,2)-SGD，

(16)

ZBH(m,2)=ZBH(m,2)-SGD，

(17)

其中，

(18)

2 實驗結(jié)果及分析

2.1 數(shù)據(jù)集介紹

本文實驗的數(shù)據(jù)集包括自行設(shè)計的人工數(shù)據(jù)集Balls和2個UCI數(shù)據(jù)集，各數(shù)據(jù)集的基本信息如表1所示。

表1 數(shù)據(jù)集的基本信息

2.2 實驗結(jié)果及分析

2.2.1 對Balls數(shù)據(jù)集的分析 本次實驗選擇的數(shù)據(jù)集是一系列二維的坐標(biāo)點，用PC方法進行分析。本文用的聚類方法是譜聚類，也可以采用其他聚類算法，在此不做累述。下面是數(shù)據(jù)集Balls，如圖2所示。

圖2 balls數(shù)據(jù)集

在實驗中，使用PC方法進行計算分別得到了x維度的PC(見圖3(a))和y維度的PC(見圖3(b))。

圖3 balls數(shù)據(jù)集按不同維度計算得到的PC

按x維度得到的PC從數(shù)據(jù)簇為4時開始，往后的拆分重組不多，交叉不多。而按y維度得到的PC從數(shù)據(jù)簇為4時開始，往后的拆分重組現(xiàn)象比較嚴(yán)重，交叉復(fù)雜。通過比較上述兩種情形，能夠很容易的看到數(shù)據(jù)集在y維度的聚類過程中，數(shù)據(jù)簇的拆分重組現(xiàn)象比較嚴(yán)重，判斷出balls數(shù)據(jù)集按x維度聚類效果比按y維度聚類效果好。

2.2.2 對UCI其他數(shù)據(jù)集分析

(1)對數(shù)據(jù)集glass的分析 通過PC可視化算法對數(shù)據(jù)集glass進行分析，分別得到了9維度的PC(見圖4(a))和2維度的PC(見圖4(b))，判斷出glass數(shù)據(jù)集按2維度聚類效果比按9維度聚類效果好。

圖4 glass數(shù)據(jù)集按不同維度聚類的PC

(2)對數(shù)據(jù)集heart的分析 通過PC可視化算法對數(shù)據(jù)集heart進行分析，分別得到了2維度的PC(見圖5(a))和7維度的PC(見圖5(b))，判斷出heart數(shù)據(jù)集按7維度聚類效果比按2維度聚類效果好。

圖5 heart數(shù)據(jù)集按不同維度聚類的PC

3 結(jié)語

本文運用PC方法針對不同的數(shù)據(jù)集進行實驗，能夠展現(xiàn)出聚類的過程中數(shù)據(jù)簇的拆分和重組情況，很容易地發(fā)現(xiàn)其他可視化算法不能展現(xiàn)出的聚類結(jié)果穩(wěn)定性與不同維度的數(shù)據(jù)之間的規(guī)律，極大的提高了聚類分析的效率。