《推薦系統：技術、評估及高效算法》一2.4 聚類分析

本節書摘來自華章出版社《推薦系統：技術、評估及高效算法》一書中的第2章，第2.4節，作者 [ 美］弗朗西斯科·裡奇（francesco ricci）利奧·羅卡奇（lior rokach）布拉哈·夏皮拉（bracha shapira）保羅 b.坎特（paul b.kantor），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

擴充cf分類器的最大問題是計算距離時的操作量，如發現最好的k近鄰。如我們在2.2.3節中所看到那樣，一種可能的解決方法是降維。但是，即使降低了特征次元，仍有許多對象要計算距離，這就是聚類算法的用武之地。基于内容的推薦系統也是這樣，檢索相似對象也需要計算距離。由于操作量的減少，聚類可以提高效率。但是，不像降維方法，它不太可能提高精确度。是以，在設計推薦系統時必須謹慎使用聚類，必須小心地衡量提高效率和降低精度之間的平衡。

聚類［41］，也稱為無監督的學習，配置設定物品到一個組中使得在同一組中的物品比不同組中的物品更加類似：目的是發現存在資料中的自然（或者說是有意義）的組。相似度是由距離衡量決定的，如在2.2.1節中叙述的。聚類算法的目标是在最小化群内距離的同時最大化群間距離。

聚類算法有兩個主要的類别：分層和劃分。劃分聚類算法把資料劃分成非重合的聚類，使得每一個資料項确切在一個聚類中。分層聚類算法在已知聚類上繼續聚合物品，生成聚類的嵌套集合，組成一個層級樹。

許多聚類算法試圖最小化一個函數來衡量聚類的品質。這樣的品質函數一般被稱為目标函數，是以聚類可以看作最優化的問題：理想聚類算法考慮所有可能資料劃分，并且輸出最小化品質函數的劃分。但相應的最優化問題是np難問題，是以許多算法采用啟發式方法（例如，k-means算法中局部最優化過程最可能結束于局部最小）。主要問題還是聚類問題太難了，很多情況下要想找到最優解就是不可能的。同樣的原因，特殊聚類算法的選擇和它的參數（如相似度測量）取決于許多的因素，包括資料的特征。在下面的章節将描述k-means聚類算法和其他的候選算法。

k-means聚類是一種分塊方法。函數劃分n個物品的資料集到k個不相關的子集sj，其中包含nj物品，以便于它們按照給定的距離名額盡可能地靠近。在分塊中每一個聚類通過它的nj個成員和它的中心點λj來定義。每一個聚類的中心點是聚類中所有其他物品到它的距離之和最小的那個點。是以，我們定義k-means算法作為疊代來最小化1-1e≈0.623，其中xn是向量，代表第n個物品，λj是在sj中物品的中心點，并且d是距離尺度。k-means算法移動聚類間的物品直到e不再進一步降低。

算法一開始會随機選擇k個中心點。所有物品都會被配置設定到它們最靠近的中心節點的類中。由于聚類新添加或是移出物品，新聚類的中心節點需要更新，聚類的成員關系也需要更新。這個操作會持續下去，直到再沒有物品改變它們的聚類成員關系。算法第一次疊代時，大部分的聚類的最終位置就會發生，是以，跳出疊代的條件一般改變成“直到相對少的點改變聚類”來提高效率。

基礎的k-means是極其簡單和有效的算法。但是，它有幾個缺陷：1）為了選擇合适的k值，假定有先驗的資料知識；2）最終的聚類對于初始的中心點非常敏感；3）它會産生空聚類。k-means也有幾個關于資料的缺陷：當聚類是不同的大小、密度、非球狀形狀時，就會有問題，并且當資料包含異常值時它也會有問題。

xue等［77］提出一種在推薦環境中典型的聚類用法，通過使用k-means算法作為預處理步驟來幫助構造鄰居。他們沒有将鄰居限制在使用者所屬的聚類内，相反是使用從使用者到不同聚類中心點的距離作為預選階段發現鄰居。他們實作了基于聚類平滑技術，其技術是對于使用者在聚類中的缺失值被典型聚類取代。他們的方法據稱比标準的基于knn的cf效果要好。相類似，sarwar等［26］描述了一個方法來實作可擴充的knn分類器。他們通過平分k-means算法來劃分使用者空間，然後用這些聚類作為鄰居的形成的基礎。據稱與标準的knn的cf相比準确率降低了大約5%。但是，他們的方法顯著地提高了效率。

基于密度的聚類算法，諸如，dbscan通過建立密度定義作為在一定範圍内的點的數量。例如，dbscan定義了三種點：核心點是在給定距離内擁有超過一定數量鄰居的點；邊界點沒有超過指定數量的鄰居但屬于核心點鄰居；噪聲點既不是核心點也不是邊界點。算法疊代移除掉噪聲資料并且在剩下的點上進行聚類。

消息傳遞聚類算法是最近基于圖聚類方法的系列之一。消息傳遞算法沒有一開始就将節點的初始子集作為中心點，然後逐漸調适，而是一開始就将所有節點都看作中心點，一般稱為标本。在算法執行時，這些點，現在已經是網絡中的節點了，會交換消息直到聚類逐漸出現。相似傳播是這種系列算法的代表，通過定義節點之間的兩種資訊來起作用：“責任”，反映了在考慮其他潛在标本的情況下，接收點有多适合作為發送點的标本；“可用性”，從候選标本發送到節點，它反映了在考慮其他選擇相同标本的節點支援的情況下，這個節點選擇候選标本作為其标本的合适程度。相似傳播已經被應用到ＤＮＡ序列聚類，在圖形中人臉聚類，或者是文本摘要等不同問題，并且效果很好。

最後，分層聚類按照層級樹（樹枝形結構聯系圖）的結構産生一系列嵌套聚類。分層聚類不會預先假設聚類的既定數量。同樣，任何數量的聚類都能夠通過選擇合适等級的樹來獲得。分層聚類有時也與有意義的分類學相關。傳統的分層算法使用一個相似度或者距離矩陣來合并或分裂一個聚類。有兩種主要方法來分層聚類。在聚集分層聚類中，我們以點作為個體聚類，并且每一個步合并最近的聚類對，直到隻有一個（或是k個聚類）聚類剩下。分裂分層聚類從一個包含所有物品的聚類開始，并且每一個分裂每一聚類，直到每一聚類包含一個點（或是有k個聚類）。

就我們所知，諸如前面提到k-means的替代方法沒有應用在推薦系統中。k-means算法的簡單和效率優于它的替代算法。基于密度或者是分層聚類方法在推薦系統領域能起的作用還不是很清楚。另一方面，消息傳遞算法已經顯示了其高效的特點，并且基于圖的範例很容易轉換成推薦問題。在未來一段時間内我們看到這些算法的應用是可能的。