數(shù)據(jù)挖掘經(jīng)典算法

1、Apriori算法一、Apriori算法簡(jiǎn)介：  Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來挖掘頻繁項(xiàng)集。 Apriori（先驗(yàn)的，推測(cè)的）算法應(yīng)用廣泛，可用于消費(fèi)市場(chǎng)價(jià)格分析，猜測(cè)顧客的消費(fèi)習(xí)慣；網(wǎng)絡(luò)安全領(lǐng)域中的入侵檢測(cè)技術(shù)；可用在用于高校管理中，根據(jù)挖掘規(guī)則可以有效地輔助學(xué)校管理部門有針對(duì)性的開展貧困助學(xué)工作；也可用在移動(dòng)通信領(lǐng)域中，指導(dǎo)運(yùn)營商的業(yè)務(wù)運(yùn)營和輔助業(yè)務(wù)提供商的決策制定。二、挖掘步驟：1.依據(jù)支持度找出所有頻繁項(xiàng)集（頻度）2.依據(jù)置信度產(chǎn)生關(guān)聯(lián)規(guī)則（強(qiáng)度）三、基本概念對(duì)于A->B支持度：P(A

2、60; B)，既有A又有B的概率置信度：P(B|A)，在A發(fā)生的事件中同時(shí)發(fā)生B的概率 p(AB)/P(A)     例如購物籃分析：牛奶  面包例子：支持度：3%，置信度：40%支持度3%：意味著3%顧客同時(shí)購買牛奶和面包置信度40%：意味著購買牛奶的顧客40%也購買面包如果事件A中包含k個(gè)元素，那么稱這個(gè)事件A為k項(xiàng)集事件A滿足最小支持度閾值的事件稱為頻繁k項(xiàng)集。同時(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則四、實(shí)現(xiàn)步驟    Apriori算法是一種最

3、有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項(xiàng)集”用于搜索“K項(xiàng)集”。首先，找出頻繁“1項(xiàng)集”的集合，該集合記作L1。L1用于找頻繁“2項(xiàng)集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項(xiàng)集”。找每個(gè)Lk都需要一次數(shù)據(jù)庫掃描。核心思想是：連接步和剪枝步。連接步是自連接，原則是保證前k-2項(xiàng)相同，并按照字典順序連接。剪枝步，是使任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的。反之，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。簡(jiǎn)單的講，1、發(fā)現(xiàn)頻繁項(xiàng)集，過程為（1）掃描（2）計(jì)數(shù)（3）比較（4）產(chǎn)生頻繁

4、項(xiàng)集（5）連接、剪枝，產(chǎn)生候選項(xiàng)集   重復(fù)步驟（1）（5）直到不能發(fā)現(xiàn)更大的頻集2、產(chǎn)生關(guān)聯(lián)規(guī)則，過程為:根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對(duì)于每個(gè)頻繁項(xiàng)集L，產(chǎn)生L的所有非空子集；（2）對(duì)于L的每個(gè)非空子集S，如果                P（L）/P（S）min_conf則輸出規(guī)則“SàL-S”注：L-S表示在項(xiàng)集L中除去S子集的項(xiàng)集KNN最鄰近規(guī)則KNN最鄰近規(guī)則

5、，主要應(yīng)用領(lǐng)域是對(duì)未知事物的識(shí)別，即判斷未知事物屬于哪一類，判斷思想是，基于歐幾里得定理，判斷未知事物的特征和哪一類已知事物的的特征最接近；K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣

6、本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比（組合函數(shù)）。該算法在分類時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。 該算法只計(jì)算“最近

7、的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果?？梢圆捎脵?quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。K-NN可以說是一種最直接的用來分類未知數(shù)據(jù)的方法?；就ㄟ^下面這張圖跟文字說明就可以明白K-NN是干什么的簡(jiǎn)單來說

8、，K-NN可以看成：有那么一堆你已經(jīng)知道分類的數(shù)據(jù)，然后當(dāng)一個(gè)新數(shù)據(jù)進(jìn)入的時(shí)候，就開始跟訓(xùn)練數(shù)據(jù)里的每個(gè)點(diǎn)求距離，然后挑離這個(gè)訓(xùn)練數(shù)據(jù)最近的K個(gè)點(diǎn)看看這幾個(gè)點(diǎn)屬于什么類型，然后用少數(shù)服從多數(shù)的原則，給新數(shù)據(jù)歸類。 算法步驟：step.1-初始化距離為最大值step.2-計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離diststep.3-得到目前K個(gè)最臨近樣本中的最大距離maxdiststep.4-如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本step.5-重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離都算完step.6-統(tǒng)計(jì)K-最近鄰樣本中每個(gè)類標(biāo)號(hào)出現(xiàn)的次數(shù)step.7-

9、選擇出現(xiàn)頻率最大的類標(biāo)號(hào)作為未知樣本的類標(biāo)號(hào)（EM算法）The EM Algorithm      EM是我一直想深入學(xué)習(xí)的算法之一，第一次聽說是在NLP課中的HMM那一節(jié)，為了解決HMM的參數(shù)估計(jì)問題，使用了EM算法。在之后的MT中的詞對(duì)齊中也用到了。在Mitchell的書中也提到EM可以用于貝葉斯網(wǎng)絡(luò)中。下面主要介紹EM的整個(gè)推導(dǎo)過程。1. Jensen不等式      回顧優(yōu)化理論中的一些概念。設(shè)f是定義域?yàn)閷?shí)數(shù)的函數(shù)，如果對(duì)于所有的實(shí)數(shù)x，那么f是凸函數(shù)。當(dāng)x是向量時(shí)，如果其hessia

