一、聚類算法的簡介
??聚類算法是一種典型的無監(jiān)督學(xué)習(xí)算法娶牌，主要用于將相似的樣本自動歸到一個類別中允蚣。聚類算法與分類算法最大的區(qū)別是：聚類算法是無監(jiān)督的學(xué)習(xí)算法，而分類算法屬于監(jiān)督的學(xué)習(xí)算法柏锄。
??在聚類算法中根據(jù)樣本之間的相似性，將樣本劃分到不同的類別中复亏，對于不同的相似度計算方法趾娃，會得到不同的聚類結(jié)果，常用的相似度計算方法有歐式距離法缔御。
二抬闷、K-Means算法的概述
??K-Means聚類的目的是將n個觀測值劃分為k個類，使每個類中的觀測值距離該類的中心（類均值）比距離其他類中心都近耕突。
??事先確定常數(shù)k笤成，常數(shù)k意味著最終的聚類類別數(shù)，首先隨機選定初始點為質(zhì)心眷茁，并通過計算每一個樣本與質(zhì)心之間的相似度(這里為歐式距離)炕泳，將樣本點歸到最相似的類中，接著上祈，重新計算每個類的質(zhì)心(即為類中心)培遵，重復(fù)這樣的過程浙芙，知道質(zhì)心不再改變，最終就確定了每個樣本所屬的類別以及每個類的質(zhì)心籽腕。
??由于每次都要計算所有的樣本與每一個質(zhì)心之間的相似度嗡呼，故在大規(guī)模的數(shù)據(jù)集上，K-Means算法的收斂速度比較慢节仿。
三晤锥、K-Means算法的流程
1、初始化常數(shù)K廊宪，隨機選取初始點為質(zhì)心
2、重復(fù)計算一下過程女轿，直到質(zhì)心不再改變
?（1）計算樣本與每個質(zhì)心之間的相似度箭启，將樣本歸類到最相似的類中
?（2）重新計算質(zhì)心
3、輸出最終的質(zhì)心以及每個類
四蛉迹、K-Means算法的實現(xiàn)
1傅寡、K-Means算法實現(xiàn)代碼如下：
import numpy as np
import matplotlib.pyplot as plt
'''
算法思想大致為：先從樣本集中隨機選取 ?? 個樣本作為簇中心，并計算所有樣本與這 ?? 個“簇中心”的距離北救，對于每一個樣本荐操，
將其劃分到與其距離最近的“簇中心”所在的簇中，對于新的簇計算各個簇的新的“簇中心”珍策。
根據(jù)以上描述托启，我們大致可以猜測到實現(xiàn)kmeans算法的主要三點：
（1）簇個數(shù) ?? 的選擇
（2）各個樣本點到“簇中心”的距離
（3）根據(jù)新劃分的簇，更新“簇中心”
'''
def loadDataSet(filename):
'''
讀取數(shù)據(jù)集
Args:
filename: 文件名
Returns:
dataMat: 數(shù)據(jù)樣本矩陣
'''
dataMat = []
with open(filename, 'rb') as f:
for line in f:
# 讀取的字節(jié)流需要先解碼成utf-8再處理
eles = list(map(float, line.decode('utf-8').strip().split('\t')))
dataMat.append(eles)
return dataMat
def distEclud(vecA, vecB):
'''
計算兩向量的歐氏距離
Args:
vecA: 向量A
vecB: 向量B
Returns:
歐式距離
'''
return np.sqrt(np.sum(np.power(vecA-vecB,2)))
def randCent(dataSet, k):
'''
隨機生成k個聚類中心
Args:
dataSet: 數(shù)據(jù)集
k: 簇數(shù)目
Returns:
centroids: 聚類中心矩陣
'''
m, _ = dataSet.shape
# 隨機從數(shù)據(jù)集中選幾個作為初始聚類中心
centroids = dataSet.take(np.random.choice(80,k), axis=0)
return centroids
def kMeans(dataSet, k, maxIter=5):
'''
K-Means
Args:
dataSet: 數(shù)據(jù)集
k: 聚類數(shù)
Returns:
centroids: 聚類中心
clusterAssment: 點分配結(jié)果
'''
# 隨機初始化聚類中心
centroids = randCent(dataSet, k)
init_centroids = centroids.copy()
m, n = dataSet.shape
# 點分配結(jié)果：第一列指明樣本所在的簇攘宙，第二列指明該樣本到聚類中心的距離
clusterAssment = np.mat(np.zeros((m, 2)))
# 標(biāo)識聚類中心是否仍在變化
clusterChanged = True
# 直至聚類中心不再變化
iterCount = 0
while clusterChanged and iterCount < maxIter:
iterCount += 1
clusterChanged = False
# 分配樣本到簇
for i in range(m):
# 計算第i個樣本到各個聚類中心的距離
minIndex = 0
minDist = np.inf
for j in range(k):
dist = distEclud(dataSet[i, :], centroids[j, :])
if dist < minDist:
minIndex = j
minDist = dist
# 任何一個樣本的類簇分配發(fā)生變化則認(rèn)為變化
if clusterAssment[i, 0] != minIndex:
clusterChanged = True
clusterAssment[i, :] = minIndex, minDist ** 2
# 刷新聚類中心：移動聚類中心點到所有簇的均值位置
for cent in range(k):
# 通過數(shù)組過濾得到簇中的點
# matrix.A 是將matrix-->array
ptsInCluster = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]
if ptsInCluster.shape[0] > 0:
# 計算均值并移動
centroids[cent, :] = np.mean(ptsInCluster, axis=0)
return centroids, clusterAssment, init_centroids
if __name__ == '__main__':
dataMat = np.mat(loadDataSet('./testSet.txt'))
m, n = np.shape(dataMat)
set_k = 4
centroids, clusterAssment, init_centroids = kMeans(dataMat, set_k)
clusterCount = np.shape(centroids)[0]
# 我們這里只設(shè)定了最多四個簇的樣式屯耸，所以前面如果set_k設(shè)置超過了4，后面就會出現(xiàn)index error
patterns = ['o', 'D', '^', 's']
colors = ['b', 'g', 'y', 'black']
fig = plt.figure()
title = 'kmeans with k={}'.format(set_k)
ax = fig.add_subplot(111, title=title)
for k in range(clusterCount):
# 繪制聚類中心
ax.scatter(centroids[k, 0], centroids[k, 1], color='r', marker='+', linewidth=20)
# 繪制初始聚類中心
ax.scatter(init_centroids[k, 0], init_centroids[k, 1], color='purple', marker='*', linewidth=10)
for i in range(m):
# 繪制屬于該聚類中心的樣本
ptsInCluster = dataMat[np.nonzero(clusterAssment[:, 0].A == k)[0]]
ax.scatter(ptsInCluster[:, 0].flatten().A[0], ptsInCluster[:, 1].flatten().A[0], color=colors[k],
marker=patterns[k])
plt.show()
效果圖.png
2蹭劈、sklearn中K-Means算法實現(xiàn)代碼如下：
from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt
def loadDataSet(filename):
'''
讀取數(shù)據(jù)集
Args:
filename: 文件名
Returns:
dataMat: 數(shù)據(jù)樣本矩陣
'''
dataMat = []
with open(filename, 'rb') as f:
for line in f:
# 讀取的字節(jié)流需要先解碼成utf-8再處理
eles = list(map(float, line.decode('utf-8').strip().split('\t')))
dataMat.append(eles)
return dataMat
dataMat = np.mat(loadDataSet('./testSet.txt'))
kmeans = KMeans(init='random', n_clusters=4, random_state=0).fit(dataMat)
centroids = kmeans.cluster_centers_
clusterAssment = kmeans.labels_
m, n = np.shape(dataMat)
set_k = 4
clusterCount = np.shape(centroids)[0]
# 我們這里只設(shè)定了最多四個簇的樣式疗绣，所以前面如果set_k設(shè)置超過了4，后面就會出現(xiàn)index error
patterns = ['o', 'D', '^', 's']
colors = ['b', 'g', 'y', 'black']
fig = plt.figure()
title = 'kmeans with k={}'.format(set_k)
ax = fig.add_subplot(111, title=title)
for k in range(clusterCount):
# 繪制聚類中心
ax.scatter(centroids[k, 0], centroids[k, 1], color='r', marker='+', linewidth=20)
for i in range(m):
# 繪制屬于該聚類中心的樣本
ptsInCluster = dataMat[np.nonzero(clusterAssment == k)[0]]
ax.scatter(ptsInCluster[:, 0].flatten().A[0], ptsInCluster[:, 1].flatten().A[0], color=colors[k],
marker=patterns[k])
plt.show()
分類效果圖.png
