K-means也是聚類算法中最簡單的一種了，但是里面包含的思想?yún)s是不一般蔑匣。最早我使用并實現(xiàn)這個算法是在學(xué)習(xí)韓爺爺那本數(shù)據(jù)挖掘的書中蒿往，那本書比較注重應(yīng)用盛垦。看了Andrew Ng的這個講義后才有些明白K-means后面包含的EM思想瓤漏。

聚類屬于無監(jiān)督學(xué)習(xí)腾夯，以往的回歸、樸素貝葉斯蔬充、SVM等都是有類別標(biāo)簽y的蝶俱，也就是說樣例中已經(jīng)給出了樣例的分類。而聚類的樣本中卻沒有給定y饥漫，只有特征x榨呆，比如假設(shè)宇宙中的星星可以表示成三維空間中的點集。聚類的目的是找到每個樣本x潛在的類別y庸队，并將同類別y的樣本x放在一起积蜻。比如上面的星星，聚類后結(jié)果是一個個星團(tuán)彻消，星團(tuán)里面的點相互距離比較近竿拆，星團(tuán)間的星星距離就比較遠(yuǎn)了。

在聚類問題中宾尚，給我們的訓(xùn)練樣本是如输，每個，沒有了y央勒。

???? K-means算法是將樣本聚類成k個簇（cluster）不见，具體算法描述如下：

1、 隨機(jī)選取k個聚類質(zhì)心點（cluster centroids）為崔步。

2稳吮、 重復(fù)下面過程直到收斂 {

?????????????? 對于每一個樣例i，計算其應(yīng)該屬于的類

?????????????? 對于每一個類j井濒，重新計算該類的質(zhì)心

}

K是我們事先給定的聚類數(shù)灶似，代表樣例i與k個類中距離最近的那個類，的值是1到k中的一個瑞你。質(zhì)心代表我們對屬于同一個類的樣本中心點的猜測酪惭，拿星團(tuán)模型來解釋就是要將所有的星星聚成k個星團(tuán)，首先隨機(jī)選取k個宇宙中的點（或者k個星星）作為k個星團(tuán)的質(zhì)心者甲，然后第一步對于每一個星星計算其到k個質(zhì)心中每一個的距離春感，然后選取距離最近的那個星團(tuán)作為，這樣經(jīng)過第一步每一個星星都有了所屬的星團(tuán)；第二步對于每一個星團(tuán)鲫懒，重新計算它的質(zhì)心（對里面所有的星星坐標(biāo)求平均）嫩实。重復(fù)迭代第一步和第二步直到質(zhì)心不變或者變化很小。

???? 下圖展示了對n個樣本點進(jìn)行K-means聚類的效果窥岩，這里k取2甲献。

???? K-means面對的第一個問題是如何保證收斂，前面的算法中強(qiáng)調(diào)結(jié)束條件就是收斂颂翼，可以證明的是K-means完全可以保證收斂性晃洒。下面我們定性的描述一下收斂性，我們定義畸變函數(shù)（distortion function）如下：

J函數(shù)表示每個樣本點到其質(zhì)心的距離平方和朦乏。K-means是要將J調(diào)整到最小球及。假設(shè)當(dāng)前J沒有達(dá)到最小值，那么首先可以固定每個類的質(zhì)心集歇，調(diào)整每個樣例的所屬的類別來讓J函數(shù)減少桶略，同樣，固定诲宇，調(diào)整每個類的質(zhì)心也可以使J減小际歼。這兩個過程就是內(nèi)循環(huán)中使J單調(diào)遞減的過程。當(dāng)J遞減到最小時姑蓝，和c也同時收斂鹅心。（在理論上，可以有多組不同的和c值能夠使得J取得最小值纺荧，但這種現(xiàn)象實際上很少見）旭愧。

由于畸變函數(shù)J是非凸函數(shù)，意味著我們不能保證取得的最小值是全局最小值宙暇，也就是說k-means對質(zhì)心初始位置的選取比較感冒输枯，但一般情況下k-means達(dá)到的局部最優(yōu)已經(jīng)滿足需求。但如果你怕陷入局部最優(yōu)占贫，那么可以選取不同的初始值跑多遍k-means桃熄，然后取其中最小的J對應(yīng)的和c輸出。

