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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

(3)

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

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

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

(4)

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

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

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

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

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

2.2 基于KL散度的聚類過程

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

2.2.1 概率矩陣的形成過程

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

(5)

2.2.2 距離矩陣的形成過程

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

(6)

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

(7)

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

圖1 KL聚類算法流程圖

KL_cluster算法：

表2 KL聚類算法

3 實驗與分析

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

為了驗證本算法的有效性，并且本算法主要針對的是離散性數(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。來驗證算法的有效性。數(shù)據(jù)基本情況見表3。

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

3.2 過程分析

3.2.1 算法評價指標

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

(8)

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

3.2.2 預(yù)聚類分析

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

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

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

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

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

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

3.2.3 實驗結(jié)果對比分析

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

本文算法與K-Means以及K-Prototypes運行時間的對比見表5。

表4 SSE對比分析

表5 運行時間對比

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

4 結(jié)語

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