數(shù)據(jù)挖掘算法綜述

1、分類算法總結(jié)比較各種常見的分類算法，在過分?jǐn)M合，最優(yōu)解等方面決策樹分類（三種屬性選擇度量）基于規(guī)則的分類貝葉斯（樸素貝葉斯，貝葉斯網(wǎng)絡(luò)）基于后驗(yàn)概率支持向量機(jī)（凸二次規(guī)劃，全局最優(yōu)解）惰性學(xué)習(xí)法（k最近鄰分類法，基于案例的推理）分類算法的驗(yàn)證和評(píng)估方法二、聚類算法總結(jié)K劃分方法1）基于質(zhì)心的技術(shù)，k-means （K均值）聚類k均值算法以k為輸入，把n個(gè)對(duì)象的集合分成k個(gè)簇。首先，隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象代表一個(gè)簇的初值 均值或中心，對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇均值 的距離，將其指派到最相似的簇中。然后計(jì)算每個(gè)簇的 新的均值，重復(fù)這個(gè)過程，直到準(zhǔn)則函數(shù)的值收斂。通 常采用平方誤差準(zhǔn)則。其

2、中，E是數(shù)據(jù)集中所有對(duì)象的平方誤差和，P是空間中 的點(diǎn)，表示給定對(duì)象，叫是簇&的均值，換句話說，對(duì) 于每個(gè)簇中的每個(gè)對(duì)象，求其到其簇中心距離的平方， 然后求和。具體算法過程如下：首先任意選取k個(gè)對(duì)象作為初始的簇中心，根據(jù)對(duì)象與 簇中心的距離，每個(gè)對(duì)象指派個(gè)最近的簇。然后，更新簇中心，根據(jù)當(dāng)前簇中的對(duì)象，重新計(jì)算每 個(gè)簇的中心(均值)，使用新的簇中心，將對(duì)象重新指派 到距簇中心最近的簇中，即重新計(jì)算每個(gè)對(duì)象到新的簇 中心的距離，將對(duì)象重新指派到距其最近的簇中。重復(fù) 這個(gè)過程，直到簇中對(duì)象的重新分布不再發(fā)生改變。優(yōu)點(diǎn)：k均值算法的結(jié)果簇是緊湊的，對(duì)于處理大數(shù)據(jù) 集，該算法是相對(duì)可伸縮的和有效率的。

3、它的計(jì)算復(fù)雜 度是0(nkt), n是對(duì)象總數(shù)，k是簇的個(gè)數(shù)，t是迭代 次數(shù)。通常該方法終止于局部最優(yōu)解.缺點(diǎn)：只有當(dāng)簇均值有定義的情況下k均值方法才能使 用，在某些應(yīng)用中，例如當(dāng)涉及具有分類屬性的數(shù)據(jù)時(shí), 均值可能無定義另外，用戶必須先給出簇的個(gè)數(shù)k也 是一個(gè)缺點(diǎn)，該算法不適合發(fā)現(xiàn)非凸形狀的簇，或者大 小差別很大的簇.它對(duì)噪聲和離群點(diǎn)是敏感的，少量的 這種數(shù)據(jù)會(huì)對(duì)均值產(chǎn)生很大的影響.所以對(duì)于k個(gè)初值的選取，通常采用一種啟發(fā)式的選取 方法，或者大多數(shù)情況下采取隨機(jī)選取的方法。因?yàn)閗 均值并不能保證全局最優(yōu)解，而是否能收斂到全局最優(yōu) 解其實(shí)和初值的選取有很大關(guān)系，所以通常會(huì)多次選取 初值運(yùn)行該算

4、法，然后選取一個(gè)最好的結(jié)果.2)基于代表對(duì)象的技術(shù)，k中心點(diǎn)法(k-medoids )k均值對(duì)離群點(diǎn)是敏感的，一個(gè)具有很大的極端值的對(duì) 象可能會(huì)顯著扭曲簇的分布，平方誤差函數(shù)的使用更是 嚴(yán)重惡化了這種敏感性。可不可以不采用簇中對(duì)象的均值作為參照點(diǎn)，而是在每 個(gè)簇中選取一個(gè)實(shí)際的對(duì)象來代表該簇。其余的每個(gè)對(duì) 象聚類到與其最相似的代表性的對(duì)象所在的簇中。這樣, 劃分方法仍然基于最小化對(duì)象與其對(duì)應(yīng)的參照點(diǎn)之間的相異度之和的原則來執(zhí)行。這就是k中心點(diǎn)聚類算法的 思想。k-means和k-medoids之間的差異就類似于一個(gè)數(shù)據(jù) 樣本的均值(mean)和中位數(shù)(median)之間的差異: 前者的取值范圍

