moead算法流程步骤_数据聚类（一）常见聚类算法的基本原理[图解]
相關(guān)名詞的英文翻譯
監(jiān)督學(xué)習(xí)Supervised Learning無監(jiān)督學(xué)習(xí)Unsupervised Learning半監(jiān)督學(xué)習(xí)Semi-Supervised Learning, SSL強(qiáng)化學(xué)習(xí)Reinforcement Learning, RL聚類 Clustering高斯混合模型Gaussian Mixture Model, GMM最大期望算法Expectation-Maximization algorithm, EMDBSCAN聚類算法Density-Based Spatial Clustering of Applications with Noise層次聚類Hierarchical Clustering學(xué)習(xí)向量量化Learning Vector Quantization, LVQ一、無監(jiān)督學(xué)習(xí)與聚類01Learning家族機(jī)器學(xué)習(xí)的一種常見劃分方式如下
【監(jiān)督學(xué)習(xí)】訓(xùn)練數(shù)據(jù)有標(biāo)簽，使機(jī)器根據(jù)已有的示例進(jìn)行學(xué)習(xí)，如分類和回歸【無監(jiān)督學(xué)習(xí)】
訓(xùn)練數(shù)據(jù)無標(biāo)簽，機(jī)器根據(jù)數(shù)據(jù)性質(zhì)自主進(jìn)行學(xué)習(xí)，如聚類【半監(jiān)督學(xué)習(xí)】
訓(xùn)練時使用大量未標(biāo)記數(shù)據(jù)及一部分標(biāo)記數(shù)據(jù)，充分利用未標(biāo)記樣本來提升模型的泛化能力【強(qiáng)化學(xué)習(xí)】
在學(xué)習(xí)過程中不斷收到環(huán)境的反饋，最佳的行為由環(huán)境的正回報來強(qiáng)化，強(qiáng)化學(xué)習(xí)的典型代表為AlphaGo02聚類任務(wù)
聚類任務(wù)是一種無監(jiān)督學(xué)習(xí)，通過聚類將數(shù)據(jù)集中的樣本劃分為若干子集(“簇”)，每個簇可能對應(yīng)于一些潛在的概念和類別。之所以說是“潛在”，是因為聚類得到的劃分結(jié)果是事先未知的，因此通過聚類任務(wù)，可以發(fā)掘數(shù)據(jù)內(nèi)在的分布結(jié)構(gòu)，探究數(shù)據(jù)樣本之間的潛在聯(lián)系。
二、K-Means算法01K-Means算法原理演示現(xiàn)在有一個任務(wù)，把下面六個點分成兩類：
首先選擇兩個點作為初始中心(x1和x2)
分別計算剩下的四個點到兩個初始中心的距離，選擇距離較近的一個初始中心，歸為一類
第1次迭代完成，六個樣本被分成了兩類{x1,x3,x5}(黃色)和{x2,x4,x6}(藍(lán)色)，然后對于劃分好的兩類，重新計算每一類的均值，如紅色點1和2所示
開始第2次迭代，計算每個樣本點到兩個新均值的距離，選擇距離較近的一個中心歸為一類
第2次迭代結(jié)束之后，六個樣本被重新分成了兩類{x1,x3,x5,x6}(黃色)和{x2,x4 }(藍(lán)色)，重新計算每一類的均值，如紅色點1和2所示。
判斷這次迭代得到的中心點與上次迭代的結(jié)果是否有更新，若有變動，則繼續(xù)上述過程，計算每個樣本點到兩個中心的距離，生成新的簇劃分，再計算新的簇中心……依次循環(huán)，直至各個簇的中心點不再更新，得到最終的聚類結(jié)果。
注：上述過程給出的距離劃分結(jié)果僅用作演示說明算法的流程，并非嚴(yán)格按照背景方格紙的刻度進(jìn)行計算得出。
02算法實現(xiàn)流程【輸入】樣本集和預(yù)設(shè)聚類個數(shù)k【過程】給定樣本集
k均值算法針對聚類所得的簇劃分最小化平方誤差
其中
表示第i簇的均值向量。E在一定程度上刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度，求解簇劃分的過程即為最小化上述E值的過程。但直接求解E的最小值需要考察樣本集D內(nèi)所有可能的簇劃分，這是一個NP難問題。因此在k均值算法的實際求解中，采用了貪心策略，通過迭代更新當(dāng)前的簇劃分及均值向量進(jìn)行近似求解。
05K-Means算法的變體：K-modes和K-prototypeK-Means是用每個聚類中的均值(mean)做中心點，K-Modes是用每個聚類中的眾數(shù)(mode)做中心點。通常K-Means較多使用歐式距離，而K-Modes一般是漢明距離，也就是對于每個特征來說，如果不同記為1，相同則為0。
K-prototype則是K-means與K-modes的一種結(jié)合形式。
K-modes算法的適用情形：對于非數(shù)值集合上的聚類任務(wù)，我們通常會采用K-modes算法，將原本K-means使用的歐式距離替換成字符間的漢明距離。
K-prototype算法的適用情形：適用于數(shù)值類型與字符類型結(jié)合的數(shù)據(jù)。
三、高斯混合聚類算法01高斯混合聚類的基本思想高斯混合聚類的過程比較抽象，它采用概率模型來表達(dá)聚類原型。高斯混合模型不僅考慮到了數(shù)據(jù)分布的均值，同時也考慮到了協(xié)方差。通常利用最大期望算法(EM算法)對高斯混合模型中的參數(shù)進(jìn)行估計。EM算法的推導(dǎo)過程較為復(fù)雜，該過程的數(shù)學(xué)推導(dǎo)在后面單獨(dú)作為一個篇幅來整理。02高斯混合聚類過程演示在此給出算法復(fù)現(xiàn)的結(jié)果，直觀地對混合高斯模型在聚類中的應(yīng)用進(jìn)行理解。圖中實線是數(shù)據(jù)對應(yīng)的真實的高斯分布，虛線是估計的高斯分布，從迭代過程可以看出，高斯分布的參數(shù)不斷更新，最終估計出的高斯分布與實際值幾乎完全重合。
03高斯混合聚類算法流程【輸入】樣本集和高斯混合成分的個數(shù)【過程】K-Means算法可以看做是高斯混合聚類的一個特例，它的各混合成分方差相等，且每個樣本僅指派一個混合成分。
同樣可以使用EM算法對K-means算法進(jìn)行推導(dǎo)：K-means中每個樣本所屬的類就可以看成是一個隱變量，在E步中，我們固定每個類的中心，通過對每一個樣本選擇最近的類優(yōu)化目標(biāo)函數(shù)；在M步，重新更新每個類的中心點，該步驟可以通過對目標(biāo)函數(shù)求導(dǎo)實現(xiàn)，最終可得新的類中心就是類中樣本的均值。
對高斯混合聚類過程的深入了解需要理解EM算法的原理，后面會對其數(shù)學(xué)推導(dǎo)另做整理。
四、DBSCAN算法01與DBSCAN算法相關(guān)的概念定義理解DBSCAN算法首先要理解以下幾個概念：
- ε鄰域：首先我們需要設(shè)定一個鄰域參數(shù)ε(即下圖中的max_dis)，樣本x的ε鄰域包含了樣本集中所有與該樣本距離小于ε的樣本。例如下圖中的兩個紅色區(qū)域，分別表示樣本x1和x3的ε鄰域。
- 核心對象：我們需要設(shè)定一個MinPts參數(shù)，當(dāng)樣本x的ε鄰域內(nèi)樣本數(shù)大于等于MinPts個時，我們將x稱為一個核心對象。在下圖中，假設(shè)MinPts=3，則我們可以將x1看做一個核心對象，其ε鄰域內(nèi)包含了三個樣本{x1,x2,x5}
- 密度直達(dá)：假設(shè)有兩個樣本xi和xj，如果xj位于xi的ε鄰域中，并且xi是核心對象，那么我們稱xj由xi密度直達(dá)。在下圖中，x2位于x1的ε鄰域內(nèi)，且x1是核心對象，所以我們可以說x2可由x1密度直達(dá)。
- 密度可達(dá)：對xi與xj，若存在樣本序列p1,p2,p3,...pn，其中p1=x1,pn=xj，且pi+1由pi密度直達(dá)，則稱xi與xj密度可達(dá)。在下圖中，x2可由x1密度直達(dá)，x3可由x2密度直達(dá)，所以我們認(rèn)為x1和x3是密度可達(dá)的。
基于上面的幾種概念，給出DBSCAN算法的基本流程：
【輸入】樣本集和鄰域參數(shù)，其中鄰域參數(shù)包括判斷為領(lǐng)域內(nèi)樣本的最大距離max_dis、樣本被看作核心對象的最小鄰域內(nèi)樣本數(shù)量min_pts
【過程】
根據(jù)鄰域參數(shù)max_dis確定每個樣本的鄰域，統(tǒng)計鄰域內(nèi)樣本個數(shù)
根據(jù)鄰域參數(shù)min_pts生成核心對象集合
重復(fù)步驟4-5直至核心對象集合為空
隨機(jī)選取一個核心對象，找到這個核心對象的所有密度可達(dá)的樣本，構(gòu)成一個聚類簇
在核心對象集合中去除包含在該聚類簇中的樣本
【輸出】簇劃分結(jié)果
03DBSCAN算法執(zhí)行過程演示生成一組模擬數(shù)據(jù)用于聚類，數(shù)據(jù)分布如下：
設(shè)定兩個鄰域參數(shù)，找出核心對象集合(下圖中紅色點)
隨機(jī)選取一個核心對象，找到這個核心對象的所有密度可達(dá)的樣本，構(gòu)成一個聚類簇。(圖中紅色點表示選取的核心對象)，重復(fù)該過程直至核心對象集合為空
檢測到核心樣本集合為空，停止聚類，得到最終的聚類結(jié)果。
我們可以看到邊緣稀疏處，深藍(lán)色的點表示被識別為噪聲數(shù)據(jù)的樣本。這里就涉及到鄰域參數(shù)的選擇，參數(shù)設(shè)置不當(dāng)可能會導(dǎo)致大量噪聲樣本，或者所有數(shù)據(jù)均聚成一簇(即樣本間全部密度可達(dá))。五、AGNES算法01AGNES算法基本思想AGNES算法是一種常見的層次聚類算法，它采用自底向上的聚合策略，該算法的原理非常簡單：先將數(shù)據(jù)集中的每個樣本看作一個初始聚類簇，然后在算法運(yùn)行的每一步中找出距離最近的兩個聚類簇進(jìn)行合并，直到達(dá)到預(yù)設(shè)的聚類簇個數(shù)為止。
在算法復(fù)現(xiàn)過程中，為了方便進(jìn)行聚類簇合并及層次遍歷操作，可以選擇借助二叉樹進(jìn)行該過程的模擬。
隨著聚類的進(jìn)行，每一步都有兩個簇被歸并為一個新的簇，顯然這種方式有助于發(fā)現(xiàn)各個簇之間的層次關(guān)系，并能夠?qū)ψ钸m用的聚類數(shù)目進(jìn)行探索。但是，每個步驟都需要完成當(dāng)前所有簇兩兩之間距離的計算，該算法的復(fù)雜度非常高。
02算法流程【輸入】樣本集及聚類簇數(shù)
【過程】
算法由將每個樣本作為一個簇開始執(zhí)行，每一步合并兩個簇，當(dāng)算法執(zhí)行到聚成7個簇時，在模擬數(shù)據(jù)上的聚類結(jié)果如下圖：
接下來，黃色和紫色的兩個簇進(jìn)行了合并，聚成6類
接下來，藍(lán)色和紅色的兩個簇進(jìn)行了合并，聚成5類
以此類推，聚成4類時：
聚成3類時：
六、學(xué)習(xí)向量量化(LVQ)算法01LVQ算法的基本思想除了上面介紹的幾種聚類算法外，還有一種比較特殊的聚類算法，它屬于“監(jiān)督學(xué)習(xí)”的范疇，學(xué)習(xí)向量量化聚類方法的每個樣例均有類別標(biāo)簽。該算法的輸出是一組原型向量，每個原型向量定義了與之相關(guān)的一個區(qū)域，區(qū)域中每個樣本與自身類別的原型向量的距離不大于它與其他原型向量的距離。
02算法流程該算法實現(xiàn)的流程如下，不斷調(diào)整原型向量使其對樣本空間的劃分更符合實際的類別標(biāo)簽劃分：
【輸入】樣本集，聚類個數(shù)，原型向量預(yù)設(shè)類別標(biāo)記，學(xué)習(xí)率
【過程】
【輸出】一組原型向量
03LVQ算法聚類過程演示通過聚類的過程來直觀地理解原型向量如何對樣本空間進(jìn)行切分：
生成如下所示的模擬數(shù)據(jù)，進(jìn)行LVQ聚類。
下面的動圖展示了聚類過程中的原型向量變化(四個紅色點表示一組原型向量，將樣本空間分為四份)04LVQ算法的數(shù)學(xué)表示給定樣本集
每個樣本xj是由個n屬性描述的特征向量
yj是樣本的類別標(biāo)記。LVQ的目標(biāo)是學(xué)得一組n維的原型向量
每個原型向量代表了一個聚類簇。對于樣本空間X，學(xué)習(xí)到一組原型向量后，每個樣本x將被劃入與其距離最近的原型向量所代表的簇中：???
式中每個原型向量pi定義了一個與之相關(guān)的區(qū)域Ri，該區(qū)域中的每個樣本與pi的距離不大于它與其他原型向量的距離。由此形成的樣本空間X的簇劃分
稱為“Voronoi剖分”。
END 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖總結(jié)
以上是生活随笔為你收集整理的moead算法流程步骤_数据聚类（一）常见聚类算法的基本原理[图解]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： bartlett方差齐性检验_基于R实现
- 下一篇： mac版lightroom cc_Pho