基于滿二叉樹的二分K－means聚類并行推薦算法＊

陳平華，陳傳瑜

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州510006）

1 引言

隨著網(wǎng)絡(luò)應(yīng)用的飛速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)指數(shù)增長，出現(xiàn)了“信息過載”問題，推薦系統(tǒng)應(yīng)運(yùn)而生［1］。協(xié)同過濾作為應(yīng)用最廣泛的推薦算法，其簡單的模型理念和實(shí)現(xiàn)備受大型企業(yè)青睞［2］。然而，隨著用戶數(shù)和物品數(shù)的指數(shù)上升，計(jì)算量急增，協(xié)同過濾算法遇到了性能瓶頸。于是，通過聚類算法減少協(xié)同過濾中尋找最相似鄰居集的匹配次數(shù)同時(shí)又不降低推薦準(zhǔn)確性成為當(dāng)前推薦領(lǐng)域熱點(diǎn)。

為了減少最相似鄰居集的匹配次數(shù)同時(shí)不降低推薦準(zhǔn)確性，文獻(xiàn)［3］采用中心聚類算法，先求出各樣本與其所屬類別之間的類別關(guān)聯(lián)度，再利用類別關(guān)聯(lián)度區(qū)別對待預(yù)測樣本的最近鄰；文獻(xiàn)［4］利用聚類算法使數(shù)據(jù)平滑，以組合傳統(tǒng)協(xié)同過濾和聚類形成推薦算法；文獻(xiàn)［5］利用蟻群聚類算法，并結(jié)合協(xié)同過濾算法挖掘用戶的隱含模式，從而將相似用戶進(jìn)行較為準(zhǔn)確的分類；文獻(xiàn)［6］將PCA 和聚類算法組合協(xié)同過濾，形成推薦，減少目標(biāo)用戶的最近鄰搜索范圍；文獻(xiàn)［7］組合兩種聚類算法：Kmeans和SOM，以此提高推薦系統(tǒng)的準(zhǔn)確性；文獻(xiàn)［8］利用遺傳算法將聚類和協(xié)同過濾組合起來進(jìn)行項(xiàng)目推薦；文獻(xiàn)［9］將用戶聚類和項(xiàng)目聚類進(jìn)行交叉迭代，使得聚類簇達(dá)到較為穩(wěn)定的狀態(tài)。

不過，傳統(tǒng)聚類算法，如K－means、DBSCAN等，應(yīng)用于推薦系統(tǒng)時(shí)存在如下不足：將用戶歸入最相似目標(biāo)簇后，推薦過程只針對目標(biāo)簇成員，與其他簇成員無關(guān)，可能造成與用戶相似的其他簇內(nèi)成員丟失，降低推薦系統(tǒng)的準(zhǔn)確性。此處，傳統(tǒng)聚類算法（非模糊聚類）不能使聚類對象同時(shí)屬于多個(gè)類別，比如一篇屬于體育又屬于娛樂的新聞報(bào)道，K－means可能將其歸入到體育類別中，也可能歸到娛樂類別中，但不能同時(shí)歸為這兩個(gè)類別。為了解決這些問題，本文提出一種基于滿二叉樹的K－means聚類并行推薦算法K－FBT（BisectingKmeans clustering parallel recommendation algorithm based on Full Binary Tree）。K－FBT 算 法中K值代表的不再是簇的個(gè)數(shù)，而是滿二叉樹的深度，同時(shí)也代表用戶最多可屬于簇的個(gè)數(shù)。由于聚類后的K個(gè)簇并無關(guān)聯(lián)，所以基于K－FBT 算法的推薦過程可并行執(zhí)行，可應(yīng)用MapReduce等分布式系統(tǒng)框架。

2 滿二叉樹

二叉樹是一種應(yīng)用廣泛的非線性數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是每個(gè)節(jié)點(diǎn)至多有兩棵子樹（即二叉樹不存在度大于2的節(jié)點(diǎn)）［10］。二叉樹中有三類節(jié)點(diǎn)：樹根節(jié)點(diǎn)、非葉子節(jié)點(diǎn)、葉子節(jié)點(diǎn)。滿二叉樹是二叉樹的一種特殊情形。滿二叉樹具有以下性質(zhì)：

定義1總節(jié)點(diǎn)數(shù)是2k－1，第i層的節(jié)點(diǎn)數(shù)是2i－1（k代表樹的深度）。

