聚類介紹
聚類在機器學習，數據挖掘，模式識別，圖像分析以及生物信息等領域有廣泛的應用。聚類是把相似的對象通過靜態分類的方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐標系中更加短的空間距離（一般是歐式距離）等。
聚類的應用
在商務上，聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群，並且用購買模式來刻畫不同的客戶群的特徵。在生物學上，聚類能用於推導植物和動物的分類，對基因進行分類，獲得對種群中固有結構的認識。聚類在地球觀測資料庫中相似地區的確定，汽車保險單持有者的分組，及根據房子的類型、價值和地理位置對一個城市中房屋的分組上也可以發揮作用。聚類也能用於對Web上的文檔進行分類，以發現信息。諸如此類，聚類有著廣泛的實際應用。
K-Means聚類算法簡介
K-Means是發現給定數據集的 K 個簇的聚類算法, 之所以稱之為 K-均值是因為它可以發現 K 個不同的簇, 且每個簇的中心採用簇中所含值的均值計算而成。簇個數 K 是用戶指定的, 每一個簇通過其質心（centroid）, 即簇中所有點的中心來描述。聚類與分類算法的最大區別在於, 分類的目標類別已知, 而聚類的目標類別是未知的。
K-Means聚類算法步驟
K-Means聚類步驟是一個循環迭代的算法，具體·步驟如下：
1、先隨機選取K個對象作為初始的聚類中心，隨機選擇K個初始中心點；2、計算每個對象與各個種子聚類中心之間的距離，按照距離初始中心點最小的原則，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。3、一旦全部對象都被分配了，每個聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重複直到滿足某個終止條件。終止條件可以是以下任何一個：1）沒有（或最小數目）對象被重新分配給不同的聚類。2）沒有（或最小數目）聚類中心再發生變化。3）誤差平方和局部最小。
因此得到相互分離的球狀聚類，在這些聚類中，均值點趨向收斂於聚類中心。 一般會希望得到的聚類大小大致相當，這樣把每個觀測都分配到離它最近的聚類中心（即均值點）就是比較正確的分配方案。
K-Means的數學描述
聚類是把相似的物體聚在一起，這個相似度（或稱距離）是用歐氏距離來衡量的。
給定兩個樣本 與 ，其中n表示特徵數 ，X和Y兩個向量間的歐氏距離(Euclidean Distance)表示為：
k-means算法是把數據給分成不同的簇，目標是同一個簇中的差異小，不同簇之間的差異大，這個目標怎麼用數學語言描述呢？我們一般用誤差平方和作為目標函數（想想線性回歸中說過的殘差平方和、損失函數，是不是很相似），公式如下:
其中C表示聚類中心，如果x屬於這個簇，則計算兩者的歐式距離，將所有樣本點到其中心點距離算出來，並加總，就是k-means的目標函數。實現同一個簇中的樣本差異小，就是最小化SSE。
可以通過求導來求函數的極值，我們對SSE求偏導看看能得到什麼結果：
式中m是簇中點的數量，發現了沒有，這個C的解，就是X的均值點。多點的均值點應該很好理解吧，給定一組點 ，其中 ，這組點的均值向量表示為：
K-Means偽代碼
function K-Means(輸入數據，中心點個數K)獲取輸入數據的維度Dim和個數N 隨機生成K個Dim維的點while(算法未收斂) 對N個點：計算每個點屬於哪一類。 對於K個中心點： 1，找出所有屬於自己這一類的所有數據點 2，把自己的坐標修改為這些數據點的中心點坐標 end 輸出結果：end
K-Means優缺點
優點:
屬於無監督學習，無須準備訓練集原理簡單，實現起來較為容易結果可解釋性較好缺點:
聚類數目k是一個輸入參數。選擇不恰當的k值可能會導致糟糕的聚類結果。這也是為什麼要進行特徵檢查來決定數據集的聚類數目了。可能收斂到局部最小值, 在大規模數據集上收斂較慢對於異常點、離群點敏感K-Means算法實現
from collections import defaultdictfrom random import uniformfrom math import sqrtdef point_avg(points):"""Accepts a list of points, each with the same number of dimensions. NB. points can have more dimensions than 2 Returns a new point which is the center of all the points. """ dimensions = len(points[0]) new_center = []for dimension in xrange(dimensions): dim_sum = 0 # dimension sumfor p in points: dim_sum += p[dimension]# average of each dimension new_center.append(dim_sum / float(len(points)))return new_centerdef update_centers(data_set, assignments):""" Accepts a dataset and a list of assignments; the indexes of both lists correspond to each other. Compute the center for each of the assigned groups. Return `k` centers where `k` is the number of unique assignments. """ new_means = defaultdict(list) centers = []for assignment, point in zip(assignments, data_set): new_means[assignment].append(point)for points in new_means.itervalues(): centers.append(point_avg(points))return centersdef assign_points(data_points, centers):""" Given a data set and a list of points betweeen other points, assign each point to an index that corresponds to the index of the center point on it's proximity to that point. Return a an array of indexes of centers that correspond to an index in the data set; that is, if there are N points in `data_set` the list we return will have N elements. Also If there are Y points in `centers` there will be Y unique possible values within the returned list. """ assignments = []for point in data_points: shortest = () # positive infinity shortest_index = 0for i in xrange(len(centers)): val = distance(point, centers[i])if val < shortest: shortest = val shortest_index = i assignments.append(shortest_index)return assignmentsdef distance(a, b):""" """ dimensions = len(a) _sum = 0for dimension in xrange(dimensions): difference_sq = (a[dimension] - b[dimension]) ** 2 _sum += difference_sqreturn sqrt(_sum)def generate_k(data_set, k):""" Given `data_set`, which is an array of arrays, find the minimum and maximum for each coordinate, a range. Generate `k` random points between the ranges. Return an array of the random points within the ranges. """ centers = [] dimensions = len(data_set[0]) min_max = defaultdict(int)for point in data_set:for i in xrange(dimensions): val = point[i] min_key = 'min_%d' % i max_key = 'max_%d' % iif min_key not in min_max or val < min_max[min_key]: min_max[min_key] = valif max_key not in min_max or val > min_max[max_key]: min_max[max_key] = valfor _k in xrange(k): rand_point = []for i in xrange(dimensions): min_val = min_max['min_%d' % i] max_val = min_max['max_%d' % i] rand_point.append(uniform(min_val, max_val)) centers.append(rand_point)return centersdef k_means(dataset, k): k_points = generate_k(dataset, k) assignments = assign_points(dataset, k_points) old_assignments = Nonewhile assignments != old_assignments: new_centers = update_centers(dataset, assignments) old_assignments = assignments assignments = assign_points(dataset, new_centers)return zip(assignments, dataset)# points = [# [1, 2],# [2, 1],# [3, 1],# [5, 4],# [5, 5],# [6, 5],# [10, 8],# [7, 9],# [11, 5],# [14, 9],# [14, 14],# ]# print k_means(points, 3)
參考文獻
https://zhuanlan.zhihu.com/p/75477709