一、什么是聚類演算法？

1、用于發現共同的群體(cluster)，比如：郵件聚類、用戶聚類、圖片邊緣，

2、聚類唯一會使用到的資訊是：樣本與樣本之間的相似度（跟距離負相關）

給定N個訓練樣本(未標記的){x 1 , . . . , x N },同時給定結果聚類的個數K 目標：把比較“接近”的樣本放到一個cluster里，總共得到K個cluster

二、不同場景的判定內容

圖片檢索：圖片內容相似度

圖片分割：圖片像素(顏色)相似度

網頁聚類：文本內容相似度

社交網路聚類：(被)關注人群，喜好，喜好內容

電商用戶聚類：點擊/加車/購買商品，行為序列…

三、樣本—向量—距離

四、Kmeans聚類和層次聚類

Kmeans聚類：

得到的聚類是一個獨立于另外一個的

收斂：

聚類中心不再有變化每個樣本到對應聚類中心的距離之和不再有很大變化

層次聚類：

可以看做樹狀層疊無需初始輸入聚類個數

k-means聚類與層次聚類區別：

kmeans每次聚類產生一個聚類結果，層次聚類可以通過聚類程度不同產生不同結果 kmeans需要指定聚類個數K，層次聚類不用 kmeans比層次聚類更快 kmeans用的多，且可以用k-median

五、損失函式

六、K的選定

k值的影響：

k過大過小對結果都不好

“肘點”法：

選取不同的K值，畫出損失函式曲線，選取“肘點”值

七、優缺點

優點：

1. 易于理解，聚類效果不錯；

2. 處理大資料集的時候，該演算法可以保證較好的伸縮性和高效率；

3. 當簇近似高斯分布的時候，效果非常不錯，

缺點：

1. k值是用戶給定的，進行資料處理前，k值是未知的，不同的k值得到的結果不一樣；

2. 對初始簇中心點是敏感的；

3. 對于團狀的資料點集區分度好，對于帶狀(環繞)等“非凸”形狀不太好，(用譜聚類或者做特征映射)

4. 對例外點的“免疫力”很差，我們可以通過一些調整(比如中心不直接取均值，而是找均值最近的樣本點代替)

八、代碼示例

import random
import matplotlib.pyplot as plt

class Kmeans():
    def __init__(self,k):
        '''
        初始化
        param k:代表聚類中心個數
        '''
        self.__k=k
        self.__data = [] #存放原始資料
        self.__pointCenter = [] #存放聚類中心點
        self.__result = [] #存放最后的聚類結果
        for i in range(k):
            self.__result.append([])
            
    def calDistance(self,points1,points2):
        '''
        歐氏距離:sprt(x1-x2)^2+(y1-y2)^2
        param points1:一維串列
        param points2:一維串列
        return:兩點之間直線距離
        '''
        distance = (sum([(x1-x2)**2 for x1,x2 in zip(points1, points2)]))**0.5 #開平方
        return distance

    def randomCenter(self):
        '''
        生成self.__pointCenter:初次聚類中心點串列
        return:
        '''
        while len(self.__pointCenter)<self.__k:
            index = random.randint(0,len(self.__data)) #得到0到len(self.__data)-1之間的索引
            if self.__data[index] not in self.__pointCenter: #用索引值得到串列的值
                self.__pointCenter.append(self.__data[index])
    
    def calPointToCenterDistance(self,data,center):
        '''
        計算每個店和聚類中心之間的距離
        param data:原始資料
        param center:中心聚類點
        return:距離
        '''
        distance = []
        for i in data:
            distance.append([self.calDistance(i,centerpoint) for centerpoint in center])
        return distance
    
    def sortPoint(self,distance):
        '''
        對原始資料進行分類，將每個點分到離它最近的聚類中心點
        param distance:得到的距離
        return:回傳最終的分類結果
        '''
        for i in distance:
            index = i.index(min(i)) #得到五個距離之中的最小值的索引
            self.__result[index].append(self.__data[i]) #通過索引進行分類
        return self.__result
    
    def calNewCenterPoint(self,result):
        '''
        計算新的中心點：通過生成新的聚類求取新的平均值
        param result:分類結果
        return:回傳新的聚類中心點
        '''
        newCenterPoint1 = []
        for temp in result:
            #進行轉置，將N*M轉為M*N形式，將所有point.x值和point,y值撞到一個串列中,便于求取新的平均值
            temps = [[temp[x][i] for x in range(len(temp))] for i in range(len(temp[0]))]
            point = []
            for i in temps:
                point.append(sum(i)/len(i)) #求和再除以陣列長度,求取平均值
            newCenterPoint1.append(point)
        return newCenterPoint1
    
    def calCenterToCenterDistance(self,old,new):
        '''
        迭代結束條件
        計算新舊中心點之間的距離
        param old:
        param new:
        return:
        '''
        total = 0
        for point1,point2 in zip(old,new):
            total += self.calDistance(point1,point2)
        return total/len(old)
    
    def fit(self,data,threshold,time=50000):
        self.__data = data
        self.randomCenter()
        print(self.__pointCenter)
        centerDistance = self.calPointToCenterDistance(self.__data,self.__pointCenter)
        
        #對原始資料進行分類，將每個點分到離它最近的中心點
        i = 0
        for temp in centerDistance:
            index = temp.index(min(temp))
            self.__result[index].append(self.__data[i])
            i +=1
        #列印分類結果
        print(self.__result)
        oldCenterPoint = self.__pointCenter
        newCenterPoint = self.calNewCenterPoint(self.__result)
        while self.calCenterToCenterDistance(oldCenterPoint,newCenterPoint) > threshold:
            time -= 1
            result = []
            for i in range(self.__k):
                result.append([])
            #保存上次的中心點
            oldCenterPoint = newCenterPoint
            centerDistance = self.calPointToCenterDistance(self.__data,newCenterPoint)
            #對原始資料進行分類,將每個點分到離它最近的中心點
            i = 0
            for temp in centerDistance:
                index = temp.index(min(temp))
                result[index].append(self.__data[i])
                i += 1
            newCenterPoint = self.calNewCenterPoint(result)
            print(self.calCenterToCenterDistance(oldCenterPoint,newCenterPoint))
            self.__result = result
        self.__pointCenter = newCenterPoint
        return newCenterPoint,self.__result
    
if __name__ == "__main__":
    data = []
    k = 6 #分類數量
    for i in range(len(data)):
        kmeans = Kmeans(k=k)
        centerPoint,result = kmeans.fit(data,0.0001)
        print(centerPoint)
        plt.plot()
        plt.title('Kmeans')
        i = 0
        tempx = []
        tempy = []
        color = []
        for temp in result:
            temps = [[temp[x][i] for x in range(len(temp))] for i in range(len(temp[0]))]
            color += [i]*len(temps[0])
            tempx += temps[0]
            tempy += temps[1]
            i+=2
        plt.scatter(tempx,tempy,c=color,s=30)
        plt.show()