定義2除最后一層無任何子節(jié)點(diǎn)外，其它層上每個(gè)節(jié)點(diǎn)均有兩個(gè)子節(jié)點(diǎn)。

定義3從上往下編號（從1開始），第i個(gè)節(jié)點(diǎn)的左孩子編號是2＊i，右孩子是2＊i＋1。

定義4從上往下編號（從1開始），第i個(gè)節(jié)點(diǎn)的父親編號是i/2（保留到整數(shù)位）。

3 K－means與滿二叉樹

3.1 K－means

MacQueen J提 出 了K－means聚 類 算 法［11］。K－means的主要優(yōu)點(diǎn)是：算法可快速收斂，并得到局部的最優(yōu)解。K－means算法應(yīng)用于推薦系統(tǒng)時(shí)的主要思想是：給定n個(gè)數(shù)據(jù)點(diǎn)（向量）｛X1，X2，…，Xn｝，找到K個(gè)聚類中心｛A1，A2，…，AK｝，使得每個(gè)數(shù)據(jù)點(diǎn)（向量）與其最近的聚類中心的相似度和最大，并以這個(gè)相似度和為目標(biāo)函數(shù)，記作W。設(shè)Sim（Xi，Aj）表示數(shù)據(jù)點(diǎn)Xi和簇中心Aj的相似度，計(jì)算如公式（1）所示：

3.2 K－FBT算法

K－FBT 算法的基本思想是初始數(shù)據(jù)集作為樹根節(jié)點(diǎn)，再通過二分K－means算法將數(shù)據(jù)集分成兩簇，并使這兩個(gè)簇成為其左右孩子節(jié)點(diǎn)。接著，對這兩個(gè)節(jié)點(diǎn)進(jìn)行同樣的操作，直到形成一棵滿二叉樹且深度為K，算法結(jié)束。其中，樹根節(jié)點(diǎn)存儲(chǔ)初始數(shù)據(jù)集，非葉子節(jié)點(diǎn)存儲(chǔ)簇的中心向量，葉子節(jié)點(diǎn)存儲(chǔ)簇的中心向量和簇內(nèi)數(shù)據(jù)集。實(shí)現(xiàn)如算法1所示：

算法1創(chuàng)建滿二叉樹算法

輸入：初始數(shù)據(jù)集Dataset，二叉樹深度K。

輸出：滿二叉樹。

步驟1初始數(shù)據(jù)集設(shè)定為樹根節(jié)點(diǎn)；

步驟2初始化隊(duì)列，樹根節(jié)點(diǎn)入隊(duì)；

步驟3根據(jù)定義1，計(jì)算K層節(jié)點(diǎn)總數(shù)；

步驟4隊(duì)頭元素出隊(duì)，執(zhí)行二分K－means算法；

步驟5將步驟4所得，作為步驟4元素的左右孩子并入隊(duì)；

步驟6步驟3節(jié)點(diǎn)總數(shù)減1，若節(jié)點(diǎn)總數(shù)大于0則執(zhí)行步驟4，否則算法結(jié)束。

3.3 簇內(nèi)凝聚度

通過算法1可得到滿二叉樹。但是，分裂過程中可能存在一種情況：簇內(nèi)已經(jīng)有很高的凝聚度，不再需要分裂。基于此，本文引入簇內(nèi)凝聚度CCL（Cluster Cohesion Level），認(rèn)為CCL達(dá)到一個(gè)閾值α后，就無需繼續(xù)分裂。以Sim（Ui，Centerj）表示第i個(gè)用戶和第j個(gè)簇之間的相似度，Centerj表示第j個(gè)簇的中心向量，Clusterj表示第j個(gè)簇內(nèi)的用戶集，Count（Clusterj）表示第j個(gè)簇內(nèi)用戶集的個(gè)數(shù)。CCL是簇內(nèi)所有用戶集與該簇中心向量相似度之和的均值，計(jì)算如公式（2）所示：

采用CCL作為分裂閾值后，由于有節(jié)點(diǎn)不會(huì)繼續(xù)分裂，因此可能無法構(gòu)成一顆滿二叉樹。針對這種情況，本文采取填補(bǔ)空節(jié)點(diǎn)的方法使其建立一棵偽滿二叉樹。故本文的滿二叉樹存在四類節(jié)點(diǎn)：樹根節(jié)點(diǎn)（用＃表示）、非葉子節(jié)點(diǎn)（用＋表示）、葉子節(jié)點(diǎn)（用－表示）、空節(jié)點(diǎn)（用N 表示）。空節(jié)點(diǎn)僅僅起到占位符的作用，本身并不攜帶任何信息，其作用是方便對多個(gè)簇的預(yù)測結(jié)果進(jìn)行合并時(shí)，計(jì)算每個(gè)簇對應(yīng)的權(quán)值。偽滿二叉樹如圖1所示，線上數(shù)值表示CCL。

