聚類

• 聚類就是對(duì)大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù) 的內(nèi)在相似性將數(shù)據(jù)集劃分為多個(gè)類別坛掠，使 類別內(nèi)的數(shù)據(jù)相似度較大而類別間的數(shù)據(jù)相 似度較小
• 無監(jiān)督

如何計(jì)算相似度/距離

• 閔可夫斯基距離Minkowski/歐式距離 (針對(duì)坐標(biāo)點(diǎn)):

• 杰卡德相似系數(shù)(Jaccard)(針對(duì)集合):

• 余弦相似度(cosine similarity)(針對(duì)向量):
  

• Pearson相似系數(shù)

• 相對(duì)熵(K-L距離)(K-L距離一般不對(duì)稱):

• Hellinger距離

余弦相似度與Pearson相關(guān)系數(shù)的區(qū)別:

• n維向量x和y的夾角記做θ舷蒲，根據(jù)余弦定理友多，其余弦值為:

  
  

• 這兩個(gè)向量的相關(guān)系數(shù)是:

  
  
  
  

  相關(guān)系數(shù)即將x域滥、y坐標(biāo)向量各自平移到原點(diǎn)后的夾角余弦

• 這即解釋了為何文檔間求距離使用夾角余弦——因?yàn)檫@一物理
  量表征了文檔去均值化后的隨機(jī)向量間相關(guān)系數(shù)启绰。

聚類的基本思想:

給定一個(gè)有N個(gè)對(duì)象的數(shù)據(jù)集，構(gòu)造數(shù)據(jù)的k 個(gè)簇渊跋，k≤n着倾。滿足下列條件:

• 每一個(gè)簇至少包含一個(gè)對(duì)象
• 每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇
• 將滿足上述條件的k個(gè)簇稱作一個(gè)合理劃分
  基本思想:對(duì)于給定的類別數(shù)目k卡者，首先給 出初始劃分，通過迭代改變樣本和簇的隸屬 關(guān)系，使得每一次改進(jìn)之后的劃分方案都較 前一次好嗽桩。

K-means算法:

輸入：k, data[n];

• (1) 選擇k個(gè)初始中心點(diǎn)凄敢，例如c[0]=data[0],…c[k-1]=data[k-1];
• (2) 對(duì)于data[0]….data[n], 分別與c[0]…c[k-1]比較，假定與c[i]差值最少扑庞，就標(biāo)記為i;
• (3) 對(duì)于所有標(biāo)記為i點(diǎn)拒逮，重新計(jì)算c[i]={ 所有標(biāo)記為i的data[j]之和}/標(biāo)記為i的個(gè)數(shù)滩援；
• (4) 重復(fù)(2)(3),直到所有c[i]值的變化小于給定閾值。

K-means是對(duì)初值敏感的
簇近似為高斯分布的的時(shí)候,效果較好

迭代終止條件:

• 迭代次數(shù)
• 簇中心變化率
• 最小平方差

import numpy as np




def kmeans(X, k, maxIt):
    '''
    :param X: 數(shù)據(jù)集,數(shù)據(jù)集的最后一列表示標(biāo)簽值（或者組號(hào)）
    :param k: k個(gè)分類
    :param maxIt: 循環(huán)幾次
    :return:
    '''
    numPoints, numDim = X.shape

    dataSet = np.zeros((numPoints, numDim + 1))
    dataSet[:, :-1] = X

    # Initialize centroids randomly
    centroids = dataSet[np.random.randint(numPoints, size = k), :]
    centroids = dataSet[0:2, :]
    #Randomly assign labels to initial centorid
    centroids[:, -1] = range(1, k +1)

    # Initialize book keeping vars.
    iterations = 0
    oldCentroids = None

    # Run the main k-means algorithm
    while not shouldStop(oldCentroids, centroids, iterations, maxIt):
        print("iteration: \n", iterations)
        print ("dataSet: \n", dataSet)
        print ("centroids: \n", centroids)
        # Save old centroids for convergence test. Book keeping.
        oldCentroids = np.copy(centroids)
        iterations += 1

        # Assign labels to each datapoint based on centroids
        updateLabels(dataSet, centroids)

        # Assign centroids based on datapoint labels
        centroids = getCentroids(dataSet, k)

    # We can get the labels too by calling getLabels(dataSet, centroids)
    return dataSet

def shouldStop(oldCentroids,centroids,iterations,maxIt):
    if iterations > maxIt:
        return True
    return np.array_equal(oldCentroids,centroids)

def updateLabels(dataset,centroids):
    numPoints,numDim = dataset.shape
    #算每一行的點(diǎn)離哪個(gè)中心點(diǎn)最近
    for i in range(0,numPoints):
        dataset[i,-1] = getLabelFromClosestCentroid(dataset[i,:-1],centroids)

