[發明專利]一種基于用戶偏好與項目屬性的聚類初始點選擇方法

有效

• 申請號: 201410035844.X
• 申請日: 2014-01-24
• 公開（公告）號: CN103793504B
• 公開（公告）日: 2018-02-27
• 發明（設計）人: 宿紅毅;王彩群;閆波;鄭宏
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京理工正陽知識產權代理事務所(普通合伙)11639
• 代理人: 唐華

技術領域

本發明涉及一種基于用戶偏好與項目屬性的聚類初始點選擇方法，屬于機器學習領域。

背景技術

聚類是一種無監督的學習方法，它通過一定的規則將數據對象按照定義的相似性劃分成為多個類或簇，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。到目前為止，聚類分析的應用已十分廣泛，包括統計學、機器學習、圖像分割、和數據挖掘等。目前，主要的聚類算法分為劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法。而劃分式聚類算法是實際應用中聚類分析的支柱。劃分式聚類算法需要預先指定聚類數目或聚類中心，通過反復迭代運算，逐步降低目標函數的誤差值，當目標函數值收斂時，得到最終聚類結果。劃分式聚類算法簡單、快速而且能有效的處理大數據集，但此聚類算法存在高計算性及對數據的輸入順序敏感的缺點，且需要預先指定聚類數目或聚類中心。初始聚類中心點對聚類結果的影響很大。如果初始聚類中心點選擇不當，得到的聚類結果可能會陷入局部最優，從而得不到較好的聚類結果。而劃分式聚類初始聚類中心點的選擇方法也是多種多樣，主要有以下幾種方法：

隨機選擇法：隨機選取k個數據點作為初始聚類中心點；

經驗法：依據經驗，根據個體性質，選擇k個有代表意義的點作為初始聚類中心點；

遞推法：首先計算全體數據樣本的均值，以這個數值點作為初始聚類中心，然后計算距離第一個數值點最遠的一個點作為第2個聚類中心，以此類推，由第k-1個聚類中心計算聚類最遠的一個數據樣本作為最后一個聚類中心。

密度估計選擇法：計算特定半徑內的每個數據樣本的密度，具有最大密度的點作為第一個聚類中心點，然后再計算剩下的初始中心點，若是具有第二大密度的點距離第一個聚類中心點的距離大于特定值則作為第2個初始聚類中心點，按此方法依次選出k個中心點；

距離優化選擇法：按照最大最小距離計算

采用遺傳算法計算聚類初始中心點等。

由于初始聚類中心點對聚類結果的影響很大。如果初始聚類中心點選擇不當，得到的聚類結果可能會陷入局部最優，從而得不到較好的聚類結果。為了獲得恰當的初始聚類中心點，避免聚類結果陷入局部最優，本專利提出一種新的聚類初始中心點的選擇方法。

發明內容

本發明的目的是為了解決基于劃分的算法的初始中心點的選擇的問題，使用用戶的偏好信息和商品屬性來構造相似矩陣，從而得到初試中心點。

本發明技術方案的實現過程為：

步驟1、確定基于項目的相似矩陣；

定義項目的特征向量：item_i=(p₁，p₂，…，p_m)；其中m為項目的屬性個數，p_i(1≤i≤m)代表了此項目第i個特征向量的值。然后每個項目可以轉換為用一個向量item_i＝(w₁，w₂，…，w_m)表示，其中向量維數是m，即項目的屬性特征個數。然后通過計算表示項目的向量間的距離A_ij來表示item_i和item_j之間的相似性，從而構成相似矩陣

所屬項目u與項目v之間通過距離獲取相似度的計算方法包括：皮爾遜相關的距離、歐氏距離、余弦距離、斯皮爾曼距離和基于谷本相關的距離。

步驟2、確定基于用戶偏好的同現矩陣；

定義用戶對項目的偏好列表：prefs＝(user_id，item_id，pref)，其中pref代表用戶對項目的評分，所有用戶對項目的評分組成評分列表prefs。通過計算item_i和item_j同時出現在相同的用戶的偏好列表中的次數B_ij，來構成同現矩陣

步驟3、確定最終的相似矩陣；

最終的相似矩陣定義為其中和β為自定義的權重。

步驟4、去除邊緣點；

在TS的每行中，分別計算相似度大于給定閾值θ的項目的個數，記為α_i，若是α_i的個數小于給定閾值μ表示此點是邊緣點，則從相似矩陣中刪除代表此項目的行和列以此來實現從相似矩陣中去除此邊緣點；遍歷所有的行后完成所有去除邊緣點的操作后再次獲得相似矩陣；

步驟5、選擇聚類初始中心點：