Figure 1 A full binary tree by filling blank nodes圖1 填補(bǔ)空節(jié)點(diǎn)的滿二叉樹

4 推薦過程

4.1 層次遍歷

根據(jù)目標(biāo)用戶的歷史行為記錄，建立對應(yīng)的向量空間模型VSM （Vector Space Model）。接著針對目標(biāo)用戶，進(jìn)行層次遍歷算法。其算法主要思想是：從滿二叉樹的第二層開始迭代尋找屬于用戶的K個(gè)最佳葉子節(jié)點(diǎn)（簇）。在K－FBT 算法中，用戶可以歸入到當(dāng)前層的節(jié)點(diǎn)數(shù)目（簇）等于這一層的深度。比如用戶和第三層的四個(gè)節(jié)點(diǎn)（定義1）進(jìn)行相似度比較，用戶可以歸入到相似度靠前的三個(gè)節(jié)點(diǎn)中。然后，用戶再向下遍歷這三個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，總共是六個(gè)節(jié)點(diǎn)（定義2）。由于此時(shí)是處于第四層，用戶可以歸入到相似度靠前的四個(gè)節(jié)點(diǎn)中。最后，直到節(jié)點(diǎn)為葉子節(jié)點(diǎn)，遍歷結(jié)束。算法結(jié)束后，用戶將從屬于K個(gè)葉子節(jié)點(diǎn)（簇）。

由于分裂閾值的原因，用戶從屬的K個(gè)葉子節(jié)點(diǎn)（簇）可能不會(huì)處于滿二叉樹的同一層次，所以需要對上述層次遍歷算法進(jìn)行修正。實(shí)現(xiàn)過程見算法2：

算法2目標(biāo)用戶相似簇發(fā)現(xiàn)算法

輸入：滿二叉樹BT，目標(biāo)用戶特征向量ActiveUse－rVector。

輸出：K個(gè)葉子節(jié)點(diǎn)（簇）。

步驟1初始化四個(gè)隊(duì)列，BT樹根節(jié)點(diǎn)加入隊(duì)列1；

步驟2隊(duì)列1元素依次出隊(duì)，并將該層元素入隊(duì)到隊(duì)列2；

步驟3計(jì)算目標(biāo)用戶和隊(duì)列2中所有元素節(jié)點(diǎn)的相似度，將相似度值和節(jié)點(diǎn)編號加入到隊(duì)列3；

步驟4歸一化隊(duì)列3的相似度值，接著，根據(jù)相似度降序排列，（當(dāng)前深度－隊(duì)列4元素個(gè)數(shù)）之后的隊(duì)列元素出隊(duì)；

步驟5隊(duì)列3元素依次出隊(duì)，若元素為葉子節(jié)點(diǎn)，則加入到隊(duì)列4，否則元素加入到隊(duì)列1；

步驟6若隊(duì)列4元素個(gè)數(shù)小于K且隊(duì)列1非空，執(zhí)行步驟2，否則算法結(jié)束并返回隊(duì)列4。

通過設(shè)定適當(dāng)?shù)姆至验撝担軌蛴行У販p少創(chuàng)建二叉樹時(shí)執(zhí)行K－means算法的次數(shù)，顯著地縮短預(yù)處理時(shí)所需的時(shí)間。另外，對于規(guī)則" 用戶可以歸入當(dāng)前層的節(jié)點(diǎn)數(shù)目等于這一層的深度”也需作出相應(yīng)修改，變更為“用戶可以歸入當(dāng)前層的節(jié)點(diǎn)數(shù)目等于這一層的深度減去已選擇的葉子節(jié)點(diǎn)數(shù)目”，如圖2所示，線上數(shù)值表示目標(biāo)用戶與簇中心的相似度，右邊等式表示目標(biāo)用戶處于該層時(shí)可歸入節(jié)點(diǎn)（簇）數(shù)。

Figure 2 Selecting the optimal Kclusters圖2 選擇最優(yōu)的K 個(gè)簇

