羅 俊，李勁華

青島大學(xué) 數(shù)據(jù)科學(xué)與軟件工程學(xué)院，山東 青島 266071

◎大數(shù)據(jù)與云計(jì)算◎

LSHBMRPK-means算法及其應(yīng)用

羅 俊，李勁華

青島大學(xué) 數(shù)據(jù)科學(xué)與軟件工程學(xué)院，山東 青島 266071

針對(duì)傳統(tǒng)的k-means聚類算法在處理大數(shù)據(jù)時(shí)算法時(shí)間復(fù)雜度極高和聚類效果不佳的問題，提出了LSHBMRPK-means算法，即基于局部敏感哈希函數(shù)的MapReduce并行化的k-means聚類算法；針對(duì)推薦系統(tǒng)的可擴(kuò)展性問題，將LSHBMRPK-means應(yīng)用于基于聚類的協(xié)同過濾算法。此外，針對(duì)評(píng)分?jǐn)?shù)據(jù)的稀疏性問題，使用LFM，即隱語義模型，對(duì)缺失值進(jìn)行填充，進(jìn)而提出了基于LFM的LSHBMRPK-means聚類算法。實(shí)驗(yàn)結(jié)果表明，LSHBMRPK-means聚類算法提高了聚類效率和質(zhì)量，基于LFM的LSHBMRPK-means協(xié)同過濾算法具有較好的可擴(kuò)展性，同時(shí)解決了因評(píng)分?jǐn)?shù)據(jù)稀疏導(dǎo)致聚類質(zhì)量不好的問題。

大數(shù)據(jù)；k-means；局部敏感哈希函數(shù)；MapReduce；推薦算法

1 引言

隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)的規(guī)模、種類和維度激增，同時(shí)要求處理的效率越來越高。單一機(jī)器節(jié)點(diǎn)的計(jì)算能力已不可能滿足大數(shù)據(jù)的應(yīng)用需求[1]。為了將算法應(yīng)用到分布式并行計(jì)算平臺(tái)，需要將其進(jìn)行并行化改造。k-means聚類算法是一種基于原型的創(chuàng)建數(shù)據(jù)對(duì)象的單層劃分聚類技術(shù)[2]。由于它簡(jiǎn)單、高效，特別是在應(yīng)用于大數(shù)據(jù)時(shí)具有很好的可擴(kuò)展性，因而廣泛用于商務(wù)智能、基因?qū)W、信息檢索、心理學(xué)和醫(yī)學(xué)等領(lǐng)域。

海量高維數(shù)據(jù)的挖掘存在兩大挑戰(zhàn)：數(shù)據(jù)的規(guī)模問題和數(shù)據(jù)的高維度問題。k-means算法在數(shù)據(jù)集增大的同時(shí)，簇?cái)?shù)k值也隨之增大。k-means算法具有獨(dú)立可拆分性，可以通過使用MapReduce編程模型[3]實(shí)現(xiàn)并行化改造。同時(shí)，k-means算法需要多次迭代，若數(shù)據(jù)集中的所有點(diǎn)都與中心點(diǎn)進(jìn)行比較，將導(dǎo)致巨大的計(jì)算代價(jià)，并增加了節(jié)點(diǎn)間的通信開銷。為減少數(shù)據(jù)量，傳統(tǒng)的方法是采樣。但是，采樣的方式會(huì)導(dǎo)致聚類結(jié)果的準(zhǔn)確率不高。局部敏感哈希算法[4]是一種應(yīng)用于大規(guī)模高維數(shù)據(jù)的技術(shù)，它能夠很快搜索到最近鄰的數(shù)據(jù)。它的基本思想是：在原始數(shù)據(jù)空間中有若干數(shù)據(jù)點(diǎn)，將相鄰的數(shù)據(jù)點(diǎn)進(jìn)行相同的投影映射后，在投影的目標(biāo)低維空間中，這些數(shù)據(jù)點(diǎn)以很高的概率聚集在一起。本文提出了LSHBMRPK-means算法，算法首先通過局部敏感哈希函數(shù)對(duì)數(shù)據(jù)集進(jìn)行分區(qū)，選出代表點(diǎn)代表每個(gè)分區(qū)[5]，然后使用MapReduce并行化的k-means算法對(duì)代表點(diǎn)集進(jìn)行聚類。LSHBMRPK-means算法具有很好的可擴(kuò)展性，同時(shí)提高了聚類的效率。

