第四章無(wú)監(jiān)督模式識(shí)別無(wú)監(jiān)督模式識(shí)別無(wú)監(jiān)督模式識(shí)別4.1

高斯混合模型4.2動(dòng)態(tài)聚類算法4.3層次聚類算法

無(wú)監(jiān)督模式識(shí)別4.1高斯混合模型4.2動(dòng)態(tài)聚類算法4.3層次聚類算法

無(wú)監(jiān)督模式識(shí)別4.1高斯混合模型

統(tǒng)計(jì)學(xué)習(xí)模型可以分為兩類，一類是概率模型，另一類是非概率模型。概率模型：概率模型的形式是P(Y|X)。如果輸入是X，輸出是Y，訓(xùn)練后模型得到的輸出不是一個(gè)具體的值，而是一系列的概率值。

對(duì)于聚類問(wèn)題來(lái)說(shuō)，就是輸入X對(duì)應(yīng)于各個(gè)不同聚類簇Y的概率，稱作軟聚類。4.1高斯混合模型非概率模型：

非概率模型的形式是一個(gè)決策函數(shù)Y=f(X)，如果輸入是X，輸出是Y，訓(xùn)練后模型得到的輸出是一個(gè)具體的值。對(duì)于聚類問(wèn)題來(lái)說(shuō)，輸入數(shù)據(jù)X后就可以通過(guò)模型映射得到唯一的判決結(jié)果Y，在無(wú)監(jiān)督學(xué)習(xí)中稱作硬聚類。4.1高斯混合模型高斯混合模型（GMM）：一種典型的概率模型。假設(shè)所有數(shù)據(jù)點(diǎn)都是由具有未知參數(shù)的有限個(gè)高斯分布混合產(chǎn)生的?？梢园迅咚够旌夏Ｐ涂醋魇菑V義的k-均值聚類，它包含了關(guān)于數(shù)據(jù)協(xié)方差結(jié)構(gòu)和隱含的高斯中心的信息。作為一種基于概率模型的軟聚類算法，高斯混合模型采用高斯分布作為參數(shù)模型，并使用期望最大化（EM）算法來(lái)求解模型參數(shù)。

4.1高斯混合模型高斯混合模型（GMM）：

高斯混合模型是用于估計(jì)樣本的概率密度分布的方法，其估計(jì)采用的模型是幾個(gè)在訓(xùn)練前就已經(jīng)建立好的高斯模型的加權(quán)和。高斯模型的數(shù)目是一個(gè)超參數(shù)，在模型建立前給定，每個(gè)聚類簇都對(duì)應(yīng)于一個(gè)高斯分布。對(duì)樣本中的數(shù)據(jù)給定的幾個(gè)高斯模型上分別進(jìn)行投影，就會(huì)得到樣本對(duì)應(yīng)在各個(gè)聚類簇上的概率。可以根據(jù)實(shí)際數(shù)據(jù)定義任何分布的混合模型，但是定義高斯分布更有利于計(jì)算。理論上，高斯混合模型可用于近似任何概率分布。

4.1.1單高斯模型單高斯模型的基本定義是：若隨機(jī)變量服從一個(gè)數(shù)學(xué)期望為、方差為的高斯分布，則該分布記為。在統(tǒng)計(jì)學(xué)中，指的就是樣本均值，為標(biāo)準(zhǔn)差。

一維情況下高斯分布的概率密度函數(shù)為：使用單高斯模型，可以簡(jiǎn)單地確定樣本是否屬于類別C。將樣本代入上式，當(dāng)概率值大于給定閾值時(shí)，就認(rèn)為該樣本屬于C類。

高維情況下的高斯分布模型的概率密度函數(shù)為：其中是d維的列向量，是模型的期望，是模型的方差。這里，用樣本均值來(lái)代替模型的期望，用樣本方差來(lái)代替模型方差。

單高斯分布模型可以擬合數(shù)據(jù)接近高斯分布的情況，但實(shí)際應(yīng)用中，數(shù)據(jù)的分布情況往往不滿足高斯分布，這就引入了高斯混合模型。4.1.1單高斯模型4.1.2高斯混合模型高斯混合模型假定樣本數(shù)據(jù)分布服從幾個(gè)高斯分布的加權(quán)和的形式。其中的任意一個(gè)高斯分布稱作這個(gè)模型的一個(gè)分量。是混合系數(shù)，表示每個(gè)分量的權(quán)重。需滿足：