4.2 分布式預(yù)測

Figure 3 Executing process of the MapReduce圖3 MapReduce的執(zhí)行過程

根據(jù)上一節(jié)得到的K個(gè)葉子節(jié)點(diǎn)（簇），分別找出和用戶最相似的鄰居集。最后，根據(jù)這K個(gè)鄰居集分別對用戶未評分項(xiàng)目進(jìn)行預(yù)測。由于K個(gè)葉子節(jié)點(diǎn)（簇）之間并無任何關(guān)聯(lián)，所以可以通過并行化的手段來提高推薦系統(tǒng)的性能，同時(shí)增強(qiáng)系統(tǒng)的可擴(kuò)展性。對于大數(shù)據(jù)的處理或者聚類，應(yīng)用MapReduce框架可以較快地完成［12］。所以，本文在Hadoop平臺上利用MapReduce并行處理框架對這K個(gè)不同的簇進(jìn)行分布式處理。由于需要計(jì)算用戶相似度和預(yù)測評分兩個(gè)步驟，所以需要兩個(gè)MapReduce順序組合起來執(zhí)行，處理步驟如下：

Mapper1：首先讀取HDFS中數(shù)據(jù)信息，以行讀取，每行數(shù)據(jù)由樹節(jié)點(diǎn)ID、用戶信息（包括用戶ID、用戶特征向量）組成。接著使用相似度度量方法（如余弦相似度、Pearson相關(guān)系數(shù)、修正余弦相似度等方法），計(jì)算該用戶和目標(biāo)用戶的相似度。最后，輸出新的鍵值對〈樹節(jié)點(diǎn)ID－相似度，用戶ID〉，其中，該輸出鍵值對中key為復(fù)合鍵，主要是為了實(shí)現(xiàn)樹節(jié)點(diǎn)ID 升序且相似度降序排列。

Partitioner1：為了實(shí)現(xiàn)按照樹節(jié)點(diǎn)ID 升序排列，并且若樹節(jié)點(diǎn)ID 相同，則按照相似度降序排列的需求，需要重寫 WritableComparator 類和GroupComparator類。另外，由于Reducer的輸入?yún)?shù)中key是需要根據(jù)樹節(jié)點(diǎn)ID 來劃分，所以在Partitioner類中需要重寫getPartition方法，使分片時(shí)按照樹節(jié)點(diǎn)ID 劃分。

Reducer1：輸入鍵值對〈樹節(jié)點(diǎn)ID－相似度，用戶ID〉。將輸入鍵值對作簡單變換，形成新的鍵值對〈樹節(jié)點(diǎn)ID，用戶ID－相似度〉。由于數(shù)據(jù)已按照相似度降序排列，所以只選取前N個(gè)輸入鍵值對作為輸出鍵值對。

Mapper2：輸入鍵值對〈樹節(jié)點(diǎn)ID，用戶ID－相似度〉。根據(jù)用戶ID 獲取用戶的歷史評分記錄，形成新的鍵值對〈樹節(jié)點(diǎn)ID－項(xiàng)目ID，相似度－用戶評分均值－該項(xiàng)目評分值〉。

Reducer2：輸入鍵值對〈樹節(jié)點(diǎn)ID－項(xiàng)目ID，相似度－用戶評分均值－該項(xiàng)目評分值〉，根據(jù)預(yù)測公式對每個(gè)樹節(jié)點(diǎn)中的項(xiàng)目進(jìn)行評分預(yù)測。最后，形成新的鍵值對〈項(xiàng)目ID，樹節(jié)點(diǎn)ID－參與人數(shù)－預(yù)測分?jǐn)?shù)〉，保留樹節(jié)點(diǎn)ID 和參與人數(shù)是為了對相同項(xiàng)目合并時(shí)權(quán)值的計(jì)算。

根據(jù)上述步驟，可以完成多個(gè)樹節(jié)點(diǎn)（簇）對目標(biāo)用戶未評價(jià)項(xiàng)目的評分預(yù)測，然后將評分高的項(xiàng)目推薦給目標(biāo)用戶。但是，不同樹節(jié)點(diǎn)的推薦結(jié)果中可能存在相同的項(xiàng)目，所以需要將這些相同項(xiàng)目進(jìn)行評分合并。

4.3 合并策略

4.3.1 節(jié)點(diǎn)權(quán)值

