摘 要：本文通過(guò)對(duì)K-means聚類(lèi)算法和協(xié)同過(guò)濾推薦算法的學(xué)習(xí)研究。針對(duì)基于用戶(hù)的協(xié)同過(guò)濾算法的不足，將改進(jìn)的K-means聚類(lèi)算法融入其中，設(shè)計(jì)了基于K-means聚類(lèi)算法的個(gè)性化推薦算法，并將其應(yīng)用于旅游景點(diǎn)及線(xiàn)路的個(gè)性化推薦中，以提高個(gè)性化推薦質(zhì)量。實(shí)驗(yàn)結(jié)果表明，基于改進(jìn)的K-means聚類(lèi)的協(xié)同過(guò)濾算法緩解了初始數(shù)據(jù)的稀疏性問(wèn)題，針對(duì)不同用戶(hù)喜愛(ài)的旅游景點(diǎn)及線(xiàn)路推薦，在準(zhǔn)確率和召回率兩個(gè)方面證明可以提高個(gè)性化推薦的準(zhǔn)確度。

關(guān)鍵詞：K-means聚類(lèi);協(xié)同過(guò)濾算法;最小生成樹(shù)

中圖分類(lèi)號(hào)：TP183 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2021.03.027

本文著錄格式：劉鑫.融入改進(jìn)的K-means聚類(lèi)的協(xié)同過(guò)濾算法的研究與應(yīng)用[J].軟件，2021，42（03）：097-099

Research and Application of Collaborative Filtering Algorithm Incorporating Improved K-means Clustering

LIU Xin

（Jilin Institute of Architecture and Technology， Changchun? Jilin? 130114）

【Abstract】：This article is based on the study of K-means clustering algorithm and collaborative filtering recommendation algorithm. Aiming at the deficiencies of the user-based collaborative filtering algorithm， the improved K-means clustering algorithm is incorporated into it， and a personalized recommendation algorithm based on the K-means clustering algorithm is designed and applied to the personalized recommendation of tourist attractions and routes In order to improve the quality of personalized recommendations. The experimental results show that the collaborative filtering algorithm based on improved K-means clustering alleviates the sparsity problem of the initial data. It is proved that it can improve the personalization in terms of accuracy and recall rate for different users' favorite tourist attractions and routes recommendation. Recommended accuracy.

【Key words】： K-means clustering;collaborative filtering algorithm;minimum spanning tree

0引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，信息資源呈現(xiàn)幾何級(jí)數(shù)增長(zhǎng)，用戶(hù)在大量的信息中很難獲取到真正需要的數(shù)據(jù)信息。傳統(tǒng)的搜索引擎已無(wú)法滿(mǎn)足用戶(hù)的特殊需求，因此個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生，并成為了解決信息過(guò)載問(wèn)題的有效方法。一個(gè)完整的個(gè)性化推薦系統(tǒng)總體框架包含三個(gè)部分：數(shù)據(jù)特征提取模塊、個(gè)性化推薦模塊、推薦結(jié)果模塊。個(gè)性化推薦系統(tǒng)能夠根據(jù)用戶(hù)個(gè)人喜好自動(dòng)進(jìn)行信息推薦，減少信息的冗余，簡(jiǎn)化用戶(hù)的操作，因此個(gè)性化推薦算法也逐漸成為學(xué)術(shù)界的研究熱點(diǎn)之一[1]。

1主要技術(shù)

1.1協(xié)同過(guò)濾算法及其存在的問(wèn)題

推薦系統(tǒng)中協(xié)同過(guò)濾推薦算法是當(dāng)前應(yīng)用最為廣泛，研究最多，影響最為深遠(yuǎn)的個(gè)性化推薦技術(shù)，協(xié)同過(guò)濾推薦算法的主要思想是：為了更好的服務(wù)目標(biāo)用戶(hù)，為用戶(hù)推薦個(gè)性化的商品信息，需要獲得用戶(hù)的喜好，即在一個(gè)大的數(shù)據(jù)庫(kù)中使用相似度計(jì)算公式計(jì)算搜索目標(biāo)用戶(hù)的N個(gè)最近鄰居，根據(jù)N個(gè)用戶(hù)對(duì)商品喜好的評(píng)分，建立評(píng)分矩陣，并預(yù)測(cè)目標(biāo)用戶(hù)所喜好的商品的評(píng)分，進(jìn)行降序排序，將評(píng)分最高的前M個(gè)商品推薦給目標(biāo)用戶(hù)。協(xié)同過(guò)濾算法的原理圖如圖1所示。首先進(jìn)行算法的輸入，即數(shù)據(jù)信息的采集，包括用戶(hù)的基本信息、商品的基本信息及用戶(hù)與商品間的關(guān)系信息，然后進(jìn)行協(xié)同過(guò)濾算法處理，即相似度計(jì)算，找到N個(gè)最近鄰居，最后得到輸出結(jié)果，即將前M個(gè)商品推薦給目標(biāo)用戶(hù)。協(xié)同過(guò)濾算法依據(jù)初始評(píng)分矩陣，因此存在著數(shù)據(jù)稀疏性問(wèn)題，會(huì)導(dǎo)致推薦準(zhǔn)確性不高[2]。

