魏振鋼， 鄭東輝， 魏兆強(qiáng)

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

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

圖1 matlab中dendrogram

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

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

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

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

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

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

(1)

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

②把得到的類別矩陣合并為一個(gè)矩陣

首先初始化HB矩陣：

(2)

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

(3)

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

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

初始化矩陣TJX，如下：

(4)

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

然后運(yùn)用下面公式計(jì)算TJX矩陣。

(5)

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

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

(6)

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

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

(7)

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

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

(8)

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

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

(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í)的聚類數(shù)目。

利用ZBH矩陣存儲(chǔ)此時(shí)的矩形塊的長(zhǎng)度和坐標(biāo)

ZBH(j,1)=JS，

(11)

(12)

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

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

(13)

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

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

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 實(shí)驗(yàn)結(jié)果及分析

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

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

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

2.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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