上圖分別為單個(gè)高斯分布和兩個(gè)高斯分布情況下的高斯混合模型。從圖中可以看出數(shù)據(jù)明顯的分為兩簇，用單個(gè)高斯模型無(wú)法擬合這些數(shù)據(jù)，因此可以用兩個(gè)二維高斯分布來(lái)表示。4.1.2高斯混合模型將高斯混合模型用于聚類過(guò)程：先假設(shè)數(shù)據(jù)服從混合高斯分布，再根據(jù)

數(shù)據(jù)推出高斯混合模型的概率分布就可

以進(jìn)一步求出各個(gè)樣本屬于每個(gè)聚類類

別的概率。高斯混合模型的K個(gè)高斯模型實(shí)際上對(duì)應(yīng)K個(gè)聚類簇。高斯混合模型參數(shù)的求解，就是在只有樣本數(shù)據(jù)，而不知道樣本分類的情況下，計(jì)算出模型的隱含參數(shù)，和。這里的參數(shù)可以使用期望最大化（EM）算法來(lái)求解。

4.1.2高斯混合模型將高斯混合模型用于聚類的具體步驟Step1:以為概率隨機(jī)選擇K個(gè)高斯分布分量中

的一個(gè)；Step2:把樣本數(shù)據(jù)代入Step1中選中的高斯分布，

判斷輸出概率是否屬于大于閾值，如果不

屬于則返回Step1重新選擇。根據(jù)是否已知樣本分類情況，可以把高斯混合模型的求解問(wèn)題分為兩大類：樣本分類已知情況下的高斯混合模型和樣本分類未知情況下的高斯混合模型。4.1.2高斯混合模型將高斯混合模型用于聚類的具體步驟1.樣本分類已知情況下的高斯混合模型此時(shí)高斯混合模型的求解是一個(gè)有監(jiān)督學(xué)習(xí)過(guò)程。高斯混合模型的參數(shù)可以使用最大似然估計(jì)求解。具體模型參數(shù)按照以下公式求解：其中N為樣本容量，即樣本的數(shù)目，屬于每個(gè)分類的樣本數(shù)量分別是N1,N2,...,Nk，K為類別數(shù)目，L(k)表示屬于第k個(gè)分類的樣本的集合。4.1.2高斯混合模型將高斯混合模型用于聚類的具體步驟2.樣本分類未知情況下的高斯混合模型此時(shí)高斯混合模型的求解是一個(gè)無(wú)監(jiān)督學(xué)習(xí)過(guò)程。類似于有監(jiān)督的情況，假設(shè)有N個(gè)數(shù)據(jù)點(diǎn)，其服從某種分布Pr(x;θ)，我們的目標(biāo)是找到一組這種分布的參數(shù)θ，使得在這種分布下生成這些數(shù)據(jù)點(diǎn)的概率最大，也就是似然函數(shù)最大。似然函數(shù)可表示為：4.1.2高斯混合模型將高斯混合模型用于聚類的具體步驟2.樣本分類未知情況下的高斯混合模型在實(shí)際應(yīng)用中，往往常單個(gè)點(diǎn)分布的概率都很小，為了便于求解，一般對(duì)似然函數(shù)取對(duì)數(shù)，得到對(duì)數(shù)似然函數(shù)。對(duì)高斯混合模型求對(duì)數(shù)似然函數(shù)：這里每個(gè)樣本所屬的類別是隱含變量。我們的目標(biāo)是要找到一組最佳的模型參數(shù)，使得上式所示的期望最大，期望最大化算法（EM）的名字就由此而來(lái)。4.1.2高斯混合模型4.1.3EM算法求解高斯混合模型在統(tǒng)計(jì)模型中，EM算法是一種求參數(shù)的最大似然或最大后驗(yàn)概率(MAP)估計(jì)的迭代方法，其模型依賴于未觀測(cè)到的隱含變量。EM算法迭代地交替執(zhí)行期望(E)步和最大化(M)步，E步使用參數(shù)的當(dāng)前估計(jì)計(jì)算的對(duì)數(shù)似然的期望值創(chuàng)建函數(shù)，

M步計(jì)算最大化在E步上找到的期望對(duì)數(shù)似然的參數(shù)。然后用這些參數(shù)估計(jì)來(lái)確定下一步中隱含變量的分布。

EM要求解問(wèn)題的一般形式是：其中Y是隱含變量。如果已知數(shù)據(jù)點(diǎn)的分類標(biāo)簽Y，則可以使用最大似然估計(jì)直接求解模型參數(shù)。

EM算法的基本思路是：隨機(jī)初始化一組模型參數(shù)，并根據(jù)后驗(yàn)概率更新Y的預(yù)期，然后用

