基于改進K-means的K近鄰算法在電影推薦系統中的應用

蔡暢

（遼寧科技大學 遼寧省鞍山市 114051）

推薦系統是通過分析客戶的歷史行為對用戶所感興趣的內容進行預測[1]，它可以幫助用戶找到感興趣的電影，同時可以發現那些不容易被發現的好電影。本文融合改進K-means 算法和K 近鄰算法給用戶推薦感興趣的電影，由于K-means 算法對初始聚類中心敏感，選取不當可能會導致不理想的聚類[2-3]，文獻[4]設計了改進的混合推薦提高算法的收斂速度，采用改進的LeaderRank 方法增強網絡的連通性。文獻[5]提出了一種改進的K-means 算法，IPSGWO-KMeans 算法可以跳出已經找到的較好的聚類中心，從較好的聚類中心附近找到更優解，有更強的尋優能力。推薦算法和K-means 算法一直被研究，但都沒有一個很好的進展。

1 相關基礎

傳統的K-means 算法使用的是隨機采取機制，它的目的是將所有數據點劃分為聚類中心，使簇內方差之和最小化。該算法對初始聚類中心的選擇也會明顯的影響聚類結果。本文用肘部法估算數據的聚類數量K，在開始聚類之前設置一個K 值及每個簇的初始聚類中心，當K-means 算法中沒有指定的K 值時，K-means 參數的最優解是以成本函數最小化為目標，成本函數為各個簇畸變程度之和，每個簇的畸變程度為每個變量點到其類別中心的位置距離的平方和，而簇內成員的緊湊性與簇的畸變程度成正比，畸變程度的改善效果下降幅度最大的位置對應的值就是肘部。

肘部法的核心是SSE（sum of the squared errors,誤差平方和），

其中，Ci是第i 個簇，p 是Ci中的樣本點，mi是Ci的質心(Ci中所有樣本的均值)，SSE 是所有樣本的聚類誤差，代表了聚類效果的好壞。聚類數目K 越多，簇內成員間的緊湊度會隨之提高，SSE 值會隨之降低。當聚類數目K 達到一個最優值后，在持續增加K 值時，簇內成員間的緊湊度的增加幅度以及SSE 值的下降幅度會趨于平緩。

2 改進的算法

2.1 改進的K-means算法

本文提出用最大最小距離算法對K-means 算法做出改進，采用最大最小距離算法隨機選取一個初始聚類中心，剩余的初始聚類中心根據歐式距離準則進行計算獲得，用該算法選取初始聚類中心可以降低聚類的迭代次數，同時可避免聚類中心出現鄰近的情況。改進后的K-means 算法流程：

（1）使用肘部法選取聚類數目K 值，并設置初始的K 個簇為空值。

（2）從測試數據集X={X1,X2...,Xn}中隨機選取一個初始聚類中心Z1。

（3）計算各數據點到Z1的距離，距離Z1最大的數據點作為第二個初始聚類中心Z2。

dij=‖Xi-Zj‖(j=1,2..k;i=1,2...n)

（4）計算其余數據點到Z1，Z2的距離，并求出它們（i ≤ K)中距離的最小值。

di=min[di1,di2](i=1,2,...,n)

W=θ*‖Z1-Z2‖(θ 為選定n 比例系數)

（5）從已知最小距離中計算出最大的距離值，它所對應的數據點作為第i 個（i ≤ K)初始聚類中心。當i>K 或dl

dl=max[min[di1,di2,...dik]]>W

（6）計算數據點Xi(i=1,2,...,n)到初始聚類中心Zi(i=1,2,...k)的距離，按照最小距離準則，將數據分配給距離它們最近的聚類中心。

