趙玉明, 舒紅平, 魏培陽, 劉 魁

(成都信息工程大學(xué)軟件工程學(xué)院；成都信息工程大學(xué)軟件自動生成與智能服務(wù)四川省重點(diǎn)實(shí)驗(yàn)室，成都 610225)

作為知識庫發(fā)現(xiàn)的一個(gè)步驟，數(shù)據(jù)挖掘可以幫助人們從大型數(shù)據(jù)庫中提取模式、關(guān)聯(lián)、變化、異常及有意義的結(jié)構(gòu)[1]。其中，聚類是數(shù)據(jù)挖掘的重要研究方向，可以將數(shù)據(jù)對象分成簇或類，讓同一個(gè)簇中的對象具有很高的相似性，而不同簇的對象相異。聚類主要源于很多學(xué)科領(lǐng)域，包括：數(shù)學(xué)、計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)、生物學(xué)和經(jīng)濟(jì)學(xué)等[2]。在不同的領(lǐng)域中，都有適用于該領(lǐng)域的聚類技術(shù)，并被用來衡量數(shù)據(jù)之間的相似性，從而對該領(lǐng)域的樣本進(jìn)行有效的劃分。

聚類算法可以分為劃分聚類、層次聚類以及密度聚類等。它們的共性就是采用歐式距離來衡量類之間的距離，如最近距離單連接(single-link)、最遠(yuǎn)距離全連接(complete-link)、平均距離聚類(group-average)和中心距離聚類(centroid-similarity)。同時(shí)，聚類的基本的框架是搜索和合并，所以每次都要掃描整體數(shù)據(jù)，進(jìn)行大量的歐式距離計(jì)算。而在此過程中會遇到如下的3個(gè)問題：

(1)在數(shù)據(jù)分布相對離散的時(shí)候，數(shù)據(jù)集中存在大量的空值，如果仍用歐氏距離，反復(fù)掃描整個(gè)數(shù)據(jù)集，則會進(jìn)行大量無意義的計(jì)算。導(dǎo)致聚類的時(shí)間效率受到很大的影響，如果數(shù)據(jù)量很大，會導(dǎo)致內(nèi)存不足的問題。

(2)在數(shù)據(jù)分布相對離散的時(shí)候，使用歐式距離，無法很好的衡量出不同簇之間數(shù)據(jù)的依賴性以及分布密度不均衡的特點(diǎn)。同時(shí)缺乏從數(shù)據(jù)的整體分布進(jìn)行聚類，導(dǎo)致聚類的質(zhì)量產(chǎn)生嚴(yán)重的影響。

(3)在數(shù)據(jù)分布相對離散的時(shí)候，使用歐式距離，計(jì)算不同簇之間的距離。更多考慮共同項(xiàng)之間的距離，忽略非共同項(xiàng)之間可能蘊(yùn)藏的信息。尤其在數(shù)據(jù)分布呈現(xiàn)極度稀疏性的時(shí)候，歐式聚類缺乏考慮數(shù)據(jù)上下文之間的關(guān)系，無法達(dá)到預(yù)計(jì)的聚類效果。

在信息論中，KL(Kullback-Leibler)散度用來衡量用一個(gè)分布來擬合另一個(gè)分布時(shí)候產(chǎn)生的信息損耗。典型情況下，P表示數(shù)據(jù)的真實(shí)分布，Q表示數(shù)據(jù)的理論分布、模型分布或P的近似分布。當(dāng)兩個(gè)隨機(jī)分布相同時(shí)，它們的相對熵為零，當(dāng)兩個(gè)隨機(jī)分布的差別增大時(shí)，它們的相對熵也會增大。KL的值越大，說明兩個(gè)分布差距越大，KL為零則說明分布近似相同[3]。目前，KL散度主要最為圖像、信號、聲音信號的處理上，文獻(xiàn)[3,5-6]的作者，已將開始將KL散度引入到相似性度量上，并且已經(jīng)取得很好的效果。在文獻(xiàn)[4]中，使用KL散度來計(jì)算用戶的相似性，進(jìn)而應(yīng)用在協(xié)同過濾算法中，減少了用戶評分稀疏性的問題，提高了推薦的質(zhì)量和效率。

基于以上分析，在面對稀疏數(shù)據(jù)集的聚類過程中，提供以下的聚類思路：