由于K個(gè)葉子節(jié)點(diǎn)（簇）的聚合程度不相同，并且所在層次也不相同，所以得到的權(quán)值也應(yīng)不相同。有以下三種情況：

（1）層次越低的葉子節(jié)點(diǎn)（簇）內(nèi)成員會(huì)越少，即層次越低的葉子節(jié)點(diǎn)（簇）的聚合程度應(yīng)該更高，對應(yīng)的權(quán)值應(yīng)更高。

（2）有共同祖先節(jié)點(diǎn)的葉子節(jié)點(diǎn)，自身與目標(biāo)用戶相似度越高，對應(yīng)的權(quán)值就應(yīng)越高。

（3）同一層且無相同父節(jié)點(diǎn)的葉子節(jié)點(diǎn)可能具有不同的祖先節(jié)點(diǎn)。換句話說，祖先集與目標(biāo)用戶相似度越高，對應(yīng)子孫節(jié)點(diǎn)的權(quán)值就應(yīng)該越高。

為了滿足上述三點(diǎn)，本文提出一種節(jié)點(diǎn)權(quán)值計(jì)算方法，記作NodeWeighti，k。根據(jù)定義4，滿二叉樹中任意節(jié)點(diǎn)的所有祖先都可以被獲得，記作NodeSet。NormalSim（i，j）表示目標(biāo)用戶i和歸一化后第j個(gè)簇的相似度值。NodeSet包括自身。計(jì)算如公式（3）所示：

圖4中線上數(shù)值是對圖2中相似度進(jìn)行歸一化后的結(jié)果。圖5中線上數(shù)值表示該節(jié)點(diǎn)（簇）的權(quán)值。從圖4和圖5可以看出，層次越低的葉子節(jié)點(diǎn)（簇）得到的權(quán)值越高；同一層次且相同祖先的節(jié)點(diǎn)的權(quán)值由自身權(quán)值所決定，是正相關(guān)關(guān)系。同一層次且不同祖先的節(jié)點(diǎn)的權(quán)值由祖先節(jié)點(diǎn)的權(quán)值和自身權(quán)值所決定，并且兩者是正相關(guān)關(guān)系。經(jīng)實(shí)驗(yàn)表明，這種節(jié)點(diǎn)權(quán)值的計(jì)算方法能夠有效地提高推薦系統(tǒng)的準(zhǔn)確性。

Figure 4 A full binary tree after normalizing similarities圖4 歸一化后的滿二叉樹

Figure 5 A full binary tree of node weights圖5 節(jié)點(diǎn)權(quán)值的滿二叉樹

4.3.2 人數(shù)權(quán)值

每個(gè)簇內(nèi)參與預(yù)測相同項(xiàng)目的人數(shù)越多，則這個(gè)簇對該項(xiàng)目的評分預(yù)測會(huì)更加準(zhǔn)確。所以，本文認(rèn)為簇內(nèi)對相同項(xiàng)目的預(yù)測人數(shù)應(yīng)作為合并權(quán)值的一部分，記作CountWeight。

4.3.3 最終評分

本文結(jié)合上述兩種策略對公共項(xiàng)目進(jìn)行評分合并。給定：PUi，Ij表示預(yù)測用戶i對項(xiàng)目j的評分，NodeWeight（k，Ui）表示用戶i對于第k個(gè)簇的節(jié)點(diǎn)權(quán)值，CountWeight（k，Ij）表示第k個(gè)簇內(nèi)參與預(yù)測項(xiàng)目j的人數(shù)權(quán)值，Predict（k，Ui，Ij）表示第k個(gè)簇預(yù)測用戶i對項(xiàng)目j的評分。計(jì)算如公式（4）所示：

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)環(huán)境

K－FBT 算法的仿真實(shí)驗(yàn)在具有五個(gè)節(jié)點(diǎn)的計(jì)算機(jī)集群上實(shí)現(xiàn)。集群的單個(gè)節(jié)點(diǎn)采用聯(lián)想ThinkCentre M8400t普通商用臺式機(jī)，電腦具體配置：CPU 是Intel酷睿i7 4770S，內(nèi)存大小是4GB，硬盤大小是1 TB。操作系統(tǒng)采用Linux ubuntu12.10。所有的節(jié)點(diǎn)由一個(gè)千兆以太網(wǎng)交換機(jī)相連，其中一個(gè)節(jié)點(diǎn)配置成NameNode 與Job Tracker，其余的四個(gè)節(jié)點(diǎn)配置為DataNode，MapReduce平臺采用分布式開源平臺Hadoop1.2.1。