代替Y求出新的模型參數(shù)。如此迭代直到趨于穩(wěn)定。4.1.3EM算法求解高斯混合模型EM算法的具體步驟Step1:定義分量數(shù)目K，對(duì)每個(gè)分量k設(shè)置，

和的初始值，然后計(jì)算對(duì)數(shù)似然函數(shù)；Step2:E步：假設(shè)模型參數(shù)已知，引入隱含變量，該隱變量在高斯混合模型中表示數(shù)據(jù)點(diǎn)由各個(gè)分量生成的概率。4.1.3EM算法求解高斯混合模型EM算法的具體步驟Step3:M步：通過(guò)最大似然估計(jì)來(lái)求解模型參數(shù)。

現(xiàn)在我們認(rèn)為上一步求出的就是“數(shù)

據(jù)點(diǎn)由分量k生成的概率”。根據(jù)4.1.2

節(jié)介紹的

，和的公式可以推出：4.1.3EM算法求解高斯混合模型EM算法的具體步驟Step4:計(jì)算對(duì)數(shù)似然函數(shù)：Step5:檢查參數(shù)是否收斂或?qū)?shù)似然函數(shù)是否收 斂，若不收斂，則返回Step2。4.1.3EM算法求解高斯混合模型4.1.3EM算法求解高斯混合模型4.1.3EM算法求解高斯混合模型EM算法的實(shí)例1.怎么通俗易懂地解釋EM算法并且舉個(gè)例子?/question/279766342.如何感性地理解EM算法？/p/1121509ac1dc4.1

高斯混合模型4.2動(dòng)態(tài)聚類算法4.3層次聚類算法

無(wú)監(jiān)督模式識(shí)別4.2動(dòng)態(tài)聚類算法除了基于樣本概率分布模型的聚類方法外，基于樣本間相似性度量的聚類方法也是非監(jiān)督學(xué)習(xí)的重要組成部分。一般來(lái)說(shuō)，聚類準(zhǔn)則是根據(jù)樣本之間的距離或相似程度來(lái)定義的。例如以“類內(nèi)的差異盡量小，類間的差異盡量大”為聚類準(zhǔn)則，也就是將相似或相近的樣本分成一組，不同的或相距較遠(yuǎn)的樣本聚集在其他組中。動(dòng)態(tài)聚類算法的關(guān)鍵點(diǎn)是：1.選取一定的距離度量方法作為樣本間的相似性度量準(zhǔn)則。2.確定樣本的合理初始劃分，包括代表點(diǎn)的選擇，初始分類方法的選擇等。3.確定評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，對(duì)初始分類進(jìn)行調(diào)整，使其達(dá)到該準(zhǔn)則函數(shù)的極值。4.2動(dòng)態(tài)聚類算法

基于相似性度量的聚類方法又可以分為動(dòng)態(tài)聚類法和層次聚類法。4.2動(dòng)態(tài)聚類算法基于相似性度量的間接方法目標(biāo)：類內(nèi)樣本相似性高，類間樣本相似性低。要點(diǎn)：相似性度量：特征空間的某種距離度量。最常用歐式距離：準(zhǔn)則函數(shù)：聚類質(zhì)量的判別標(biāo)準(zhǔn)。常用最小誤差平方和準(zhǔn)則：4.2動(dòng)態(tài)聚類算法動(dòng)態(tài)聚類方法：對(duì)數(shù)據(jù)聚類的優(yōu)化過(guò)程是從”不合理的”劃分到“最佳”劃分，是一個(gè)動(dòng)態(tài)的迭代過(guò)程。要點(diǎn)：選定某種距離度量作為樣本間的相似性度量。確定樣本合理的初始分類，包括聚類中心的選擇等。確定某種評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，用以調(diào)整初始分類直至達(dá)到該準(zhǔn)則函數(shù)的極值。4.2.1K-均值算法K-均值(K-means)聚類算法是應(yīng)用最廣泛的基于劃分的聚類算法之一，適用于處理大樣本數(shù)據(jù)。它是一種典型的基于相似性度量的方法。目標(biāo)是根據(jù)輸入?yún)?shù)K將數(shù)據(jù)集劃分為K個(gè)簇。根據(jù)初始值、相似度、聚類均值計(jì)算策略的不同，有很多種K-均值的變種。在數(shù)據(jù)分布接近球體的情況下，K-均值具有較好的聚類效果。

4.2.1

K-均值算法