???? 下面累述一下K-means與EM的關(guān)系型奥，首先回到初始問題瞳收，我們目的是將樣本分成k個類，其實說白了就是求每個樣例x的隱含類別y厢汹，然后利用隱含類別將x歸類螟深。由于我們事先不知道類別y，那么我們首先可以對每個樣例假定一個y吧烫葬，但是怎么知道假定的對不對呢界弧？怎么評價假定的好不好呢？我們使用樣本的極大似然估計來度量，這里是就是x和y的聯(lián)合分布P(x,y)了夹纫。如果找到的y能夠使P(x,y)最大咽瓷，那么我們找到的y就是樣例x的最佳類別了设凹，x順手就聚類了舰讹。但是我們第一次指定的y不一定會讓P(x,y)最大，而且P(x,y)還依賴于其他未知參數(shù)闪朱，當(dāng)然在給定y的情況下月匣，我們可以調(diào)整其他參數(shù)讓P(x,y)最大。但是調(diào)整完參數(shù)后奋姿，我們發(fā)現(xiàn)有更好的y可以指定锄开，那么我們重新指定y，然后再計算P(x,y)最大時的參數(shù)称诗，反復(fù)迭代直至沒有更好的y可以指定萍悴。

???? 這個過程有幾個難點，第一怎么假定y寓免？是每個樣例硬指派一個y還是不同的y有不同的概率癣诱，概率如何度量。第二如何估計P(x,y)袜香，P(x,y)還可能依賴很多其他參數(shù)撕予，如何調(diào)整里面的參數(shù)讓P(x,y)最大。這些問題在以后的篇章里回答蜈首。

???? 這里只是指出EM的思想实抡，E步就是估計隱含類別y的期望值，M步調(diào)整其他參數(shù)使得在給定類別y的情況下欢策，極大似然估計P(x,y)能夠達(dá)到極大值吆寨。然后在其他參數(shù)確定的情況下，重新估計y踩寇，周而復(fù)始啄清，直至收斂。

上面的闡述有點費解姑荷，對應(yīng)于K-means來說就是我們一開始不知道每個樣例對應(yīng)隱含變量也就是最佳類別盒延。最開始可以隨便指定一個給它，然后為了讓P(x,y)最大（這里是要讓J最惺竺帷）添寺，我們求出在給定c情況下，J最小時的（前面提到的其他未知參數(shù)）懈费，然而此時發(fā)現(xiàn)计露，可以有更好的（質(zhì)心與樣例距離最小的類別）指定給樣例，那么得到重新調(diào)整，上述過程就開始重復(fù)了票罐，直到?jīng)]有更好的指定叉趣。這樣從K-means里我們可以看出它其實就是EM的體現(xiàn)，E步是確定隱含類別變量该押，M步更新其他參數(shù)來使J最小化疗杉。這里的隱含類別變量指定方法比較特殊，屬于硬指定蚕礼，從k個類別中硬選出一個給樣例烟具，而不是對每個類別賦予不同的概率〉斓牛總體思想還是一個迭代優(yōu)化過程朝聋，有目標(biāo)函數(shù)，也有參數(shù)變量囤躁，只是多了個隱含變量冀痕，確定其他參數(shù)估計隱含變量，再確定隱含變量估計其他參數(shù)狸演，直至目標(biāo)函數(shù)最優(yōu)言蛇。

K-means算法步驟詳解

協(xié)同過濾推薦算法是誕生最早，并且較為著名的推薦算法严沥。主要的功能是預(yù)測和推薦猜极。算法通過對用戶歷史行為數(shù)據(jù)的挖掘發(fā)現(xiàn)用戶的偏好，基于不同的偏好對用戶進(jìn)行群組劃分并推薦品味相似的商品消玄。協(xié)同過濾推薦算法分為兩類跟伏，分別是基于用戶的協(xié)同過濾算法(user-based collaboratIve filtering)，和基于物品的協(xié)同過濾算法(item-based collaborative filtering)翩瓜。簡單的說就是：物以類聚受扳，物以群分。下面我們將分別說明這兩類推薦算法的原理和實現(xiàn)方法兔跌。

