什么是聚類

聚類試圖將數(shù)據(jù)集中的樣本劃分為若干個通常是不相交的子集，每個子集成為一個“簇”。通過這樣的劃分，每個簇可能對應(yīng)于一些潛在的概念（也就是類別），如“淺色瓜” “深色瓜”，“有籽瓜” “無籽瓜”，甚至“本地瓜” “外地瓜”等；需說明的是，這些概念對聚類算法而言事先是未知的，聚類過程僅能自動形成簇結(jié)構(gòu)，簇對應(yīng)的概念語義由使用者來把握和命名。

聚類和分類的區(qū)別？

聚類是無監(jiān)督的學(xué)習(xí)算法，分類是有監(jiān)督的學(xué)習(xí)算法。所謂有監(jiān)督就是有已知標(biāo)簽的訓(xùn)練集（也就是說提前知道訓(xùn)練集里的數(shù)據(jù)屬于哪個類別），機器學(xué)習(xí)算法在訓(xùn)練集上學(xué)習(xí)到相應(yīng)的參數(shù)，構(gòu)建模型，然后應(yīng)用到測試集上。而聚類算法是沒有標(biāo)簽的，聚類的時候，我們并不關(guān)心某一類是什么，我們需要實現(xiàn)的目標(biāo)只是把相似的東西聚到一起。

性能度量

聚類的目的是把相似的樣本聚到一起，而將不相似的樣本分開，類似于“物以類聚”，很直觀的想法是同一個簇中的相似度要盡可能高，而簇與簇之間的相似度要盡可能的低。
性能度量大概可分為兩類： 一是外部指標(biāo)， 二是內(nèi)部指標(biāo) 。
外部指標(biāo)：將聚類結(jié)果和某個“參考模型”進(jìn)行比較。
內(nèi)部指標(biāo)：不利用任何參考模型，直接考察聚類結(jié)果。

K-Means的原理

對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內(nèi)的點盡量緊密的連在一起，而讓簇間的距離盡量的大

K-Means算法

給定樣本集D，k-means算法針對聚類所得簇劃分C最小化平方誤差。

K-Means算法

其中第一行對均值向量進(jìn)行初始化，在第4-8行與第9-16行依次對當(dāng)前簇劃分及均值向量迭代更新，若迭代更新后聚類結(jié)果保持不變，則在第18行將當(dāng)前簇劃分結(jié)果返回。

西瓜數(shù)據(jù)集4.0

K-Means與KNN

初學(xué)者會很容易就把K-Means和KNN搞混，其實兩者的差別還是很大的。
K-Means是無監(jiān)督學(xué)習(xí)的聚類算法，沒有樣本輸出；而KNN是監(jiān)督學(xué)習(xí)的分類算法，有對應(yīng)的類別輸出。KNN基本不需要訓(xùn)練，對測試集里面的點，只需要找到在訓(xùn)練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓(xùn)練過程，找到k個類別的最佳質(zhì)心，從而決定樣本的簇類別。
當(dāng)然，兩者也有一些相似點，兩個算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

K-Means的優(yōu)點與缺點

優(yōu)點：
簡單，易于理解和實現(xiàn)；收斂快，一般僅需5-10次迭代即可，高效
缺點：
1，對K值得選取把握不同對結(jié)果有很大的不同
2，對于初始點的選取敏感，不同的隨機初始點得到的聚類結(jié)果可能完全不同
3，對于不是凸的數(shù)據(jù)集比較難收斂
4，對噪點過于敏感，因為算法是根據(jù)基于均值的
5，結(jié)果不一定是全局最優(yōu)，只能保證局部最優(yōu)
6，對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。

代碼部分

讀取數(shù)據(jù)

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
dataset = pd.read_csv('watermelon_4.csv', delimiter=",")
data = dataset.values
print(dataset)

K-Means算法

import random
def distance(x1, x2):
    return sum((x1-x2)**2)
def Kmeans(D,K,maxIter):
    m, n = np.shape(D)
    if K >= m:
        return D
    initSet = set()
    curK = K
    while(curK>0):  # 隨機選取k個樣本
        randomInt = random.randint(0, m-1)
        if randomInt not in initSet:
            curK -= 1
            initSet.add(randomInt)
    U = D[list(initSet), :]  # 均值向量
    C = np.zeros(m)
    curIter = maxIter
    while curIter > 0:
        curIter -= 1
        for i in range(m):
            p = 0
            minDistance = distance(D[i], U[0])
            for j in range(1, K):
                if distance(D[i], U[j]) < minDistance:
                    p = j
                    minDistance = distance(D[i], U[j])
            C[i] = p
        newU = np.zeros((K, n))
        cnt = np.zeros(K)
        for i in range(m):
            newU[int(C[i])] += D[i]
            cnt[int(C[i])] += 1
        changed = 0
        for i in range(K):
            newU[i] /= cnt[i]
            for j in range(n):
                if U[i, j] != newU[i, j]:
                    changed = 1
                    U[i, j] = newU[i, j]
        if changed == 0:
            return U, C, maxIter-curIter
    return U, C, maxIter-curIter

作圖查看結(jié)果

U, C, iter = Kmeans(data,3,10)
# print(U)
# print(C)
# print(iter)

f1 = plt.figure(1)
plt.title('watermelon_4')
plt.xlabel('density')
plt.ylabel('ratio')
plt.scatter(data[:, 0], data[:, 1], marker='o', color='g', s=50)
plt.scatter(U[:, 0], U[:, 1], marker='o', color='r', s=100)
# plt.xlim(0,1)
# plt.ylim(0,1)
m, n = np.shape(data)
for i in range(m):
    plt.plot([data[i, 0], U[int(C[i]), 0]], [data[i, 1], U[int(C[i]), 1]], "c--", linewidth=0.3)
plt.show()