推薦系統(tǒng)的核心思想是將用戶和物品聯(lián)系在一起，即幫助用戶找到用戶感興趣的物品，同時(shí)將物品推薦給對(duì)它有興趣的用戶[6]。傳統(tǒng)的推薦方法主要有基于內(nèi)容的方法[7]、基于鄰域的方法和混合的方法?，F(xiàn)代的推薦方法有：上下文感知的方法、基于語義的方法、基于跨領(lǐng)域的方法、點(diǎn)到點(diǎn)的方法和跨語言的方法。從廣義上來看，推薦技術(shù)屬于數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)的范疇，一個(gè)好的推薦服務(wù)依賴于科學(xué)的推薦算法和大量的學(xué)習(xí)數(shù)據(jù)。面對(duì)大數(shù)據(jù)問題，現(xiàn)在的推薦算法還需要考慮是否能夠處理海量高維數(shù)據(jù)，以及是否能夠大規(guī)模并行化等問題。

協(xié)同過濾算法是推薦系統(tǒng)中經(jīng)常被使用的技術(shù)，它分為：基于鄰域的方法、基于模型的方法以及基于聚類的方法。基于鄰域的方法又分為基于物品的方法和基于用戶的方法。基于用戶的方法首先找到與目標(biāo)用戶有共同興趣的用戶群，然后向目標(biāo)用戶推薦他們感興趣的但其本身不知道的物品項(xiàng)；基于物品的方法通過在所有的用戶歷史行為中查找與目標(biāo)用戶興趣度相似的其他物品，然后將它們推薦給目標(biāo)用戶；基于模型的方法是一種機(jī)器學(xué)習(xí)的方法，它利用目標(biāo)用戶的興趣度自動(dòng)對(duì)物品進(jìn)行分類，然后向目標(biāo)用戶推薦其他可能感興趣的物品。隱語義模型（Latent Factor Model，LFM）[8]是一種典型的基于模型的協(xié)同過濾算法，它是基于機(jī)器學(xué)習(xí)的算法，從相關(guān)理論知識(shí)發(fā)展而來?；诰垲惖膮f(xié)同過濾算法，通過對(duì)評(píng)分?jǐn)?shù)據(jù)集進(jìn)行聚類，得到有相似評(píng)分的簇集。傳統(tǒng)的基于聚類的協(xié)同過濾算法，往往由于評(píng)分?jǐn)?shù)據(jù)比較稀疏，導(dǎo)致聚類效果較差[9]。本文提出了基于LFM的LSHBMRPK-means協(xié)同過濾算法，算法首先利用LFM的方法補(bǔ)全高維稀疏的評(píng)分?jǐn)?shù)據(jù)集矩陣中的缺失值，從而得到一個(gè)完整的評(píng)分?jǐn)?shù)據(jù)集矩陣，然后利用LSHBMRPK-means算法在沒有缺失值的評(píng)分?jǐn)?shù)據(jù)集上以用戶為向量進(jìn)行聚類，預(yù)測(cè)分析測(cè)試集上的用戶的未知評(píng)分。該算法能有效解決因評(píng)分?jǐn)?shù)據(jù)集的數(shù)據(jù)稀疏導(dǎo)致的推薦結(jié)果準(zhǔn)確率不高的問題，此外，算法還可以進(jìn)行離線計(jì)算處理，從而提高推薦系統(tǒng)的可擴(kuò)展性，同時(shí)降低線上計(jì)算負(fù)擔(dān)。

2LSHBMRPK-means算法

2.1 k-means算法及其應(yīng)對(duì)海量高維數(shù)據(jù)的不足

k-means算法是一種基于原型的單層劃分聚類技術(shù)。算法簡(jiǎn)單、高效，被廣泛應(yīng)用。它首先從所有點(diǎn)中按某種方式選出k個(gè)初始質(zhì)心，其中k是用戶期望的簇個(gè)數(shù)，然后將每個(gè)點(diǎn)分配到距離最近的質(zhì)心，形成簇集，再重新計(jì)算質(zhì)心。重復(fù)分配和更新步驟，直到k個(gè)簇的質(zhì)心不發(fā)生變化，算法如算法1所示。

算法1基本的k-means聚類算法

步驟1 Initially choose k centroids to be centroids

步驟2 Repeat

步驟3 Find centroid to which point is closest

步驟4 Adjust the centroids of each cluster

步驟5 Until centroids do not change

在數(shù)列、生物學(xué)、多媒體以及推薦系統(tǒng)等應(yīng)用領(lǐng)域，需要處理規(guī)模和維度都很大的數(shù)據(jù)。傳統(tǒng)的基本k-means聚類算法在處理這些海量高維數(shù)據(jù)時(shí)遇到了困難，一方面是由于數(shù)據(jù)的稀疏性[10]，另一方面是因?yàn)楦呔S數(shù)據(jù)的距離計(jì)算問題[11]。