1.2 K-means 算法

K-means算法是James MacQueen在1967年提出的，K-means算法是一種基于最近距離劃分進(jìn)行聚類(lèi)的算法，算法根據(jù)目標(biāo)函數(shù)求得最近距離計(jì)算相似度，是數(shù)據(jù)挖掘研究領(lǐng)域中最常用的算法之一。K-means的基本思想是首先在預(yù)定的樣本集中隨機(jī)選取K個(gè)質(zhì)心作為初始聚類(lèi)中心，構(gòu)成K個(gè)簇集，然后計(jì)算剩下樣本和 K 個(gè)初始聚類(lèi)中心的距離即相似度，將各個(gè)樣本分別劃分給離他最近也就是相似度的值最大的一個(gè)簇集中，每次劃分后，再根據(jù)現(xiàn)有簇集重新計(jì)算獲得新的聚類(lèi)中心。不斷循環(huán)這個(gè)過(guò)程，直到聚類(lèi)中心不再變化或者函數(shù)滿(mǎn)足了收斂條件[3]。

K-means算法進(jìn)行聚類(lèi)操作，算法原理簡(jiǎn)單，易于操作，基于大數(shù)據(jù)集合進(jìn)行聚類(lèi)的運(yùn)算速度快、效率高。但由于K-means算法中初始的聚類(lèi)中心是由隨機(jī)選取方式選定，因此，在聚類(lèi)過(guò)程中初始聚類(lèi)中心的不確定性會(huì)影響推薦結(jié)果的準(zhǔn)確性。本文提出改進(jìn)的K-means聚類(lèi)算法。

2 改進(jìn)的K-means算法

針對(duì)K-means算法由于初始聚類(lèi)中心不確定帶來(lái)的影響，增加了用戶(hù)的屬性描述，并基于用戶(hù)屬性計(jì)算用戶(hù)相異度的值，作為邊的權(quán)值建立圖結(jié)構(gòu)，應(yīng)用kruskal算法計(jì)算生成初始聚類(lèi)中心，將其用于K-means算法中，該算法可以提高初始聚類(lèi)中心的個(gè)數(shù)和位置的準(zhǔn)確性，提高推薦系統(tǒng)的推薦效率[4]。改進(jìn)的K-means算法的具體步驟如下：

（1）初始用戶(hù)信息，對(duì)系統(tǒng)中用戶(hù)基本信息進(jìn)行預(yù)處理，增加用戶(hù)屬性描述（性別、年齡、學(xué)歷、職業(yè)、興趣愛(ài)好）使用公式1.1計(jì)算用戶(hù)間的相異度值C（不同用戶(hù)相同屬性的相異值的個(gè)數(shù)P（ui≠u(mài)j）與用戶(hù)屬性總個(gè)數(shù)P（ui，uj）的比值），規(guī)定相異度值越小則用戶(hù)間的相似度越大。

公式1.1

（2）根據(jù)公式1.1計(jì)算用戶(hù)相異度值;

（3）將用戶(hù)相異度值C作為邊的權(quán)值，構(gòu)造無(wú)向加權(quán)圖G=（{V}，{E}）;

（4）應(yīng)用Kruskal算法求出圖G的最小生成樹(shù)T= （U，TE），步驟如下：

1）初始化：U=V;TE={ };

2）將邊集E按照從小到大進(jìn)行排序，依次在E集合中尋找最短邊（u，v）

3）如果頂點(diǎn)u，v位于T的兩個(gè)不同的連通分量，則將邊（u，v）加入到最小生成樹(shù)的邊集合TE中，頂點(diǎn)u，v 加入到頂點(diǎn)集合U中;

4）循環(huán)執(zhí)行第③步，直到最小生成樹(shù)T中的連通分量個(gè)數(shù)為1結(jié)束;

（5）在建立的最小生成樹(shù)中選擇權(quán)值最大的N個(gè)WeightMax和權(quán)值最小的N個(gè)WeightMin，求出它們的平均值，在最小生成樹(shù)中刪除大于平均值的邊及孤立的頂點(diǎn)，將剩余頂點(diǎn)作為k個(gè)用戶(hù)集合，然后計(jì)算得到k個(gè)分類(lèi)的集合中心，即構(gòu)成了初始的k個(gè)聚類(lèi)中心。