def getLabelFromClosestCentroid(dataRow,centroids):
    label = centroids[0,-1]
    #numpy.linalg.norm傳入任意兩個(gè)向量谨究，-為距離
    minDist = np.linalg.norm(dataRow-centroids[0,:-1])
    #找最小距離
    for i in range(1,centroids.shape[0]):
        dist = np.linalg.norm(dataRow-centroids[i,:-1])
        if dist < minDist:
            minDist = dist
            label = centroids[i,-1]
    print("minDist:"+str(minDist))
    return label
def getCentroids(dataSet,k):
    result = np.zeros((k,dataSet.shape[1]))
    for i in range(1,k+1):
        #所有求 標(biāo)簽值為i的值
        oneCluster = dataSet[dataSet[:,-1]==i,:-1]
        #axis =0 對(duì)行求平均值胶哲，axis=1 對(duì)列求平均值
        result[i-1,:-1]=np.mean(oneCluster,axis=0)
        #最后賦值標(biāo)簽
        result[i-1,-1]=i
    return result

x1 = np.array([1, 1])
x2 = np.array([2, 1])
x3 = np.array([4, 3])
x4 = np.array([5, 4])
testX = np.vstack((x1, x2, x3, x4))

result = kmeans(testX,2,10)
print("final result:\n"+str(result))

輪廓系數(shù)(Silhouette)

Silhouette系數(shù)是對(duì)聚類結(jié)果有效性的解釋跟驗(yàn)證

計(jì)算樣本i到同簇其他樣本的平均距離為ai.ai越小,說明樣本i越應(yīng)該被聚類到該簇.稱ai為樣本i的簇內(nèi)不相似度

計(jì)算樣本i到其他某簇C1的所有樣本的平均距離bil,稱為樣本i到簇c1的不相似度.bi越大,說明樣本i越不屬于其他簇

輪廓系數(shù)si:
$$S(i)=b(i)-a(i)/max{a(i),b(i)}$$

si接近1,說明樣本i聚類合理,si接近-1,則說明樣本i更應(yīng)該分類到其他簇;若si 近似于0,說明樣本i在兩個(gè)簇的邊界.

所有樣本的si的均值為聚類結(jié)果的輪廓系數(shù)

密度聚類

DBSCAN算法

若干概念:
對(duì)象的ε-領(lǐng)域,給定對(duì)象在半徑ε內(nèi)的區(qū)域
核心對(duì)象:對(duì)于給定的數(shù)目m,如果一個(gè)對(duì)象的ε-領(lǐng)域至少包含m個(gè)對(duì)象,則稱該對(duì)象為核心對(duì)象.
ε-領(lǐng)域內(nèi),而q是一個(gè)核心對(duì)象,我們說對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的.
密度可達(dá):如果存在一個(gè)對(duì)象煉p1p2p3pn,如果p1=q,pn=p,則pi+1是從pi 關(guān)于ε 和m直接密度可達(dá),
密度相連:如果對(duì)象集合D中存在一個(gè)對(duì)象o鸯屿，使得對(duì)象p和q 是從o關(guān)于ε和m密度可達(dá)的萎胰，那么對(duì)象p和q是關(guān)于ε和m密 度相連的技竟。
簇:一個(gè)基于密度的簇是最大的密度相連對(duì)象的集合。
噪聲:不包含在任何簇中的對(duì)象稱為噪聲熙尉。
DBSCAN算法過程:
* 如果一個(gè)點(diǎn)p的ε-鄰域包含多于m個(gè)對(duì)象搓扯，則創(chuàng)建一個(gè)p 作為核心對(duì)象的新簇;
* 尋找并合并核心對(duì)象直接密度可達(dá)的對(duì)象;
* 沒有新點(diǎn)可以更新簇時(shí)，算法結(jié)束铅歼。

密度最大值聚類

局部密度:

W的第i行元素的和為vi的度,形成了頂點(diǎn)度對(duì)角陣D
dii表示第i個(gè)點(diǎn)的度
除主對(duì)角線元素坷澡，D其他位置為0
未正則的拉普拉斯矩陣:$$L=D-W$$

未正則拉普拉斯矩陣譜聚類算法:
輸入:n個(gè)點(diǎn){pi}频敛，簇的數(shù)目k
計(jì)算n×n的相似度矩陣W和度矩陣D;
計(jì)算拉普拉斯矩陣L=D-W;
計(jì)算L的前k個(gè)特征向量u1,u2,...,uk(從小到大);特征值的意義:降維處理