（7）將分配后的Xi標記到所屬簇zi(i=1,2,...,k）中。計算各簇中所有數據點的平均矢量，更新簇的聚類中心，重復（5）、（6）。

（8）經過多次迭代計算得到最終的聚類結果K 個簇Z={Z1,Z2,...,ZK}和各簇的聚類中心z={z1,z2,...,zk}。

2.2 改進K-means的K近鄰算法

K 近鄰算法是數據挖掘和推薦系統中非常流行的算法，本文提出了改進K-means 的K 近鄰算法,可以為K 近鄰分類減少了計算量，降低時間成本。

改進K-means 算法對訓練集聚類后，計算待分類用戶與各簇聚類中心的距離，距離最小的聚類中心所屬簇中的數據作為待分類用戶的訓練集，在新訓練集中，根據待分類用戶與訓練數據的距離，找到與待分類用戶最近的K 個用戶，取用戶中類別最多的一類作為待分類用戶的類別，再將該類別中電影評分較高的電影推薦給用戶。改進算法的具體步驟如下：

（1）根據改進K-means 算法得到聚類結果K 個簇Z={Z1,Z2,...,Zk}。

（2）計算各簇的聚類中心與待分類用戶u={u1,u2,...,un}的距離，按照最小距離原則，選取距離最小的聚類中心所在的簇。

表1：分析指標表

（3）將簇中數據作為新的訓練集Y，查找與待分類用戶距離最近的K 個最近鄰子集。

（5）根據待分類用戶u 的類別歸屬決策函數確定u 的所屬類別：

Cu=arg max(Su-Zi)

（6）重復操作，直到所有待分類用戶完成分類。

2.3 引入用戶個人信息

在傳統推薦系統中，大部分推薦算法是以用戶對電影評分作為測試數據，會出現數據稀疏問題。以用戶的個人信息作為依據可以緩解這一問題，例如，未成年用戶會更喜歡動漫，女生用戶會給愛情電影評分更高。本文將用戶年齡考慮在內，拼接用戶年齡信息與電影評分向量，將用戶年齡劃分為七個年齡段1-17 歲、18-24 歲、25-34 歲、35-44 歲、45-49 歲、50-55 歲、56+歲，把用戶所屬年齡段設置為值1，其余的值為0，例如某一用戶35 歲，可以表示為[0,0,0,1,0,0,0]。出現用戶數據稀疏時，可根據相近的年齡選取相似性用戶，同時可以緩解冷啟動的問題。

2.4 改進算法在電影推薦中的應用

本文系統分為訓練、測試兩部分。

訓練部分：本文改進K-means 算法是基于電影評分相似度的用戶聚類算法，首先獲取用戶對電影的評分數據，從中隨機選取用戶對看過電影的評分作為第一個初始聚類中心，再根據歐氏距離計算各用戶與第一個初始聚類中心用戶之間相似度，選取其余用戶作為剩余的初始聚類中心，根據訓練集中用戶與初始聚類中心的最小距離進行分配，形成用戶簇。

測試部分：當測試用戶進入推薦系統后，根據用戶對電影評分作為數據點，計算到簇的聚類中心距離，將用戶劃分到距離最近的簇中，將簇中用戶作為新訓練集，在新的電影評分訓練集中查找相似度較高的K 個最近鄰用戶形成最近鄰用戶集合，根據K 個用戶鄰居對已看電影的實際評分來預測用戶對電影的評分值，按照評分進行排序，向用戶推薦電影列表。

3 實驗結果與分析

本文的算法是通過python 實現的，運行環境：Dual-Core Intel Core i5 CPU，主頻2.3GHz，內存8G，Macos64 位操作系統。

為了驗證改進算法的性能，實驗使用了真實的MovieLens 數據集，將數據集按照2：8 的比例隨機劃分為測試集和訓練集。

實驗用三個分析指標衡量電影推薦的結果：準確率、召回率、F1 綜合評定準確率和召回率的調和平均數。

表1 將本文提出的改進算法與融合時間因素和用戶評分特性的協同過濾算法（CF-TP）、K 近鄰算法從上述的三個指標進行對比分析。可直觀的看出推薦結果的優化程度，改進的算法與其他兩種算法相比，推薦結果的準確率明顯提高，同時召回率也有改善，但隨著電影推薦數目的增加準確率隨之遞減。

4 結束語

本文提出了用肘部法確定K 值并且用最大最小距離法優化了K-means 算法，在聚類數據中考慮到用戶年齡信息，最后應用到K近鄰算法中對用戶進行電影推薦。并對本文算法進行實驗評估了，結果表明改進后的算法對電影推薦的準確率等性能都有了明顯的提高。