Verleysen[12]提出了“維度災(zāi)難”的概念，Michael Steinbach和他的同事[13]指出“維度災(zāi)難”是對(duì)高維數(shù)據(jù)進(jìn)行聚類的主要挑戰(zhàn)。高維數(shù)據(jù)與低維數(shù)據(jù)的主要區(qū)別點(diǎn)在于高維數(shù)據(jù)比較稀疏[14]，以及高維空間中距離計(jì)算的不同?！案呔S災(zāi)難”主要體現(xiàn)在兩個(gè)方面：在高維空間中，點(diǎn)間的距離相差不大，幾乎任意兩個(gè)點(diǎn)向量都成直角[15]。

海量高維數(shù)據(jù)給聚類帶來了數(shù)據(jù)的規(guī)模問題和高維度問題，并給現(xiàn)有的數(shù)據(jù)挖掘技術(shù)帶來了極大的挑戰(zhàn)。k-means聚類算法對(duì)低維和高維數(shù)據(jù)都有很好的支持，但如果數(shù)據(jù)的規(guī)模越來越大，同時(shí)k-means算法需要進(jìn)行多次迭代，數(shù)據(jù)集中的所有點(diǎn)都與k個(gè)質(zhì)心進(jìn)行比較將導(dǎo)致巨大的比較計(jì)算代價(jià)，盡管可以使用并行化的k-means聚類算法應(yīng)對(duì)大數(shù)據(jù)的規(guī)模問題，當(dāng)數(shù)據(jù)的維度很大時(shí)，每個(gè)點(diǎn)與中心點(diǎn)間的距離計(jì)算，也將產(chǎn)生很大的計(jì)算代價(jià)。針對(duì)大數(shù)據(jù)的高維度問題，一方面可以進(jìn)行維約簡(jiǎn)從而降低數(shù)據(jù)的維度，另一方面可以通過減少聚類簇?cái)?shù)k的規(guī)模來降低計(jì)算代價(jià)。

基于排序?qū)W習(xí)的推薦算法[16]，推高了推薦算法的性能和用戶的滿意度，但在處理大數(shù)據(jù)問題時(shí)遇到了困難；并行化的大規(guī)模分類數(shù)據(jù)聚類算法[17]，以及啟發(fā)式流程挖掘算法[18]能夠處理大數(shù)據(jù)帶來的挑戰(zhàn)，但不適用于推薦算法。

2.2 局部敏感哈希函數(shù)

局部敏感哈希算法是Piotr Indyk等[19-20]在研究依靠可用的數(shù)據(jù)量線性依賴關(guān)系尋找高維相似度模式中提出的一種新方法。它是一種基于概率的在高維空間中搜索最近鄰的方法，基本思想是通過一組哈希函數(shù)將數(shù)據(jù)點(diǎn)進(jìn)行哈希，使得在新空間中，距離比較近的數(shù)據(jù)點(diǎn)在原始空間中的相似度也比較高。局部敏感哈希的定義如定義1所示。

定義1一組函數(shù)集H={h:S→U}被稱為對(duì)于距離度量函數(shù)D，(r1,r2,p1,p2)-敏感，若任意v,q∈S滿足下面的條件：

（1）Ifv∈B(q,r1)then PrH[h(q)=h(v)]≥p1；

（2）Ifv?B(q,r2)then PrH[h(q)=h(v)]≤p2。

為了使局部敏感哈希函數(shù)的集合有效，其參數(shù)必須滿足不等式：p1＞p2和r1＜r2。

LSHBMRPK-means算法根據(jù)滿足局部敏感哈希函數(shù)的條件確定最佳的哈希函數(shù)集。

2.3 LSHBMRPK-means算法的基本思想

海量高維數(shù)據(jù)面臨兩大挑戰(zhàn)，分別是數(shù)據(jù)的規(guī)模問題和數(shù)據(jù)的高維度問題。當(dāng)k-means處理海量高維數(shù)據(jù)時(shí)，簇?cái)?shù)k值往往很大，k-means的迭代次數(shù)明顯上升，單個(gè)數(shù)據(jù)點(diǎn)與中心點(diǎn)間的距離計(jì)算代價(jià)也很大。若共有n個(gè)數(shù)據(jù)點(diǎn)，k個(gè)中心點(diǎn)，數(shù)據(jù)的維度為d，k-means的中心點(diǎn)距離計(jì)算的代價(jià)為o(n×k×d)。為降低比較計(jì)算的復(fù)雜度，一方面可以降低數(shù)據(jù)的規(guī)模，另一方面可以對(duì)數(shù)據(jù)點(diǎn)進(jìn)行降維處理。本文采用降低數(shù)據(jù)的規(guī)模的方法。傳統(tǒng)的是采用統(tǒng)計(jì)方法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行采樣，但采樣會(huì)影響數(shù)據(jù)的質(zhì)量，導(dǎo)致聚類的準(zhǔn)確率不高。上一小節(jié)提到的局部敏感哈希算法在處理海量高維數(shù)據(jù)時(shí)有很好的效果，因此，將利用局部敏感哈希算法降低數(shù)據(jù)集的規(guī)模，之后，再進(jìn)行聚類。進(jìn)而，k-means的迭代次數(shù)和聚類簇?cái)?shù)k值都會(huì)下降，k-means算法的總復(fù)雜度也就降低了。