將k個(gè)列向量u1,u2,...,uk組成矩陣U馅扣，U∈Rn×k;
對(duì)于i=1,2,...,n,令yi∈Rk是U的第i行的向量;
使用k-means算法將點(diǎn)(yi)i=1,2,...,n聚類成簇 C1,C2,...Ck;
輸出簇A1,A2,...Ak岂嗓，其中鹊碍，Ai={j|yj∈Ci}

hierarchical clustering 層次聚類

假如有N個(gè)待聚類的樣本,步驟:

• (初始化)把每個(gè)樣本歸為一類,計(jì)算類之間的距離,(樣本之間的相似度)
• 尋找各個(gè)類之間最近的兩個(gè)類,把它們歸為一類
• 重新計(jì)算新生產(chǎn)的這個(gè)類與各個(gè)舊類之間的相識(shí)度;
• 重復(fù)2,3,直到所有的樣本點(diǎn)都?xì)w為一類.

距離的選擇:

• SingleLinkage(nearest-neighbor)兩個(gè)類中距離最近的兩個(gè)點(diǎn)的距離作為兩個(gè)類的距離.
• CompleteLinkage 正好相反.兩個(gè)集合中距離最遠(yuǎn)的兩個(gè)點(diǎn)的距離作為集合距離
• AverageLinkage 兩個(gè)集合中點(diǎn)兩兩距離全部放在一起求均值

代碼:

import  numpy as np
class cluster_node(object):
   def __init__(self,vec,left = None,right = None,distance = 0.0,id = None,count =1):
       self.left = left
       self.right = right
       self.vec = vec
       self.id = id
       self.distance = distance
       self.count = count
def L2dist(v1,v2):
   return  np.sqrt(np.sum((v1-v2)**2))

def L1dist(v1,v2):
   return np.sum(np.abs(v1-v2))

def hcluster(features,distance = L2dist):
   distances = {}
   currentclustid = 1
   clust = [cluster_node(np.array(features[i]),id=i) for i in range(len(features))]


   ##聚類過程
   while len(clust) > 1:
       lowestpair = (0,1)
       closest = distance(clust[0].vec,clust[1].vec)

       for i in range(len(clust)):
           for j in range(i+1,len(clust)):
               if (clust[i].id,clust[j].id) not in distances:
                   distances[(clust[i].id,clust[j].id)] = distance(clust[i].vec,clust[j].vec)
               ##找最短距離
               d = distances[(clust[i].id,clust[j].id)]

               if d < closest:
                   closest = d
                   lowestpair = (i,j)
       ##兩個(gè)類的合并
       mergevec = [(clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i]) /2.0 \
                   for i in range(len(clust[0].vec))]

       newcluster = cluster_node(np.array(mergevec),left=clust[lowestpair[0]],
                                 right=clust[lowestpair[1]],distance=closest,id=currentclustid)

       currentclustid = -1

       del clust[lowestpair[0]]
       del clust[lowestpair[1]]
       clust.append(newcluster)
   return clust[0]
def extract_clusters(clust,dist):
   clusters = {}
   if clust.distance < dist:
       return [clust]

   if clust.left != None:
       cl = extract_clusters(clust.left,dist = dist)
   if clust.right != None:
       cr =extract_clusters(clust.right,dist = dist)

def get_cluster_elements(clust):
   # return ids for elements in a cluster sub-tree
   if clust.id>=0:
       # positive id means that this is a leaf
       return [clust.id]
   else:
       # check the right and left branches
       cl = []
       cr = []
       if clust.left!=None:
           cl = get_cluster_elements(clust.left)
       if clust.right!=None:
           cr = get_cluster_elements(clust.right)
       return cl+cr


def printclust(clust, labels=None, n=0):
   # indent to make a hierarchy layout
   for i in range(n): print
   (' '),
   if clust.id < 0:
       # negative id means that this is branch
       print
       ('-')
   else:
       # positive id means that this is an endpoint
       if labels == None:
           print (clust.id)
       else:
           print(labels[clust.id])

   # now print the right and left branches
   if clust.left != None: printclust(clust.left, labels=labels, n=n + 1)
   if clust.right != None: printclust(clust.right, labels=labels, n=n + 1)


def getheight(clust):
   # Is this an endpoint? Then the height is just 1
   if clust.left == None and clust.right == None: return 1

   # Otherwise the height is the same of the heights of
   # each branch
   return getheight(clust.left) + getheight(clust.right)


def getdepth(clust):
   # The distance of an endpoint is 0.0
   if clust.left == None and clust.right == None: return 0

   # The distance of a branch is the greater of its two sides
   # plus its own distance
   return max(getdepth(clust.left), getdepth(clust.right)) + clust.distance