10、n矩陣H是半正定的（），那么f是凸函數(shù)。如果或者，那么稱f是嚴(yán)格凸函數(shù)。      Jensen不等式表述如下：      如果f是凸函數(shù)，X是隨機(jī)變量，那么            特別地，如果f是嚴(yán)格凸函數(shù)，那么當(dāng)且僅當(dāng)，也就是說X是常量。      這里我們將簡(jiǎn)寫為。      如果用

11、圖表示會(huì)很清晰：            圖中，實(shí)線f是凸函數(shù)，X是隨機(jī)變量，有0.5的概率是a，有0.5的概率是b。（就像擲硬幣一樣）。X的期望值就是a和b的中值了，圖中可以看到成立。      當(dāng)f是（嚴(yán)格）凹函數(shù)當(dāng)且僅當(dāng)-f是（嚴(yán)格）凸函數(shù)。      Jensen不等式應(yīng)用于凹函數(shù)時(shí)，不等號(hào)方向反向，也就是。2. EM算法     

12、 給定的訓(xùn)練樣本是，樣例間獨(dú)立，我們想找到每個(gè)樣例隱含的類別z，能使得p(x,z)最大。p(x,z)的最大似然估計(jì)如下：            第一步是對(duì)極大似然取對(duì)數(shù)，第二步是對(duì)每個(gè)樣例的每個(gè)可能類別z求聯(lián)合分布概率和。但是直接求一般比較困難，因?yàn)橛须[藏變量z存在，但是一般確定了z后，求解就容易了。      EM是一種解決存在隱含變量?jī)?yōu)化問題的有效方法。竟然不能直接最大化，我們可以不斷地建立的下界（E步），然后優(yōu)化下界（M步）。這句

13、話比較抽象，看下面的。      對(duì)于每一個(gè)樣例i，讓表示該樣例隱含變量z的某種分布，滿足的條件是。（如果z是連續(xù)性的，那么是概率密度函數(shù)，需要將求和符號(hào)換做積分符號(hào)）。比如要將班上學(xué)生聚類，假設(shè)隱藏變量z是身高，那么就是連續(xù)的高斯分布。如果按照隱藏變量是男女，那么就是伯努利分布了?？梢杂汕懊骊U述的內(nèi)容得到下面的公式：            （1）到（2）比較直接，就是分子分母同乘以一個(gè)相等的函數(shù)。（2）到（3）利用了Jensen不等式

