蔡暢

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

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

1 相關基礎

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

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

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

2 改進的算法

2.1 改進的K-means算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1：分析指標表

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

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

Cu=arg max(Su-Zi)

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

2.3 引入用戶個人信息

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

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

本文系統(tǒng)分為訓練、測試兩部分。

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

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

3 實驗結果與分析

本文的算法是通過python 實現(xiàn)的，運行環(huán)境：Dual-Core Intel Core i5 CPU，主頻2.3GHz，內(nèi)存8G，Macos64 位操作系統(tǒng)。

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

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

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

4 結束語

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