柚子快報激活碼778899分享：機器學習-10 聚類算法
聚類算法
算法概括聚類（clustering）聚類的概念聚類的要求聚類與分類的區(qū)別
常見算法分類聚類算法中存在的問題
距離度量閔可夫斯基距離歐式距離（歐幾里得距離）曼哈頓距離切比雪夫距離皮爾遜相關系數余弦相似度杰卡德相似系數
劃分聚類K-means聚類算法算法原理基本概念算法實例聚類分析的度量
聚類評價指標簇內平方和（Inertia）輪廓系數（Silhouette Coefficient）
簇類個數k的調整（了解）選擇正確的聚簇數相似性度量初始聚類中心的選擇
K-Means算法評價
算法概括
機器學習有兩種學習類型：
有監(jiān)督學習：即數據點有已知的結果。無監(jiān)督學習：即數據點沒有已知的結果，利用無標簽的數據學習數據的分布或數據與數據之間的關系被稱作無監(jiān)督學習。 注： ①有監(jiān)督學習和無監(jiān)督學習的最大區(qū)別在于數據是否有標簽。 ②無監(jiān)督學習最常應用的場景是聚類和降維，聚類算法用于識別數據中未知的結構，降維則是使用數據中的結構特征來簡化數據。
聚類（clustering）
聚類的概念
聚類就是根據數據的“相似性”將數據分為多類的過程。聚類把各不相同的個體分割為有更多相似子集合的工作。聚類生成的子集合稱為簇。
聚類的要求
生成的簇內部的任意兩個對象之間具有較高的相似度。屬于不同簇的兩個對象間具有較高的相異度
聚類與分類的區(qū)別
之前學習過k近鄰算法分類算法，分類和聚類聽上去好像很相似，但是兩者完全是不同的應用和原理。 例如，根據下圖的四個屬性進行預測某一輸入的所屬類別： 概括而來就是這樣一個流程： 可以看出訓練樣本是有明確的標簽的，數據點是有已知結果的，而聚類不同，聚類算法本身訓練的樣本就是無標簽的，你不知道它屬于哪一類，而把具有空間相近性、性質相似性的數據點歸為一類，這就是聚類算法要做的事情。 還是上面的例子： 這個時候訓練樣本的標簽被蓋住了，我們必須從這四個屬性入手，把樣本聚合成不同的簇，每個簇中的數據點的屬性最相似。 概括而來就是這樣一個過程： 現(xiàn)在小結一下，分類和聚類的區(qū)別概括而來就是這樣：
分類：學習/訓練有監(jiān)督，訓練樣本有明確標簽。 聚類：學習/訓練過程無監(jiān)督，樣本無明確標簽。 聚類與分類的區(qū)別在于聚類不依賴于預先定義的類，沒有預定義的類和樣本——聚類是一種無監(jiān)督的數據挖掘任務。
常見算法分類
劃分聚類： 大部分方法是基于距離的聚類算法。如：K-Means、K-Medoids、CLARANS等。層次聚類： 例如：BIRCH、CURE、CHAMELEON等。層次聚類可采用“自底向上”或“自頂向下”方案。在“自底向上”方案中，初始時每一個數據紀錄都被視作一個單獨的簇，接著再把那些相互鄰近的簇合并成一個新的簇，直到所有的記錄都在一個簇或者滿足某個終止條件為止。密度聚類： 該方法是基于（結點）密度的聚類算法，主要算法有：DBSCAN、OPTICS、DENCLUE等。只要一個區(qū)域中的點的密度大于某個閾值，就把它加到與之相近的聚類中去。網格聚類： 主要算法有：STING、CLIQUE、WAVE-CLUSTER。將數據空間按某種特征（屬性）劃分成網格，聚類處理以網格（單元）為基本單位。 注： ①后邊三種聚類不做介紹，主要以劃分聚類中的K-Means算法作為本章學習重點。 ②需要說明的是，這些算法本身無所謂優(yōu)劣，而最終運用于數據的效果卻存在好壞差異，這在很大程度上取決于數據使用者對于算法的選擇是否得當。
聚類算法中存在的問題
①高維數據集中存在大量無關的屬性，所有維中存在簇的可能性幾乎為零。②高維空間中數據較低維空間中數據分布稀疏，其中數據間距離幾乎相等是普遍現(xiàn)象，而傳統(tǒng)聚類方法是基于距離進行聚類的，因此在高維空間中無法基于距離來構建簇。
距離度量
評估兩個不同樣本之間的“相似性”，通常使用的方法就是計算兩個樣本之間的“距離”，使用不同的方法計算樣本間的距離關系到聚類結果的好壞。 大多數聚類分析是以相似性計算為基礎的，同一個聚類中的個體模式相似，不在同一個聚類中的個體模式則相異。目前，相似性距離的計算都是基于向量的，也就是計算兩個向量的距離，距離相近則相似度越大。 下面，介紹幾種常見的距離計算方法。
閔可夫斯基距離
閔可夫斯基距離（Minkowski Distance）是一種常見的方法，用于衡量數值點之間距離。 假設
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1?,x2?,...,xn?）,Y（y1?,y2?,...,yn?)是n維空間的兩個向量，那么，閔可夫斯基距離定義為：
d
i
s
t
（
X
,
Y
）
=
∑
k
=
1
n
∣
x
k
?
y
k
∣
p
p
dist（X,Y）=\sqrt[p]{\textstyle \sum_{k=1}^{n} |x_k-y_k|^p}
dist（X,Y）=p∑k=1n?∣xk??yk?∣p
? 注：該距離最常用的p是2和1，前者是歐幾里得距離，后者是曼哈頓距離。當p趨近于無窮大時，閔可夫斯基距離轉化為切比雪夫距離。
閔可夫斯基距離計算距離如下：
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
dist=np.linalg.norm(x-y,ord=4)#閔可夫斯基距離，此時p=4
歐式距離（歐幾里得距離）
歐式距離（Euclidean Distance）最初用于計算歐幾里得空間中兩個點的距離。假設
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1?,x2?,...,xn?）,Y（y1?,y2?,...,yn?)是n維空間的兩個向量，它們之間的歐幾里得距離是：
d
i
s
t
（
X
,
Y
）
=
∑
k
=
1
n
(
x
k
?
y
k
)
2
p
dist（X,Y）=\sqrt[p]{\textstyle \sum_{k=1}^{n} (x_k-y_k)^2}
dist（X,Y）=p∑k=1n?(xk??yk?)2
? n=2歐幾里得距離就是平面上兩個點的距離。如果歐式距離看作物品相似程度，那么距離越近就越相似，也就是說距離越小，相似度越大。
歐式距離計算舉例如下：
import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=dis.pdist(X,metric='euclidean')
#或者直接按照閔可夫斯基距離的計算方式
dist=np.linalg.norm(x-y,ord=2)
曼哈頓距離
曼哈段距離也稱為城市街區(qū)距離（City Block distance），或絕對距離。即在歐幾里得空間的固定直角坐標系上兩點所形成的線段對軸的投影距離總和。 坐標
(
x
1
,
y
1
)
(x_1,y_1)
(x1?,y1?)的點
P
1
P_1
P1?與坐標
(
x
2
,
y
2
)
(x_2,y_2)
(x2?,y2?)的點
P
2
P_2
P2?的曼哈頓距離為：
d
i
s
t
(
P
1
,
P
2
)
=
∣
x
1
?
x
2
∣
+
∣
y
1
?
y
2
∣
dist(P_1,P_2)=|x_1-x_2|+|y_1-y_2|
dist(P1?,P2?)=∣x1??x2?∣+∣y1??y2?∣
曼哈頓距離計算Python語句如下：
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
dist=np.linalg.norm(x-y,ord=1)
切比雪夫距離
閔可夫斯基距離定義中，當p=
+
∞
+\infty
+∞時，稱為切比雪夫距離（Chebyshev Distance）。 假設
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1?,x2?,...,xn?）,Y（y1?,y2?,...,yn?)是n維空間的兩個向量，它們之間的切比雪夫距離是：
d
i
s
t
(
X
,
Y
)
=
lim
?
n
→
∞
)
(
∑
i
=
1
n
∣
x
i
?
y
i
∣
k
)
1
k
=
max
?
(
∣
x
i
?
y
i
∣
)
,
1
≤
i
≤
n
dist(X,Y) = \lim_{n \to \infty})(\sum_{i=1}^{n}|x_i-y_i|^k)^\frac{1}{k} = \max(|x_i-y_i|), 1 \leq i \leq n
dist(X,Y)=n→∞lim?)(i=1∑n?∣xi??yi?∣k)k1?=max(∣xi??yi?∣),1≤i≤n
切比雪夫距離計算Python語句如下：
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
dist=np.linalg.norm(x-y,ord=np.inf)
皮爾遜相關系數
皮爾遜相關系數（Pearson Correlation Coeffient）即相關分析中的相關系數r，一般用于計算兩個定距變量間聯(lián)系的緊密程度，它的取值在[-1，+1]之間。 當相關系數為0時，X和Y兩變量無線性關系（不代表沒有除了線性關系外的其他關系）；當X的值增大，Y也增大，正相關關系，相關系數在0.00與1.00之間；當X的值增大，Y減小，負相關關系，相關系數在-1.00與0.00之間。相關系數的絕對值越大，相關性越強，相關系數越接近于1和-1，相關度越強，相關系數越接近于0，相關度越弱。 公式如下：
r
(
x
,
y
)
=
E
(
x
y
)
?
E
(
x
)
(
y
)
E
(
x
2
)
?
(
E
(
x
)
)
2
E
(
y
2
)
?
(
E
(
y
)
)
2
=
c
o
v
(
x
,
y
)
σ
x
σ
y
r(x,y) = \frac{E(xy)-E(x)(y)}{\sqrt[]{E(x^2)-(E(x))^2}{\sqrt[]{E(y^2)-(E(y))^2}}} = \frac{cov(x,y)}{\sigma_x\sigma_y}
r(x,y)=E(x2)?(E(x))2
?E(y2)?(E(y))2
?E(xy)?E(x)(y)?=σx?σy?cov(x,y)?
皮爾遜相關系數計算Python語句如下：
import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=1-dis.pdist(X,metric='correlation')
余弦相似度
余弦相似度就是兩個向量之間的夾角的余弦值。假設
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1?,x2?,...,xn?）,Y（y1?,y2?,...,yn?)是n維空間的兩個向量，它們之間的余弦相似度是：
cos
?
θ
=
X
Y
∣
X
∣
∣
Y
∣
\cos \theta = \frac{XY}{|X||Y|}
cosθ=∣X∣∣Y∣XY? 余弦相似度用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小。相比距離向量，余弦相似度更加注重兩個向量在方向上的差異，而非距離或長度。 夾角余弦取值范圍為[-1,1]。夾角余弦越大表示兩個向量的夾角越小，夾角余弦越大表示兩個向量的夾角越大。當兩個向量的方向重合時余弦取最大值1，當兩個向量的方向完全相反夾角余弦取最小值-1。 余弦相似度計算Python語句如下：
import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=1-dis.pdist(X,metric='cosine')
歐幾里得vs余弦距離
歐幾里得距離適合于基于坐標的度量。余弦距離更適合那些出現(xiàn)位置不重要的數據，例如文本數據。歐幾里得距離對維度災難更敏感。
杰卡德相似系數
Jaccard系數主要用于計算符號度量或布爾值度量的個體間的相似度，只關心個體間共同具有的特征是否一致這個問題。假設集合 A和 B，兩個集合的杰卡德相似系數表示如下：
J
(
A
,
B
)
=
∣
A
∩
B
∣
∣
A
∪
B
∣
J(A,B)= \frac {|A∩B|}{|A∪B|}
J(A,B)=∣A∪B∣∣A∩B∣?
杰卡德相似距離計算Python語句如下：
import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=dis.pdist(X,metric='jaccard')
劃分聚類
K-means聚類算法
算法原理
k-means算法以k為參數，把n個對象分為k個簇，使簇內具有較高的相似度，而簇間的相似度較低。 其處理過程如下: ①隨機選擇k個點作為初始的聚類中心。 ②對于剩下的點，根據其與聚類中心的距離，將其歸入最近的簇。 ③對于每個簇，計算所有點的均值作為新的聚類中心。 ④重復2、3直到聚類中心不再發(fā)生改變。
算法流程如下所示：
如下圖所示為聚類A、B、C、D、E五個點的聚類中心的選取過程：
基本概念
要得到簇的個數，需要指定K值。 質心：均值，即向量各維取平均即可。 距離的度量：常用歐幾里得距離和余弦相似度（先標準化）。 優(yōu)化目標：
min
?
∑
i
=
1
K
∑
x
∈
C
i
d
i
s
t
(
c
i
,
x
)
2
\min \sum_{i=1}^{K}\sum_{x \in C_i}^{}dist(c_i,x)^2
min∑i=1K?∑x∈Ci??dist(ci?,x)2
算法實例
題目背景
練習算法實例，要求做到： 1、理解程序中每個函數以及每個變量的含義； 2、掌握k-means算法的實現(xiàn)過程； 3、使用k-means算法對下表中的5個樣本進行聚類（k=2）。
k-means的手動實現(xiàn)
import numpy as np
def kmeans(X, k, max_iter=300):
# 隨機選擇k個初始質心
centroids = X[np.random.choice(X.shape[0], k)]
for i in range(max_iter):
# 計算每個樣本點到質心的距離，并分配到最近質心所在的簇中
distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))
labels = distances.argmin(axis=0)
# 重新計算每個簇的質心
new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])
# 檢查質心是否變化，若沒有則退出
if np.all(centroids == new_centroids):
break
centroids = new_centroids
return labels, centroids
X=np.array([[170,70],[178,75],[100,100],[120,40],[10,0.1]])
labels,centroids=kmeans(X,k=2)
print("當k=3時,簇劃分情況為：",labels)
print("當k=3時,質心為：\n",centroids)
sklearn庫中K-means算法
scikit-learn模塊提供了k-Means聚類方法，原型為： class sklearn.cluster.KMeans(n_clusters=8, init=’k-means++’, n_init=10, max_iter=300, tol=0.0001, precompute_distances=’auto’, verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm=’auto’) 主要參數包括：
n_clusters：整型，可選，默認參數值為8，聚類數量。init：‘k-means++’，‘random’或者ndarray之一，默認為’k-means++’。 ’k-means++’： 以一種巧妙的方式選擇k-均值聚類的初始集群中心，以加快收斂速度。 ‘random’：從初始質心的數據中隨機選取 k 觀察 (行)。 ndarray：給出形狀 (n_clusters, n_features)的初始中心。n_init：整型，默認參數值為10。用不同的初始化質心運行算法的次數。由于k-Means是結果受初始值影響的局部最優(yōu)的迭代算法，因此需要多跑幾次以選擇一個較好的聚類效果。max_iter：整型，默認參數值為300，最大的迭代次數。tol：浮點型，默認參數值為0.0001，最小容忍誤差，當誤差小于tol就會退出迭代。algorithm：可以是‘auto’，‘full’或者’elkan’之一，默認參數值為’auto’。’full’適合于EM類算法；’elkan’適合于三角形不等式，但暫不支持稀疏數據；而當設置為’auto’時，稠密數據用’elkan’，稀疏數據用’full’。random_state：整型，RandonState實例或None，默認參數值為None。具體如下： int：該參數用于設置隨機數發(fā)生器的種子； RandonState instance：該參數是一個隨機數發(fā)生器； None：使用np.random作為隨機數發(fā)生器。
import numpy as np
from sklearn.cluster import KMeans
#使用k-means算法對數據進行聚類
X=np.array([[170,70],[178,75],[100,100],[120,40],[10,0.1]])
kmeans_model=KMeans(n_clusters=2,init="k-means++")
kmeans_model.fit(X)
print("當k=2時,簇劃分情況為：",kmeans2_model.labels_)
print("當k=2時,質心為：\n",kmeans2_model.cluster_centers_)
聚類分析的度量
聚類分析的度量指標用于對聚類結果進行評判，分為內部指標和外部指標兩大類： 外部指標指用事先指定的聚類模型作為參考來評判聚類結果的好壞。 內部指標是指不借助任何外部參考，只用參與聚類的樣本評判聚類結果好壞。聚類的目標是得到較高的簇內相似度和較低的簇間相似度，使得簇間的距離盡可能大，簇內樣本與簇中心的距離盡可能小。聚類得到的簇可以用聚類中心、簇大小、簇密度和簇描述等來表示： 聚類中心是一個簇中所有樣本點的均值(質心)。 簇大小表示簇中所含樣本的數量。 簇密度表示簇中樣本點的緊密程度。 簇描述是簇中樣本的業(yè)務特征。
聚類評價指標
簇內平方和（Inertia）
每個數據點
x
i
x_i
xi?距其聚簇中心
C
k
C_k
Ck?的距離平方和
∑
i
=
1
n
(
x
i
?
C
k
)
2
\sum_{i=1}^{n}(x_i-C_k)^2
i=1∑n?(xi??Ck?)2值越小表示聚簇越緊密。
輪廓系數（Silhouette Coefficient）
對每個數據點計算一個輪廓系數： a=此數據點到同簇中所有其他點的平均距離，凝聚度。 b=此數據點到最近簇中所有點的平均距離，分離度。
S
=
b
?
a
m
a
x
(
a
,
b
)
S=\frac{b-a}{max(a,b)}
S=max(a,b)b?a?將所有數據點的輪廓系數取平均值就得到一個總的評分。取值在[-1,1]之間，值越大，聚類效果越好。
簇類個數k的調整（了解）
選擇正確的聚簇數
Inertia衡量點到聚簇中心的距離的值會隨著K的增大而不斷降低，只要聚簇密度在不斷增大，也就是說簇分的越多，每個簇的特征會愈加明顯。小于真實K值時，下降幅度很大；超過真實K值時，下降趨于平緩。 選擇輪廓系數最大的K值。
相似性度量
相似系數： 兩個僅包含二元屬性的對象之間的相似性度量也稱相似系數。 兩個對象的比較有四種情況：f00 = x取0并且y取0的屬性個數；f01 = x取0并且y取1的屬性個數；f10 = x取1并且y取0的屬性個數；f11 = x取1并且y取1的屬性個數 簡單匹配系數： SMC = 值匹配的屬性個數 / 屬性個數== (f11 +f00) / (f01 + f10 + f11 + f00) Jaccard（杰卡德）系數： J = 匹配的個數 / 不涉及0-0匹配的屬性個數 = (f11) / (f01 + f10 +f11)
初始聚類中心的選擇
K-means算法的初值敏感，容易陷入局部最小值，同一個算法運行兩次有可能得到不同的結果，所以建議初始選點可以根據多次交叉去做，選擇多次中心點。
更聰明的K-Means初始化方法 ①隨機地選取一點作為起始點。 ②計算每個點與已有聚簇中心點之間的最短距離，D(x)。 ③按照
D
(
x
)
2
/
∑
D
(
x
)
2
D(x)^2/\sum_{}^{}D(x)^2
D(x)2/∑?D(x)2的概率Income選取下一個點。 Kmeans++（分配聚簇） kmeans++是為了解決初始值敏感問題：與kmeans區(qū)別是選擇質心的方式不一樣。 ①從數據集中間，任選一個點作為質心。 ②把所有樣本到質心距離計算出來，選擇較遠的距離（從離中心點第一遠，第二遠，第三遠，第四遠，第五遠中，選一個距離），作為另外一個質心，從而解決了在較近的距離選擇兩個點。 ③這里有缺陷，選擇的第二點依賴第一個點，第三點前依賴前兩點，第四點依賴前三點。每次選擇點都要計算所有中心點，到所有點的距離。計算量有點大。
注：初始質心的選擇和聚類簇數k的選擇都會對聚類結果產生影響，它們的選擇會導致不同的聚類效果，因此需要進行多次實驗，選擇最優(yōu)的初始質心、聚類簇數k。在極端情況下，有時候會出現(xiàn)局部最優(yōu)解問題，即算法陷入局部最優(yōu)解，無法到達全局最優(yōu)解?？偟膩碚f，KMeans算法具有一定的隨機性。
K-Means算法評價
優(yōu)點： ①算法簡單，易于理解。 ②對球形簇樣本聚類效果好。 ③二分k均值等變種算法運行良好，不受初始化問題的影響。缺點： ①不能處理非球形簇、不同尺寸和不同密度的簇，存在局限性。 ②對離群點、噪聲敏感。 ③數據比較大的時候，收斂會比較慢。
柚子快報激活碼778899分享：機器學習-10 聚類算法
好文鏈接
本文內容根據網絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉載請注明，如有侵權，聯(lián)系刪除。
Ioffer我提供