14、，考慮到是凹函數(shù)（二階導(dǎo)數(shù)小于0），而且            就是的期望（回想期望公式中的Lazy Statistician規(guī)則）      設(shè)Y是隨機(jī)變量X的函數(shù)（g是連續(xù)函數(shù)），那么      （1） X是離散型隨機(jī)變量，它的分布律為，k=1,2,。若絕對(duì)收斂，則有          

15、;  （2） X是連續(xù)型隨機(jī)變量，它的概率密度為，若絕對(duì)收斂，則有            對(duì)應(yīng)于上述問題，Y是，X是，是，g是到的映射。這樣解釋了式子（2）中的期望，再根據(jù)凹函數(shù)時(shí)的Jensen不等式：      可以得到（3）。      這個(gè)過程可以看作是對(duì)求了下界。對(duì)于的選擇，有多種可能，那種更好的？假設(shè)已經(jīng)給定，那么的值就決定于和了。我們可以通過調(diào)整這兩個(gè)概率

16、使下界不斷上升，以逼近的真實(shí)值，那么什么時(shí)候算是調(diào)整好了呢？當(dāng)不等式變成等式時(shí)，說明我們調(diào)整后的概率能夠等價(jià)于了。按照這個(gè)思路，我們要找到等式成立的條件。根據(jù)Jensen不等式，要想讓等式成立，需要讓隨機(jī)變量變成常數(shù)值，這里得到：            c為常數(shù)，不依賴于。對(duì)此式子做進(jìn)一步推導(dǎo)，我們知道，那么也就有，（多個(gè)等式分子分母相加不變，這個(gè)認(rèn)為每個(gè)樣例的兩個(gè)概率比值都是c），那么有下式：       

17、0;    至此，我們推出了在固定其他參數(shù)后，的計(jì)算公式就是后驗(yàn)概率，解決了如何選擇的問題。這一步就是E步，建立的下界。接下來的M步，就是在給定后，調(diào)整，去極大化的下界（在固定后，下界還可以調(diào)整的更大）。那么一般的EM算法的步驟如下：循環(huán)重復(fù)直到收斂       （E步）對(duì)于每一個(gè)i，計(jì)算                   &

18、#160;    （M步）計(jì)算                        那么究竟怎么確保EM收斂？假定和是EM第t次和t+1次迭代后的結(jié)果。如果我們證明了，也就是說極大似然估計(jì)單調(diào)增加，那么最終我們會(huì)到達(dá)最大似然估計(jì)的最大值。下面來證明，選定后，我們得到E步      &#

19、160;     這一步保證了在給定時(shí)，Jensen不等式中的等式成立，也就是            然后進(jìn)行M步，固定，并將視作變量，對(duì)上面的求導(dǎo)后，得到，這樣經(jīng)過一些推導(dǎo)會(huì)有以下式子成立：            解釋第（4）步，得到時(shí)，只是最大化，也就是的下界，而沒有使等式成立，等式成立只有是在固定，并按E步得到時(shí)才能成立。 

20、;     況且根據(jù)我們前面得到的下式，對(duì)于所有的和都成立            第（5）步利用了M步的定義，M步就是將調(diào)整到，使得下界最大化。因此（5）成立，（6）是之前的等式結(jié)果。      這樣就證明了會(huì)單調(diào)增加。一種收斂方法是不再變化，還有一種就是變化幅度很小。      再次解釋一下（4）、（5）、（6）。首先（4）對(duì)所有的參數(shù)都滿足，而

21、其等式成立條件只是在固定，并調(diào)整好Q時(shí)成立，而第（4）步只是固定Q，調(diào)整，不能保證等式一定成立。（4）到（5）就是M步的定義，（5）到（6）是前面E步所保證等式成立條件。也就是說E步會(huì)將下界拉到與一個(gè)特定值（這里）一樣的高度，而此時(shí)發(fā)現(xiàn)下界仍然可以上升，因此經(jīng)過M步后，下界又被拉升，但達(dá)不到與另外一個(gè)特定值一樣的高度，之后E步又將下界拉到與這個(gè)特定值一樣的高度，重復(fù)下去，直到最大值。      如果我們定義            從前面

