[發明專利]一種基于動態臨近點譜聚類的個性化推薦方法

有效

• 申請號: 201710944655.8
• 申請日: 2017-10-12
• 公開（公告）號: CN107885778B
• 公開（公告）日: 2020-08-04
• 發明（設計）人: 陳晉音;吳洋洋;徐軒桁;宣琦;俞山青
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/2458;G06F16/9535;G06Q30/06
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種基于動態臨近點譜聚類的個性化推薦方法，其特征在于：所述方法包括以下步驟：

1)將數據庫的簽到數據所對應的用戶-商店的二分網絡映射到兩個不同的向量空間中進行表示，過程如下：

1.1)首先，依據數據庫中的簽到數據建立用戶-商店的二分網絡，其中用戶與商店之間的權重為用戶訪問過該商店的次數；

1.2)將當前的用戶-商店網絡進行單邊投影得到用戶-用戶網絡以及商店-商店的網絡，其中用戶-用戶網絡的權重的大小為用戶去過的相同商店的個數，商店-商店的網絡的權重的大小為商店被訪問過的相同用戶的個數；

1.3)調用node2vec算法分別將用戶-用戶網絡以及商店-商店的網絡轉換到向量空間中，得到用戶向量和商店向量；

2)利用動態臨近點譜聚類算法將用戶和商店分別進行聚類，過程如下：

2.1)分別將用戶向量和商店向量進行初始化，對向量的所有維進行了歸一化處理；

2.2)建立基于動態臨近點的稀疏相似度矩陣，過程如下：

2.2.1)首先對數據點的局部密度和動態臨近點集合進行定義：

定義1：對于任意數據對象i，其局部密度計算方法為：

其中，m矩陣是由距離矩陣中最小的np_ercent個距離值組成，p_ercent表示鄰居點個數占總數據點距離個數的比例，d(i,j)表示點i和點j之間的距離；在計算每個區間距離矩陣的同時，利用該區間距離矩陣逐個與m矩陣中仍保留的距離值比較，每次比較只將其中np_ercent個最小距離值保留在m矩陣中，直到所有區間距離矩陣比較完為止；

定義2：對于任意數據對象i，其動態臨近點集合T_i為：

J_i＝{j∈N_i||ρ_i-ρ_j|＞ρ_thre} (4)

其中N_i表示離樣本點i最近樣本點組成的樣本點i的總臨近點集合，ρ_thre表示的是密度差閾值，J_i表示數據點i與總臨近點集合中臨近點的局部密度差大于密度差閾值ρ_thre的臨近點的集合，d(i,j)表示數據點i和數據點j之間的距離值，|ρ_i-ρ_j|表示數據點i和數據點j之間的密度差值的絕對值；

2.2.2)將數據點的動態臨近點集合引入到相似函數中，先通過每個數據點與其動態臨近點集合中所有樣本點之間的距離確定每個數據點的局部尺度參數，再通過數據點領域內動態臨近點集合對數據點之間的相似度進行調整；每個數據點只保留與其動態臨近點之間的相似度，舍棄與動態臨近點集合范圍外樣本點的相似度；

基于動態臨近點的相似函數的計算公式：

σ_i＝∑_j∈Nid(i,j)/t_i (6)

其中的d(i,j)表示數據點i和數據點j之間的距離值，t_i表示動態臨近點集合T_i內樣本點個數；

2.2.3)在計算基于動態臨近點的稀疏相似度矩陣的時候，首先要將所有數據分成一定區間，計算出每個數據點與所有數據點之間的距離組成的區間距離矩陣以及每個區間內所有數據點的動態臨近點集合，得到區間稀疏距離矩陣；接著依據基于動態臨近點的相似度函數和區間稀疏距離矩陣計算得到區間稀疏相似度矩陣，整合所有區間稀疏相似度矩陣得到完整的稀疏相似度矩陣；

2.3)確定聚類中心，過程如下：

2.3.1)密度的定義引用2.2.1)中局部密度的定義；

2.3.2)定義每個數據點的最小距離值：

定義3：對于任何樣本點，如果其所有動態臨近點的局部密度都小于該點的局部密度，則將該點判斷為候選點，否則將其判斷為非候選點；

對于一個非候選點i來說，點i的最小距離為i點到其所有局部密度高于i點的動態臨近點中的距離最小值：

δ_i＝min(DN_i) (7)

其中DN_i表示點i與局部密度大于該點的動態臨近點的距離集合；

對于一個候選點i來說，點i的最小距離為點到局部密度大于該點的樣本點的最小距離：

其中DH_i表示點i與所有樣本點中局部密度大于i點的樣本點的距離集合，max(ρ)表示最大局部密度，max(δ)表示計算得到的所有樣本點的最小距離中的最大值；

2.3.3)根據步驟2.3.1)和2.3.2)得到的密度矩陣和距離矩陣繪制出對應的決策圖；