另外，k-means算法對(duì)海量高維數(shù)據(jù)進(jìn)行聚類時(shí)，如果每個(gè)點(diǎn)與中心點(diǎn)都進(jìn)行距離計(jì)算再比較，計(jì)算量會(huì)很大。由于在局部敏感哈希算法中，原始空間中距離很近的點(diǎn)通過哈希函數(shù)映射出來的哈希值也是相近的，通過局部敏感哈希算法劃分出來的點(diǎn)屬于同一個(gè)分類。從而可以利用局部敏感哈希算法將距離較近的點(diǎn)分到一個(gè)類別中，并用一個(gè)代表點(diǎn)代表同一分類中的點(diǎn)[5]。通過局部敏感哈希算法生成代表點(diǎn)后，再針對(duì)這些含有代表點(diǎn)的數(shù)據(jù)集，使用MapReduce并行化的k-means聚類算法進(jìn)行聚類，詳見參考文獻(xiàn)[21]。

本文提出的LSHBMRPK-means算法包含如下兩個(gè)主要步驟：

步驟1利用局部敏感哈希函數(shù)生成代表點(diǎn)集。

步驟2使用MapReduce并行化的k-means算法對(duì)由局部敏感哈希函數(shù)生成的代表點(diǎn)集進(jìn)行聚類操作。

算法流程圖如圖1所示。

圖1LSHBMRPK-means算法執(zhí)行過程

2.4 LSHBMRPK-means算法描述

LSHBMRPK-means算法含有的子算法有：利用局部敏感哈希函數(shù)生成代表點(diǎn)集的算法和MapReduce并行化的k-means聚類算法。利用局部敏感哈希函數(shù)生成代表點(diǎn)集的算法如算法2所示。

算法2利用局部敏感哈希函數(shù)生成代表點(diǎn)集

步驟1 Select m hash functions

步驟2 Set hashArray←h1（point），h2（point），…，hm（point）

步驟3 for each hashValue of hashArray do

步驟4 Re-cluster the bucket，get a cluster and its center

步驟5Output（c1，point lists in the radius d）

步驟6 end for

算法2描述了通過局部敏感哈希算法產(chǎn)生出規(guī)模比較小的代表點(diǎn)集的方法。步驟1挑選出m個(gè)可用的局部敏感哈希函數(shù)，而且m比數(shù)據(jù)點(diǎn)的維度小很多。步驟2基于每個(gè)局部敏感哈希函數(shù)計(jì)算出各數(shù)據(jù)點(diǎn)相對(duì)于全部的哈希函數(shù)的哈希值，這些哈希值是全部數(shù)據(jù)點(diǎn)通過局部敏感哈希函數(shù)進(jìn)行降維后得到的點(diǎn)。由于降維后，很多距離比較近的原始點(diǎn)降維后哈希值是相近的，所以，步驟3至步驟6中對(duì)每個(gè)由相同哈希值組成的桶（數(shù)據(jù)集）進(jìn)行聚類。具有相同哈希值組的點(diǎn)聚集在一起，代表點(diǎn)的半徑用參數(shù)d表示。由于具有相同哈希值組的點(diǎn)距離也都比較近，也還有很少的點(diǎn)可能距離不是很近，因而使用k-means聚類算法對(duì)這些點(diǎn)進(jìn)行聚類，聚類的簇?cái)?shù)為1，從而產(chǎn)生代表點(diǎn)代表由相同哈希值組成的桶。進(jìn)而，得到一個(gè)降低規(guī)模的代表點(diǎn)集，此代表點(diǎn)集是通過對(duì)原始數(shù)據(jù)集進(jìn)行局部敏感哈希操作得來的，它能夠有效代表原始數(shù)據(jù)集。然后使用MapReduce編程模型對(duì)基本的k-means聚類算法進(jìn)行并行化改造，使其能夠處理大數(shù)據(jù)問題，且算法將具有較好的可擴(kuò)展性。然后，針對(duì)規(guī)模較小的數(shù)據(jù)集使用MapReduce并行化的k-means聚類算法，所需時(shí)間比在原數(shù)據(jù)集上執(zhí)行MapReduce并行化的k-means算法要少，同時(shí)隨著集群規(guī)模的增大，在一定范圍內(nèi)，算法的執(zhí)行效率也逐漸提高。另外，通過選取代表點(diǎn)的方式能夠防止彼此距離比較近的兩個(gè)點(diǎn)同時(shí)被當(dāng)作初始中心點(diǎn)的問題。同時(shí)，由于數(shù)據(jù)規(guī)模的減少以及k-means的質(zhì)心更新次數(shù)的降低，能有效降低集群的網(wǎng)絡(luò)開銷。