22、的推導(dǎo)中我們知道，EM可以看作是J的坐標(biāo)上升法，E步固定，優(yōu)化，M步固定優(yōu)化。3. 重新審視混合高斯模型      我們已經(jīng)知道了EM的精髓和推導(dǎo)過程，再次審視一下混合高斯模型。之前提到的混合高斯模型的參數(shù)和計(jì)算公式都是根據(jù)很多假定得出的，有些沒有說明來由。為了簡(jiǎn)單，這里在M步只給出和的推導(dǎo)方法。E步很簡(jiǎn)單，按照一般EM公式得到：            簡(jiǎn)單解釋就是每個(gè)樣例i的隱含類別為j的概率可以通過后驗(yàn)概率計(jì)算得到。 &#

23、160;    在M步中，我們需要在固定后最大化最大似然估計(jì)，也就是            這是將的k種情況展開后的樣子，未知參數(shù)和。      固定和，對(duì)求導(dǎo)得            等于0時(shí)，得到        &#

24、160;   這就是我們之前模型中的的更新公式。      然后推導(dǎo)的更新公式?？粗暗玫降?#160;           在和確定后，分子上面的一串都是常數(shù)了，實(shí)際上需要優(yōu)化的公式是：            需要知道的是，還需要滿足一定的約束條件就是。      這

25、個(gè)優(yōu)化問題我們很熟悉了，直接構(gòu)造拉格朗日乘子。            還有一點(diǎn)就是，但這一點(diǎn)會(huì)在得到的公式里自動(dòng)滿足。      求導(dǎo)得，            等于0，得到            也就是說再次使用，得到

26、            這樣就神奇地得到了。      那么就順勢(shì)得到M步中的更新公式：            的推導(dǎo)也類似，不過稍微復(fù)雜一些，畢竟是矩陣。結(jié)果在之前的混合高斯模型中已經(jīng)給出。4. 總結(jié)      如果將樣本看作觀察值，潛在類別看作是隱藏變量，那么聚類問

27、題也就是參數(shù)估計(jì)問題，只不過聚類問題中參數(shù)分為隱含類別變量和其他參數(shù)，這猶如在x-y坐標(biāo)系中找一個(gè)曲線的極值，然而曲線函數(shù)不能直接求導(dǎo)，因此什么梯度下降方法就不適用了。但固定一個(gè)變量后，另外一個(gè)可以通過求導(dǎo)得到，因此可以使用坐標(biāo)上升法，一次固定一個(gè)變量，對(duì)另外的求極值，最后逐步逼近極值。對(duì)應(yīng)到EM上，E步估計(jì)隱含變量，M步估計(jì)其他參數(shù)，交替將極值推向最大。EM中還有“硬”指定和“軟”指定的概念，“軟”指定看似更為合理，但計(jì)算量要大，“硬”指定在某些場(chǎng)合如K-means中更為實(shí)用（要是保持一個(gè)樣本點(diǎn)到其他所有中心的概率，就會(huì)很麻煩）。     

28、另外，EM的收斂性證明方法確實(shí)很牛，能夠利用log的凹函數(shù)性質(zhì)，還能夠想到利用創(chuàng)造下界，拉平函數(shù)下界，優(yōu)化下界的方法來逐步逼近極大值。而且每一步迭代都能保證是單調(diào)的。最重要的是證明的數(shù)學(xué)公式非常精妙，硬是分子分母都乘以z的概率變成期望來套上Jensen不等式，前人都是怎么想到的。      在Mitchell的Machine Learning書中也舉了一個(gè)EM應(yīng)用的例子，明白地說就是將班上學(xué)生的身高都放在一起，要求聚成兩個(gè)類。這些身高可以看作是男生身高的高斯分布和女生身高的高斯分布組成。因此變成了如何估計(jì)每個(gè)樣例是男生還是女生，然后在確定男女生