如圖，K-均值算法采用迭代更新的方法：在每一輪中，根據(jù)K個(gè)參考點(diǎn)將其周圍的點(diǎn)分成K個(gè)簇，并將每個(gè)簇的質(zhì)心作為下一次迭代的參考點(diǎn)。在連續(xù)迭代之后，所選擇的參考點(diǎn)越來(lái)越接近真實(shí)的聚類中心，聚類效果越來(lái)越好。對(duì)于重新劃分后的新簇，如果兩個(gè)相鄰的簇中心沒(méi)有變化，則誤差準(zhǔn)則函數(shù)已達(dá)到最小值，我們認(rèn)為聚類準(zhǔn)則函數(shù)已收斂，算法結(jié)束。K-均值算法流程圖

問(wèn)題：將N個(gè)樣本{x1,…,xN}劃分到k個(gè)類{C1,…,Ck}中，k為一正整數(shù)

目標(biāo)：使得各個(gè)數(shù)據(jù)與其對(duì)應(yīng)聚類中心點(diǎn)的誤差平方和最小Ji為第i

類聚類的目標(biāo)函數(shù)k為聚類個(gè)數(shù)x是劃分到類Ci的樣本m1,…,mk

是類C1,…,Ck的質(zhì)心（均值向量）(1)

k-均值聚類模型4.2.1

K-均值算法k-均值聚類算法流程Step1.初始化：隨機(jī)選擇k個(gè)樣本點(diǎn)，并將其視為各聚類的初始中心m1,…,mk

；Step2.按照最小距離法則逐個(gè)將樣本x劃分到以聚類中心m1,…,mk為代表的k個(gè)類C1,…,Ck中；Step3.計(jì)算聚類準(zhǔn)則函數(shù)J，重新計(jì)算k個(gè)類的聚類中心

m1,…,mk

；Step4.重復(fù)Step

2和3直到聚類中心m1,…,mk無(wú)改變或目標(biāo)函數(shù)J不減小?！安缓侠怼薄?gt;

“最佳”劃分4.2.1

K-均值算法算法實(shí)例例：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，如下表：樣本序號(hào)x1x2x3x4x5x6x7x8x9x10特征10101212367特征20011122266x11x12x13x14x15x16x17x18x19x20867897898967777888994.2.1

K-均值算法算法實(shí)例數(shù)據(jù)分布圖：4.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：Step1：令k=2，選初始聚類中心為Step2：計(jì)算所有樣本點(diǎn)到各聚類中心的距離因?yàn)?，所以?.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：因?yàn)椋?。同理，把所有其余點(diǎn)與兩個(gè)聚類中心的距離計(jì)算出來(lái)，并判斷其聚類歸屬。最終我們得到第一次迭代的聚類結(jié)果：第一類：第二類：4.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：Step3：根據(jù)新分成的兩類建立新的聚類中心4.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：Step4：判斷算法是否終止，由，新舊中心不相等，不滿足終止條件，轉(zhuǎn)置Step2.Step2：重新計(jì)算所有數(shù)據(jù)點(diǎn)到兩個(gè)聚類中心的距離，將它們歸為最近聚類中心，重新分為兩類，得到第二次迭代的聚類結(jié)果：第一類：第二類：4.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：Step3：更新聚類中心4.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：Step4：判斷算法是否終止，由，新舊中心不相等，不滿足終止條件，轉(zhuǎn)置Step2.Step2：重新計(jì)算所有數(shù)據(jù)點(diǎn)到兩個(gè)聚類中心的距離，將它們歸為最近聚類中心，重新分為兩類，得到第三次迭代的聚類結(jié)果：第一類：第二類：4.2.1

K-均值算法算法實(shí)例k-means計(jì)算步驟：Step3：更新聚類中心Step4：判斷算法是否終止，由于新舊中心相等，滿足終止條件，算法結(jié)束。4.2.1

K-均值算法k-均值聚類的特點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。當(dāng)類密集，且類與類之間區(qū)別明顯（比如球型聚集）時(shí)，聚類效果很好；缺點(diǎn)：結(jié)果與初始聚類中心有關(guān)；必須預(yù)先給出聚類的類別數(shù)k；對(duì)“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感，少量的這些數(shù)據(jù)對(duì)平均值產(chǎn)生較大的影響；不適合發(fā)現(xiàn)非凸面形狀的聚類4.2.1

K-均值算法k-means算法圖例演示較好的初始化

選取初始聚類中心4.2.1

K-均值算法k-means算法圖例演示較好的初始化

第一次迭代

4.2.1

K-均值算法k-means算法圖例演示較好的初始化

第二次迭代

4.2.1

K-均值算法k-means算法圖例演示較好的初始化

最終聚類結(jié)果4.2.1

K-均值算法k-means算法圖例演示較差的初始化

