"M
LK,即Machine Learning Knowledge,本專欄在於對機器學習的重點知識做一次梳理,便於日後溫習,內容主要來自於《百面機器學習》一書,結合自己的經驗與思考做的一些總結與歸納,本次主要講解的內容是機器學習裡的非監督學習經典原理與演算法,非監督,也就是沒有target(標籤)的演算法模型。
"
(歡迎關注微信公眾號瞭解更多知識:SAMshare)
Index
K-Mean聚類演算法
高斯混合模型
自組織對映神經網路
聚類演算法的評估指標
常見聚類演算法對比
常見聚類演算法的Python實現
在機器學習中存在一種問題,那就是模型是沒有target的,給機器輸入大量的特徵資料,期望機器可以學習出當中的共性或者結構又或者是關聯,並不需要像監督學習那樣輸出某個預測值。
K-Mean聚類演算法
K-Mean的基本思想就是透過迭代的方式尋找K個簇(Cluster)的一種劃分方案,使得聚類結果對應的Cost Function最小,一般K-Mean的Cost Function為各個樣本距離所屬簇中心點的誤差平方和,公式為:
其中Xi代表第i個樣本,Ci是Xi所屬的簇,μci代表簇對應的中心點,M是樣本總數。
首先先來看一下K-Mean演算法的具體步驟描述:
1)資料預處理,如歸一化、異常值處理;
2)隨機抽取K個簇(K由人工設定);
3)定義Cost Function:
4)不斷迭代下面 步驟,直到CF收斂:
對於每個樣本Xi,將其分配到距離最近的簇:
對於每個簇,重新計算簇中心:
K-Mean的優點
1)對於大資料集,演算法還是相對高效的,計算複雜度為O(NKt),其中N為樣本數,K為聚類數,t為迭代的論數;
2)一般情況下都可以滿足聚類的需求。
K-Mean的缺點
1)需要人工確定K值,人工對大資料的K值預判有的時候不太好;
2)K-Mean很容易區域性最優,所以效果很受一開始的初始值影響;
3)容易受到異常值,噪點的影響。
K-Mean調優思路
1)資料歸一化和異常值處理。
因為K-Mean本質上是基於歐式距離度量的資料聚類方法,所以少量的極端值會影響聚類效果的,而且不同量綱的資料也會有不一樣的影響,所以需要做一下預處理。
2)合理選擇K值。
K值並不是拍腦袋拍出來的,需要用科學的辦法去確定。一般可以透過多次試驗結果決定,如採用手肘法:
其中,橫軸為K的取值,縱軸為誤差平方和所定義的Loss Function。
可以看出,K值越大,距離和越小,我們看到當K=3的時候,曲線出現“拐點”,因此一般我們選擇這個點作為我們的K值。
此外,這裡還介紹一個
GS(Gap Statistic)方法
,可參考:
https://
blog。csdn。net/baidu_176
40849/article/details/70769555
3)採用核函式。
傳統的歐式距離度量方式使得K-Mean演算法本質上是假設各個簇的資料具有一樣的先驗機率,並呈現球形或者高維球形分佈,但這種分佈在現實中不太常見,這個時候我們引入一個
核K-Mean演算法
,主要面對非凸的資料分佈。
這類核聚類方法主要是透過一個非線性對映,將輸入控制元件中的資料點對映到高位的特徵空間中,並在新的特徵空間中進行聚類,非線性對映增加了資料點線性可分的機率,從而達到更高精度的聚類結果。
再說說兩種演算法
1)K-Mean++演算法
這個從名字上看,就是K-Mean的改良版,主要是在初始值的選取上作了改進。原先的K-Mean是隨機選擇初始值,而K-Mean++演算法則是:
第1個聚類中心也是隨機;
接下來的聚類中心,也就是第2個,按照距離當前聚類中心越遠越好;
按照上述思想,選擇了k個初始的聚類中心;
初始值選取完畢後,後續的流程和K-Mean是一樣的。
2)ISODATA演算法
當K值的大小不確定的時候,可以使用ISODATA演算法,全稱叫迭代自組織資料分析法。ISODATA演算法在K-Mean演算法的基礎上增加了兩個操作:
分裂操作,對應著增加聚類中心數
合併操作,對應著減少聚類中心數
ISODATA的應用也是比較複雜的,需要填比較多的引數:
預期的聚類中心資料K0:在ISODATA執行過程中聚類中心數可以自動變化,這裡的K0只是一個參考值;
每個類所要求的的最少樣本數Nmin:如果分裂後會導致某個子類別所包含的樣本數量少於該閾值,會拒絕本次分裂操作;
最大方差Sigma:用於控制某個類別中樣本的分散程度,當樣本的分散程度超過某個閾值時,且分裂後滿足第一條要求,則進行分裂操作;
兩個聚類中心之間所允許的最小距離Dmin:如果兩個簇靠得很近,就會被進行合併操作。
(歡迎關注微信公眾號瞭解更多知識:SAMshare)
高斯混合模型
高斯模型,對應著高斯分佈,高斯分佈也就是我們平時常說的正態分佈,高斯混合模型(Gaussian Mixed Model,GMM)也是一種聚類演算法,和K-Mean演算法類似,都是用了EM演算法進行迭代計算。高斯混合模型是假設每個簇的資料都符合正態分佈,當前資料呈現的分佈則是每個正態分佈的混合結果。
高斯混合模型的核心思想,每個單獨的分模型都是
標準高斯分佈
模型,其均值和方差都是待估計的引數,還有一個引數π,可以理解為權重(or 生成資料的機率),其公式為:
它是一個生成式模型,並且透過EM演算法框架來求解,具體的迭代過程如下:
首先,初始隨機選擇各個引數的值(總共3個引數,均值、方差和權重),然後迭代下面兩步,直到收斂:
1)E步驟:根據當前的引數,計算每個點由某個分模型生成的機率。
2)M步驟:使用E步驟估計出來的機率,來改進每個分模型的均值、方差和權重。
高斯混合模型與K-Mean演算法的相同點:
1)他們都是用於聚類的演算法,都需要指定K值;
2)都是使用EM演算法來求解;
3)往往都是得到區域性最優。
而它相比於K-Mean演算法的優點,就是它還可以用於機率密度的估計,而且可以用於生成新的樣本點。
生成式模型(Generative Model):對聯合分佈機率p(x,y)進行建模,常見生成式模型有:隱馬爾可夫模型HMM、樸素貝葉斯模型、高斯混合模型GMM、LDA等。
判別式模型(Discriminative Model):直接對條件機率p(y|x)進行建模,常見判別模型有:線性迴歸、決策樹、支援向量機SVM、k近鄰、神經網路等。
自組織對映神經網路
自組織對映神經網路(Self-Organizing Map,SOM)
是無監督學習方法中的一類重要方法,可以用於聚類、高維視覺化、資料壓縮、特徵提取等等用途,因為提出者是Teuvo Kohonen教授,因此也被稱為Kohonen網路。
講SOM之前,先科普一些生物學研究:
1)在人腦的感知通道上,神經元組織是有序排列的;
2)大腦皮層會對外界特定的資訊在特定的區域產生興奮;
3)在生物神經系統中存在著一種側抑制現象,即一個神經細胞興奮後,會對周圍其他神經細胞產生抑制作用,這種抑制作用會使得神經細胞之間出現競爭,其結果是某些獲勝,某些失敗,表現則為獲勝細胞興奮,失敗細胞抑制。
而我們的SOM就是對以上的生物神經系統功能的一種
人工神經網路模型
。
SOM本質上是一個兩層神經網路,包含輸入層和輸出層。輸入層模擬感知外界輸入資訊,輸出層模擬做出響應的大腦皮層。
1)輸出層中,神經元的個數就是聚類的個數;
2)訓練時採用“競爭學習”的方式,每個輸入的樣本,都會在輸出層中找到與之最為匹配的節點,這個節點被稱之為
"啟用節點"
(winning neuron);
3)緊接著採用隨機梯度下降法更新啟用節點的引數,同時適當地更新啟用節點附近的節點(會根據距離遠近選擇更新的“力度”);
4)上面說到的“競爭學習”,可以透過神經元之間的橫向抑制連線(負反饋路徑)來實現。
一般,SOM模型的常見網路結構有兩種,分別是一維和二維的:
SOM的自組織學習過程,可以歸納為下面幾個子過程:
1)
初始化:
所有連線權重都用小的隨機值進行初始化。
2)
競爭:
神經元計算每一個輸入模式各自的判別函式值,並宣佈具有最小判別函式值的特定神經元為勝利者,每個神經元j的判別函式為:
3)
合作:
獲勝的神經元決定了興奮神經元拓撲鄰域的空間位置,確定了啟用節點後,更新臨近的節點。
4)
適應:
適當調整相關興奮神經元的連線權重,使得獲勝神經元對相似輸入模式的後續應用的響應增強。
5)迭代第2-4步,直到特徵對映趨於穩定。
等到最後迭代結束之後,每個樣本所啟用的神經元就是它對應的類別。
SOM與K-Mean演算法的區別
1)K-Mean演算法需要事先確定好K值,而SOM不需要;
2)K-Mean演算法為每個輸入資料找到一個最相似的類,只更新這個類的引數;而SOM則會更新臨近的節點,所以,K-Mean演算法受噪聲影響比較大,SOM則可能準確性方面會差一些;
3)SOM的視覺化很好,有優雅的拓撲關係圖。
如何訓練引數
1)
設定輸出層神經元的數量
:如果不清楚,可以儘可能設定較多的節點數。
2)
設計輸出節點的排列
:對於不同的問題,事先選擇好模式。
3)
初始化權值
。
4)
設計拓撲鄰域
:拓撲鄰域的設計原則是使得鄰域不斷縮小,從而輸出平面上相鄰神經元對應的權向量既有區別又有相當的相似度,從而保證獲勝節點對某一類模式產生最大響應時,其鄰域節點也產生較大響應。
5)
設計學習率
:學習率是一個遞減函式,可以結合拓撲鄰域一起考慮。在訓練開始時,可以選擇較大的值,這樣子比較快下降,後面慢慢減少。
聚類演算法的評估指標
聚類演算法不像有監督學習有一個target,更多的都是沒有目標的,所以評估指標也是不一樣的,下面介紹幾種常用的評估指標:
1)輪廓係數(Silhouette Coefficient)
silhouette 是一個衡量一個結點與它屬聚類相較於其它聚類的相似程度,取值範圍-1到1,值越大表明這個結點更匹配其屬聚類而不與相鄰的聚類匹配。如果大多數結點都有很高的silhouette value,那麼聚類適當。若許多點都有低或者負的值,說明分類過多或者過少。
定義
輪廓係數結合了凝聚度和分離度,其計算步驟如下:
對於第i個物件,計算它到所屬簇中所有其他物件的平均距離,記為ai(體現凝聚度)
對於第i個物件和不包含該物件的任意簇,記為bi(體現分離度)
第i個物件的輪廓係數為si=(bi-ai)/max(ai,bi)
2)Calinski-Harabaz指數
如果標籤是未知的,sklearn。metrics。calinski_harabaz_score則可以使用Calinski-Harabaz指數來評估模型,其中較高的Calinski-Harabaz分數與具有更好定義的聚類的模型相關。
優點:
當叢集密集且分離好時,分數更高,這與叢集的標準概念有關。
得分快速計算
缺點:
凸群的Calinski-Harabaz指數通常高於簇的其他概念,例如透過DBSCAN獲得的基於密度的叢集。
3)Adjusted Rand index(調整後蘭德指數)
該指標是衡量兩個賦值相似度的函式,忽略排列組合
優點
:
隨機(統一)標籤分配 對於任何值的ARI分數接近0。0n_clusters,n_samples(對於原始的蘭德指數或V度量,情況不是這樣)。
有界範圍[-1,1]:負值是壞的(獨立標註),相似的聚類具有正的ARI,1。0是完美的匹配得分。
對叢集結構沒有作出任何假設:可以用於比較聚類演算法,例如k-means,其假設各向同性斑點形狀與可以找到具有“摺疊”形狀的聚類的頻譜聚類演算法的結果。
缺點
:
與慣性相反,ARI需要對地面真相類的知識,而在實踐中幾乎不可用,或者需要人工註釋者的人工分配(如在受監督的學習環境中)。
然而,ARI也可以在純無人監控的設定中用作可用於聚類模型選擇(TODO)的共識索引的構建塊。
4)Mutual Information based scores(基於相互資訊的分數)
鑑於labels_true相同樣本的基本真實類分配和我們的聚類演算法分配的知識labels_pred, 互資訊是衡量兩個分配的一致性的函式,忽略排列。這種措施的兩個不同的標準化版本是可用的,歸一化互資訊(NMI)和調整的相互資訊(AMI)。文獻中經常使用NMI,而最近提出了AMI,並針對機會進行歸一化:
優點
:
隨機的(均勻的)標籤指定具有AMI得分接近0。0 為任何值n_clusters和n_samples(其不是生互資訊或V-措施例如的情況下)。
有界範圍[0,1]:接近零的值表示兩個主要獨立的標籤分配,而接近1的值表示重要的一致性。此外,恰好為0的值表示純獨立的標籤分配,並且恰好為1的AMI表示兩個標籤分配是相等的(有或沒有排列)。
對叢集結構沒有作出任何假設:可以用於比較聚類演算法,例如k-means,其假設各向同性斑點形狀與可以找到具有“摺疊”形狀的聚類的頻譜聚類演算法的結果。
缺點
:
與慣性相反,基於MI的措施需要了解地面真相類,而在實踐中幾乎不可用,或需要人為註釋者的人工分配(如在受監督的學習環境中)。然而,基於MI的措施也可用於純粹無監督的設定,作為可用於聚類模型選擇的共識索引的構建塊。
常見聚類演算法對比
下面一張圖介紹幾種Scikit learn的常用聚類演算法的比較:
常見聚類演算法的Python實現
上面說了這麼多聚類演算法,還是在最後面,把演算法的Python實現程式碼給大家貼一下,我們全文使用鸞尾花資料集:
‘’‘
使用Iris資料集(鳶尾花卉資料集)來進行我們的第一次預測。
該資料集包含150條記錄的一組資料,有5個屬性——花瓣長度,花瓣寬度,萼片長度,萼片寬度和類別。
三個類別分別是Iris Setosa(山鳶尾),Iris Virginica(維吉尼亞鳶尾)和Iris Versicolor(變色鳶尾)。
對於我們的無監督演算法,我們給出鳶尾花的這四個特徵,並預測它屬於哪一類。
’‘’
# Importing Modules
from sklearn import datasets
import matplotlib。pyplot as plt
# Loading dataset
iris_df = datasets。load_iris()
print(dir(iris_df))
# Features
print(iris_df。feature_names)
# Targets
print(iris_df。target)
# Target Names
print(iris_df。target_names)
label = {0:‘red’,1:‘blue’,2:‘green’}
# Dataset slicing
x_axis = iris_df。data[:,0]
y_axis = iris_df。data[:,2]
# Plotting
plt。scatter(x_axis, y_axis, c=iris_df。target)
plt。show()
1)K-Means聚類
# Importing Modules
from sklearn import datasets
from sklearn。cluster import KMeans
# Loaning dataset
iris_df = datasets。load_iris()
# Declaring Model 初始化模型
model = KMeans(n_clusters=3)
# Fitting Model
model。fit(iris_df。data)
# Predicting a single input
predicted_label = model。predict([[7。2, 3。5, 0。8, 1。6]])
# Prediction on the entire data
all_predictions = model。predict(iris_df。data)
# Printing Predictions
print(predicted_label)
print(all_predictions)
2)分層聚類(Hierarchical clustering)
from scipy。cluster。hierarchy import linkage, dendrogram
import matplotlib。pyplot as plt
import pandas as pd
seeds_df = pd。read_csv(
“https://raw。githubusercontent。com/vihar/unsupervised-learning-with-python/master/seeds-less-rows。csv”)
# remove the grain species from the DataFrame, save for later
varieties = list(seeds_df。pop(‘grain_variety’))
# extract the measurements as a NumPy array
samples = seeds_df。values
“”“
Perform hierarchical clustering on samples using the
linkage() function with the method=‘complete’ keyword argument。
Assign the result to mergings。
”“”
mergings = linkage(samples, method=‘complete’)
“”“
Plot a dendrogram using the dendrogram() function on mergings,
specifying the keyword arguments labels=varieties, leaf_rotation=90,
and leaf_font_size=6。
”“”
dendrogram(mergings,
labels=varieties,
leaf_rotation=90,
leaf_font_size=6,
)
plt。show()
3)t-SNE聚類
# Importing Modules
from sklearn import datasets
from sklearn。manifold import TSNE
import matplotlib。pyplot as plt
# Loading dataset
iris_df = datasets。load_iris()
# Defining Model
model = TSNE(learning_rate=100)
# Fitting Model
transformed = model。fit_transform(iris_df。data)
# Plotting 2d t-Sne
x_axis = transformed[:, 0]
y_axis = transformed[:, 1]
plt。scatter(x_axis, y_axis, c=iris_df。target)
plt。show()
‘’‘
這裡Iris資料集具有四個特徵(4d),它被變換並以二維圖形表示。類似地,t-SNE模型可以應用於具有n個特徵的資料集
’‘’
4)DBSCAN聚類
# Importing Modules
from sklearn。datasets import load_iris
import matplotlib。pyplot as plt
from sklearn。cluster import DBSCAN
from sklearn。decomposition import PCA
# Load Dataset
iris = load_iris()
# Declaring Model
dbscan = DBSCAN()
# Fitting
dbscan。fit(iris。data)
# Transoring Using PCA
pca = PCA(n_components=2)。fit(iris。data)
pca_2d = pca。transform(iris。data)
# Plot based on Class
for i in range(0, pca_2d。shape[0]):
if dbscan。labels_[i] == 0:
c1 = plt。scatter(pca_2d[i, 0], pca_2d[i, 1], c=‘r’, marker=‘+’)
elif dbscan。labels_[i] == 1:
c2 = plt。scatter(pca_2d[i, 0], pca_2d[i, 1], c=‘g’, marker=‘o’)
elif dbscan。labels_[i] == -1:
c3 = plt。scatter(pca_2d[i, 0], pca_2d[i, 1], c=‘b’, marker=‘*’)
plt。legend([c1, c2, c3], [‘Cluster 1’, ‘Cluster 2’, ‘Noise’])
plt。title(‘DBSCAN finds 2 clusters and Noise’)
plt。show()
5)MiniBatchKMeans
‘’‘
Comparison of the K-Means and MiniBatchKMeans clustering algorithms
’‘’
print(__doc__)
import time
import numpy as np
import matplotlib。pyplot as plt
from sklearn。cluster import MiniBatchKMeans, KMeans
from sklearn。metrics。pairwise import pairwise_distances_argmin
from sklearn。datasets。samples_generator import make_blobs
# Generate sample data
np。random。seed(0)
batch_size = 45
centers = [[1, 1], [-1, -1], [1, -1]]
n_clusters = len(centers)
X, labels_true = make_blobs(n_samples=300000, centers=centers, cluster_std=0。7)
# Compute clustering with Means
k_means = KMeans(init=‘k-means++’, n_clusters=3, n_init=10)
t0 = time。time()
k_means。fit(X)
t_batch = time。time() - t0
# Compute clustering with MiniBatchKMeans
mbk = MiniBatchKMeans(init=‘k-means++’, n_clusters=3, batch_size=batch_size,
n_init=10, max_no_improvement=10, verbose=0)
t0 = time。time()
mbk。fit(X)
t_mini_batch = time。time() - t0
# Plot result
fig = plt。figure(figsize=(8, 3))
fig。subplots_adjust(left=0。02, right=0。98, bottom=0。05, top=0。9)
colors = [‘#4EACC5’, ‘#FF9C34’, ‘#4E9A06’]
# We want to have the same colors for the same cluster from the
# MiniBatchKMeans and the KMeans algorithm。 Let‘s pair the cluster centers per
# closest one。
k_means_cluster_centers = np。sort(k_means。cluster_centers_, axis=0)
mbk_means_cluster_centers = np。sort(mbk。cluster_centers_, axis=0)
k_means_labels = pairwise_distances_argmin(X, k_means_cluster_centers)
mbk_means_labels = pairwise_distances_argmin(X, mbk_means_cluster_centers)
order = pairwise_distances_argmin(k_means_cluster_centers,
mbk_means_cluster_centers)
# KMeans
ax = fig。add_subplot(1, 3, 1)
for k, col in zip(range(n_clusters), colors):
my_members = k_means_labels == k
cluster_center = k_means_cluster_centers[k]
ax。plot(X[my_members, 0], X[my_members, 1], ’w‘,
markerfacecolor=col, marker=’。‘)
ax。plot(cluster_center[0], cluster_center[1], ’o‘, markerfacecolor=col,
markeredgecolor=’k‘, markersize=6)
ax。set_title(’KMeans‘)
ax。set_xticks(())
ax。set_yticks(())
plt。text(-3。5, 1。8, ’train time: %。2fs\ninertia: %f‘ % (
t_batch, k_means。inertia_))
# MiniBatchKMeans
ax = fig。add_subplot(1, 3, 2)
for k, col in zip(range(n_clusters), colors):
my_members = mbk_means_labels == order[k]
cluster_center = mbk_means_cluster_centers[order[k]]
ax。plot(X[my_members, 0], X[my_members, 1], ’w‘,
markerfacecolor=col, marker=’。‘)
ax。plot(cluster_center[0], cluster_center[1], ’o‘, markerfacecolor=col,
markeredgecolor=’k‘, markersize=6)
ax。set_title(’MiniBatchKMeans‘)
ax。set_xticks(())
ax。set_yticks(())
plt。text(-3。5, 1。8, ’train time: %。2fs\ninertia: %f‘ %
(t_mini_batch, mbk。inertia_))
# Initialise the different array to all False
different = (mbk_means_labels == 4)
ax = fig。add_subplot(1, 3, 3)
for k in range(n_clusters):
different += ((k_means_labels == k) != (mbk_means_labels == order[k]))
identic = np。logical_not(different)
ax。plot(X[identic, 0], X[identic, 1], ’w‘,
markerfacecolor=’#bbbbbb‘, marker=’。‘)
ax。plot(X[different, 0], X[different, 1], ’w‘,
markerfacecolor=’m‘, marker=’。‘)
ax。set_title(’Difference‘)
ax。set_xticks(())
ax。set_yticks(())
plt。show()
6)Affinity Propagation(近鄰傳播)
# Demo of affinity propagation clustering algorithm
print(__doc__)
from sklearn。cluster import AffinityPropagation
from sklearn import metrics
from sklearn。datasets。samples_generator import make_blobs
# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0。5,
random_state=0)
# Compute Affinity Propagation
af = AffinityPropagation(preference=-50)。fit(X)
cluster_centers_indices = af。cluster_centers_indices_
labels = af。labels_
n_clusters_ = len(cluster_centers_indices)
print(’Estimated number of clusters: %d‘ % n_clusters_)
print(“Homogeneity: %0。3f” % metrics。homogeneity_score(labels_true, labels))
print(“Completeness: %0。3f” % metrics。completeness_score(labels_true, labels))
print(“V-measure: %0。3f” % metrics。v_measure_score(labels_true, labels))
print(“Adjusted Rand Index: %0。3f”
% metrics。adjusted_rand_score(labels_true, labels))
print(“Adjusted Mutual Information: %0。3f”
% metrics。adjusted_mutual_info_score(labels_true, labels))
print(“Silhouette Coefficient: %0。3f”
% metrics。silhouette_score(X, labels, metric=’sqeuclidean‘))
# Plot result
import matplotlib。pyplot as plt
from itertools import cycle
plt。close(’all‘)
plt。figure(1)
plt。clf()
colors = cycle(’bgrcmykbgrcmykbgrcmykbgrcmyk‘)
for k, col in zip(range(n_clusters_), colors):
class_members = labels == k
cluster_center = X[cluster_centers_indices[k]]
plt。plot(X[class_members, 0], X[class_members, 1], col + ’。‘)
plt。plot(cluster_center[0], cluster_center[1], ’o‘, markerfacecolor=col,
markeredgecolor=’k‘, markersize=14)
for x in X[class_members]:
plt。plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)
plt。title(’Estimated number of clusters: %d‘ % n_clusters_)
plt。show()
Reference
《百面機器學習》——chapter5
(歡迎關注微信公眾號瞭解更多知識:SAMshare)