轉載鏈接：https://blog.csdn.net/hanxia159357/article/details/81530361

本文完成程序及測試數據集詳細見：https://github.com/HanXia001/k-means-python3-

本文主要內容：

? ? ? ? ? ? ? ? 1.k-means解決的問題；

? ? ? ? ? ? ? ? 2.k-means原理介紹；

? ? ? ? ? ? ? ? 3.k-means的簡單實現。

1.k-means解決的問題

? ? ? ? ?k-means算法屬于無監督學習的一種聚類算法，其目的為：在不知數據所屬類別及類別數量的前提下，依據數據自身所暗含的特點對數據進行聚類。對于聚類過程中類別數量k的選取，需要一定的先驗知識，也可根據“類內間距小，類間間距大“（一種聚類算法的理想情況）為目標進行實現。

2.k-means原理介紹

? ? ? ? k-means算法以數據間的距離作為數據對象相似性度量的標準，因此選擇計算數據間距離的計算方式對最后的聚類效果有顯著的影響，常用計算距離的方式有：余弦距離、歐式距離、曼哈頓距離等。本文以歐式距離為例（會一種，其余也就會了）。

歐式距離公式：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

例子：若數據為其計算歐式距離如下(可理解為D表示維度，i,j表示行數)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ?通過公式（1）可計算出每對數據對象間的距離，根據距離的遠近進行聚類成指定的類別數K。對每一類中的數據初步選取類心，取的方式有多種如：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1.該類所有數據的均值；

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2.隨機取k個數據作為類心；

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3.選取距離最遠的k個點作為類心等。

以上方法均需要對初步的類心進行迭代，當類心變化緩慢時便可認為收斂，此時該點便為最終的類型。本文以方法1為例：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

表示第k類，表示第k類中數據對象的個數。類心迭代過程如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

通常迭代終止的條件有兩種：1）達到指定的迭代次數T；2）類心不再發生明顯的變化，即收斂。

3.k-means的簡單實現

原理講過，此處直接上代碼（python3實現）：

            
              
import numpy as np

import matplotlib.pyplot as plt

 

# 加載數據

def loadDataSet(fileName):

    data = np.loadtxt(fileName,delimiter='\t')

    return data

 

# 歐氏距離計算

def distEclud(x,y):

    return np.sqrt(np.sum((x-y)**2))  # 計算歐氏距離

 

# 為給定數據集構建一個包含K個隨機質心的集合

def randCent(dataSet,k):

    m,n = dataSet.shape

    centroids = np.zeros((k,n))

    for i in range(k):

        index = int(np.random.uniform(0,m)) #

        centroids[i,:] = dataSet[index,:]

    return centroids

 

# k均值聚類

def KMeans(dataSet,k):

 

    m = np.shape(dataSet)[0]  #行的數目

    # 第一列存樣本屬于哪一簇

    # 第二列存樣本的到簇的中心點的誤差

    clusterAssment = np.mat(np.zeros((m,2)))

    clusterChange = True

 

    # 第1步 初始化centroids

    centroids = randCent(dataSet,k)

    while clusterChange:

        clusterChange = False

 

        # 遍歷所有的樣本（行數）

        for i in range(m):

            minDist = 100000.0

            minIndex = -1

 

            # 遍歷所有的質心

            #第2步 找出最近的質心

            for j in range(k):

                # 計算該樣本到質心的歐式距離

                distance = distEclud(centroids[j,:],dataSet[i,:])

                if distance < minDist:

                    minDist = distance

                    minIndex = j

            # 第 3 步：更新每一行樣本所屬的簇

            if clusterAssment[i,0] != minIndex:

                clusterChange = True

                clusterAssment[i,:] = minIndex,minDist**2

        #第 4 步：更新質心

        for j in range(k):

            pointsInCluster = dataSet[np.nonzero(clusterAssment[:,0].A == j)[0]]  # 獲取簇類所有的點

            centroids[j,:] = np.mean(pointsInCluster,axis=0)   # 對矩陣的行求均值

 

    print("Congratulations,cluster complete!")

    return centroids,clusterAssment

 

def showCluster(dataSet,k,centroids,clusterAssment):

    m,n = dataSet.shape

    if n != 2:

        print("數據不是二維的")

        return 1

 

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '
              
                 len(mark):

        print("k值太大了")

        return 1

 

    # 繪制所有的樣本

    for i in range(m):

        markIndex = int(clusterAssment[i,0])

        plt.plot(dataSet[i,0],dataSet[i,1],mark[markIndex])

 

    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '
                
              
            
            
          

效果如圖：

? ? ? ? ? ? ? ? ? ?
版權聲明：本文為CSDN博主「寒夏12」的原創文章，遵循CC 4.0 by-sa版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/hanxia159357/article/details/81530361