選取初始聚類中心最終聚類結(jié)果4.2.1

K-均值算法蝴蝶型數(shù)據(jù)集k-means算法圖例演示4.2.1

K-均值算法蝴蝶型數(shù)據(jù)集很明確的屬于Cluster1很明確的屬于Cluster2屬于Cluster1or2?4.2.1

K-均值算法蝴蝶型數(shù)據(jù)集**聚類中心4.2.1

K-均值算法不能處理任意形狀的聚類k-means算法圖例演示4.2.1

K-均值算法k-均值聚類算法分析k-means聚類算法對(duì)于不同的初始聚類中心，可能會(huì)得到不同的聚類結(jié)果。解決方法：多設(shè)置一些不同的初值，對(duì)比最后的運(yùn)算結(jié)果，直到結(jié)果趨于穩(wěn)定結(jié)束。聚類數(shù)未知情況下的聚類問(wèn)題解決方法：聚類分裂、合并確定聚類數(shù)——ISODATA

k值可以通過(guò)其他的算法來(lái)估計(jì)，如：BIC(Bayesianinformationcriterion)MDL(minimumdescriptionlength)4.2.1

K-均值算法k-means算法在圖像分割上的應(yīng)用例：圖像：一只遙望大海的小狗。此圖為100x100像素的JPG圖片，每個(gè)像素表示為三維向量（對(duì)應(yīng)JPEG圖像中的紅色、綠色和藍(lán)色道）；使用k-means算法對(duì)圖像進(jìn)行分割，將圖像分割為合適的背景區(qū)域（三個(gè)）和前景區(qū)域（小狗）。4.2.1

K-均值算法k-means算法在圖像分割上的應(yīng)用分割后的結(jié)果：注：最大迭代次數(shù)為20次，需運(yùn)行多次才能得到較好的效果。4.2.1

K-均值算法1965年美國(guó)L.A.Zadeh教授首次發(fā)表“FuzzySets”重要論文，奠定了模糊數(shù)學(xué)的理論基礎(chǔ)，目前“模糊數(shù)學(xué)”已廣泛應(yīng)用在系統(tǒng)工程、生物科學(xué)、社會(huì)科學(xué)等領(lǐng)域中。模糊集理論：在傳統(tǒng)集合理論中，一個(gè)元素或者屬于一個(gè)集合，或者不屬于一個(gè)集合；而對(duì)于模糊集來(lái)說(shuō)，每一個(gè)元素是以一定的程度屬于某個(gè)集合，也同時(shí)可以以不同的程度屬于幾個(gè)集合。模糊性:“高矮”、“胖瘦”、“年青”、“大胡子”模糊性的存在需要把模糊數(shù)學(xué)理論引入模式識(shí)別之中。模糊聚類方法是模糊模式識(shí)別中最有代表性的方法。模糊數(shù)學(xué)概論4.2.2

模糊聚類算法隸屬度函數(shù)：表示一個(gè)對(duì)象x隸屬于集合A的程度的函數(shù)，通常記為，其自變量范圍是所有可能屬于集合A的對(duì)象（即集合A所有空間中的所有點(diǎn)），取值范圍是[0，1]，即。表示x完全屬于集合A，相當(dāng)于傳統(tǒng)集合概念上的；則表示x完全不屬于集合A，相當(dāng)于傳統(tǒng)集合概念上的。模糊集的基本知識(shí)4.2.2

模糊聚類算法模糊集合：

模糊集合也稱模糊子集,是由其隸屬函數(shù)來(lái)定義的。

定義：在空間上的隸屬度函數(shù)就定義了一個(gè)模糊集合A。對(duì)于有限個(gè)對(duì)象，模糊集合A可以表示為：

例子：用水溫來(lái)表示開(kāi)水這個(gè)概念，(a)和(b)是確定性集合，分別表示100度和80~100度的水；(c)是模糊集合，用隸屬度函數(shù)來(lái)表示。這種表示更接近我們?nèi)粘＠斫?。模糊集的基本知識(shí)4.2.2

模糊聚類算法設(shè)：A，B為一個(gè)空間上的兩個(gè)模糊集，則它們的并集A∪B、交集A∩B、及A的補(bǔ)集仍為模糊集，則它們的隸屬函數(shù)為：并集:μA∪B(x)＝max{μA(x),μB(x)}交集:μA∩B(x)＝min{μA(x),μB(x)}補(bǔ)集:=1-μB(x),μA(x),μB(x)分別為A、B的隸屬函數(shù)模糊集的簡(jiǎn)單運(yùn)算4.2.2

