幾張GIF理解K-均值聚類原理
k均值聚類數(shù)學(xué)推導(dǎo)與python實(shí)現(xiàn)
前文說(shuō)了k均值聚類,他是基于中心的聚類方法,通過(guò)迭代將樣本分到k個(gè)類中,使每個(gè)樣本與其所屬類的中心或均值最近。
今天我們看一下無(wú)監(jiān)督學(xué)習(xí)之聚類方法的另一種算法,層次聚類:
層次聚類前提假設(shè)類別直接存在層次關(guān)系,通過(guò)計(jì)算不同類別數(shù)據(jù)點(diǎn)間的相似度來(lái)創(chuàng)建一棵有層次的嵌套聚類樹。在聚類樹中,不同類別的原始數(shù)據(jù)點(diǎn)是樹的最低層,樹的頂層是一個(gè)聚類的根節(jié)點(diǎn)。創(chuàng)建聚類樹有聚合聚類(自下而上合并)和分裂聚類(自上而下分裂)兩種方法,分裂聚類一般很少使用,不做介紹。
聚合聚類
聚合聚類具體過(guò)程
對(duì)于給定的樣本集合,開始將每個(gè)樣本分到一個(gè)類,然后再按照一定的規(guī)則(比如類間距最?。?,將滿足規(guī)則的類進(jìn)行合并,反復(fù)進(jìn)行,直到滿足停止條件。聚合聚類三要素有:
①距離或相似度(閔可夫斯基距離,相關(guān)系數(shù)、夾角余弦)
②合并規(guī)則(最長(zhǎng)/短距離,中心距離,平均距離)
③停止條件(類個(gè)數(shù)或類直徑達(dá)到或超過(guò)閾值)
聚合聚類算法
輸入:n個(gè)樣本組成的樣本集合及樣本間距離
輸出:樣本集合的層次化聚類
(1)計(jì)算n個(gè)樣本兩兩之間歐氏距離{dij}
(2)構(gòu)造n個(gè)類,每個(gè)類只包含一個(gè)樣本
(3)合并類間距最小的兩個(gè)類,構(gòu)造一個(gè)新類
(4)計(jì)算新類與其他各類的距離,若類的個(gè)數(shù)為1,終止計(jì)算,否則回到(3)
動(dòng)畫表示:
python實(shí)現(xiàn)及案例
import queue
import math
import copy
import numpy as np
import matplotlib.pyplot as plt
class clusterNode:
def __init__(self, value, id=[],left=None, right=None, distance=-1, count=-1, check = 0):
'''
value: 該節(jié)點(diǎn)的數(shù)值,合并節(jié)點(diǎn)時(shí)等于原來(lái)節(jié)點(diǎn)值的平均值
id:節(jié)點(diǎn)的id,包含該節(jié)點(diǎn)下的所有單個(gè)元素
left和right:合并得到該節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)
distance:兩個(gè)子節(jié)點(diǎn)的距離
count:該節(jié)點(diǎn)所包含的單個(gè)元素個(gè)數(shù)
check:標(biāo)識(shí)符,用于遍歷時(shí)記錄該節(jié)點(diǎn)是否被遍歷過(guò)
'''
self.value = value
self.id = id
self.left = left
self.right = right
self.distance = distance
self.count = count
self.check = check
def show(self):
#顯示節(jié)點(diǎn)相關(guān)屬性
print(self.value,' ',self.left.id if self.left!=None else None,' ',/
self.right.id if self.right!=None else None,' ',self.distance,' ',self.count)
class hcluster:
def distance(self,x,y):
#計(jì)算兩個(gè)節(jié)點(diǎn)的距離,可以換成別的距離
return math.sqrt(pow((x.value-y.value),2))
def minDist(self,dataset):
#計(jì)算所有節(jié)點(diǎn)中距離最小的節(jié)點(diǎn)對(duì)
mindist = 1000
for i in range(len(dataset)-1):
if dataset[i].check == 1:
#略過(guò)合并過(guò)的節(jié)點(diǎn)
continue
for j in range(i+1,len(dataset)):
if dataset[j].check == 1:
continue
dist = self.distance(dataset[i],dataset[j])
if dist < mindist:
mindist = dist
x, y = i, j
return mindist, x, y
#返回最小距離、距離最小的兩個(gè)節(jié)點(diǎn)的索引
def fit(self,data):
dataset = [clusterNode(value=item,id=[(chr(ord('a')+i))],count=1) for i,item in enumerate(data)]
#將輸入的數(shù)據(jù)元素轉(zhuǎn)化成節(jié)點(diǎn),并存入節(jié)點(diǎn)的列表
length = len(dataset)
Backup = copy.deepcopy(dataset)
#備份數(shù)據(jù)
while(True):
mindist, x, y = self.minDist(dataset)
dataset[x].check = 1
dataset[y].check = 1
tmpid = copy.deepcopy(dataset[x].id)
tmpid.extend(dataset[y].id)
dataset.append(clusterNode(value=(dataset[x].value+dataset[y].value)/2,id=tmpid,/
left=dataset[x],right=dataset[y],distance=mindist,count=dataset[x].count+dataset[y].count))
#生成新節(jié)點(diǎn)
if len(tmpid) == length:
#當(dāng)新生成的節(jié)點(diǎn)已經(jīng)包含所有元素時(shí),退出循環(huán),完成聚類
break
for item in dataset:
item.show()
return dataset
def show(self,dataset,num):
plt.figure(1)
showqueue = queue.Queue()
#存放節(jié)點(diǎn)信息的隊(duì)列
showqueue.put(dataset[len(dataset) - 1])
#存入根節(jié)點(diǎn)
showqueue.put(num)
#存入根節(jié)點(diǎn)的中心橫坐標(biāo)
while not showqueue.empty():
index = showqueue.get()
#當(dāng)前繪制的節(jié)點(diǎn)
i = showqueue.get()
#當(dāng)前繪制節(jié)點(diǎn)中心的橫坐標(biāo)
left = i - (index.count)/2
right = i + (index.count)/2
if index.left != None:
x = [left,right]
y = [index.distance,index.distance]
plt.plot(x,y)
x = [left,left]
y = [index.distance,index.left.distance]
plt.plot(x,y)
showqueue.put(index.left)
showqueue.put(left)
if index.right != None:
x = [right,right]
y = [index.distance,index.right.distance]
plt.plot(x,y)
showqueue.put(index.right)
showqueue.put(right)
plt.show()
def setData(num):
#生成num個(gè)隨機(jī)數(shù)據(jù)
Data = list(np.random.randint(1,100,size=num))
return Data
if name == '__main__':
num = 20
dataset = setData(num)
h = hcluster()
resultset = h.fit(dataset)
h.show(resultset,num)
本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布!
審核編輯 黃昊宇
-
機(jī)器學(xué)習(xí)
+關(guān)注
關(guān)注
66文章
8324瀏覽量
132192 -
深度學(xué)習(xí)
+關(guān)注
關(guān)注
73文章
5440瀏覽量
120798
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論