3 基于LFM的LSHBMRPK-means協(xié)同過濾算法

本文將LSHBMRPK-means算法應(yīng)用到基于聚類的協(xié)同過濾算法中，同時(shí)利用LFM補(bǔ)全稀疏的評(píng)分?jǐn)?shù)據(jù)集，提出了基于LFM的LSHBMRPK-means協(xié)同過濾算法，算法的具體算法步驟如下：

步驟1利用評(píng)分?jǐn)?shù)據(jù)集，生成用戶-項(xiàng)目評(píng)分矩陣。由于數(shù)據(jù)量很大，很多評(píng)分?jǐn)?shù)據(jù)是缺失的，因而得到的用戶-項(xiàng)目評(píng)分矩陣是比較稀疏的。

步驟2使用LFM填充稀疏的評(píng)分矩陣。利用用戶的歷史評(píng)分?jǐn)?shù)據(jù)中提供訓(xùn)練用的用戶-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)集，計(jì)算用戶u會(huì)給物品i打幾分。在填補(bǔ)完所有訓(xùn)練用戶的缺失評(píng)分后，得到一個(gè)完整的用戶-項(xiàng)目評(píng)分矩陣 R′。

步驟3使用LSHBMRPK-means算法聚類分析完整的用戶-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)集R′。采用LSHBMRPK-means算法以用戶為向量對(duì)評(píng)分矩陣進(jìn)行聚類分析，通過聚類，獲得相近的用戶類別：U1,U2,…,Uj，通過多次實(shí)驗(yàn)結(jié)果獲得聚類類別的最優(yōu)個(gè)數(shù) j。

步驟4預(yù)測(cè)用戶評(píng)分。一個(gè)用戶a使用推薦系統(tǒng)時(shí)，通過分析該測(cè)試用戶的歷史評(píng)分?jǐn)?shù)據(jù)來計(jì)算用戶a與每個(gè)聚類類別中心的距離，隨后把用戶分配到相應(yīng)的聚類類別Um(m∈[1,j])中去。

通過搜索測(cè)試用戶的聚類類別Um來計(jì)算與它相似的其他用戶。這種方式，不僅使推薦系統(tǒng)算法具備了可擴(kuò)展性，同時(shí)也極大地提高了計(jì)算效率。

用戶a與b之間的相似度Sim(a,b)用公式（1）表示。

通過在目標(biāo)用戶a所在的聚類簇Um中查找它的最近鄰集合來預(yù)測(cè)用戶評(píng)分，提高算法的執(zhí)行效率和可擴(kuò)展性。然后使用公式（2）計(jì)算用戶的未知評(píng)分項(xiàng)。

本算法的流程圖如圖2所示。

圖2 基于LFM的LSHBMRPK-means協(xié)同過濾算法流程圖

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境中Hadoop集群共有三個(gè)節(jié)點(diǎn)，有一個(gè)主節(jié)點(diǎn)，兩個(gè)從節(jié)點(diǎn)。

實(shí)驗(yàn)集群是由搭建在ESXI 5.5上的三臺(tái)Linux虛擬機(jī)組成，各節(jié)點(diǎn)所使用的Hadoop版本均為2.7.1。各節(jié)點(diǎn)的配置信息均為，CPU：10個(gè)2.13 GHz主頻的單元，內(nèi)存：40 GB，磁盤：300 GB。

本文采用GroupLens小組提供的MovieLens數(shù)據(jù)集（http：//grouplens.org/datasets/movielens/20m/.）對(duì)推薦算法進(jìn)行測(cè)評(píng)。實(shí)驗(yàn)選用的數(shù)據(jù)集包含了138 493個(gè)用戶對(duì)27 278部電影的評(píng)分?jǐn)?shù)據(jù)，總的評(píng)分?jǐn)?shù)據(jù)達(dá)20 000 263條。該數(shù)據(jù)集是公開的，具有較高的可靠性。評(píng)分等級(jí)由0.5～5.0，增量是0.5，表示用戶對(duì)電影的喜歡程度越來越高。

