机器学习——聚类算法
文章目錄
- 聚類算法
- 1 k-Means算法
- 1.1 基本概念
- 1.2 k-Means算法原理
- 1.3 k-Means算法的可視化演示
- 1.4 實驗
- 2 DBSCAN算法
- 2.1 基本概念
- 2.2 DBSCAN算法原理
- 2.3 DBSCAN算法的可視化演示
- 2.4 實驗
- 總結
聚類算法
在機器學習中，若訓練樣本的標記信息未知，則稱為無監(jiān)督學習。無監(jiān)督學習通過對無標記訓練樣本的學習來尋找這些數(shù)據(jù)的內(nèi)在性質(zhì)，其主要的工具就是聚類算法。
1 k-Means算法
k-Means算法也稱為k-平均或k-均值算法，是一種聚類算法，它是一種基于相似性的無監(jiān)督學習，通過比較樣本之間的相似性，將較為相似的樣本劃分到同一個類別中。由于k-Means算法簡單、易于實現(xiàn)的特點，故在圖像分割中得到廣泛的應用。
1.1 基本概念
簇：把數(shù)據(jù)分為幾類，每一類就是一個簇，也是k的由來。
歐式距離（歐幾里得距離）：計算兩個點之間的距離，即計算數(shù)據(jù)與指定點的距離的衡量。二維空間的兩點歐式距離表示為：
兩個n向量a和b之間的歐式距離：
該式也可以表示成向量運算的形式：
質(zhì)心：每次分類后求得的均值。
1.2 k-Means算法原理
k-Means算法主要分為以下三個步驟：
對于一個表示為m*n矩陣的樣本，假設歸為k個類，分別為{C1, C2, ···, Ck}。
k-Means算法的目標是使得每一個樣本X被劃分到最相似的類別中，利用每個類別的 樣本重新計算聚類中心Ck：
k-Means算法的停止條件是最終的聚類中心不再改變，此時所有的樣本被劃分到了最近的聚類中心所屬的類別中：
其中樣本X(i)數(shù)據(jù)集中的第i行，Cj表示的是第j個聚類中心。
1.3 k-Means算法的可視化演示
在演示模型中隨機生成一些數(shù)據(jù)點，并以高斯分布的形式出現(xiàn)：
然后添加三個隨機的質(zhì)心作為初始化的點：
可以看到這三個點距離很近，就意味著他們可能并不能對這三堆數(shù)據(jù)進行正確的分組。換句話說就是初始點的選擇會影響最終的分類結果。接下來就要用所有的數(shù)據(jù)對這個三個點求距離來看那些數(shù)據(jù)離哪個點最近。那么就認為他們是一類。
第一步之后，可以看到所有的數(shù)據(jù)點都被分類。接下來要對三堆數(shù)據(jù)重新求質(zhì)心，即對他們每一類求均值。
更新完質(zhì)心即新的質(zhì)心到了圖中的新位置。接下來做相同動作，針對新的三個質(zhì)心求距離將數(shù)據(jù)重新分類。一直重復直到數(shù)據(jù)點不發(fā)生變化。
可以看出正是由于初始的質(zhì)心選擇不好，所以導致沒有一個相對正確的結果。那么重新選擇三個質(zhì)心，完成上述的步驟。
可以看到重新選擇了三個初始點，得到的結果相對正確了許多。
接下來選擇不規(guī)則的圖形進行演示。
上圖對一個笑臉圖進行分類發(fā)現(xiàn)得到的并不是我們想要的結果，那就說明k-Means算法對于任意形狀的圖形分類不一定得到正確的結果，因為它只是求一個距離的最小值并按這個距離來進行分類。
所以重新選擇一個規(guī)則圖形進行演示發(fā)現(xiàn)的確可以得到一個較好的分類結果。
但是觀察上圖，發(fā)現(xiàn)數(shù)據(jù)中有7個明顯的圓，選擇7個質(zhì)心效果就比較好，但是如果只選擇6個質(zhì)心，如上圖。可以發(fā)現(xiàn)他們對于多出來的一個圓的分類達不到想要的效果，分類效果確實不如7個質(zhì)心。所以這就說明了在初始k值的選擇對最后結果的影響還是比較大的。
1.4 實驗
利用Python代碼實現(xiàn)給定的隨機數(shù)據(jù)點聚類分析。
import numpy as np import random import matplotlib.pyplot as pltdef k_means(data, k):sample_num = data.shape[0]center_index = random.sample(range(sample_num), k)cluster_cen = data[center_index, :]is_change = 1cat = np.zeros(sample_num)while is_change:is_change = 0for i in range(sample_num):min_distance = 100000min_index = 0for j in range(k):sub_data = data[i, :] - cluster_cen[j, :]distance = np.inner(sub_data, sub_data)if distance < min_distance:min_distance = distancemin_index = j + 1if cat[i] != min_index:is_change = 1cat[i] = min_indexfor j in range(k):cluster_cen[j] = np.mean(data[cat == j + 1], axis = 0)return cat, cluster_cenif __name__ == '__main__':cov = [[1,0], [0,1]]mean1 = [1,-1] x1 = np.random.multivariate_normal(mean1, cov, 200)mean2 = [5.5,-4.5]x2 = np.random.multivariate_normal(mean2, cov, 200)mean3 = [1,4]x3 = np.random.multivariate_normal(mean3, cov, 200)mean4 = [6,4.5]x4 = np.random.multivariate_normal(mean4, cov, 200)mean5 = [9,0.0]x5 = np.random.multivariate_normal(mean5, cov, 200)X = np.vstack((x1,x2,x3,x4,x5))fig1 = plt.figure(1)p1 = plt.scatter(x1[:,0], x1[:,1],marker = 'o', color = 'r', label = 'x1')p2 = plt.scatter(x2[:,0], x2[:,1],marker = '+', color = 'm', label = 'x2')p3 = plt.scatter(x3[:,0], x3[:,1],marker = 'x', color = 'b', label = 'x3')p4 = plt.scatter(x4[:,0], x4[:,1],marker = '*', color = 'g', label = 'x4')p5 = plt.scatter(x5[:,0], x5[:,1],marker = '+', color = 'y', label = 'x5')plt.title('original data')plt.legend(loc = 'upper right')cat, cluster_cen = k_means(X,5)print('the number of cluster 1:', sum(cat ==1))print('the number of cluster 2:', sum(cat ==2))print('the number of cluster 3:', sum(cat ==3))print('the number of cluster 4:', sum(cat ==4))print('the number of cluster 5:', sum(cat ==5))fig2 = plt.figure(2)for i, m, lo, label in zip(range(5), ['o', '+', 'x', '*', '+'], ['r', 'm', 'b', 'g', 'y'], ['x1', 'x2', 'x3', 'x4', 'x5']):p = plt.scatter(X[cat == (i + 1), 0], X[cat == (i + 1), 1], marker = m, color = lo, label = label)plt.legend(loc = 'upper right')plt.title('the clusting result')plt.show()這張圖片顯示的是打印出的每一類的數(shù)據(jù)點的個數(shù)。
這兩張圖分別表示原始的數(shù)據(jù)點的分布和聚類后的分布結果，可以看出通過k-Means聚類將圖中的數(shù)據(jù)點較為均勻的分成5類。
可以改變參數(shù)觀察實驗結果：
上面兩張圖分別是分6類和分4類的實驗結果，可以明顯看出當分成6類時均勻想過明顯不如5個中心的效果要好。而當只有4個聚類中心時發(fā)現(xiàn)左側兩簇距離明顯很近而右邊兩簇距離較遠，效果也不如5個聚類中心。
2 DBSCAN算法
DBSCN算法可以用力解決k-Means算法中的一些不好聚類的問題，例如前文實驗中的笑臉圖，k-Means無法對這種特殊形狀來分組。
2.1 基本概念
DBSCAN算法是一種基于密度的聚類算法。這個密度就是指一個點周圍包含的點的個數(shù)。
這類密度聚類算法一般假定類別可以由樣本分布的緊密程度決定。同一類樣本之間是緊密相連的，也就是說在該類別任意樣本周圍不遠處一定有同類別的樣本存在。通過將緊密相連的樣本劃為一類就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃分為各個不同的類別，就得到了最終的所有聚類類別結果。
核心點：某個點的密度達到算法設定的閾值。例如在這個點鄰域中的點的個數(shù)超過了設定值，那么這個點就是一個核心點。
距離閾值：點的半徑r，即設定鄰域的大小。
直接密度可達：某點a在點b的r距離閾值內(nèi)，且b是核心點，則稱a，b直接密度可達。
密度可達：如果點a和b直接密度可大，b和c直接密度可達，并且a和c不是直接密度可達，則稱a和c密度可達。
2.2 DBSCAN算法原理
DBSCAN的聚類定義很簡單，即由密度可達關系導出的最大密度相連的樣本集合，即為最終聚類的一個類別或者說是一個簇。
它的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然后找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續(xù)選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這就得到另一個聚類簇，一直運行到所有核心對象都有類別為止。
但是需要考慮以下的三個問題：
2.3 DBSCAN算法的可視化演示
選擇高斯分布的數(shù)據(jù)
此時默認的距離閾值是1，密度閾值是4。開始運行該算法。
算法開始運行后會在數(shù)據(jù)點中隨機尋找一個點作為核心點以1為半徑開始畫圈，當?shù)谝欢言僖舱也坏胶诵狞c之后，就在這一堆以外的數(shù)據(jù)中隨機選擇核心點繼續(xù)開始迭代分組。它相比與k-Means更智能的地方就在于不斷自主的擴展、傳播來進行分組。最后圖中的白色圓點就是噪聲點。
修改半徑觀察分組結果。
將半徑擴大后發(fā)現(xiàn)分組效果更好，這是由于增大半徑后囊括進行的數(shù)據(jù)就更多了，減少了噪聲點。
接下來觀察笑臉圖的分組情況，選擇距離閾值為1，密度閾值為4。
可以看到此時笑臉中的數(shù)據(jù)點被分為5組。這里發(fā)現(xiàn)，正式由于半徑距離閾值的選擇不夠恰當，就導致笑臉臉部圓圈被分為了兩組，而非我們想要獲取的一組的樣式，不是特別正確，但是眼睛和嘴部相對正確。
接下來調(diào)節(jié)距離閾值為1.22，密度閾值設為2，觀察結果。
此時分類的效果就比較正確，可見DBSCAN算法對初始值設定的要求是很高的，初始值選擇恰當?shù)玫降男Ч隙ǜ谩?/p>
對于初始值的選擇問題，下圖更能說明問題。
這里我們?nèi)∶芏乳撝禐?，發(fā)現(xiàn)只有右上部分一些點可以得到正確的劃分，而其他點全部被歸為噪聲點，能分的組比不能分的組還要少。將距離閾值改為2，半徑改為1.74，發(fā)現(xiàn)分組效果確實是好了一些。足以說明，對于距離閾值和密度閾值的初始值選擇在這個算法中是非常重要的。
2.4 實驗
用Python代碼實現(xiàn)密度聚類。
輸入一組數(shù)據(jù)集，每三個是一組，分別是西瓜的編號、密度和含糖量。
data = """1,0.697,0.46,2,0.774,0.376,3,0634,0.264,4,0.608,0.318,5,0.556,0.215,6,0.403,0.237,7,0.481,0.149,8,0.437,0.211,9,0.666,0.091,10,0.243,0.267,11,0.245,0.057,12,0.343,0.099,13,0.639,0.161,14,0.657,0.198,15,0.36,0.3716,0.593,0.042,17,0.719,0.103,18,0.359,0.188,19,0.339,0.241,20,0.282,0.257"""接下來數(shù)據(jù)處理，dataest是30個樣本的列表。
a = data.split(',') dataset = [(float(a[i]), float(a[i + 1])) for i in range(1, len(a - 1), 3)]計算歐幾里得距離，a，b分別為兩個元組。
def dist(a, b):return math.sqrt(math.pow(a[0] - b[0], 2) + math.pow(a[1] - b[1], 2))算法模型。
def DBSCAN(D, e, Minpts):T = set()k = 0C = []P = set(D)for d in D:if len([i for i in D if dist(d, i) <= e]) >= Minpts:T.add(d)while len(T):P_old = Po = list(T)[np.random.randint(0, len(T))]P = P - set(o)Q = []Q.append(o)while len(Q):q = Q[0]Nq = [i for i in D if dist(q,i) <= e]if len(Nq) >= Minpts:S = P & set(Nq)Q += (list(S))P = P - SQ.remove(q)k += 1Ck = list(P_old - P)T = T - set(Ck)C.append(Ck)return C畫圖，畫出DBSCAN算法對隨機數(shù)據(jù)進行聚類的效果。
def draw(C):colValue = ['r','y','g','b','c','k','m']for i in range(len(C)):coo_X = []coo_Y = []for j in range(len(C[i])):coo_X.append(C[i][j][0])coo_Y.append(C[i][j][1])pl.scatter(coo_X, coo_Y, marker = 'x', color = colValue[i % len(colValue)], label = i)pl.legend(loc = 'upper right')pl.show()C = DBSCAN(dataset, 0.11, 5) draw(C)得到的結果如圖所示：
下面利用Python代碼對隨機數(shù)據(jù)進行DBSCAN聚類分析：
得到的效果如圖所示：
由上圖可以看出，對于隨機生成的不規(guī)則數(shù)據(jù)點，DBSCAN算法可以很好的對數(shù)據(jù)點進行劃分，對于單獨的一個噪聲點可以較好的將其區(qū)分出來。
若是改變距離閾值和密度閾值，得到的效果并不是很滿意，會有一些臨近的數(shù)據(jù)點被錯誤的認為成噪聲點。
總結
聚類算法的思想是將數(shù)據(jù)劃分為若干個不相交的子集，稱為簇，每個簇潛在對應某一個概念。但是聚類算法只生成簇結構，每個簇所代表的概念的語義由使用者自己解釋。也就是說聚類算法并不會告訴你：它生成的這些簇分別代表什么意義，它只會告訴你算法已經(jīng)將數(shù)據(jù)集劃分為這些不相關的簇了。
這類算法作為一種探索性的分析方法，用來分析數(shù)據(jù)的內(nèi)在特點，尋找數(shù)據(jù)之間的分布規(guī)律，同時在分類的處理過程中，首先對需要分類的數(shù)據(jù)進行聚類，然后對聚類出的結果的每一個簇進行分類，實現(xiàn)的是對數(shù)據(jù)的預處理。
k-Means算法就是通過某種相似性度量的方法，將較為相似的個體劃分到同一個類別中。對于不同的應用場景，有著不同的相似性度量方法，為了度量樣本X和樣本Y之間的相似性一般會定義一個距離函數(shù)來分析相似性。雖然算法思想和計算都很簡單，但是k的選取是需要不斷實驗的，同時如果在數(shù)據(jù)量特別大的時候，要計算每個點的歐式距離計算量過于巨大。對任意圖像的處理結果也不好確定，畢竟只是以距離作為衡量標準，將相近的作為一組。
DBSCAN算法是一種很典型的密度聚類算法，相比于k-Means算法既適用于凸樣本集也適用于非凸樣本集。也就是樣本集的密度不均勻、聚類間距相差很大時，用DBSCAN算法并不是很合適。與k-Means相比最大的不同就是在于不需要輸入類別數(shù)k，其最大的優(yōu)勢更是在于可以發(fā)現(xiàn)任意形狀的聚類簇，同時可以在聚類的同時發(fā)現(xiàn)異常點，聚類的結果偏差也不是很大，但是需要對距離閾值和密度閾值聯(lián)合調(diào)參。
總結
以上是生活随笔為你收集整理的机器学习——聚类算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 机器学习——逻辑回归算法
- 下一篇： 机器学习——数据降维