9.1 聚類任務(wù)

在無監(jiān)督學(xué)習(xí)任務(wù)中，包括了密度估計、異常檢測以及聚類等。其中應(yīng)用最廣泛的是聚類。

聚類就是對大量未知標(biāo)注的數(shù)據(jù)集，按照數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個簇，使簇內(nèi)的數(shù)據(jù)相似度高，兩簇間的數(shù)據(jù)相似度低。

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

更加具體來說，假設(shè)數(shù)據(jù)集D={x₁,x₂,……,x_m}有m個樣本；每個樣本x_i有n個屬性特征，x_i={x_i1,x_i2,……,x_in}；則聚類算法將數(shù)據(jù)集D劃分為k個不相交的簇，{C_l|l = 1,2,3,……,k}；用λ_j表示樣本x_j的"簇標(biāo)記"，λ_j∈{1,2,……,k}，x_j∈C_λj；聚類結(jié)果包含m個元素的簇標(biāo)記向量λ=(λ₁,λ₂,……,λ_m)。

我們先討論聚類算法涉及的性能度量和距離計算，再介紹幾種不同類型的代表性聚類算法。

9.2 性能度量

要想獲得好的聚類結(jié)果，我們希望聚類結(jié)果的"簇內(nèi)相似度"高，而"簇間相似度"低，即同一簇的樣本盡可能彼此相似，不同簇的樣本盡可能不同。

聚類性能度量大致有兩類。
一類是將聚類結(jié)果與某個"參考模型"進行比較，稱為"外部指標(biāo)"；
一類是直接考察聚類結(jié)果而不利用任何參考模型，稱為"內(nèi)部指標(biāo)"。

• 外部指標(biāo)
  
  根據(jù)上面四式，有常用的聚類性能度量外部指標(biāo)
  上面三個性能度量的結(jié)果值均在[0,1]之間，且越大聚類結(jié)果越好。

• 內(nèi)部指標(biāo)
  設(shè)dist (·,·)用于計算兩個樣本之間的距離，μ代表簇C的中心點
  
  基于式(9.8)-(9.11) 可導(dǎo)出下面這些常用的聚類性能度量內(nèi)部指標(biāo):
  
  其中，DBI的值越小聚類結(jié)果越好；而DI的值越大聚類結(jié)果越好。

9.3 距離計算

對于函數(shù)dist(·,·)，它是一個距離度量，其需要滿足的基本性質(zhì)：
1）非負性：dist(x_i,x_j)≥0
2）同一性：dist(x_i,x_j)=0當(dāng)且僅當(dāng)x_i=x_j
3）對稱性：dist(x_i,x_j)=dist(x_j,x_i)
4）直遞性：dist(x_i,x_j)≤dist(x_i,x_k)+dist(x_k,x_j)

樣本屬性還可以分為"無序?qū)傩?和"有序?qū)傩?
無序?qū)傩?如 {蜷縮,稍蜷,硬直}，{火車,飛機,輪船}
有序?qū)傩?如 {1,2,3}，{高,中,低}，{大,中,小}

• 對于有序?qū)傩缘木嚯x計算
  最常用的是閔可夫斯基距離
  
  當(dāng)p=1時，閔可夫斯基距離為曼哈頓距離
  
  當(dāng)p=2時，閔可夫斯基距離為歐氏距離

• 對于無序?qū)傩缘木嚯x計算
  

  對無序?qū)傩裕捎肰DM。

于是，將閔可夫斯基距離和VDM結(jié)合之后，可以處理混合屬性。
假定有n_c個有序?qū)傩?、n-n_c個無序?qū)傩?，讓有序?qū)傩耘帕性跓o序?qū)傩悦媲?。?/p>

9.4 原型聚類

"原型"指：樣本空間中具有代表性的點。
原型聚類亦稱"基于原型的聚類"。
以下是幾種知名的原型聚類算法。

1. k均值算法

基本思路：通過人工指定k的值確定分類簇的類別數(shù)，隨機選擇k個數(shù)據(jù)點作為各個簇的中心點，然后通過迭代將一類數(shù)據(jù)（相似度高的一類數(shù)據(jù)）劃入各個簇中。