　<!--more-->

推薦算法的分類

下面是我們基于領(lǐng)域的方法分類：

1.基于用戶的協(xié)同過濾算法(user-based collaboratIve filtering)

　　基于用戶的協(xié)同過濾算法是通過用戶的歷史行為數(shù)據(jù)發(fā)現(xiàn)用戶對商品或內(nèi)容的喜歡(如商品購買勘高，收藏，內(nèi)容評論或分享)坟桅，并對這些喜好進(jìn)行度量和打分华望。根據(jù)不同用戶對相同商品或內(nèi)容的態(tài)度和偏好程度計算用戶之間的關(guān)系。在有相同喜好的用戶間進(jìn)行商品推薦仅乓。簡單的說就是如果A,B兩個用戶都購買了x,y,z三本圖書赖舟，并且給出了5星的好評。那么A和B就屬于同一類用戶夸楣”鲎ィ可以將A看過的圖書w也推薦給用戶B子漩。

1.尋找偏好相似的用戶

　　我們模擬了5個用戶對兩件商品的評分，來說明如何通過用戶對不同商品的態(tài)度和偏好尋找相似的用戶石洗。在示例中幢泼，5個用戶分別對兩件商品進(jìn)行了評分。這里的分值可能表示真實的購買讲衫，也可以是用戶對商品不同行為的量化指標(biāo)缕棵。例如，瀏覽商品的次數(shù)焦人，向朋友推薦商品挥吵，收藏重父，分享花椭，或評論等等。這些行為都可以表示用戶對商品的態(tài)度和偏好程度房午。

　　從表格中很難直觀發(fā)現(xiàn)5個用戶間的聯(lián)系矿辽，我們將5個用戶對兩件商品的評分用散點圖表示出來后，用戶間的關(guān)系就很容易發(fā)現(xiàn)了郭厌。在散點圖中袋倔，Y軸是商品1的評分，X軸是商品2的評分折柠，通過用戶的分布情況可以發(fā)現(xiàn)宾娜，A,C,D三個用戶距離較近。用戶A(3.3 6.5)和用戶C(3.6 6.3)扇售，用戶D(3.4 5.8)對兩件商品的評分較為接近前塔。而用戶E和用戶B則形成了另一個群體。

　　散點圖雖然直觀承冰，但無法投入實際的應(yīng)用华弓，也不能準(zhǔn)確的度量用戶間的關(guān)系。因此我們需要通過數(shù)字對用戶的關(guān)系進(jìn)行準(zhǔn)確的度量困乒，并依據(jù)這些關(guān)系完成商品的推薦寂屏。

評價方式：

1.2歐幾里德距離評價

　　歐幾里德距離（兩點間的距離公式）評價是一個較為簡單的用戶關(guān)系評價方法。原理是通過計算兩個用戶在散點圖中的距離來判斷不同的用戶是否有相同的偏好娜搂。以下是歐幾里德距離評價的計算公式迁霎。

　　通過公式我們獲得了5個用戶相互間的歐幾里德系數(shù)，也就是用戶間的距離百宇。系數(shù)越小表示兩個用戶間的距離越近考廉，偏好也越是接近。不過這里有個問題恳谎，太小的數(shù)值可能無法準(zhǔn)確的表現(xiàn)出不同用戶間距離的差異芝此，因此我們對求得的系數(shù)取倒數(shù)憋肖，使用戶間的距離約接近，數(shù)值越大婚苹。在下面的表格中岸更，可以發(fā)現(xiàn)，用戶A&C用戶A&D和用戶C&D距離較近膊升。同時用戶B&E的距離也較為接近怎炊。與我們前面在散點圖中看到的情況一致。

1.3皮爾遜相關(guān)度評價

x,y分別代表兩個用戶