(1)通過預(yù)聚類，根據(jù)整體數(shù)據(jù)集的分布特點(diǎn)，將不同簇之間的數(shù)據(jù)進(jìn)行聚類[7]。解決沒有考慮數(shù)據(jù)整體分布的缺點(diǎn)。

(2)構(gòu)建整體數(shù)據(jù)集的概率矩陣，然后計(jì)算KL矩陣，根據(jù)KL矩陣合并數(shù)據(jù)。完成對數(shù)據(jù)集的第一次聚類。在計(jì)算KL矩陣的時(shí)候，借助預(yù)聚類中數(shù)據(jù)的分布特性，考慮不同數(shù)據(jù)蘊(yùn)含的信息[8]。解決沒有考慮非共同項(xiàng)之間距離以及數(shù)據(jù)本身信息的缺點(diǎn)。

(3)在完成第一次聚類后，再次重復(fù)以上的步驟，直到最后的距離矩陣[9]無法指導(dǎo)聚類為止。而在此過程中，數(shù)據(jù)只需要在預(yù)聚類過程中讀入內(nèi)存，完成對數(shù)據(jù)的預(yù)聚類。后期的工作是處理概率矩陣和距離矩陣。解決了反復(fù)掃描數(shù)據(jù)，進(jìn)行大量計(jì)算的問題。

1 KL散度的引入及數(shù)據(jù)特征分析

在介紹相對熵之前，首先了解什么是信息熵[10]。

一個(gè)隨機(jī)變量X的可能取值為X={x1,x2,…,xn}，對應(yīng)的概率為P(X=xi)(i=1,2,3,…,n)，則隨機(jī)變量X的熵定義為：

(1)

信息熵主要是反應(yīng)信息的不確定性，在機(jī)器學(xué)習(xí)中，它的一個(gè)很重要的作用是可以為做決策提供一定的判斷依據(jù)。

在概率學(xué)和統(tǒng)計(jì)學(xué)上，經(jīng)常會使用一種更簡單的、近似的分布來替代觀察數(shù)據(jù)或太復(fù)雜的分布。KL散度能度量使用一個(gè)分布來近似代替另一個(gè)分布時(shí)所損失的信息。

相對熵又稱互熵、交叉熵、鑒別信息、Kullback熵[11]、Kullback-Leible散度(即KL散度)等。設(shè)P(x)和Q(x)是X取值的兩個(gè)概率概率分布，則P對Q的相對熵為:

(2)

相對熵突出的特點(diǎn)是非對稱性[12]，也就是D(P||Q)和D(Q||P)是不相等的，但是表示的都是P和Q之間的距離，在本文算法設(shè)計(jì)中采取兩者的平均值(DSKL)作為兩個(gè)簇或者類之間的距離，即

(3)

在聚類過程中，假設(shè)要聚類的數(shù)據(jù)為：X={X1,X2,…,Xn-1,Xn}。X是n個(gè)Rx(x=1,2…,m-1,m)空間的數(shù)據(jù)。其基本的分布見表1。

表1 數(shù)據(jù)分布表

在以上的數(shù)據(jù)分布中，每一個(gè)Xi所對應(yīng)的m都不完全相同，并且數(shù)據(jù)的稀疏性很大。設(shè)N是數(shù)據(jù)集的個(gè)數(shù)，M是每個(gè)數(shù)據(jù)的最大空間維度，V表示非零數(shù)據(jù)的個(gè)數(shù)，K表示此數(shù)據(jù)集的稀疏度。則

(4)

通常認(rèn)為K<5%的時(shí)候，可以將這類數(shù)據(jù)集歸納為稀疏性數(shù)據(jù)。

2 基于KL散度的聚類算法(KL-cluster)

2.1 數(shù)據(jù)預(yù)聚類

首先，掃描整體數(shù)據(jù)，對稀疏數(shù)據(jù)集上的數(shù)據(jù)進(jìn)行整體的預(yù)聚類。預(yù)聚類是完成對整體數(shù)據(jù)所屬類別的確定，可以在整體上分析數(shù)據(jù)[13]。在確定好具體的類別數(shù)目后，就可以對每個(gè)簇中的數(shù)據(jù)所屬類別進(jìn)行處理。從而為形成概率矩陣提供依據(jù)。所以預(yù)聚類的結(jié)果直接影響到以后的聚類效果。

