基于用戶特征的K-means聚類算法應用與改進研究

王輝 趙瑋 祁 薇

摘要：隨著電子商務的快速發展，用戶數量與日俱增，商品數量龐大。在海量商品中，如何快速地得到自己想要的商品?；谶@個問題，該文利用了用戶的個人信息，將用戶的個人性格特征、所屬職業，以層次樹的方式進行量化表示，并采用K-means算法將用戶進行聚類，具有相似特征的用戶在同一個類別中，將查詢最近鄰時間降低。最后針對K-means聚類算法初始中心的選擇問題，采用kruskal算法構造最小生成樹的思想進行改進，解決了k中心點的選擇問題。

關鍵詞：個人特征;次樹;k-means算法;Kruskal最小生成樹

中圖分類號：TP391? ? 文獻標識碼：A? ? ? ? 文章編號：1009-3044（2018）35-0017-03

1? 背景

中國電子商務研究中心2018年統計數據表明[1]，我國電子商務全局保持了快速發展的勢頭，成為我國經濟發展的主力軍。個性化推薦技術是電子商務領域核心技術，它能根據不同的用戶推薦符合個人需求的商品。個性化推薦系統的可以劃分為三個模塊：第一個模塊用來提取用戶特征，第二個模塊進行相關物品檢索，最后一個模塊用于推薦結果。聚類是用戶特征提取模塊的重要算法，屬于數據挖掘技術之一，能夠幫助市場分析人員區分出不同的消費群體來。聚類分析算法有很多，有基于密度的聚類、基于模型的聚類、基于層次的聚類、基于劃分的聚類，我們通常使用基于劃分中的k-means聚類算法[2]。

該文利用了用戶的個人信息，將不同用戶的性格特征、從事的行業，通過層次樹的方法進行量化表示，之后，利用K-means算法將用戶進行聚類，使具有相似個人特征的用戶在同一個簇中，降低了搜索最近鄰的時間。

2 K-means聚類算法

K-means是一種常見的數據聚類算法，基本思想是：算法接收參數k，然后將事先輸入的n個數據對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高，不同聚類中的對象相似度較小。通過不斷的迭代，逐次更新各聚類中心的值，直至得到最好的聚類結果。

K-means聚類算法步驟：

1） 先從沒有標簽的元素集合A中隨機抽取k個元素，作為k個子集各自的重心;

2） 分別計算剩下的元素到k個子集重心的距離，根據距離將這些元素分別劃歸到最近的子集;

3） 根據聚類結果，重新計算重心：

4） 判斷聚類函數是否收斂，收斂則結束，不收斂轉向2）進一步迭代：[E=i=1kx∈cix-xi2] （2）

K-means聚類算法簡單高效，適用于海量數據的處理的特性，但是k值的選擇是隨機的，對于初始質心點的選取的好壞容易影響最終聚類結果，容易陷入局部最優解。

針對k-means聚類算法的缺陷，該文采用kruskal算法構造最小生成樹的思想優化初始聚類質心數目k的選擇，避免局部最優解的產生。

3 k-means聚類算法的改進

該文借鑒了最小生成樹的原來，提出了一種改進的k-means聚類算法。將系統中的用戶作為數據空間的頂點，用戶之間的距離，看作是一條邊，根據kruskal[4]算法來用點和邊構造最小生成樹。

改進的k-means聚類算法步驟：

1） 所有用戶表示成連通網N=（V，{E}），其中V是頂點的集合，每一個頂點代表一個用戶，E是全部邊的集合，每一條邊代表用戶之間的距離。

2） 使用具有n個頂點且無邊的非連通圖T=（V，{ }）表示初始狀態，把每個頂點看成一個連通分量。

3） 在E中選擇邊長最小的邊，如果該邊對應的頂點處于T中不同的連通分量上，則將此邊加入T中，否則，去掉該邊，重新選擇一條邊長最小的邊。重復以上步驟，直到某些頂點的連線構成了環，則將這些頂點加入同一個集合k中，然后把這些頂點在T中刪除。

4） 重復第3）步，直到所有的頂點都分配到k個集合中。

5） 計算每個集合的中心，以此作為k個初始的聚類中心。

6） 應用傳統的k-means聚類算法完成聚類。

求解過程演示如圖1。

4 基于用戶個人特征的聚類算法實現

該文將用戶的個人特征分為六個屬性：年齡，性別，學歷，職業，性格特點，個人偏好，按照用戶個人特征的不同對其進行聚類。