29、情況下，如何估計(jì)均值和方差，里面也給出了公式，有興趣可以參考。K-means聚類算法     K-means也是聚類算法中最簡(jiǎn)單的一種了，但是里面包含的思想?yún)s是不一般。最早我使用并實(shí)現(xiàn)這個(gè)算法是在學(xué)習(xí)韓爺爺那本數(shù)據(jù)挖掘的書中，那本書比較注重應(yīng)用?？戳薃ndrew Ng的這個(gè)講義后才有些明白K-means后面包含的EM思想。     聚類屬于無監(jiān)督學(xué)習(xí)，以往的回歸、樸素貝葉斯、SVM等都是有類別標(biāo)簽y的，也就是說樣例中已經(jīng)給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特征x，比如假設(shè)宇宙中的星星可以表示成三維空間

30、中的點(diǎn)集。聚類的目的是找到每個(gè)樣本x潛在的類別y，并將同類別y的樣本x放在一起。比如上面的星星，聚類后結(jié)果是一個(gè)個(gè)星團(tuán)，星團(tuán)里面的點(diǎn)相互距離比較近，星團(tuán)間的星星距離就比較遠(yuǎn)了。     在聚類問題中，給我們的訓(xùn)練樣本是，每個(gè)，沒有了y。     K-means算法是將樣本聚類成k個(gè)簇（cluster），具體算法描述如下：1、 隨機(jī)選取k個(gè)聚類質(zhì)心點(diǎn)（cluster centroids）為。2、 重復(fù)下面過程直到收斂         &#

31、160;      對(duì)于每一個(gè)樣例i，計(jì)算其應(yīng)該屬于的類                              對(duì)于每一個(gè)類j，重新計(jì)算該類的質(zhì)心         &

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

33、變化很小。     下圖展示了對(duì)n個(gè)樣本點(diǎn)進(jìn)行K-means聚類的效果，這里k取2。          K-means面對(duì)的第一個(gè)問題是如何保證收斂，前面的算法中強(qiáng)調(diào)結(jié)束條件就是收斂，可以證明的是K-means完全可以保證收斂性。下面我們定性的描述一下收斂性，我們定義畸變函數(shù)（distortion function）如下：          J函數(shù)表示每個(gè)樣本點(diǎn)到其質(zhì)心的距離平

34、方和。K-means是要將J調(diào)整到最小。假設(shè)當(dāng)前J沒有達(dá)到最小值，那么首先可以固定每個(gè)類的質(zhì)心，調(diào)整每個(gè)樣例的所屬的類別來讓J函數(shù)減少，同樣，固定，調(diào)整每個(gè)類的質(zhì)心也可以使J減小。這兩個(gè)過程就是內(nèi)循環(huán)中使J單調(diào)遞減的過程。當(dāng)J遞減到最小時(shí)，和c也同時(shí)收斂。（在理論上，可以有多組不同的和c值能夠使得J取得最小值，但這種現(xiàn)象實(shí)際上很少見）。     由于畸變函數(shù)J是非凸函數(shù)，意味著我們不能保證取得的最小值是全局最小值，也就是說k-means對(duì)質(zhì)心初始位置的選取比較感冒，但一般情況下k-means達(dá)到的局部最優(yōu)已經(jīng)滿足需求。但如果你怕陷入局部最優(yōu)，那么可以選取

35、不同的初始值跑多遍k-means，然后取其中最小的J對(duì)應(yīng)的和c輸出。     下面累述一下K-means與EM的關(guān)系，首先回到初始問題，我們目的是將樣本分成k個(gè)類，其實(shí)說白了就是求每個(gè)樣例x的隱含類別y，然后利用隱含類別將x歸類。由于我們事先不知道類別y，那么我們首先可以對(duì)每個(gè)樣例假定一個(gè)y吧，但是怎么知道假定的對(duì)不對(duì)呢？怎么評(píng)價(jià)假定的好不好呢？我們使用樣本的極大似然估計(jì)來度量，這里是就是x和y的聯(lián)合分布P(x,y)了。如果找到的y能夠使P(x,y)最大，那么我們找到的y就是樣例x的最佳類別了，x順手就聚類了。但是我們第一次指定的y不一定會(huì)讓P(x,y)