數(shù)據(jù)集由4個(gè)文件組成：links.csv、movies.csv、ratings.csv和tags.csv。所有的評(píng)分?jǐn)?shù)據(jù)都在ratings.csv文件中，文件格式為：userId、movieId、ratings、timestamp。Movies.csv收集了movieId、title和genres信息。

4.2 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)內(nèi)容包括：LSHBMRPK-means算法和基于LFM的LSHBMRPK-means協(xié)同過濾算法。針對(duì)LSHBMRPK-means算法，選擇的評(píng)價(jià)指標(biāo)為聚類簇的個(gè)數(shù)、算法執(zhí)行時(shí)間和局部敏感哈希函數(shù)的有效性；針對(duì)基于LFM的LSHBMRPK-means協(xié)同過濾算法，選擇的評(píng)估指標(biāo)有：聚類的簇?cái)?shù)與推薦性能的關(guān)系。推薦系統(tǒng)的離線實(shí)驗(yàn)只需收集用戶的歷史評(píng)分?jǐn)?shù)據(jù)，不需要搭建系統(tǒng)，也無需用戶參與。離線實(shí)驗(yàn)可以很方便地對(duì)很多推薦算法進(jìn)行測(cè)試。本實(shí)驗(yàn)步驟設(shè)計(jì)如下：

步驟1將所有的評(píng)分?jǐn)?shù)據(jù)隨機(jī)均勻的分成M(M=10)份，取其中一份作測(cè)試數(shù)據(jù)集，M-1份訓(xùn)練數(shù)據(jù)。

步驟2用訓(xùn)練數(shù)據(jù)集生成稀疏的用戶-項(xiàng)目評(píng)分矩陣。

步驟3使用LFM補(bǔ)全用戶-項(xiàng)目評(píng)分矩陣，得到完整的評(píng)分?jǐn)?shù)據(jù)。

步驟4使用LSHBMRPK-means算法對(duì)完整的用戶-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)進(jìn)行聚類。

步驟5將目標(biāo)用戶與各聚類中心進(jìn)行比較，找出目標(biāo)用戶的所屬分類。

步驟6在相似度較高的各簇中查找最近鄰居，生成推薦。

步驟7對(duì)推薦結(jié)果進(jìn)行分析和測(cè)評(píng)。

4.3 確定正確的聚類算法的簇個(gè)數(shù)

確定正確的簇的個(gè)數(shù)。將誤差的平方和SSE（公式（3））作為度量聚類質(zhì)量的函數(shù)。

其中x代表對(duì)象，K是簇的個(gè)數(shù)，Ci表示第i個(gè)簇，ci是簇Ci的質(zhì)心。dist是兩個(gè)對(duì)象之間的歐幾里得距離。SSE的值越小，表明聚類效果就越好。但簇個(gè)數(shù)不能過大，同時(shí)也不能過小，因而選擇合適的簇個(gè)數(shù)對(duì)聚類的結(jié)果很關(guān)鍵。通過選取不同的初始簇個(gè)數(shù)，計(jì)算出相應(yīng)的誤差平方和，得到簇個(gè)數(shù)的SSE曲線，如圖3所示。

圖3 簇個(gè)數(shù)的SSE曲線

圖3 中，橫坐標(biāo)表示簇的個(gè)數(shù)，縱坐標(biāo)是對(duì)應(yīng)的誤差平方和。從圖可以看出，當(dāng)簇個(gè)數(shù)為160時(shí)，SSE曲線下降的比其他點(diǎn)要多些，之后隨著簇個(gè)數(shù)的增加，SSE的值變化減少。因此本實(shí)驗(yàn)的簇?cái)?shù)選為160。

4.4 測(cè)試LSHBMRPK-means算法的執(zhí)行時(shí)間

分別在不同集群規(guī)模環(huán)境下對(duì)LSHBMRPK-means算法進(jìn)行測(cè)試，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。測(cè)試MapReduce并行化的算法的有效性，和節(jié)點(diǎn)數(shù)對(duì)并行化算法的影響。

對(duì)同一數(shù)據(jù)集，不同節(jié)點(diǎn)數(shù)對(duì)應(yīng)的算法執(zhí)行時(shí)間如圖4所示。

圖4 不同節(jié)點(diǎn)數(shù)與執(zhí)行時(shí)間測(cè)試結(jié)果

從圖4看到不同的節(jié)點(diǎn)數(shù)對(duì)應(yīng)的算法執(zhí)行時(shí)間。測(cè)試結(jié)果可以看出，多個(gè)節(jié)點(diǎn)環(huán)境相比于單個(gè)節(jié)點(diǎn)環(huán)境，算法的執(zhí)行效率得到了極大提高。在集群環(huán)境下，隨著節(jié)點(diǎn)數(shù)的不斷增加，LSHBMRPK-means算法生成聚類結(jié)果的時(shí)間也會(huì)減少。此外，實(shí)驗(yàn)結(jié)果說明LSHBMRPK-means算法有很好的擴(kuò)展性和加速比。