在進(jìn)行預(yù)聚類的時(shí)候，最為關(guān)鍵的就是聚類數(shù)目的確定。在文獻(xiàn)[1]中，提供了一種基于層次思想的計(jì)算方法，即COPS。摒棄了傳統(tǒng)的針對數(shù)據(jù)集的反復(fù)聚類，而是先掃描整體數(shù)據(jù)集，獲得聚類特征值，然后自底向上地生成不同層次的數(shù)據(jù)集劃分,增量地構(gòu)建一條關(guān)于不同層次劃分的聚類質(zhì)量曲線Q(C)，曲線極值點(diǎn)所對應(yīng)的劃分用于估計(jì)最佳的聚類數(shù)目。為此，在數(shù)據(jù)的預(yù)聚類階段采用了此種方法，對數(shù)據(jù)的整體分布進(jìn)行分析。通過預(yù)聚類形成的Q(C)曲線，可以直觀的看到每個(gè)數(shù)據(jù)分布的依賴性、噪音影響以及邊界模糊等情況。為確定每個(gè)數(shù)據(jù)集的聚類數(shù)目提供良好的依據(jù)，同時(shí)為概率矩陣和KL矩陣的構(gòu)建提供精確的標(biāo)準(zhǔn)。完整的設(shè)計(jì)過程可以參考文獻(xiàn)[1]。

2.2 基于KL散度的聚類過程

在聚類過程中，首先根據(jù)預(yù)聚類形成的類別數(shù)目，將每個(gè)簇中的數(shù)據(jù)進(jìn)行分類，然后統(tǒng)計(jì)每個(gè)簇中的數(shù)據(jù)在預(yù)聚類形成的類別上的頻率，形成整體數(shù)據(jù)集上的概率矩陣[13](probabilistic matrix，PM)。然后根據(jù)概率矩陣計(jì)算任意兩個(gè)簇之間的距離矩陣，KL距離矩陣[14](distance matrix，DM)，根據(jù)距離矩陣，將距離矩陣中的最小的兩個(gè)簇合并，再次在新形成的數(shù)據(jù)集上構(gòu)造概率矩陣和距離矩陣。重復(fù)以上的步驟。通過以上的遞歸調(diào)用，最后構(gòu)造出來的距離矩陣無法指導(dǎo)數(shù)據(jù)合并，此時(shí)完成聚類。

2.2.1 概率矩陣的形成過程

通過預(yù)聚類過程，離散數(shù)據(jù)集上的數(shù)據(jù)分為k(k=1,2…,k-1,k)類。然后循環(huán)統(tǒng)計(jì)各簇中的數(shù)據(jù)在k類數(shù)據(jù)上分頻率分布，這樣就會形成一個(gè)n×k的概率矩陣。通過這樣的方法就可以將稀疏數(shù)據(jù)根概率分布，集中在k類上，可以完成對稀疏性數(shù)據(jù)第一步收斂，減少稀疏性的弊端。形成的概率矩陣如式(5)所示：

(5)

2.2.2 距離矩陣的形成過程

根據(jù)以上的概率矩陣，分別計(jì)算矩陣中任意一行和其他一行之間的KL距離，形成整體數(shù)據(jù)集上的KL矩陣。在KL散度介紹中也談到了KL具有非對稱性，這里采用任意兩行相互計(jì)算距離的平均值作為實(shí)際的KL值[14]。剩下的部分都用0來填充，最后形成如式(6)所示的上三角概率矩陣[15]：

(6)

式(7)中：DM12的計(jì)算方式如式(7)所示：

(7)

通過形成的KL矩陣，將距離矩陣中小于一定精度的值所代表的兩行數(shù)據(jù)合并[16]。通過以上過程完成對數(shù)據(jù)集的一次合并，形成新的數(shù)據(jù)集。對合并后形成的數(shù)據(jù)集，按照上面的過程形成新的概率矩陣和距離矩陣，再次完成數(shù)據(jù)的合并。通過不斷地重復(fù)，直到KL矩陣無法達(dá)到合并數(shù)據(jù)的精度后，完成所有數(shù)據(jù)集的聚類[17]。具體的算法流程如下如圖1所示。

圖1 KL聚類算法流程圖

KL_cluster算法：

表2 KL聚類算法

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)選擇

為了驗(yàn)證本算法的有效性，并且本算法主要針對的是離散性數(shù)據(jù)集。一方面，引用公開數(shù)據(jù)集MovieLens中最新的數(shù)據(jù)，ML-Lastest-Small和Yahoo Music作為數(shù)據(jù)集。另一方面，在The MovieDB中下載數(shù)據(jù)，然后將數(shù)據(jù)清洗、整理，得到179位觀眾對國內(nèi)外將近180部電影評分的數(shù)據(jù)集，這里簡稱為MVD。來驗(yàn)證算法的有效性。數(shù)據(jù)基本情況見表3。