優(yōu)點：易于實現(xiàn)、計算效率高。
缺點：需要事前指定簇的數(shù)量k，如果k值選擇不當(dāng)，則導(dǎo)致聚類效果不佳或產(chǎn)生收斂速度慢等問題。

給定樣本集D={x₁,x₂,……,x_m}，"k均值"算法針對聚類所得簇C={C₁,C₂,……,C_k}最小化平方誤差

步驟：

• 從樣本點中隨機選取k個點作為初始簇中心；
• 將每個樣本點劃分到距離它最近到中心點所代表的簇中；
• 用各簇中所有樣本的中心點替代原有的中心點；
• 重復(fù)步驟2和3，直到中心點不變或者達到預(yù)定迭代次數(shù)，算法終止。

具體流程：

舉例：
給定數(shù)據(jù)集

代碼實現(xiàn)

import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
import seaborn as sns
import tensorflow as tf
#隨機生成數(shù)據(jù)，2000個點，隨機分為兩類
num_puntos=2000
conjunto_puntos=[]#數(shù)據(jù)存放在列表中
for i in range(num_puntos):
    if np.random.random()<0.5:
        conjunto_puntos.append([np.random.normal(0.0,0.9),np.random.normal(0.0,0.9)])
    else:
        conjunto_puntos.append([np.random.normal(3.0,0.5),np.random.normal(3.0,0.5)])
 
df=pd.DataFrame({'x':[v[0] for v in conjunto_puntos],
                 'y':[v[1] for v in conjunto_puntos]})
sns.lmplot('x','y',data=df,fit_reg=False,size=6)
plt.show()
#lmplot, 首先要明確的是:它的輸入數(shù)據(jù)必須是一個Pandas的'DataFrame Like' 對象,
#然后從這個DataFrame中挑選一些參數(shù)進入繪圖充當(dāng)不同的身份.
 
#把數(shù)組裝進tensor中
vectors=tf.constant(conjunto_puntos)
k=4
#tf.random_shuffle（value,seed=None,name=None）：對value（是一個tensor）的第一維進行隨機化。相當(dāng)于把數(shù)據(jù)隨機化
centroides=tf.Variable(tf.slice(tf.random_shuffle(vectors),[0,0],[k,-1]))
#隨機選取K個點作為質(zhì)心
 
#增加維度
expanded_vectors=tf.expand_dims(vectors,0)
expanded_centroides=tf.expand_dims(centroides,1)
 
diff=tf.sub(expanded_vectors,expanded_centroides)
sqr=tf.square(diff)
distance=tf.reduce_sum(sqr,2)
 
#挑選每一個點里的最近的質(zhì)心（返回的是最小值索引）
assignments=tf.argmin(distance,0)
 
#tf.where（）返回bool型tensor中為True的位置，
#tf.gather(params, indices, validate_indices=None, name=None)合并索引indices所指示params中的切片
means=tf.concat(0,[tf.reduce_mean(tf.gather(vectors,
                                            tf.reshape(tf.where(tf.equal(assignments,c)),[1,-1])),
                                  reduction_indices=[1])for c in range(k)])
#tf.assign()用means更新centroides
update_centroides=tf.assign(centroides,means)
 
 
init=tf.global_variables_initializer()
sess=tf.Session()
sess.run(init)
 
for step in range(100):
    _,centroid_values,assignment_values=sess.run([update_centroides,centroides,assignments])
data={'x':[],'y':[],'cluster':[]}
 
for i in range(len(assignment_values)):
    data['x'].append(conjunto_puntos[i][0])
    data['y'].append(conjunto_puntos[i][1])
    data['cluster'].append(assignment_values[i])
df=pd.DataFrame(data)   
sns.lmplot('x','y',data=df,fit_reg=False,size=6,hue='cluster',legend=False)
#hue通過指定一個分組變量, 將原來的y~x關(guān)系劃分成若干個分組;fit_reg：是否顯示回歸曲線
plt.show()

代碼鏈接：https://blog.csdn.net/weixin_31866177/article/details/88246939

2. 學(xué)習(xí)向量量化(LVQ)