首先將用戶的個人信息進行量化表示。年齡是一個數值屬性，使用用戶注冊信息時填寫的年齡值，性別是個二元屬性，男性用0表示，女性用1表示，學歷劃分為小學，中學，大學，碩士，博士五種類型，分別用數字1到5來表示，職業和性格特征將其以層次樹的形式進行表示。

美國霍普金斯大學心理學教授、著名的職業指導專家約翰.L.霍蘭德（John L.Holland）[3]將職業劃分為實際型、研究型、藝術型、社會型、企業型、傳統型六大基本類型。參照約翰.L.霍蘭德的分類方法，該文將用戶職業以層次樹的形式進行表示。如圖2所示：

六個基本類型內部還有具體的職業劃分，例如歌唱舞蹈分為：歌唱家，舞蹈家，歌唱家還分為民族，通俗，美聲等等。自然科學分為天文學工作者，物理學工作者，化學工作者等等。自頂向下，從左到右，將每一層進行編號從0開始標號，0為職業，1為實際型，2為研究型，3為藝術型…011為手工操作，012為技術操作，0111為木匠，0112為鎖匠…以此類推。

用戶的性格特征也可以分為以下幾類：嚴肅型，嚴謹型，幽默型（冷幽默，搞笑型），熱情型，內向型，外向型，綜合型…那么將用戶性格特征表示成性格層次樹，如圖3所示。

通過性格層次樹，用戶性格特征可以進行量化，例如，某一用戶的性格特征是木訥型，可以量化為022，嚴謹型則量化為0211，以此類推，全部用戶特征都可以量化表示。

通過上面兩個操作，用戶信息全部進行了量化，例如用戶甲：性別：男;年齡31，學歷：碩士，職業：物理學工作者，性格：嚴謹型，那么用戶甲個人信息量化的結果為{0，31，4，0212，0211}。

之后，采用改進的k-means算法對用戶量化向量實行聚類操作，使具有相似個人信息的用戶能夠聚為一類，從而得到k個用戶簇，最近鄰的查找在同一個簇中進行，節省了查找時間，提升了推薦精度。

5 試驗結果及其分析

該文采用的實驗數據來自movielens的數據集，分別利用傳統的k-means聚類算法以及改進的基于用戶個人特征的聚類算法仿真實驗，比較兩種算法的性能，以最小空間內搜索到最近鄰的數目作為衡量標準。

隨機選取ID為16，121，317，608，912五位用戶，最近鄰閾值選取14，聚類數目分別選取2，3，4，5，（其中4為通過kruskal找到的最佳k值）對每一個活動用戶只在其所在的簇中查找最近鄰居，查到的最近鄰居如表1、2所示：

傳統的聚類算法：

通過計算得出，聚類數目2，傳統的聚類算法搜索率為1.497，聚類數目3，搜索率為2.366，聚類數目4，搜索率為2.34…，平均搜索率為2.16。

改進的聚類算法如表2所示。

通過計算得出，聚類數目2，改進聚類算法搜索率為1.63，聚類數目3，搜索率為2.69，聚類數目是4（4是通過kruskal找到的最佳k值），搜索率為2.99…平均搜索率為2.37。

通過改進的聚類算法和傳統聚類算法的對比，證明了該文改進的聚類算法能夠合理地選擇k值，在比較小的用戶空間內搜索到更多的鄰居，這種改進方法提高了查找用戶最近鄰的效率和精度，能夠滿足推薦系統對實時性的要求。

6 總結

該文針對傳統的k-means聚類算法k值不確定問題，采用了kruskal算法構造最小生成樹的思想對其進行改進，解決了由于k的隨機性帶來的局部最優解的問題，并且按照用戶個人特征，采用職業層次樹和性格層次樹方式，對用戶個人特征進行量化表示，節省了最近鄰的搜索時間，提高了推薦精度。

參考文獻：

[1] 朱明.數據挖掘[M].合肥：中國科學技術大學出版社，2008：37-38.

[2] Han J W， Kamber M. 數據挖掘：概念與技術[M].北京： 機械工業出版社，2001： 232-235.

[3] Nada Dabbagh， Brenda Bannan-Ritland. Online learning： concepts， strategies， and application[M]. New Jersey： Prentice Hall， 2004.

[4] 嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社， 2003：175-176.

[5] Sarwar B M.， KaryPis G， Konstan J A， et al. Item-based Collaborative filtering recommendationaglgorithm[C]. Proceedings of the Tenth International World Wide Web Conference， ACM Press， 2001：285-295.

[通聯編輯：謝媛媛]