5、可以是連續(xù)空間中的任意值，而后者只 能在給樣本給定的那些點(diǎn)里面選.那么，這樣做的好處是什么呢？ 一個(gè)最直接的理由就是k-means對(duì)數(shù)據(jù)的要求太高了，它使用歐氏距離描述數(shù)據(jù)點(diǎn)之間的差異(dissimilarity),從而可以直接通過求均值來計(jì)算中心點(diǎn).然而并不是所有的數(shù)據(jù)都能滿足這樣的要求，對(duì)于數(shù)值類型的特征，比如身高，可以很自然地用這樣的 方式來處理，但是類別(categorical)類型的特征就 不行了，這里歐氏距離沒法用了. 這里我們將準(zhǔn)則函數(shù)推廣成如下形式:E（P4）1 = 1 pWCj其中P是當(dāng)前對(duì)象，qi是簇Ci的代表對(duì)象（中心點(diǎn)），v 是一個(gè)任意的距離函數(shù)，也可以叫做是計(jì)算相異度

6、的函 數(shù)，而不在是已經(jīng)定死了的歐氏距離函數(shù)，這樣對(duì)數(shù)據(jù) 的要求就更低了，除此之外，由于中心點(diǎn)是在已有的數(shù) 據(jù)點(diǎn)里面選取的，因此相對(duì)于k-means來說，不容易受 到那些由于誤差之類的原因產(chǎn)生的離群點(diǎn)的影響，更加 robust 一些。k1 = 1 pGCrk中心點(diǎn)常用絕對(duì)誤差標(biāo)準(zhǔn)，如上式所示，其中P是當(dāng) 前對(duì)象，代表簇Ci中一個(gè)給定的點(diǎn)，Oj是簇Ci的代表對(duì) 象（中心點(diǎn)）。通常該算法重復(fù)迭代，直到每個(gè)代表對(duì)象 都成為他的簇的實(shí)際中心點(diǎn)，或者最靠近中心點(diǎn)的對(duì)象。 從k-means變到k-medoids ,時(shí)間復(fù)雜度陡然增加了 許多：在k-means中只要求一個(gè)平均值0（N）即可，而 在k-medo

7、ids中則需要枚舉每個(gè)點(diǎn)，并求出它到所有其 他點(diǎn)的距離之和，復(fù)雜度為0（N2）o迭代過程即用非代表對(duì)象替代當(dāng)前代表對(duì)象的過程：a）選取k個(gè)初始點(diǎn)作為k個(gè)代表對(duì)象，這個(gè)k個(gè)代表對(duì) 象是初始的k個(gè)簇的中心點(diǎn).開始迭代b）按照一種相似度計(jì)算法則將其余對(duì)象指派到最近的 代表對(duì)象所代表簇中c）隨機(jī)選取一個(gè)非代表對(duì)象0說。，用0訕。替換一個(gè)代 表對(duì)象0”代替后，所有剩余對(duì)象會(huì)重新分布（分四種 情況），然后計(jì)算替換前后的絕對(duì)誤差的差S,如果S小 于零，則用0“耐替換6,形成新的k個(gè)代表對(duì)象.否則 不變.迭代直至不在發(fā)生變化。2. 層次方法3. 基于密度的方法4. 基于模型的聚類方法（概率模型）期望最大化方法

8、EM每個(gè)簇可以用一個(gè)概率分布函數(shù)來描述，整個(gè)數(shù)據(jù)就是 這些分布的混合，其中每個(gè)單獨(dú)的分布通常稱作成員分 布，于是我們可以使用k個(gè)概率分布的有限混合密度模型對(duì)數(shù)據(jù)進(jìn)行聚類，其中每個(gè)分布代表一個(gè)簇。問題是 估計(jì)概率分布的參數(shù)，使得分布最好的擬合數(shù)據(jù)。Gaussian Mixture Model （GMM）假設(shè)數(shù)據(jù)服從 Mixture Gaussian Distribution ,換句話說,數(shù)據(jù)可 以看作是從數(shù)個(gè)Gaussian Distribution中生成出來 的。從中心極限定理可以看出，Gaussian分布（也叫做 正態(tài)（Normal）分布）這個(gè)假設(shè)其實(shí)是比較合理的，除 此之外，Gaussia

9、n分布在計(jì)算上也有一些很好的性質(zhì), 所以，雖然我們可以用不同的分布來隨意地構(gòu)造XX Mixture Model ,但是還是GMM最為流行。另外， Mixture Model本身其實(shí)也是可以變得任意復(fù)雜的，通 過增加Model的個(gè)數(shù)，我們可以任意地逼近任何連續(xù)的 概率密分布。每個(gè)GMM由個(gè)Gaussian分布組成，每 個(gè) Gaussian 稱為一個(gè)Component”，這些 Component 線性加成在一起就組成了 GMM的概率密度函數(shù)貝葉斯聚類是一種基于模型的聚類方法5、Spectral Cluster 譜聚類譜聚類算法建立在譜圖理論基礎(chǔ)上，與傳統(tǒng)的聚類 算法相比，它具有能在任意形狀的樣本空間上聚類且收 斂于全局最優(yōu)解的優(yōu)點(diǎn)（前面介紹的聚類算法都只能保 證得到局部最優(yōu)解）該算法首先根據(jù)給定的樣本數(shù)據(jù)集定義一個(gè)描述成 對(duì)數(shù)據(jù)點(diǎn)相似度的親合矩陣，并且計(jì)算矩陣的特征值和 特征向量，然后選擇合適的特征向量聚類不同的數(shù)據(jù) 點(diǎn)。譜聚類算法最初用于計(jì)算機(jī)視覺、VLSI設(shè)