關(guān)鍵字

Q1:分類和聚類有什么不同？

第一，它們面對的根本問題不同。分類的根本問題是判斷給定的某一個樣本屬于那一個類別；聚類的根本問題是探索給定的數(shù)據(jù)集可以分成哪幾種類別。

第二，兩者使用的訓(xùn)練數(shù)據(jù)集有差異。分類任務(wù)使用的訓(xùn)練數(shù)據(jù)集中每個樣本除了有屬性數(shù)據(jù)外，還必須有一個標(biāo)記值，用以表示該樣本屬于哪一類；聚類任務(wù)的數(shù)據(jù)集中每個樣本可以只有屬性值，沒有標(biāo)記值（當(dāng)然也可以有）。這也可以認為是我們常說的，監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)。

Q2:聚類的一般方法有哪些？

有三類：基于原型的聚類、基于密度的聚類、和基于層次的聚類。

補充：算法多種多樣，但是萬變不離其宗，最基本的思想還是先提出一中衡量樣本之間相似程度的的手段，如距離、相關(guān)系數(shù)等，然后逐一計算數(shù)據(jù)集中各樣本之間的相似度，盡量把相似度高的樣本放到同一類。

1、聚類

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

2、聚類和分類的區(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)只是把相似的東西聚到一起。

3、性能度量

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

4、K-Means的原理

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

5、K-Means算法

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

這條公式在一定程度上刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度，E值越小則簇內(nèi)樣本相似度越高。
最小化上面的公式并不容易，找到它的最優(yōu)解需考察樣本集D內(nèi)所有可能的簇劃分，這是一個NP難問題。因此，k-means算法采用了貪心策略，通過迭代優(yōu)化來近似求解上面的公式。
算法流程如下：

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

下面以西瓜數(shù)據(jù)集4.0為例來演示k-means算法的學(xué)習(xí)過程。我們將編號為i的樣本稱為xi，這是一個包含“密度”與“含糖率”兩個屬性值的二維向量。

假定簇數(shù)k=3，算法開始是隨機選取三個樣本x6,x12,x27作為初始均值向量，即

考察樣本x1=（0.697；0.460），它與當(dāng)前均值向量u1，u2，u3的距離分別是0.369，0.506，0.166，因此x1將被劃入簇C3中。類似的，對數(shù)據(jù)集中所有的樣本考察一遍后，可得當(dāng)前簇劃分為

于是，可從C1，C2，C3分別求出新的均值向量

更新當(dāng)前均值向量后，不斷重復(fù)上述過程，如下圖所示，第五輪迭代產(chǎn)生的結(jié)果與第四輪迭代相同，于是算法停止，得到最終的簇劃分。

6、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)的思想。

7、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，對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。

8、代碼部分

讀取數(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()

輸出如下：

上圖劃分了三個簇，每個簇的命名都是由我們來命名，例如，我們可以把它們分別命名為：好瓜、中等瓜、壞瓜。

完整代碼參考碼云
參考文獻
http://www.itdecent.cn/p/1f8fb959e013