4.5 測(cè)試局部敏感哈希算法的有效性

通過局部敏感哈希函數(shù)生成的代表點(diǎn)，相比于原始的數(shù)據(jù)集，規(guī)模要減少很多，同時(shí)，代表點(diǎn)集的數(shù)據(jù)質(zhì)量比較高，能夠很好地代表原始數(shù)據(jù)集，在降低數(shù)據(jù)規(guī)模的同時(shí)，也能提高聚類的質(zhì)量。本實(shí)驗(yàn)內(nèi)容是將基于局部敏感哈希函數(shù)的MapReduce并行化的k-means聚類算法與未經(jīng)過局部敏感哈希函數(shù)處理的MapReduce并行化的k-means聚類算法的性能進(jìn)行比較，通過分析兩者的執(zhí)行時(shí)間，以測(cè)試局部敏感哈希函數(shù)的有效性。

對(duì)同一數(shù)據(jù)集和相同節(jié)點(diǎn)數(shù)，基于局部敏感哈希函數(shù)的MapReduce并行化的k-means聚類算法與沒有經(jīng)過局部敏感哈希函數(shù)處理的MapReduce并行化的k-means聚類算法的執(zhí)行時(shí)間進(jìn)行比較，測(cè)試結(jié)果如圖5所示。

圖5 算法執(zhí)行時(shí)間測(cè)試結(jié)果

從兩者的測(cè)試結(jié)果可以看出，由于局部敏感哈希降低了數(shù)據(jù)的規(guī)模，基于局部敏感哈希的MapReduce并行化k-means聚類算法在處理海量高維數(shù)據(jù)時(shí)具有很好的執(zhí)行效率，同時(shí)也說明了通過局部敏感哈希函數(shù)生成的代表點(diǎn)集能夠有效的代表原始數(shù)據(jù)集。

4.6 測(cè)試不同聚類個(gè)數(shù)對(duì)推薦性能的影響

使用LFM對(duì)評(píng)分矩陣進(jìn)行填充補(bǔ)全后，使用LSHBMRPK-means算法對(duì)評(píng)分?jǐn)?shù)據(jù)以用戶為向量進(jìn)行聚類操作。通過實(shí)驗(yàn)，記錄了推薦性能與聚類個(gè)數(shù)的關(guān)系如圖6所示。

圖6 推薦性能與聚類個(gè)數(shù)關(guān)系圖

圖6 中，橫坐標(biāo)表示聚類個(gè)數(shù)，縱坐標(biāo)是其對(duì)應(yīng)的平均絕對(duì)誤差（MAE）。從聚類個(gè)數(shù)與MAE的關(guān)系曲線可以看出，隨著聚類個(gè)數(shù)的增長(zhǎng)，MAE先減少，后又上升，在聚類個(gè)數(shù)為140左右時(shí)，MAE達(dá)到最低點(diǎn)，此時(shí)，推薦質(zhì)量最高。

5 結(jié)束語

本文針對(duì)基本的k-means聚類算法在處理大數(shù)據(jù)時(shí)的不足，提出了LSHBMRPK-means算法。實(shí)驗(yàn)證明LSHBMRPK-means算法具有較好的可擴(kuò)展性，且局部敏感哈希函數(shù)能夠有效降低數(shù)據(jù)的規(guī)模，提高計(jì)算效率。并將LSHBMRPK-means算法應(yīng)用到基于聚類的推薦算法中，解決推薦算法的可擴(kuò)展性問題。同時(shí)針對(duì)評(píng)分?jǐn)?shù)據(jù)的稀疏性問題，本文使用LFM方法對(duì)評(píng)分?jǐn)?shù)據(jù)集中的缺失值進(jìn)行填充。通過實(shí)驗(yàn)證明基于LFM的LSHBMRPK-means協(xié)同過濾算法具有較好的可擴(kuò)展性，同時(shí)解決了因評(píng)分?jǐn)?shù)據(jù)稀疏導(dǎo)致推薦準(zhǔn)確率不高的問題。

[1]孟小峰，慈祥.大數(shù)據(jù)管理：概念，技術(shù)與挑戰(zhàn)[J].計(jì)算機(jī)研究與發(fā)展，2013，50（1）：146-169.

[2]Tan P N，Steinbach M，Kumar V.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2006.

[3]Dean J，Ghemawat S.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

[4]Datar M，Immorlica N，Indyk P，et al.Locality-sensitive hashing scheme based on p-stable distributions[C]//Proceedings of the Twentieth Annual Symposium on Computational Geometry.ACM，2004：253-262.