模糊聚類算法特征的模糊化是指根據(jù)一定的模糊化規(guī)則把普通意義下的一個(gè)或幾個(gè)特征變量變成多個(gè)模糊變量,用來(lái)表達(dá)原始特征的某一局部特性。比如，人的體重作為一個(gè)特征使用，可以分為偏輕、中等和偏重三個(gè)模糊特征。特征模糊化的目的在于用一個(gè)特征參與分類，正確分類結(jié)果與這個(gè)特征之間可能是復(fù)雜的非線性關(guān)系；而根據(jù)先驗(yàn)知識(shí)提取一些模糊特征，雖然特征數(shù)目多了，可卻可能使分類結(jié)果與特征之間的關(guān)系線性化，簡(jiǎn)化了分類器的設(shè)計(jì)和提高了分類性能。模糊化特征4.2.2

模糊聚類算法在普通模式識(shí)別中,分類就是把樣本空間(或樣本集)分成若干個(gè)子集。在模糊模式識(shí)別中,用模糊子集代替確定子集,從而得到模糊的分類結(jié)果,即分類結(jié)果的模糊化,其中,一個(gè)樣本以不同的程度屬于各個(gè)類別,而不再屬于某個(gè)確定的類別。模糊分類與確定的分類結(jié)果相比,模糊化的分類結(jié)果主要有兩個(gè)顯著的優(yōu)點(diǎn):可以反映出分類過(guò)程中的不確定性,有利于用戶根據(jù)結(jié)果進(jìn)行決策。模糊化的分類結(jié)果比明確的分類結(jié)果中包含更多的信息,有利于進(jìn)一步?jīng)Q策。4.2.2

模糊聚類算法K-均值算法屬于硬聚類算法，它把數(shù)據(jù)點(diǎn)劃分到確切的某一聚類中。而在模糊聚類（亦稱軟聚類）中，數(shù)據(jù)點(diǎn)則可能歸屬于不止一個(gè)聚類中，并且這些聚類與數(shù)據(jù)點(diǎn)通過(guò)一個(gè)成員水平（實(shí)際上類似于模糊集合中隸屬度的概念）聯(lián)系起來(lái)。成員水平顯示了數(shù)據(jù)點(diǎn)與某一聚類之間的聯(lián)系有多強(qiáng)。模糊聚類就是計(jì)算這些成員水平，按照成員水平來(lái)決定數(shù)據(jù)點(diǎn)屬于哪一個(gè)或哪些聚類的過(guò)程。模糊C均值算法（Fuzzyc-Means，F(xiàn)CM）是最廣泛使用的模糊聚類算法之一。

4.2.2

模糊聚類算法模糊C均值(FCM)算法C均值：

把N個(gè)樣本{x1,x2,…,xN}劃分成C個(gè)子類G1,G2,…,GC,使得所有樣本到聚類中心的距離平方和最小,也就是使下式的準(zhǔn)則函數(shù)達(dá)到最小。mj為第j個(gè)子類Gj的聚類中心;xi表示分到Gj的所有樣本,j=1,2,…,C。模糊C均值：在C均值算法中,把硬分類變?yōu)槟：齽澐帧ＴO(shè)μj(xi)是第i個(gè)樣本xi屬于第j類Gj的隸屬度,利用隸屬度定義的聚類準(zhǔn)則函數(shù)為：(1)4.2.2

模糊聚類算法其中,b>1是一個(gè)可以控制聚類結(jié)果的模糊程度的常數(shù)。約束條件為一個(gè)樣本屬于各個(gè)聚類的隸屬度之和為1,即(2)利用拉格朗日乘數(shù)法來(lái)求解在條件式(2)約束下式(1)的極小值。令優(yōu)化的目標(biāo)函數(shù)為(3)(1)4.2.2

模糊聚類算法(4)分別求L對(duì)mi、λi和μj(xi)的梯度(或偏導(dǎo)),并置為0,可得必要條件:(5)4.2.2

模糊聚類算法模糊C均值(FCM)算法步驟Step1：設(shè)定聚類數(shù)目C、參數(shù)b和一個(gè)適當(dāng)?shù)男?shù)ε>0,通常取1<b≤5。Step2：初始化各個(gè)聚類中心m(s)

，迭代次數(shù)s=0。Step3：根據(jù)式(5)更新隸屬度函數(shù)；Step4：根據(jù)式(4)更新聚類中心m(s+1)；

(5)(4)4.2.2

模糊聚類算法Step5：如果‖m(s)－m(s+1)‖<ε，則停止迭代，輸出聚類中心和隸屬度函數(shù)，否則s=s+1,返回步驟(3)。