LVQ假設(shè)數(shù)據(jù)樣本帶有類別標(biāo)記，學(xué)習(xí)過程中需要利用樣本的標(biāo)記來輔助聚類。

給定數(shù)據(jù)集D={(x₁,y₁),(x₂,y₂),……,(x_m,y_m)}，每個樣本x_j是有n個屬性描述的特征向量(x_j1,x_j2,……,x_jn)，y_j∈Y是樣本x_j的類別標(biāo)記。
LVQ的目的是學(xué)得一組n維原型向量{p₁,p₂,……,p_q}，每個原型向量代表一個簇，簇標(biāo)記為t_i∈Y。LVQ算法如下

• 若p_i*與x_j的標(biāo)記相同，即y_j與t_i相同的話，則令p_i*想x_j的方向靠攏，此時新原型向量p'和新原型向量與x_j的距離分別為

  新原型向量p'
  其中，η是學(xué)習(xí)率∈(0,1)，則更新之后的原型向量更接近x_j。

• 若最近的原型向量p_i*的類別標(biāo)記與x_j不同的話，則要使得p_i*遠離x_j。

不斷重復(fù)上面的步驟之后，最終學(xué)得一組原型向量{p₁,p₂,……,p_q}，每一個原型向量代表一個簇，即可以實現(xiàn)對樣本空間X的簇劃分了。

對任意樣本x，它將被劃入與其距離最近的原型向量所代表的簇中；換言之，每個原型向量p_i定義了與之相關(guān)的一個區(qū)域R_i，該區(qū)域中每個樣本x與p_i的距離不大于x與其他原型向量p_i'(i'≠i)的距離，即

舉例：

數(shù)據(jù)集

算法開始時，根據(jù)樣本的類別標(biāo)記和簇的預(yù)設(shè)類別標(biāo)記對原型向量進行隨機初始化。假定初始化原型向量為x₅,x₁₂,x₁₈,x₂₃,x₂₉。第一輪迭代中，假設(shè)隨機選取到的樣本為x₁，該樣本與原型向量x₅,x₁₂,x₁₈,x₂₃,x₂₉的距離分別為0.283, 0.506, 0.434, 0.260, 0.032。由于p₅即x₂₉距離最近且兩者具有相同的類別標(biāo)記c₂，假定學(xué)習(xí)率η=0.1，則 LVQ更新p₅得到新原型向量

新p5

3. 高斯混合聚類

• 高斯混合聚類原理
  對于n維樣本x，服從高斯分布，概率密度函數(shù)為
  其中，μ為n維均值向量，Σ為n x n的協(xié)方差矩陣。關(guān)鍵在于Σ和μ，可以寫為p(x|μ_i,Σ_i)。若有k個高斯分布混合，即高斯混合分布，
  高斯混合分布
  其中，α_i>0為第i個高斯分布的參數(shù)(權(quán)重)。
  有數(shù)據(jù)集D，隨機變量z_j∈{1,2,...,k} 表示生成樣本x_j的高斯混合成分。z_j的先驗概率P(z_j = i)，對應(yīng)于α_i(i=1,…,k)。根據(jù)貝葉斯定理，z_j的后驗分布對應(yīng)于
  將上式簡寫為γ_ji，則有k個簇，每個樣本x_j的簇標(biāo)記為λ_j即
  對于λ_j，可以采用對數(shù)似然估計，
  上式分別對∑，μ求導(dǎo)，令導(dǎo)數(shù)為0，得
  α求和后為1，引入此約束，對數(shù)似然的拉格朗日形式為
  上式對系數(shù)α求導(dǎo)，令導(dǎo)數(shù)為0，得

• 算法流程
  基于EM算法的高斯混合聚類

  第1行對高斯混合分布的模型參數(shù)進行初始化。
  第2-12行基于EM算法對模型參數(shù)進行選代更新。
  若 EM 算法的停止條件滿足(例如己達到最大法代輪數(shù)，或似然函數(shù)LL(D)增長很少甚至不再增長)，
  則在第 14-17 行根據(jù)高斯混合分布確定簇劃分，在第 18行返回最終結(jié)果.

