K 均值聚類
算法交替執(zhí)行以下兩個(gè)步驟：
- 將每個(gè)數(shù)據(jù)點(diǎn)分配給最近的簇中心
- 將每個(gè)簇中心設(shè)置為所分配的所有數(shù)據(jù)點(diǎn)的平均值，如果簇的分配不再發(fā)生改變错览，那么算法結(jié)束。
優(yōu)點(diǎn)
- K 均值不僅相對(duì)容易理解和實(shí)現(xiàn)纲辽，而且運(yùn)行速度也相對(duì)較快啦吧。
- K 均值可以輕松擴(kuò)展到大型數(shù)據(jù)集
- scikit-learn 甚至在 MiniBatchKMeans 類中包含了一種更具可擴(kuò)展性的變體您觉，可以處理非常大的數(shù)據(jù)集。
缺點(diǎn)
- 需要人工預(yù)先確定初始 K 值授滓，且該值和真實(shí)的數(shù)據(jù)未必吻合顾犹。
- 分類結(jié)果嚴(yán)重依賴于分類中心的初始化。通常進(jìn)行多次k-means褒墨，然后選擇最優(yōu)的那次作為最終聚類結(jié)果。
- 結(jié)果不一定是全局最優(yōu)的擎宝，只能保證局部最優(yōu)郁妈。
- 對(duì)噪聲敏感。因?yàn)榇氐闹行氖侨∑骄苌辏虼司垲惔睾苓h(yuǎn)地方的噪音會(huì)導(dǎo)致簇的中心點(diǎn)偏移噩咪。
- 無法解決不規(guī)則形狀的聚類。
- 無法處理離散特征极阅，如：國籍胃碾、性別 等。
k-means 性質(zhì)：
- k-means 實(shí)際上假設(shè)數(shù)據(jù)是呈現(xiàn)球形分布筋搏，實(shí)際任務(wù)中很少有這種情況仆百。與之相比，GMM 使用更加一般的數(shù)據(jù)表示奔脐，即高斯分布俄周。
- k-means 假設(shè)各個(gè)簇的先驗(yàn)概率相同吁讨，但是各個(gè)簇的數(shù)據(jù)量可能不均勻。
- k-means 使用歐式距離來衡量樣本與各個(gè)簇的相似度峦朗。這種距離實(shí)際上假設(shè)數(shù)據(jù)的各個(gè)維度對(duì)于相似度的作用是相同的建丧。
- k-means 中，各個(gè)樣本點(diǎn)只屬于與其相似度最高的那個(gè)簇波势，這實(shí)際上是硬 分簇翎朱。
- k-means 算法的迭代過程實(shí)際上等價(jià)于EM 算法。具體參考EM 算法章節(jié)尺铣。
3拴曲、算法調(diào)優(yōu)
- 數(shù)據(jù)歸一化和離群點(diǎn)處理
- 合理選擇 K 值
K 值選擇方法：
- 手肘法：是一個(gè)經(jīng)驗(yàn)方法，缺點(diǎn)就是不能夠自動(dòng)化迄埃。
- Gap Statistic 方法：只需要找到最大的 Gap Statistic 所對(duì)應(yīng)的 K 即可疗韵。Gap（K）可以視為隨機(jī)樣本的損失和實(shí)際樣本的損失之差。
- 采用核函數(shù)：通過一個(gè)非線性映射侄非，將輸入空間中的數(shù)據(jù)點(diǎn)映射到高位的特征空間中蕉汪，并在新的特征空間進(jìn)行聚類。非線性映射增加了數(shù)據(jù)點(diǎn)線性可分的概率逞怨，從而在經(jīng)典聚類算法失效的情況下者疤，通過引入核函數(shù)可以達(dá)到更為準(zhǔn)確的聚類結(jié)果。
4叠赦、算法改進(jìn)
- K-means++：解決 k-means 嚴(yán)重依賴于分類中心初始化的問題
- k-modes：解決 k-means 無法處理離散特征的問題
- k-medoids：解決k-means 對(duì)噪聲敏感的問題驹马。
- mini-batch k-means：主要用于減少 k-means 的計(jì)算時(shí)間
- ISODATA：K值不確定可以使用
- 二分均值聚類：層次聚類
K-means++
它主要解決 k-means 嚴(yán)重依賴于分類中心初始化的問題。 已經(jīng)選取了 n(0<n<k) 個(gè)初始聚類中心除秀，距離當(dāng)前 n 個(gè)聚類中心越遠(yuǎn)的點(diǎn)會(huì)有更高的概率被選為第 n+1 個(gè)聚類中心糯累。在選取第一個(gè)聚類中心（n=1）時(shí)同樣通過隨機(jī)的方法。
image.png
k-modes
主要解決 k-means 無法處理離散特征的問題
image.png
k-medoids
主要解決k-means 對(duì)噪聲敏感的問題册踩。
image.png
mini-batch k-means
主要用于減少 k-means 的計(jì)算時(shí)間泳姐。mini-batch k-means 算法每次訓(xùn)練時(shí)隨機(jī)抽取小批量的數(shù)據(jù)，然后用這個(gè)小批量數(shù)據(jù)訓(xùn)練暂吉。這種做法減少了 k-means 的收斂時(shí)間胖秒，其效果略差于標(biāo)準(zhǔn)算法。
image.png
二分均值聚類
- 一種用于度量聚類效果的指標(biāo)是 SSE慕的，SSE 值越小表示數(shù)據(jù)點(diǎn)越接近于它們的質(zhì)心阎肝，聚類效果也越好。因?yàn)閷?duì)誤差取了平方肮街，因此更加重視那些遠(yuǎn)離中心的點(diǎn)风题。
- 一種肯定可以降低 SSE值的方式是增加簇的個(gè)數(shù)，但違背了聚類的目標(biāo)，聚類的目標(biāo)是在保持簇?cái)?shù)目不變的情況下提高簇的質(zhì)量俯邓。
- 一種方法是將具有最大 SSE 值的簇分為兩個(gè)簇骡楼。具體實(shí)現(xiàn)時(shí)可以將最大簇包含的點(diǎn)過濾出來并在這些點(diǎn)上運(yùn)行 K-均值算法，其中 k 設(shè)為 2.
def biKmeans(dataSet,k,distMeas=distEclud):
m=np.shape(dataSet)[0]
clusterAssment=np.mat(np.zeros((m,2)))
centroid0=np.mean(dataSet,axis=0).tolist()[0]
centList=[centroid0]
for j in range(m):
clusterAssment[j,1]=distMeas(np.mat(centroid0),dataSet[j,:])**2
while(len(centList)<k):
lowestSSE=np.inf
for i in range(len(centList)):
ptsInCurrCluster=dataSet[np.nonzero(clusterAssment[:,0].A==i)[0],:]
centroidMat,splistClusterAss=kMeans(ptsInCurrCluster,2,distMeas)
sseSplist=np.sum(splistClusterAss[:,1])
sseNotSplit=np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A!=i)[0],1])
print('sseSplit, and notSplit:',sseSplist,sseNotSplit)
if(sseSplist+sseNotSplit<lowestSSE):
bestCentToSplit=i
bestNewCents=centroidMat
bestClustAss=splistClusterAss.copy()
lowestSSE=sseSplist+sseNotSplit
bestClustAss[np.nonzero(bestClustAss[:,0].A==1)[0],0]=len(centList)
bestClustAss[np.nonzero(bestClustAss[:,0].A==0)[0],0]=bestCentToSplit
print('the bestCentToSplit is: ',bestCentToSplit)
print('the len of bestClustAss is:',len(bestClustAss))
centList[bestCentToSplit]=bestNewCents[0,:]
centList.append(bestNewCents[1,:])
clusterAssment[np.nonzero(clusterAssment[:,0].A==bestCentToSplit)[0],:]=bestClustAss
return centList , clusterAssment
通過迭代方式尋找 K 個(gè)簇的一種劃分方案稽鞭，使得聚類結(jié)果對(duì)應(yīng)的代價(jià)函數(shù)最小鸟整。
ISODATA
當(dāng) K 值的大小不確定時(shí)，可以使用 ISODATA 算法朦蕴。
ISODATA 的全稱是迭代自組織數(shù)據(jù)分析法篮条。當(dāng)屬于某個(gè)類別的樣本數(shù)過少，把該類別去除吩抓；當(dāng)屬于某個(gè)類別的樣本數(shù)過多涉茧、分散度較大時(shí)，把該類分為兩個(gè)子類別疹娶。在 K-means 基礎(chǔ)上增加兩個(gè)操作伴栓，一是分裂操作，對(duì)應(yīng)著增加聚類中心數(shù)雨饺；二是合并操作钳垮，對(duì)應(yīng)著減少聚類中心數(shù)。
超參數(shù)設(shè)定：
- 預(yù)期的聚類中心數(shù)目 K 额港。具體地饺窿，最終輸出的聚類中心數(shù)目常見范圍是 K 的一半或兩倍 K。
- 每個(gè)類別要求的最少樣本數(shù)目 N移斩。如果分裂后會(huì)導(dǎo)致某個(gè)子類別所包含樣本數(shù)目小于該閾值肚医，就不會(huì)對(duì)該類別進(jìn)行分裂操作
- 最大方差 Sigma。用于控制某個(gè)類別中樣本的分散程度向瓷。當(dāng)樣本分散程度超過這個(gè)閾值肠套，且分裂后滿足上條規(guī)則，進(jìn)行分裂操作猖任。
- 兩個(gè)聚類中心之間所允許最小距離 D糠排。如果兩個(gè)類靠的非常近，小于該閾值時(shí)超升，則對(duì)這兩個(gè)類進(jìn)行合并操作。
算法實(shí)現(xiàn)
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
X,y=make_blobs(random_state=1)
kmeans=KMeans(n_clusters=3)
kmeans.fit(X)
print('Cluster memberships:\n{}'.format(kmeans.labels_))
# 預(yù)測
print(kmeans.predict(X))
# 質(zhì)心
print(kmeans.cluster_centers_)