（6）執(zhí)行K-means聚類(lèi)算法，通過(guò)余弦相似度計(jì)算公式，完成聚類(lèi)劃分。改進(jìn)的K-means算法的流程圖如圖2所示。

3融入改進(jìn)的K-means聚類(lèi)的協(xié)同過(guò)濾算法在旅游景點(diǎn)及線(xiàn)路個(gè)性化推薦系統(tǒng)中的應(yīng)用

本文將融入改進(jìn)的K-means聚類(lèi)的協(xié)同過(guò)濾算法在旅游景點(diǎn)及線(xiàn)路個(gè)性化推薦系統(tǒng)中，通過(guò)用戶(hù)數(shù)據(jù)及評(píng)分矩陣，建立相似用戶(hù)集，完成旅游景點(diǎn)及線(xiàn)路的個(gè)性化推薦[5]。

第一步，數(shù)據(jù)預(yù)處理，初始化用戶(hù)特征屬性信息、各景點(diǎn)游覽路線(xiàn)信息及用戶(hù)對(duì)已游覽過(guò)的景點(diǎn)評(píng)分信息，建立初始評(píng)分矩陣Aij;

第二步，根據(jù)初始評(píng)分矩陣Aij，運(yùn)用kruskal算法獲得個(gè)數(shù)及分布均勻的初始C個(gè)聚類(lèi)中心;再執(zhí)行改進(jìn)的K-means 算法完成對(duì)用戶(hù)的聚類(lèi)劃分，形成不同的相似用戶(hù)簇集;

第三步，對(duì)于目標(biāo)用戶(hù)u，首先根據(jù)余弦相似度計(jì)算公式計(jì)算其與新生成的聚類(lèi)中心的相似度，選擇相似度最大的簇集Cu，將目標(biāo)用戶(hù)劃分到此簇集中;在簇集內(nèi)查找目標(biāo)用戶(hù)的K個(gè)最近鄰居;

第四步，根據(jù)預(yù)測(cè)評(píng)分算法及目標(biāo)用戶(hù)的K個(gè)最近鄰居，對(duì)目標(biāo)用戶(hù)中未評(píng)分的景點(diǎn)項(xiàng)目進(jìn)行預(yù)測(cè)評(píng)分，將評(píng)分由高到低排序，并將前Top N個(gè)線(xiàn)路進(jìn)行推薦。

系統(tǒng)測(cè)試產(chǎn)生的推薦結(jié)果表明：融入改進(jìn)的K-means聚類(lèi)的協(xié)同過(guò)濾算法提高了推薦質(zhì)量，針對(duì)不同用戶(hù)的喜好提高了個(gè)性化推薦的準(zhǔn)確率。

4總結(jié)

本文首先針對(duì)K-means聚類(lèi)算法隨機(jī)選取初始聚類(lèi)中心，導(dǎo)致聚類(lèi)效果不佳的問(wèn)題，將最小生成樹(shù)Kruskal算法應(yīng)用在K-means聚類(lèi)算法中，設(shè)計(jì)了改進(jìn)的K- means聚類(lèi)算法，并將其融入到協(xié)同過(guò)濾算法中，應(yīng)用于旅游景點(diǎn)及線(xiàn)路個(gè)性化推薦系統(tǒng)中，同時(shí)在建立系統(tǒng)的評(píng)分矩陣時(shí)，引入了旅游用戶(hù)、景點(diǎn)信息及用戶(hù)對(duì)線(xiàn)路的特征屬性等信息，解決了協(xié)同過(guò)濾算法在初始數(shù)據(jù)上的稀疏性問(wèn)題，提高推薦算法的準(zhǔn)確率。

參考文獻(xiàn)

[1] 劉榮權(quán)，袁仕芳.基于用戶(hù)屬性聚類(lèi)與矩陣填充的景點(diǎn)推薦算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2020（11）：206-210.

[2] 顧明星，黃偉建.結(jié)合用戶(hù)聚類(lèi)與改進(jìn)用戶(hù)相似性的協(xié)同過(guò)濾推薦[J].計(jì)算機(jī)工程與應(yīng)用，2020（9）：185-189.

[3] 常亮，曹玉婷.旅游推薦系統(tǒng)研究綜述[J].計(jì)算機(jī)科學(xué)，2017 （10）：1-6.

[4] 劉鑫.改進(jìn)的協(xié)同過(guò)濾算法在商品推薦中的應(yīng)用[J].電子技術(shù)與軟件工程，2020（2）：220-222.

[5] 李俊.基于聚類(lèi)的推薦算法研究與應(yīng)用[D].南京：南京郵電大學(xué)，2018.