表3 數(shù)據(jù)基本信息

3.2 過程分析

3.2.1 算法評價(jià)指標(biāo)

在算法準(zhǔn)確率上，使用本文算法和常用的K-Means算法以及K-Prototypes算法進(jìn)行對比，同時(shí)也使用誤差平方和指標(biāo)(SSE)進(jìn)行評判。具體的誤差平方和計(jì)算公式如式(8)所示：

(8)

式(8)中：x表示數(shù)據(jù)集中數(shù)據(jù)；μ表示類的中心點(diǎn)。通過此方法可以評估出聚類中心的準(zhǔn)確度。

3.2.2 預(yù)聚類分析

首先對每個(gè)數(shù)據(jù)集上的數(shù)據(jù)集進(jìn)行預(yù)聚類。根據(jù)文獻(xiàn)[1]的方法。得到的實(shí)驗(yàn)結(jié)果如圖3和圖4所示。

通過預(yù)聚類，可以發(fā)現(xiàn)，聚類數(shù)目從最優(yōu)變化到變到兩邊次優(yōu)的時(shí)候，聚類質(zhì)量發(fā)生大幅度下降。在圖2和圖3中，可以明顯看到有兩個(gè)基本重合的簇，數(shù)據(jù)存在一定的關(guān)聯(lián)性。而通過這種方法可以很好的監(jiān)測出數(shù)據(jù)依賴關(guān)系，同時(shí)為預(yù)聚類提供正確的結(jié)果。圖4中，在達(dá)到最佳的聚類數(shù)10之前，曲線的變化很小，說明數(shù)據(jù)由于密度分布不均勻、邊界模糊的情況，尤其是在聚類數(shù)目達(dá)到8的時(shí)候，Q(C)曲線出現(xiàn)了一定的上升趨勢。

圖2 MDB的預(yù)聚類結(jié)果

圖3 MovieValue的預(yù)聚類結(jié)果

圖4 MovieValue的預(yù)聚類結(jié)果

通過以上分析，預(yù)聚類過程中充分考慮了數(shù)據(jù)分布的特點(diǎn)，為整體的數(shù)據(jù)集類別劃分提供非常精準(zhǔn)的依據(jù)。

3.2.3 實(shí)驗(yàn)結(jié)果對比分析

通過實(shí)驗(yàn)，將本文提出的基于KL距離的聚類算法、K-Means以及K-Prototypes進(jìn)行對比，其結(jié)果見表4。

本文算法與K-Means以及K-Prototypes運(yùn)行時(shí)間的對比見表5。

表4 SSE對比分析

表5 運(yùn)行時(shí)間對比

從以上的實(shí)驗(yàn)結(jié)果可以看出，KL-cluster算法相比于傳統(tǒng)的K-Means和K-Prototypes，聚類的準(zhǔn)確度上有了明顯的提高。而運(yùn)行時(shí)間在某種程度上增加，時(shí)間差距在0.08～0.67 s。原因是在預(yù)聚類中占用了一段時(shí)間，雖然犧牲了一定的時(shí)間效率，但是針對稀疏性的數(shù)據(jù)集上的聚類質(zhì)量得到大幅度的提高。

4 結(jié)語

聚類算法是機(jī)器學(xué)習(xí)[18]中經(jīng)常使用的一類算法，傳統(tǒng)的K-Means算法并不能很好的處理數(shù)據(jù)稀疏性問題，在聚類的質(zhì)量上產(chǎn)生嚴(yán)重的誤差。為了解決此問題，提出了一種基于KL散度[19]的聚類算法。算法首先通過預(yù)聚類綜合考慮了數(shù)據(jù)的分布情況，然后對將整體的數(shù)據(jù)進(jìn)行聚類，劃分類別。然后根據(jù)的數(shù)據(jù)分布情況構(gòu)建概率矩陣，計(jì)算KL矩陣。最后通過KL矩陣知道數(shù)據(jù)聚類。通過這樣的迭代過程完成聚類[20]。通過這種方式可以減少序言中提到的三個(gè)問題，提升對稀疏數(shù)據(jù)集中聚類質(zhì)量和效率[21]。