2.3.4)依據決策圖的分析，引入變量γ，對于任意一個數據點i，其定義為：

γ_i＝ρ_i×δ_i (9)

根據γ的概率分布情況，對于該γ的分布進行曲線的擬合，發現其圖形的擬合曲線形狀近似于一條正態分布曲線；

2.3.5)利用選取置信區間的方式在所對應的正態分布曲線中尋找出聚類中心點信息，由ρ-δ關系圖上的離散數據點進行一元線性擬合，得到擬合曲線y_δ＝kx_ρ+b₀，計算各個數據點的殘差值ε_δi＝y_δi-δ_i，繪制殘差的頻度分布直方圖ε_δi-h計算得到方差值σ_δ，其中h表示不同殘差值的頻度分布， 最后利用λσ原則確定處在置信區間外的聚類中心點，其中λ是用于控制置信區間大小的參數，一般取λ＝3；

2.4)特征分解，求取特征向量組，過程如下：

2.4.1)首先需要計算出度矩陣D和拉普拉斯矩陣L，度矩陣是一個對角陣，它的對角線上的元素D_ii由相似度矩陣的第i行元素相加求和得到的，度矩陣D計算公式如下：

其中n表示數據量，S_ij表示相似度矩陣S中第i行j列的相似度值；

然后根據度矩陣D和相似度矩陣S計算得到拉普拉斯矩陣L，拉普拉斯矩陣計算公式如下：

2.4.2)將計算得到的拉普拉斯矩陣L進行特征分解，選擇出其中所有p個最能反映數據全局特征的特征值為1所對應的主特征向量；

2.4.3)接著通過拉普拉斯分值法選擇出剩余特征向量中拉普拉斯分值最小的K-p個特征向量；

拉普拉斯分值L_r計算方法為：

其中f_ri是第i個樣本點的第r個特征，定義第r個特征均值為D是度矩陣，D_ii＝∑_jS_ij，S_ij表示稀疏相似度矩陣S中互為臨近點的樣本點i和j之間的相似度；

2.4.4)將被選擇的K個特征向量組成矩陣V＝[v₁,v₂,…,v_K]；

2.5)標準化特征向量組，并聚類，過程如下：

對所選取的特征向量組V進行標準化處理，得到矩陣U：

此時U矩陣中每行數據表示原始數據在拉普拉斯空間中的映射位置，接著對U矩陣所表示的所有數據在特征空間中的映射的元素進行K-means聚類，得到當前密度差閾值所對應的聚類結果；

2.6)最優密度差閾值選取，過程如下：

2.6.1)獲得當前密度差閾值所對應的聚類結果；

2.6.2)依據當前密度差閾值所對應的聚類結果計算對應的Fitness函數值；

其中m表示簇的個數，n表示數據量，C_i和C_j表示第i個簇和第j個簇的聚類中心；

2.6.3)比較Fitness_g與當前Fitness函數值比較，其中Fitness_g表示在之前的聚類過程中所取得的最優Fitness函數值， 如果當前Fitness函數值較小，則更新Fitness_g函數值并保留該密度差閾值作為當前最優密度差閾值，否則保留Fitness_g函數值；

2.6.4)更新密度差閾值，判斷是否超出范圍，若密度差閾值超出范圍，則轉至步驟2.6.5)；否則轉至步驟2.2.1)；

2.6.5)輸出最優密度差閾值所對應的聚類結果；

3)對用戶簇初步個性化推薦多個商店簇，過程如下：

3.1)建立用戶簇與商店簇之間存在的二分網絡，其中用戶簇之間和商店簇之間的權重為用戶簇內的用戶在該商店簇內商店的簽到個數；

3.2)為每個用戶簇推薦商店簇：首先依據用戶簇與商店簇之間的二分網絡得到用戶簇所對應的所有商店簇與之的權重；接著依據權重對商店簇進行K-means聚類，將商店簇劃分成兩類；對于每個用戶簇將其中權重均值較大的類中的所有商店簇推薦給該用戶簇；

4)為每個用戶進行個性化推薦，過程如下：

依據對每個用戶簇推薦較為合適的多個的商店簇以及簽到信息所對應的打分信息，調用推薦算法對每個用戶進行個性化推薦。

2.如權利要求1所述的一種基于動態臨近點譜聚類的個性化推薦方法，其特征在于：將二分網絡的單邊投影與node2vec算法相結合更好的提取出網絡結構的特征；在對向量聚類時選擇使用基于動態臨近點的譜聚類算法，能夠準確的確定聚類中心，并且依據基于動態臨近點的稀疏相似度矩陣以及選取更為合適的特征向量能夠更好的反映出數據的結構，達到優化聚類效果的目的，最終優化了推薦算法的推薦效果；并在為用戶簇選取商店簇時實現了用戶簇的初步個性化推薦。