　　皮爾遜相關(guān)度評價是另一種計算用戶間關(guān)系的方法廓译。他比歐幾里德距離評價的計算要復(fù)雜一些评肆，但對于評分?jǐn)?shù)據(jù)不規(guī)范時皮爾遜相關(guān)度評價能夠給出更好的結(jié)果。以下是一個多用戶對多個商品進(jìn)行評分的示例非区。這個示例比之前的兩個商品的情況要復(fù)雜一些瓜挽，但也更接近真實的情況。我們通過皮爾遜相關(guān)度評價對用戶進(jìn)行分組征绸，并推薦商品久橙。

? ? ? 皮爾遜相關(guān)系數(shù)

　如下，結(jié)果是一個在-1與1之間的系數(shù)管怠。該系數(shù)用來說明兩個用戶間聯(lián)系的強(qiáng)弱程度淆衷。

*相關(guān)系數(shù)的分類*

*0.8-1.0 極強(qiáng)相關(guān)**0.6-0.8 強(qiáng)相關(guān)**0.4-0.6 中等程度相關(guān)**

0.2-0.4 弱相關(guān)**0.0-0.2 極弱相關(guān)或無相關(guān)*　　通過計算5個用戶對5件商品的評分我們獲得了用戶間的相似度數(shù)據(jù)。這里可以看到用戶A&B渤弛，C&D祝拯，C&E和D&E之間相似度較高。下一步她肯，我們可以依照相似度對用戶進(jìn)行商品推薦佳头。

2,為相似的用戶提供推薦物品

　　為用戶C推薦商品

　　當(dāng)我們需要對用戶C推薦商品時，首先我們檢查之前的相似度列表辕宏，發(fā)現(xiàn)用戶C和用戶D和E的相似度較高畜晰。換句話說這三個用戶是一個群體，擁有相同的偏好瑞筐。因此凄鼻，我們可以對用戶C推薦D和E的商品。但這里有一個問題聚假。我們不能直接推薦前面商品1-商品5的商品块蚌。因為這這些商品用戶C以及瀏覽或者購買過了。不能重復(fù)推薦膘格。因此我們要推薦用戶C還沒有瀏覽或購買過的商品峭范。

　　加權(quán)排序推薦（如何加權(quán)排序）

　　我們提取了用戶D和用戶E評價過的另外5件商品A—商品F的商品。并對不同商品的評分進(jìn)行相似度加權(quán)瘪贱。按加權(quán)后的結(jié)果對5件商品進(jìn)行排序纱控，然后推薦給用戶C辆毡。這樣，用戶C就獲得了與他偏好相似的用戶D和E評價的商品甜害。而在具體的推薦順序和展示上我們依照用戶D和用戶E與用戶C的相似度進(jìn)行排序舶掖。

　　以上是基于用戶的協(xié)同過濾算法。這個算法依靠用戶的歷史行為數(shù)據(jù)來計算相關(guān)度尔店。也就是說必須要有一定的數(shù)據(jù)積累(冷啟動問題)眨攘。對于新網(wǎng)站或數(shù)據(jù)量較少的網(wǎng)站，還有一種方法是基于物品的協(xié)同過濾算法嚣州。

2.基于項目的協(xié)同過濾

UerCF：

基于用戶對物品的偏好鲫售，然后將相似度比較高的用戶的商品推薦給研究的用戶

基于物品的協(xié)同過濾算法ItemCF：

喜歡A商品的用戶與喜歡C商品的用戶很相似，我可以把沒有C商品而有A商品的用戶推薦給他C商品

2.1 栗子

　　基于物品的協(xié)同過濾算法與基于用戶的協(xié)同過濾算法很像该肴，將商品和用戶互換情竹。通過計算不同用戶對不同物品的評分獲得物品間的關(guān)系∩陈基于物品間的關(guān)系對用戶進(jìn)行相似物品的推薦蚕苇。這里的評分代表用戶對商品的態(tài)度和偏好没酣。簡單來說就是如果用戶A同時購買了商品1和商品2，那么說明商品1和商品2的相關(guān)度較高媳维。當(dāng)用戶B也購買了商品1時底扳，可以推斷他也有購買商品2的需求铸抑。

1.尋找相似的物品