5.2 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用目前衡量推薦系統(tǒng)質(zhì)量廣泛使用的MovieLens數(shù)據(jù)集，該數(shù)據(jù)集來自美國明尼蘇達(dá)大學(xué)研究小組GroupLens。它包含了943 名用戶對1 682部電影的評分，每個(gè)用戶至少已經(jīng)評分20 部電影，評分集為｛1，2，3，4，5｝，共100 000條評分記錄。評分越大說明用戶對所評電影的認(rèn)可度越高。實(shí)驗(yàn)中將數(shù)據(jù)集分為10等份，使用留一法交互驗(yàn)證進(jìn)行實(shí)驗(yàn)分析。

5.3 評估標(biāo)準(zhǔn)

針對推薦系統(tǒng)性能評估的方法有很多，如平均絕對誤差、召回率、準(zhǔn)確率、均方根誤差、多樣性和新穎性等，本文采用推薦所用時(shí)間UTIR（Used Time In Recommended）和 平 均 絕 對 誤 差MAE（Mean Absolute Error）來衡量推薦系統(tǒng)的性能好壞。UTIR表示推薦系統(tǒng)對一個(gè)用戶產(chǎn)生推薦結(jié)果的時(shí)間。UTIR主要用來測量推薦效率，UTIR越小，說明推薦效率越高。MAE主要是計(jì)算系統(tǒng)預(yù)測推薦值與用戶真正評價(jià)值之間的差異程度，MAE值越小，系統(tǒng)的推薦質(zhì)量就越高。MAE的定義如公式（5）：

5.4 實(shí)驗(yàn)內(nèi)容

實(shí)驗(yàn)1為了驗(yàn)證K－FBT 算法對初始中心的依賴性，設(shè)計(jì)如下實(shí)驗(yàn)：初始中心在訓(xùn)練集中隨機(jī)選擇，并分別執(zhí)行K－FBT 算法和傳統(tǒng)K－means聚類推薦算法（K－means算法）。接著，根據(jù)推薦結(jié)果和實(shí)際結(jié)果的差異，計(jì)算MAE。反復(fù)進(jìn)行該實(shí)驗(yàn)10次，計(jì)算MAE均值和MAE標(biāo)準(zhǔn)差，實(shí)驗(yàn)結(jié)果如表1和表2所示。

Table 1 Experimental results of K－FBT表1 K－FBT算法的實(shí)驗(yàn)結(jié)果數(shù)據(jù)

Table 2 Experimental results of K－means表2 K－means算法的實(shí)驗(yàn)結(jié)果數(shù)據(jù)

實(shí)驗(yàn)2當(dāng)CCL達(dá)到一個(gè)值后，分裂就應(yīng)該被停止。為了觀察CCL對于推薦結(jié)果的影響，設(shè)計(jì)如下實(shí)驗(yàn)：給定鄰居數(shù)目為20，K＝5 的條件下，通過調(diào)整分裂閾值，觀察MAE值的變化，實(shí)驗(yàn)結(jié)果如圖6所示。

Figure 6 MAEof the K－FBT algorithm（different CCL）圖6 K－FBT 算法的MAE（不同CCL）

實(shí)驗(yàn)3為了驗(yàn)證本文所提出的K－FBT 算法的性能，設(shè)計(jì)如下實(shí)驗(yàn)：將傳統(tǒng)的基于用戶的Kmeans的協(xié)同過濾算法（User－Based Cluster）、基于項(xiàng)目 聚 類 的 協(xié) 同 過 濾 算 法（Item－Based Cluster）、基于遺傳算法的聚類推薦算法（Genetic Cluster）［8］和K－FBT 算法進(jìn)行比對。在測試數(shù)據(jù)集上，這四種算法在不同K的取值上的性能表現(xiàn)如圖7所示。

Figure 7 MAEof the four algorithms（different Kvalue）圖7 四種算法的MAE 比較（不同K 值）

實(shí)驗(yàn)4為了驗(yàn)證用戶鄰居數(shù)的選定對于推薦結(jié)果的影響，設(shè)計(jì)如下實(shí)驗(yàn)：給定K＝7，CCL＝0.976的條件下，將傳統(tǒng)的基于COS的協(xié)同過濾算 法（COS CF）、迭 代 聚 類 調(diào) 整 算 法（Iterative CF）［9］和K－FBT 算法進(jìn)行比對。在測試 數(shù)據(jù)集上，這三種方法在不同近鄰個(gè)數(shù)上的性能表現(xiàn)如圖8所示。