• 舉例
  模型參數(shù)更新后，不斷重復(fù)上述過程，不同輪數(shù)之后的聚類結(jié)果如圖

• 實現(xiàn)代碼

# 1 讀取數(shù)據(jù)
file='xigua4.txt'
x=[]
with open(file) as f:
    f.readline()
    lines=f.read().split('\n')
    for line in lines:
        data=line.split(',')
        x.append([float(data[-2]),float(data[-1])])
y=np.array(x)
# 2 算法部分
import numpy as np
import random
 
def probability(x,u,cov):
    cov_inv=np.linalg.inv(cov)
    cov_det=np.linalg.det(cov)
    return np.exp(-1/2*((x-u).T.dot(cov_inv.dot(x-u))))/np.sqrt(cov_det)
 
 
def gauss_mixed_clustering(x,k=3,epochs=50,reload_params=None):
    features_num=len(x[0])
    r=np.empty(shape=(len(x),k))
#     初始化系數(shù)，均值向量和協(xié)方差矩陣
    if reload_params!=None:
        a,u,cov=reload_params
    else:
        a=np.random.uniform(size=k)
        a/=np.sum(a)
        u=np.array(random.sample(list(x),k))
        cov=np.empty(shape=(k,features_num,features_num))
#         初始化為只有對角線不為0
        for i in range(k):
            for j in range(features_num):
                cov[i][j]=[0]*j+[0.5]+[0]*(features_num-j-1)
    step=0
    while step<epochs:
#         E步：計算r_ji
        for j in range(len(x)):
            for i in range(k):
                r[j,i]=a[i]*probability(x[j],u[i],cov[i])
            r[j]/=np.sum(r[j])
             
        for i in range(k):
            r_toal=np.sum(r[:,i])
            u[i]=np.sum([x[j]*r[j,i] for j in range(len(x))],axis=0)/r_toal
            cov[i]=np.sum([r[j,i]*((x[j]-u[i]).reshape((features_num,1)).dot((x[j]-u[i]).reshape((1,features_num)))) for j in range(len(x))],axis=0)/r_toal
            a[i]=r_toal/len(x)
        step+=1
    C=[]
    for i in range(k):
        C.append([])
    for j in range(len(x)):
        c_j=np.argmax(r[j,:])
        C[c_j].append(x[j])
    return C,a,u,cov

參考鏈接:https://www.cnblogs.com/lunge-blog/p/11792226.html

9.5 密度聚類

密度聚類亦稱"基于密度的聚類"，此類算法假設(shè)聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定。

DBSCAN是一種代表性聚類算法，基于一組"領(lǐng)域"參數(shù)(ε,m)來刻畫樣本分布的緊密程度。給定數(shù)據(jù)集D={x₁,x₂,……,x_m}。有以下幾個概念

• ε-領(lǐng)域
  對x_j∈D，其ε-鄰域包含樣本集D中與x_j的距離不大于ε的樣本，即在數(shù)據(jù)集D中，所有除x_j的樣本到x_j的距離小于ε的樣本集合。

  這里的dist()默認為歐氏距離。

• 核心對象
  若x_j的ε-鄰域至少包含m個樣本，即

  則x_j是一個核心對象。即如果樣本點x_j的ε-鄰域中包含的樣本個數(shù)大于等于指定值m，則該點x_j稱為核心點。

• 密度直達
  若x_j位于x_i的ε-鄰域中，且x_i是核心對象，則稱x_j由x_i密度直達。

• 密度可達
  對x_i與x_j，若存在樣本序列p₁,p₂,...,p_n，其中p₁=x_i，p_n=x_j且p_i+1由p_i密度直達，則稱x_j由x_i密度可達。

• 密度相連
  對x_i與x_j，若存在x_k使得x_i與x_j均由x_k密度可達，則稱x_i與x_j密度相連。

DBSCAN就是將數(shù)據(jù)集中的密度可達的所有樣本點劃分為一個簇，某些樣本密度可達形成一個簇，另外一些樣本點又可以密度可達就又形成另外一個簇。簇內(nèi)樣本點均密度可達，但是簇內(nèi)的樣本點與其他簇的樣本點無法可達，最后形成了多個簇類。

