一：聚類的目的
使同一類對象近可能的大，不同對象之間的相似度盡可能的小
二：聚類的分類：
1 ： 基于劃分
K-Means ,K-Medoids,CLarans
2: 基于層次
BIRCH ， CURE ，CHAMELEON
3: 基于密度
DBscan ,Optics , DenClue
推薦網站可視化：
https://www.naftaliharris.com/blog/visualizing-k-means-clustering/
比較好玩，形象化！！！
三：K -mans: 基于劃分的聚類，無監督學習算法（硬聚類）
适用資料集：球狀分布的資料，沒有标簽
K-Means works best in datasets that have with clusters that are roughly equally-sized and shaped roughly regularly.（每個類數量大緻相等，形狀規則）
資料集X：
基本思想：
The k-means algorithm captures the insight that each point in a cluster should be near to the center of that cluster. （所有樣本點到中心點的距離最小）
政策：采用歐式距離平方和最小 squared Euclidean distance
The k-means algorithm divides a set of N samples X into K disjoint clusters C（資料集n個樣本，劃分成C個族，每個族中心為uj）
(簡單了解： 每個樣本點到它的所分類中心的距離之和)
李航<<統計學習方法>>：
X = {x1, x2,x3 .....xn} , xi 是m維特征，無标簽資料集
K均值聚類的目标是将n個資料集劃分到k個不同的簇(cu) cluster, 或者叫類中k < n 。
定義樣本之間距離歐式距離：
損失函數：
優化問題： C* = arg min W(C)
算法流程：
（1）随機選取K個樣本點，作為初始化聚類 中心。
（2）資料集中每個樣本點測量其到每個聚類中心的距離，并把它劃分到最近的中心。
（3）重新計算,每個類中所有點的均值作為這個類的聚類中心。
（4）疊代（2）~（3）步直至新的中心與原中心相等或小于指定門檻值，算法結束。
注意一下幾個問題？
1：初始化K個聚類中心（centroids) 的選擇？
- 随機選擇空間中任意k個位置作為距離中心
- 随機從資料集 中選擇k個聚類中心
- 最遠中心（1：資料集随機選擇一個點作為聚類中心。然後在剩下資料中選擇距離第一個聚類中心最遠的點，作為第二個聚類中心， 循環以上，直到選擇k個聚類中心）
初始聚類中心： 不同的方法對收斂速度，聚類結果都有很大影響
k-means++ 最好的初始化聚類中心(基本思想就是：初始的聚類中心之間的互相距離要盡可能的遠)
2： 距離
- 歐式距離
- 餘弦相似度(文本資料)
3：k值選擇
事先不知道資料集能劃分多少聚類，K是試探性 的，然後比較損失函數選出合适的k值
4： 優缺點
優點：
原理比較簡單，實作也是很容易，收斂速度快
主要需要調參的參數僅僅是k
缺點：
- K值的選取不好把握
- 對于不是凸的資料集比較難收斂(改進：基于密度的聚類算法更加适合，比如DESCAN算法)
- 如果各隐含類别的資料不平衡，比如各隐含類别的資料量嚴重失衡，或者各隐含類别的方差不同，則聚類效果不佳。
- 采用疊代方法，得到的結果隻是局部最優。
- 對噪音和異常點比較的敏感(改進1：離群點檢測的LOF算法，通過去除離群點後再聚類，可以減少離群點和孤立點對于聚類效果的影響；改進2：改成求點的中位數，這種聚類方式即K-Mediods聚類（K中值）)
- 初始聚類中心的選擇(改進1：k-means++; 改進2：二分K-means）
四：代碼實作：
一：初聚類中心初始化最遠
聚類中心的選擇，第一個中心: centrod1，資料集中随機選擇一個
第二個中心: centrod2，為資料集中到第centrod1最遠的點
第三個中心 :centrod3 ,為資料集中到 centrod1,centrod2 距離之和最大的點
'''
第k個中心:centrodk ,資料集中到（centrod1,centrod2,...centrodk-1）距離之和最大的點
import numpy as np import matplotlib.pyplot as plt import random from sklearn import datasets #兩點之間的距離歐式距離 def distance(point1,point2): """ e1: 資料1 向量 e2: 資料2 return : distance(point2,point2) """ e1 = np.array(point1) e2 = np.array(point2) return np.sqrt(np.sum((point1-point2)**2)) #聚類中心 def meanCenter(class_one): """ class_one: 一個聚類的所有樣本點 return : 這個聚類所有樣本點的均值 """ arr = np.array(class_one) mean = arr.mean(axis=0) return mean #最遠中心法，用于初始化聚類中心 def farCenter(centrods,data_set): """ centrods: k個聚類中心數組 data_set: 整個資料集 return: 一個樣本點: 離已經有的聚類中心距離求和，最遠的點 """ m = np.shape(data_set)[1] #特征次元 temp_point =np.zeros([m]) # 臨時儲存樣本點資料 max_dist = 0 for point in data_set: dist =0 for i in range(len(centrods)): dist += np.sqrt(distance(centrods[i],point)) #到已經有的聚類中心求和，開平方為了簡化計算 if dist >max_dist: max_dist = dist temp_point =point return temp_point data_set = datasets.load_iris().data k= 3 # 聚類中心的個數，人為設定 # 随機選項一個點,初始化聚類中心 rand_point = random.choice(data_set) clusterCenter_K =np.array([rand_point]) class_arr = [[]] #儲存每個聚類的最近樣本點 例：cla[1][...] 第1 個類中的樣本點 # 初始化聚類中心，資料集中選擇距離最大的k個點 for i in range(k-1): far_point = farCenter(clusterCenter_K,data_set) clusterCenter_K =np.concatenate([clusterCenter_K,np.array([far_point])]) class_arr.append([]) #可視化初始化資料 col = ['HotPink', 'Aqua', 'Chartreuse', 'yellow', 'LightSalmon'] plt.scatter(data_set[:,0],data_set[:,1],label='origin data',c='g') plt.legend(loc = 'upper left') for i in range(k): plt.scatter(clusterCenter_K[i][0],clusterCenter_K[i][1],linewidth=10, color=col[i]) plt.show() #疊代 epochs = 50 for epoch in range(epochs): #1：更新樣本點所屬類,離聚類中心最近，則劃分到這個聚類中 for point in data_set: ki = 0 mid_dist =distance(point,clusterCenter_K[ki]) # 找出離聚類中心最近的聚類 for j in range(1,len(clusterCenter_K)): dist =distance(point,clusterCenter_K[j]) if dist <mid_dist: mid_dist = dist ki = j class_arr[ki].append(point) #将樣本點劃入 最近Ki類中 #2更新聚類中心 for i in range(len(clusterCenter_K)): if epochs-1 == epoch:# 最後一次不更新 break clusterCenter_K[i]= meanCenter(class_arr[i]) class_arr[i] = [] ## 可視化展示 col = ['HotPink', 'Aqua', 'red', 'yellow', 'LightSalmon'] for i in range(k): plt.scatter(clusterCenter_K[i][0], clusterCenter_K[i][1], linewidth=10, color=col[i]) plt.scatter([e[0] for e in class_arr[i]], [e[1] for e in class_arr[i]], color=col[i]) plt.show()
二： k-means ++
k-means++算法選擇初始seeds的基本思想就是：初始的聚類中心之間的互相距離要盡可能的遠。
算法步驟：
（1）從輸入的資料點集合中随機選擇一個點作為第一個聚類中心
（2）對于資料集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)
（3）選擇一個新的資料點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的機率較大
（4）重複2和3直到k個聚類中心被選出來
(5) 與K-means一樣，聚類中心更新，和在劃分類。
從上面的算法描述上可以看到，算法的關鍵是第3步，如何将D(x)反映到點被選擇的機率上，一種算法如下：
- 資料集中随機選擇一個樣本點，作為種子點
- 對于資料集中每個樣本點，我們都計算其和最近的一個“種子點”的距離D(x)并儲存在一個數組裡，然後把這些距離加起來得到Sum(D(x))。
- 再取一個機率随機值P, 屬于[0,1]，用權重的方式來取計算下一個“種子點”。這個算法的實作是，total =Sum(D(x))*P ,然後用total -= D(x)，直到其<=0，此時的點就是下一個“種子點”。
import math import random from sklearn import datasets import numpy as np import matplotlib.pyplot as plt def distance(point1,point2)->float: """ point1: 樣本點1 point2: 樣本點2 return：distance(point1,point2) 歐式距離 """ dist = 0.0 for e1,e2 in zip(point1,point2): dist += (e1-e2)**2 return math.sqrt(dist) def closest_distance(point,centroids): """ 計算樣本點到所有聚類中心最短距離 """ min_dist = math.inf #初始設定成無窮大 for _, centroid in enumerate(centroids): dist = distance(centroid,point) if dist < min_dist: min_dist = dist return min_dist #初始化聚類中心 def k_Centers(data_set:list ,k : int)->list: """ 從資料集 中傳回k個對象作為質心 """ cluster_centers = [] cluster_centers.append(random.choice(data_set)) # 第一個聚類中心在資料集中随機選擇一個 d =[0 for i in range(len(data_set))] # 初始化為0 for _ in range(1,k): total = 0 for i ,point in enumerate(data_set): d[i] = closest_distance(point,cluster_centers)#樣本點到所有聚類中心最近的點 total +=d[i] total *=random.random() # total * [0,1]的機率 for i ,di in enumerate(d): total -= di if total > 0: continue cluster_centers.append(data_set[i]) break return cluster_centers #更新聚類中心 def meanCenter_updata(subsetData:list): """ subsetData: 一個聚類中所有的樣本 return : 這個聚類中所有樣本的平均值 """ data = np.array(subsetData) mean = data.mean(axis=0) return mean data_set = datasets.load_iris().data # 加載資料 epochs = 50 class_arr = [[]] #儲存每個類的樣本資料 k= 3 # 聚類個數 cluster_centers = k_Centers(data_set,k) #初始化聚類中心 initial cluster center for _ in range(len(cluster_centers)): class_arr.append([]) #繪制初始聚類中心分布圖 col = ['HotPink', 'red', 'Chartreuse', 'yellow', 'LightSalmon'] for i in range(len(cluster_centers)): plt.scatter(cluster_centers[i][0],cluster_centers[i][1],linewidth=10, color=col[i]) plt.scatter(data_set[:,0],data_set[:,1],c="g",marker='o',label='origin data') plt.xlabel('sepal length') plt.ylabel('sepal width') plt.legend(loc=2) plt.show() for epoch in range(epochs): for point in data_set: #1将資料劃分到最近聚類中心 index = 0 min_dist = distance(point,cluster_centers[0]) for i in range(1,len(cluster_centers)): dist = distance(point,cluster_centers[i]) if dist < min_dist: min_dist =dist index = i class_arr[index].append(point) for j in range(len(cluster_centers)): #2：更新聚類中心 if epoch == epochs -1 : break cluster_centers[j] = meanCenter_updata(class_arr[j]) class_arr[j] = [] #結果可視化 for i in range(k): plt.scatter(cluster_centers[i][0], cluster_centers[i][1], linewidth=10, color=col[i]) plt.scatter([e[0] for e in class_arr[i]], [e[1] for e in class_arr[i]], color=col[i]) plt.show()
3: scikit-learn
官網手冊：https://scikit-learn.org/stable/modules/clustering.html#k-means
使用：
導包 ： from sklearn.cluster import KMeans
KMeans()
參數： paramters
- n_clusters = 8 default
- max_iter: 300 最大疊代數
- n_init : 10 用不同質心初始化運算比較次數，選擇一個損失函數最小的 inertia
- init：始化方法k-means++ , random , ndarray向量(n_cluster,n_features)自定義
- precopute_distance: 預計算距離,計算速度快，但占記憶體。auto ,True ,False
- tol: float default 1e-4
- n_jobs : -1 cpu計算 +1 ，不進行并行運算
- copy_x: True default 當我們precomputing distances時，将資料中心化會得到更準确的結果。如果把此參數值設為True，則原始資料不會被改變。如果是False，則會直接在原始資料
屬性： attributes
- cluster_centers_:
- Labels_ ： 每個點的分類
- inertia_
方法： methods
- fit()
- fit_predictt()
- fit_transform()
- get_params()
- predict()
- score()
- set_params()
- transform()
iris資料集k-means聚類
import matplotlib.pyplot as plt import numpy as np from sklearn.cluster import KMeans from sklearn import datasets from sklearn.metrics import confusion_matrix iris = datasets.load_iris() data = iris.data #繪制資料分布圖 plt.scatter(data[:,0],data[:,1],c="red",marker='o',label='see') plt.xlabel('sepal length') plt.ylabel('sepal width') plt.legend(loc=2) plt.show() estimator = KMeans(n_clusters=3,max_iter=400,n_init=11,init="k-means++") # 構造聚類器 estimator.fit(data) label_pred = estimator.labels_ # 擷取聚類标簽 每個點的分類 cluster_center = estimator.cluster_centers_ # 擷取聚類中心 color =['r','g','b'] i = 0 for e in cluster_center: plt.scatter(e[0],e[1],linewidth=10,c=color[i]) i+=1 # 繪制聚類結果 X0 = data[label_pred ==0] X1 = data[label_pred ==1] X2 = data[label_pred ==2] plt.scatter(X0[:,0],X0[:,1],c='r',marker='o',label='label0') plt.scatter(X1[:,0],X1[:,1],c='g',marker='+',label='label1') plt.scatter(X2[:,0],X2[:,1],c='b',marker='*',label='label2') plt.xlabel('sepal length') plt.ylabel('sepal width') plt.legend(loc=2) print('聚類結果，混淆矩陣') print(confusion_matrix(iris.target,label_pred)) #print(estimator.predict(data)) print(estimator.score(data)) print(estimator.get_params()) #print(estimator.fit_transform(data))
Reference：
[1]:https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68
[2]:https://medium.com/m/global-identity?redirectUrl=https%3A%2F%2Ftowardsdatascience.com%2Fthe-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68
[3] https://blog.csdn.net/github_39261590/article/details/76910689
[4] https://blog.csdn.net/loadstar_kun/article/details/39450615
[5] https://blog.csdn.net/itplus/article/details/10088429