Figure 8 MAEof the three algorithms（different neighbor numbers）圖8 三種算法的MAE 比較（不同鄰居數(shù)）

實(shí)驗(yàn)5為了驗(yàn)證K－FBT算法的高效性，設(shè)計(jì)如下實(shí)驗(yàn)：給定K＝7，CCL＝0.976的條件下，將KFBT算法與傳統(tǒng)基于K－means的協(xié)同過濾算法（Kmeans Cluster）進(jìn)行實(shí)驗(yàn)比較，通過測量UTIR進(jìn)行實(shí)驗(yàn)結(jié)果對比。實(shí)驗(yàn)結(jié)果如圖9所示。

Figure 9 UTIR of the K－FBT and the K－means Cluster（different predicting user numbers）圖9 K－FBT 和K－means Cluster的UTIR 比較（不同的預(yù)測用戶數(shù)）

5.5 實(shí)驗(yàn)分析

從表1 和表2 可發(fā)現(xiàn)，本文K－FBT 算法的MAE均值和MAE標(biāo)準(zhǔn)差均比K－means算法要小，即K－FBT 算法對初始中心的依賴遠(yuǎn)遠(yuǎn)小于傳統(tǒng)的K－means聚類推薦算法。所以，K－FBT 算法可以有效地降低初始中心對于推薦結(jié)果的影響，并且可以提高推薦結(jié)果的準(zhǔn)確性。

從圖6可發(fā)現(xiàn)，當(dāng)CCL≤0.7時(shí)，MAE的結(jié)果都相同。這是因?yàn)楫?dāng)?shù)谝淮畏至押蟮膬纱氐腃CL都會(huì)大于0.7。則當(dāng)CCL≤0.7時(shí)，K－FBT 算法創(chuàng)建的都是深度為2的滿二叉樹（3個(gè)節(jié)點(diǎn)）。當(dāng)CCL＞0.99時(shí)，MAE的結(jié)果亦都是相同的。這是因?yàn)樵诜至堰^程中生成的樹節(jié)點(diǎn)的凝聚度都小于0.99。當(dāng)CCL＞0.99時(shí)，K－FBT 算法創(chuàng)建的都是深度為K的真滿二叉樹。當(dāng)CCL＝0.976時(shí)，KFBT 算法將取得最佳的性能。

由圖7 和 圖8 可 發(fā) 現(xiàn)，K－FBT 算 法 的MAE比其他算法的小，即本文算法的準(zhǔn)確性比其他算法要高。可以看出，滿二叉樹與K－means聚類算法的結(jié)合可以提高推薦的準(zhǔn)確性，可較為有效地解決聚類算法的不足。當(dāng)用戶鄰居數(shù)為25，K＝7，CCL＝0.976 時(shí)，K－FBT 算法表現(xiàn)出最好的推薦效果。

由圖9可發(fā)現(xiàn)，K－FBT 算法平均對每個(gè)用戶進(jìn)行推薦的所用時(shí)間要少于K－means算法所需的時(shí)間。這就證明了K－FBT 算法利用MapReduce并行處理框架，可顯著地縮短對用戶進(jìn)行推薦所用的時(shí)間。從實(shí)驗(yàn)中可發(fā)現(xiàn)，當(dāng)預(yù)測用戶數(shù)小于100時(shí)，K－FBT 算法的推薦所用時(shí)間多于K－means算法，這是因?yàn)镸apReduce框架并行處理需要一定的額外開銷，比如數(shù)據(jù)的分割、數(shù)據(jù)的匯總等。這就造成了當(dāng)預(yù)測用戶數(shù)量較小時(shí)，額外開銷占據(jù)了系統(tǒng)總用時(shí)的絕大部分。但是，當(dāng)預(yù)測用戶數(shù)量較大時(shí)，這部分開銷是可以被忽略的。另外，實(shí)驗(yàn)中也可發(fā)現(xiàn)，預(yù)測用戶數(shù)從400～500的直線斜率要比300～400的直線斜率要陡，這是因?yàn)閷?shí)驗(yàn)環(huán)境只配備了五臺物理電腦。當(dāng)預(yù)測用戶數(shù)大概等于350時(shí)，系統(tǒng)性能達(dá)到最好。實(shí)驗(yàn)表明，如果額外增加物理電腦，可以提高系統(tǒng)性能，即提高系統(tǒng)的可擴(kuò)展性。