算法流程如下

簡易流程描述如下
1）如果一個點p的ε-鄰域包含多于m個樣本，則創(chuàng)建一個以p為核心對象的新簇。
2）尋找并合并核心對象直接密度可達的樣本點。
3）沒有新點可以更新簇時，算法結(jié)束。

舉例

import numpy as np
epsilon = 0.11
minpts = 5
x = np.load("watermalon4.0.npy")
#epsilon鄰域統(tǒng)計表
t = [set() for i in range(30)]
#聚類簇
clusters = []
#核心對象集
coreset = set()
for i in range(len(x)):
    t[i].add(i)
    for j in range(i+1,len(x)):
        #歐式距離
        dist = np.linalg.norm(x[i] - x[j])
        if dist <= epsilon:
            #記錄epsilon鄰域信息
            t[i].add(j)
            t[j].add(i)
for i in range(len(t)):
    if len(t[i]) >= minpts:
        #核心對象集
        coreset.add(i)
allset = {i for i in range(len(x))}
while len(coreset) > 0:
    #淺拷貝（拷貝第一層，這里沒影響）
    oldset = allset.copy();
    corepoint = coreset.pop()
    q = [corepoint]
    allset -= {corepoint}
    while len(q) > 0:
        item = q.pop(0)
        if len(t[item]) >= minpts:
            #交集
            delta = t[item] & allset
            q += [i for i in delta]
            allset -= delta
    #新的聚類簇
    newcluster = oldset - allset
    clusters.append(newcluster)
    coreset -= newcluster
print(clusters)

代碼2

代碼鏈接：https://blog.csdn.net/weixin_35732969/article/details/81291670
https://www.cnblogs.com/hiyoung/p/9821589.html

9.6 層次聚類

層次聚類是聚類算法的一種，試圖在不同層次對數(shù)據(jù)集進行劃分，從而形成聚類樹結(jié)構(gòu)。在聚類樹中，不同類別的原始數(shù)據(jù)點是樹的最低層，樹的頂層是一個聚類的根節(jié)點。數(shù)據(jù)集的劃分有自下而上聚合策略和自上而下分裂兩種方法。這里只講解聚合策略。

AGNES是一種自下而上的聚合策略。先將每個樣本作為一個初始簇，然后在算法運行的每一步中合并兩個距離最近的初始簇為越來越大的簇，直到達到預(yù)設(shè)的聚類簇個數(shù)。
簡單的流程如下
(1) 將每個樣本看作初始簇，計算兩兩之間的最小距離；
(2) 將距離最小的兩個簇合并成一個新簇；
(3) 重新計算新簇與所有簇之間的距離；
(4) 重復(fù)(2)、(3)，直到達到停止條件。

該算法的關(guān)鍵在于如何計算聚類簇之間的距離。
實際上每個簇是一個樣本集合，因此，只需采用關(guān)于集合的某種距離即可。例如，給定聚類簇C_i與C_j，可通過下面的式子來計算距離:

代碼實現(xiàn)

# 現(xiàn)有數(shù)據(jù)集circle.xls。樣本具有以下幾個特征：基站編號、工作日上班時間人均停留時間、凌晨人均停留時間、周末人均停留時間、日均人流量，
# 要求根據(jù)以上維度指標(biāo)，對數(shù)據(jù)集進行層次聚類，同時要求打印輸出樣本的類別標(biāo)簽，并畫出譜系聚類圖。
import pandas as pd
import scipy.cluster.hierarchy as sch
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import MinMaxScaler
from matplotlib import pyplot as plt
# 讀取數(shù)據(jù)
data = pd.read_excel(r'circle.xls',index_col='基站編號')
# print(data.head())
df = MinMaxScaler().fit_transform(data)

# 建立模型
model = AgglomerativeClustering(n_clusters=3)
model.fit(df)
data['類別標(biāo)簽'] = model.labels_
print(data.head())

# 畫圖
ss = sch.linkage(df,method='ward')
sch.dendrogram(ss)
plt.show()

原文鏈接：https://blog.csdn.net/qq872890060/article/details/100019662