輸出：將樣本點(diǎn)劃分為隸屬度最大的那一類。

模糊C均值(FCM)算法步驟4.2.2

模糊聚類算法

FCM算法的輸出是C個(gè)簇的中心點(diǎn)矢量和的模糊矩陣，這個(gè)矩陣表示的是每個(gè)樣本點(diǎn)屬于每個(gè)類的隸屬度。根據(jù)該模糊矩陣，按照模糊集中哪個(gè)類別的隸屬度最大，就將該樣本劃分到哪個(gè)類別的原則對(duì)所有樣本點(diǎn)進(jìn)行劃分。聚類簇的中心代表了每個(gè)簇的平均特征，因此聚類中心可以視為此聚類簇的一個(gè)代表點(diǎn)。FCM算法對(duì)于滿足正態(tài)分布的數(shù)據(jù)聚類效果會(huì)很好。此外，類似于K-均值中的情況，算法對(duì)孤立點(diǎn)是敏感的。4.2.2

模糊聚類算法算法實(shí)例例：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，如下表：樣本序號(hào)x1x2x3x4x5x6x7x8x9x10特征10101212367特征20011122266x11x12x13x14x15x16x17x18x19x20867897898967777888994.2.2

模糊聚類算法數(shù)據(jù)分布圖：算法實(shí)例4.2.2

模糊聚類算法FCM計(jì)算步驟：Step1：設(shè)定聚類數(shù)目C=2、參數(shù)b和一個(gè)適當(dāng)?shù)男?shù)ε=0.01。Step2：初始化聚類中心m(0)=[0.30.3;33;];Step3：更新隸屬度函數(shù)U(0)=算法實(shí)例4.2.2

模糊聚類算法Step4：更新聚類中心m(1)=[1.94091.8780;6.46266.1026;];Step5：如果‖m(1)－m(0)‖<ε，則停止迭代，否則s=s+1;Step3:更新隸屬度函數(shù)U(1)=算法實(shí)例4.2.2

模糊聚類算法Step4：更新聚類中心m(2)=[1.34281.2157;7.58277.2483;]Step5：如果‖m(2)－m(1)‖<ε，則停止迭代，否則s=s+1;Step3:更新隸屬度函數(shù)U(2)=算法實(shí)例4.2.2

模糊聚類算法Step4：更新聚類中心m(3)=[1.24461.1292;7.68207.3414;]Step5：如果‖m(3)－m(2)‖<ε，則停止迭代，否則s=s+1;Step3:更新隸屬度函數(shù)U(3)=算法實(shí)例4.2.2

模糊聚類算法Step4：更新聚類中心m(4)=[1.23891.1251;7.68907.3480;]Step5：如果‖m(4)－m(3)‖<ε，則停止迭代，否則s=s+1;Step3:更新隸屬度函數(shù)U(4)=算法實(shí)例4.2.2

模糊聚類算法Step4：更新聚類中心m(5)=[1.23861.1250;7.68957.3485;]Step5：如果‖m(5)－m(4)‖<ε，則停止迭代，輸出：算法實(shí)例4.2.2

模糊聚類算法

K均值聚類：硬聚類算法，隸屬度只有兩個(gè)取值0或1，提出的基本根據(jù)是“類內(nèi)誤差平方和最小化”準(zhǔn)則；模糊的c均值聚類：模糊聚類算法，是k均值聚類算法的推廣形式，隸屬度取值為[0

1]區(qū)間內(nèi)的任何一個(gè)數(shù)，提出的基本根據(jù)是“類內(nèi)加權(quán)誤差平方和最小化”準(zhǔn)則；優(yōu)缺點(diǎn)：簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。結(jié)果與初始聚類中心有關(guān)，容易陷入局部極值點(diǎn)；必須預(yù)先給出聚類的類別數(shù)k；動(dòng)態(tài)聚類算法總結(jié)與分析第三次大作業(yè)Kmeans和FCM算法要求：1.查閱無(wú)監(jiān)督聚類的評(píng)價(jià)標(biāo)準(zhǔn)有哪些，選擇其中一個(gè)標(biāo)準(zhǔn)作為后續(xù)試驗(yàn)的驗(yàn)證指標(biāo)。2.sonar和Iris數(shù)據(jù)上分別驗(yàn)證兩種聚類算法。同時(shí)，也可以先利用kmeans算法選擇初始聚類中心，然后再使用FCM聚類，觀察其結(jié)果。選做：小狗圖像數(shù)據(jù)上驗(yàn)證算法FCM公式詳細(xì)推導(dǎo)/qq_44106818/article/details/104447781聚類結(jié)果的評(píng)價(jià)指標(biāo)/qq_36064669/article/details/825865824.1