[5]李秋虹.基于MapReduce的大規(guī)模數(shù)據(jù)挖掘技術(shù)研究[D].上海：復(fù)旦大學(xué)，2013.

[6]項(xiàng)亮.推薦系統(tǒng)實(shí)戰(zhàn)[M].北京：人民郵電出版社，2012：1-2.

[7]Balabanovic M，Shoham Y.Learning information retrieval agents：Experiments with automated web browsing[C]//On-line Working Notes of the AAAI Spring Symposium Series on Information Gathering from Distributed，Heterogeneous Environments，1995：13-18.

[8]Golub G H，Reinsch C.Singular value decomposition and least squares solutions[J].Numerische Mathematik，1970，14（5）：403-420.

[9]夏培勇.個(gè)性化推薦技術(shù)中的協(xié)同過濾算法研究[D].山東青島：中國(guó)海洋大學(xué)，2011.

[10]Aggarwal C C，Yu P S.Finding generalized projected clusters in high dimensional spaces[C]//ACM Sigmod International Conference on Management of Data，2000，29（2）：70-81.

[11]Aggarwal C C，Hinneburg A，Keim D A.On the surprising behavior of distance metrics in high dimensional space[M].Berlin Heidelberg：Springer，2001.

[12]Verleysen M.Learning high-dimensional data[J].Nato Science Series Sub Series III Computer and Systems Sciences，2003，186：141-162.

[13]Steinbach M，Ert?z L，Kumar V.The challenges of clustering high dimensional data[M]//New directions in statistical physics.Berlin Heidelberg：Springer，2004：273-309.

[14]Donoho D L.High-dimensional data analysis：The curses and blessings of dimensionality[J].AMS Math Challenges Lecture，2000：1-32.

[15]Rajaraman A，Ullman J D.Mining of massive datasets[M].Cambridge：Cambridge University Press，2012.

[16]黃震華，張佳雯，田春岐，等.基于排序?qū)W習(xí)的推薦算法研究綜述[J].軟件學(xué)報(bào)，2016，27（3）：691-713.

[17]丁祥武，郭濤，王梅，等.一種大規(guī)模分類數(shù)據(jù)聚類算法及其并行實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展，2016，53（5）.

[18]魯法明，曾慶田，段華，等.一種并行化的啟發(fā)式流程挖掘算法[J].軟件學(xué)報(bào)，2015，26（3）：533-549.

[19]Har-Peled S，Indyk P，Motwani R.Approximate nearest neighbor：Towards removing the curse of dimensionality[J].Theory of Computing，2012，8（1）：321-350.

[20]Indyk P，Motwani R.Approximate nearest neighbors：Towards removing the curse of dimensionality[C]//Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing.ACM，1998：604-613.

[21]Zhao Weizhong，Ma Huifang，He Qing.Parallel k-means clustering based on mapreduce[C]//International Conference on Cloud Computing，2009：674-679.

LUO Jun,LI Jinhua

College of Data Science and Software Engineering,Qingdao University,Qingdao,Shandong 266071,China

LSHBMRPK-means algorithm and its application.Computer Engineering and Applications.Computer Engineering and Applications,2017,53（21）：62-67.

To deal with the problems that time complexity is extremely high and the result of clustering ispoor when basic k-means algorithm is used to handle on big data issues,the paper proposes LSHBMRPK-means algorithm,locality sensitive hashing-based MapReduce parallelized k-means algorithm.Due to the scalability problem of recommendation system,the paper applies LSHBMRPK-means algorithm to cluster-based collaborative filtering algorithm.In addition,to handle on the issue of sparsity in the rating dataset,the paper uses the method of LFM to fill in the sparse rating dataset,and proposes LFM-based LSHBMRPK-means collaborative filtering algorithm.Primary experiments show that LSHBMRPK-means can improve the efficiency and quality of clustering,the proposed algorithm combined with the filtering algorithm has a good scalability,and at the same time it has solved the problem of poor clustering quality caused by the sparse rating dataset.

big data;k-means;locality sensitive hashing function;MapReduce;recommendation algorithm

A

TP311

10.3778/j.issn.1002-8331.1605-0227

羅?。?989—），男，碩士研究生，研究領(lǐng)域?yàn)檐浖_發(fā)方法與技術(shù)；李勁華（1963—），通訊作者，男，博士，教授，研究領(lǐng)域?yàn)檐浖こ?、軟件理論、?shù)據(jù)科學(xué)，E-mail：lijh@qdu.edu.cn。

2016-05-18

2016-10-11

1002-8331（2017）21-0062-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-12-02,http://www.cnki.net/kcms/detail/11.2127.TP.20161202.1503.030.html