36、最大，而且P(x,y)還依賴于其他未知參數(shù)，當(dāng)然在給定y的情況下，我們可以調(diào)整其他參數(shù)讓P(x,y)最大。但是調(diào)整完參數(shù)后，我們發(fā)現(xiàn)有更好的y可以指定，那么我們重新指定y，然后再計(jì)算P(x,y)最大時(shí)的參數(shù)，反復(fù)迭代直至沒有更好的y可以指定。     這個(gè)過程有幾個(gè)難點(diǎn)，第一怎么假定y？是每個(gè)樣例硬指派一個(gè)y還是不同的y有不同的概率，概率如何度量。第二如何估計(jì)P(x,y)，P(x,y)還可能依賴很多其他參數(shù)，如何調(diào)整里面的參數(shù)讓P(x,y)最大。這些問題在以后的篇章里回答。     這里只是指出EM的思想，E步就是

37、估計(jì)隱含類別y的期望值，M步調(diào)整其他參數(shù)使得在給定類別y的情況下，極大似然估計(jì)P(x,y)能夠達(dá)到極大值。然后在其他參數(shù)確定的情況下，重新估計(jì)y，周而復(fù)始，直至收斂。     上面的闡述有點(diǎn)費(fèi)解，對(duì)應(yīng)于K-means來說就是我們一開始不知道每個(gè)樣例對(duì)應(yīng)隱含變量也就是最佳類別。最開始可以隨便指定一個(gè)給它，然后為了讓P(x,y)最大（這里是要讓J最?。覀兦蟪鲈诮o定c情況下，J最小時(shí)的（前面提到的其他未知參數(shù)），然而此時(shí)發(fā)現(xiàn)，可以有更好的（質(zhì)心與樣例距離最小的類別）指定給樣例，那么得到重新調(diào)整，上述過程就開始重復(fù)了，直到?jīng)]有更好的指定。這樣從K-means

38、里我們可以看出它其實(shí)就是EM的體現(xiàn)，E步是確定隱含類別變量，M步更新其他參數(shù)來使J最小化。這里的隱含類別變量指定方法比較特殊，屬于硬指定，從k個(gè)類別中硬選出一個(gè)給樣例，而不是對(duì)每個(gè)類別賦予不同的概率?？傮w思想還是一個(gè)迭代優(yōu)化過程，有目標(biāo)函數(shù)，也有參數(shù)變量，只是多了個(gè)隱含變量，確定其他參數(shù)估計(jì)隱含變量，再確定隱含變量估計(jì)其他參數(shù)，直至目標(biāo)函數(shù)最優(yōu)。1. 協(xié)同過濾的簡(jiǎn)介關(guān)于協(xié)同過濾的一個(gè)最經(jīng)典的例子就是看電影，有時(shí)候不知道哪一部電影是我們喜歡的或者評(píng)分比較高的，那么通常的做法就是問問周圍的朋友，看看最近有什么好的電影推薦。在問的時(shí)候，都習(xí)慣于問跟自己口味差不多的朋友，這就是協(xié)同過濾的核心思想。協(xié)同過濾是在海量數(shù)據(jù)中挖掘出小部分與你品味類似的用戶，在協(xié)同過濾中，這些用戶成為鄰居，然后根據(jù)他們喜歡的東西組織成一個(gè)排序的目錄推薦給你。所以就有如下兩個(gè)核心問題（1）如何確定一個(gè)用戶是否與你有相似的品味？（2）如何將鄰居們的喜好組織成一個(gè)排序目錄？協(xié)同過濾算法的出現(xiàn)標(biāo)志著推薦系統(tǒng)的產(chǎn)生，協(xié)同過濾算法包括基于用戶和基于物品的協(xié)同過濾算法。2. 協(xié)同過濾的核心要實(shí)現(xiàn)協(xié)同過濾，需要進(jìn)行如下幾個(gè)步驟（1）收集用戶偏好（2）找到相似的用戶或者物品（3）計(jì)算并推薦   收集用戶偏好從用戶的行為和偏好中發(fā)現(xiàn)規(guī)律，并基于此進(jìn)行推薦，所以如何