高斯混合模型4.2動(dòng)態(tài)聚類算法4.3層次聚類算法

無(wú)監(jiān)督模式識(shí)別4.3層次聚類算法

基于劃分的聚類算法可以將數(shù)據(jù)集劃分為指定數(shù)量的聚類簇，但在某些情況下，數(shù)據(jù)集需要在不同的級(jí)別進(jìn)行劃分。例如，作為班主任，可以將所有同學(xué)組織成較大的團(tuán)隊(duì)，例如班委和普通同學(xué);然后可以將它們進(jìn)一步分成更小的組。例如，班委可以進(jìn)一步分為幾組：學(xué)生負(fù)責(zé)人（班長(zhǎng)、副班長(zhǎng)）、學(xué)習(xí)類班委（學(xué)習(xí)委員、紀(jì)律委員）和生活類班委（生活委員、宣傳委員）等。

所有這些組織方法形成一個(gè)層次結(jié)構(gòu)，從中可以輕松地匯總或表征每個(gè)級(jí)別的數(shù)據(jù)。4.3

層次聚類算法

使用基于劃分的聚類算法（例如K-均值）的一個(gè)問(wèn)題是需要指定聚類的數(shù)目K。然而，在實(shí)際應(yīng)用中，往往不能預(yù)先確定簇的數(shù)目，有時(shí)根據(jù)數(shù)據(jù)的不同特點(diǎn)，所需的K值也可能會(huì)發(fā)生變化。例如對(duì)于如下圖所示的數(shù)據(jù)分布：

直觀地，將上圖中所示的數(shù)據(jù)劃分為2個(gè)簇，4個(gè)簇或甚至16個(gè)簇都是合理的。

因此，特定數(shù)據(jù)集應(yīng)該聚成多少個(gè)簇通常取決于我們研究該數(shù)據(jù)集的尺度。4.3

層次聚類算法

層次聚類算法主要分為分裂的和凝聚的兩類，具體決于其層次結(jié)構(gòu)是“自上而下”還是“自下而上”的。

分裂方法：自上而下，首先把所有樣本數(shù)據(jù)歸為同一個(gè)聚類簇。然后遞歸地把這些聚類簇劃分成更小的子聚類簇，直到每一個(gè)樣本都單獨(dú)作為一個(gè)聚類簇，或滿足某個(gè)終止條件。常見(jiàn)的基于分裂方的的算法有層次K-均值算法。

凝聚方法：自下而上，數(shù)據(jù)集中的每個(gè)樣本首先被視為一個(gè)聚類簇，然后迭代地將這些較小的簇合并為更大的聚類簇。直到最后所有樣本被歸為一個(gè)大聚類簇，或滿足某個(gè)終止條件。4.3

層次聚類算法4.3.1自上而下的算法

層次K-均值算法是一種典型的“自上而下”的層次聚類算法，它使用到了基于劃分的動(dòng)態(tài)聚類算法：K-均值，具體算法步驟如下：Step1：把所有樣本數(shù)據(jù)歸到一個(gè)簇C中，這個(gè)簇 就是層次結(jié)構(gòu)的根；Step2：使用K-均值算法把簇C劃分成指定的K個(gè) 子簇，i=1,2,…,k，形成一個(gè)新的層；Step3：對(duì)于在步驟2中生成的K個(gè)簇，使用K均值 算法將它們遞歸地劃分為更小的子簇。直 到無(wú)法再劃分（每個(gè)群集中只包含一個(gè)樣 本），或滿足終止條件。

算法實(shí)例例：如下圖，展示了一組數(shù)據(jù)經(jīng)過(guò)兩次層次K-均值算法迭代的過(guò)程。4.3.1

自上而下的算法算法實(shí)例

首先對(duì)一組數(shù)據(jù)進(jìn)行K=2的K-均值聚類，得到兩組數(shù)據(jù)。再對(duì)這兩組數(shù)據(jù)分別進(jìn)行K=2的K-均值聚類，此時(shí)數(shù)據(jù)被劃分為四組。之后再進(jìn)一步對(duì)數(shù)據(jù)進(jìn)行劃分，就可以得出自上而下的聚類結(jié)果。4.3.1

自上而下的算法

層次K-均值算法的一個(gè)問(wèn)題是，一旦兩個(gè)樣本在開(kāi)始時(shí)被分成不同的簇，即使兩點(diǎn)之間的距離非常接近，它們也不會(huì)在以后的聚類過(guò)程中聚