　　表格中是兩個用戶對5件商品的評分。在這個表格中我們用戶和商品的位置進(jìn)行了互換衷模，通過兩個用戶的評分來獲得5件商品之間的相似度情況鹊汛。單從表格中我們依然很難發(fā)現(xiàn)其中的聯(lián)系，因此我們選擇通過散點圖進(jìn)行展示阱冶。

　　在散點圖中刁憋，X軸和Y軸分別是兩個用戶的評分。5件商品按照所獲的評分值分布在散點圖中木蹬。我們可以發(fā)現(xiàn)至耻，商品1,3,4在用戶A和B中有著近似的評分，說明這三件商品的相關(guān)度較高镊叁。而商品5和2則在另一個群體中尘颓。

2.1.2評價方式：（部分）

　　歐幾里德距離評價

　　在基于物品的協(xié)同過濾算法中，我們依然可以使用歐幾里德距離評價來計算不同商品間的距離和關(guān)系晦譬。以下是計算公式疤苹。

　　通過歐幾里德系數(shù)可以發(fā)現(xiàn)，商品間的距離和關(guān)系與前面散點圖中的表現(xiàn)一致敛腌，商品1,3,4距離較近關(guān)系密切卧土。商品2和商品5距離較近惫皱。

　　皮爾遜相關(guān)度評價

　　我們選擇使用皮爾遜相關(guān)度評價來計算多用戶與多商品的關(guān)系計算。下面是5個用戶對5件商品的評分表尤莺。我們通過這些評分計算出商品間的相關(guān)度逸吵。

　　皮爾遜相關(guān)度計算公式

　　通過計算可以發(fā)現(xiàn)，商品1&2缝裁，商品3&4扫皱，商品3&5和商品4&5相似度較高。下一步我們可以依據(jù)這些商品間的相關(guān)度對用戶進(jìn)行商品推薦捷绑。

2,為用戶提供基于相似物品的推薦

　　這里我們遇到了和基于用戶進(jìn)行商品推薦相同的問題韩脑，當(dāng)需要對用戶C基于商品3推薦商品時，需要一張新的商品與已有商品間的相似度列表粹污。在前面的相似度計算中段多，商品3與商品4和商品5相似度較高，因此我們計算并獲得了商品4,5與其他商品的相似度列表壮吩。

　　以下是通過計算獲得的新商品與已有商品間的相似度數(shù)據(jù)进苍。

　　加權(quán)排序推薦

　　這里是用戶C已經(jīng)購買過的商品4,5與新商品A,B,C直接的相似程度。我們將用戶C對商品4,5的評分作為權(quán)重鸭叙。對商品A,B,C進(jìn)行加權(quán)排序觉啊。用戶C評分較高并且與之相似度較高的商品被優(yōu)先推薦。

本文改編于https://blog.csdn.net/yimingsilence/article/details/54934302 （作者：默一鳴 ）

2.2計算公式總結(jié)：

一沈贝，皮爾遜相似度

公式優(yōu)點：能夠解決分?jǐn)?shù)貶值的問題

公式缺點：數(shù)據(jù)稀疏的情況下杠人，造成計算精度下降

二，斯皮爾曼相似度

此公式不關(guān)注數(shù)值的具體大小宋下，只關(guān)注（x,y) 排序后y與x具體的名次的差值嗡善，差值為di? n為樣本數(shù)量

帶入公式，求得斯皮爾曼相關(guān)性系數(shù)：ρs= 1-6(1+1+1+9)/635=0.657

三学歧，肯德爾相關(guān)系數(shù)

有點復(fù)雜后續(xù)在學(xué)吧（http://www.reibang.com/p/93fd5ab408ae）

優(yōu)點：可以計算出不同用戶對項目評分的一致性程度罩引。（同增或同減）

缺點：在稀疏矩陣中，由于擁有共同評分項較少枝笨，導(dǎo)致性能下降袁铐。

四,jaccard相似度計算

五，余弦相似度計算

公式四伺帘，五利用方法昭躺，詳細(xì)看 ItemCF 與UserCF 區(qū)別