6 結(jié)束語

針對聚類算法存在的不足，本文結(jié)合樹結(jié)構(gòu)和K－means聚類算法，將所有用戶聚類到一棵滿二叉樹中。在執(zhí)行過程中，采用簇內(nèi)凝聚度控制分裂，最后創(chuàng)建一棵滿二叉樹。實(shí)驗(yàn)表明：本文算法對于聚類的初始中心依賴要遠(yuǎn)遠(yuǎn)低于其他的Kmeans聚類推薦算法。因此，本文算法不僅有效解決了傳統(tǒng)聚類算法的不足，而且適用于分布式框架，可顯著提高算法執(zhí)行效率和增強(qiáng)可擴(kuò)展性。本文算法中，CCL的設(shè)定需要經(jīng)驗(yàn)或者通過迭代尋找最優(yōu)值，這是本文算法在通用性方面的局限性。接下來，我們將考慮如何改進(jìn)CCL閾值的設(shè)定，使其能自適應(yīng)不同的復(fù)雜推薦系統(tǒng)。

［1］ Resnick P，Varian H R.Recommender systems［J］.Communications of the ACM，1997，40（3）：56－58.

［2］ Breese J S，Heckerman D，Kadie C.Empirical analysis of predictive algorithms for collaborative filtering［C］∥Proc of the 14th Conference on Uncertainty in Artificial Intelligence，1998：43－52.

［3］ Yin Hang，Chang Gui－ran，Wang Xing－wei.Effect of clustering algorithm inK－nearest－neighborhood based collaborative filtering［J］.Journal of Chinese Computer Systems，2013，34（4）：806－809.（in Chinese）

［4］ Xue G R，Lin C，Yang Q，et al.Scalable collaborative filtering using cluster－based smoothing［C］∥Proc of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2005：114－121.

［5］ Cao Bo，Su Yi－dan.Web log mining based on ant clustering［J］.Microcomputer Information，2009（9）：225－226.（in Chinese）

［6］ Yu Xue，Li Min－qiang.Collaborative filtering recommendation model based on effective dimension reduction andKmeans clustering［J］.Application Research of Computers，2009，26（10）：3718－3720.（in Chinese）

［7］ Tsai C F，Hung C.Cluster ensembles in collaborative filtering recommendation［J］.Applied Soft Computing，2012，12（4）：1417－1425.

［8］ Feng Zhi－ming，Su Yi－dan，Qin Hua，et al.Recommendation algorithm of combining clustering with collaborative filtering based on genetic algorithm［J］.Computer Technology and Development，2014，24（1）：35－38.（in Chinese）

［9］ Wang Ming－wen，Tao Hong－liang，Xiong Xiao－yong.A collaborative filtering recommendation algorithm based on iterative bidirectional clustering［J］.Journal of Chinese Information Processing，2008，22（4）：61－65.（in Chinese）

［10］ Yan Wei－min，Wu Wei－min.Data structures（C）［M］.1st edition.Beijing：Tsinghua University Press，2009.（in Chinese）

［11］ MacQueen J.Some methods for classification and analysis of multivariate observations［C］∥Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability，1967：281－297.

［12］ Dean J，Ghemawat S.MapReduce：Simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107－113.

附中文參考文獻(xiàn)：

［3］ 尹航，常桂然，王興偉.采用聚類算法優(yōu)化的K近鄰協(xié)同過濾算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（4）：806－809.

［5］ 曹波，蘇一丹.基于蟻群聚類的top－N推薦系統(tǒng)［J］.微計(jì)算機(jī)信息，2009（9）：225－226.

［6］ 郁雪，李敏強(qiáng).一種結(jié)合有效降維和K－means聚類的協(xié)同過濾推薦模型［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（10）：3718－3720.

［8］ 馮智明，蘇一丹，覃華，等.基于遺傳算法的聚類與協(xié)同過濾組合推薦算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（1）：35－38.

［9］ 王明文，陶紅亮，熊小勇.雙向聚類迭代的協(xié)同過濾推薦算法［J］.中文信息學(xué)報(bào)，2008，22（4）：61－65.

［10］ 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.第1版.北京：清華大學(xué)出版社，2009.