層次聚類
層次聚類：層次聚類假設類别之間存在層次結構，将樣本聚到階層化的類中。
層次聚類類型：自下而上（bottom-up）或稱聚合(agglomerative)、自上而下(top-down)或稱分裂（divisive）。
謹記：層次聚類中每個樣本隻屬于一個類，是以層次聚類屬于硬聚類。（一般來說聚類分為硬聚類和軟聚類，硬聚類明确一個樣本隻屬于一個類，而軟聚類的一個樣本可以屬于多個類）。
聚合聚類
開始将每個樣本各分到一個類，之後将距離相近的兩類合并，建立一個新的類，重複此操作直到滿足停止條件，得到階層化的類别。
分裂聚類
開始将所有的樣本分到一個類，之後将已有類中相距最遠的樣本分到兩個新的類，重複此操作直到滿足停止條件，得到階層化的類别。
實際問題中多以聚合聚類為主，故本文僅研究聚合聚類算法.
聚合聚類三要素：
（1）距離或相似度（可用闵可夫斯基距離、馬哈拉諾比斯距離、相關系數、夾角餘弦）；
（2）合并規則（類間距離最小）；
（3）停止條件（類的個數達到門檻值）。
聚合聚類算法
輸入：n個樣本組成的樣本集合及樣本之間的距離；
輸出：對樣本集合的一個階層化聚類。
（1）計算n個樣本兩兩之間的歐氏距離{dij},記作矩陣D=[dij]n*n.
（2）構造n個類，每個類隻包含一個樣本。
（3）合并類間距離最小的兩個類，其中最短距離為類間距離，建構一個新類。
（4）計算新類與目前各類的距離。若類的個數為1，終止計算，否則回到步（3）
聚合層次聚類的時間複雜度是O( n 3 n^3 n3 m),其中m樣本的維數，n是樣本個數。
舉個例子，将26個字母随機配置設定了坐标(x,y)
假設 K=3 ，合并的步驟為：
（1）26個字母首先被配置設定成 26 個簇
（2）兩兩歐氏距離最近的兩個簇合并，此時簇變成了 13 個
（3）再次兩兩歐氏距離最近的兩個簇合并，此時一共有 12 個簇合并成了6個簇，還餘下一個簇，是以此時剩下 6+1=7 個簇
（4）一直重複上一步的操作，直到簇的數量為 3 的時候，就算是分簇完成
相應python代碼如下：
# !/usr/bin/python3.4
# -*- coding: utf-8 -*-
import random
# 生成坐标字典
def buildclusters():
clusters = {}
keys = [chr(i) for i in range(ord('A'), ord('Z') + 1)]
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
# 生成第一個分簇坐标
for i in range(0, 9):
# A-I
temp = {}
x = random.randint(0, 40)
y = random.randint(0, 40)
temp["x"] = x
temp["y"] = y
clusters[keys[i]] = temp
# 生成第二個分簇坐标
for i in range(9, 18):
# J-R
temp = {}
x = random.randint(60, 100)
y = random.randint(0, 40)
temp["x"] = x
temp["y"] = y
clusters[keys[i]] = temp
# 生成第三個分簇坐标
for i in range(18, 26):
# S-Z
temp = {}
x = random.randint(40, 60)
y = random.randint(60, 100)
temp["x"] = x
temp["y"] = y
clusters[keys[i]] = temp
# {'K': {'y': 34, 'x': 81}, 'V': {'y': 68, 'x': 50}, 'G': {'y': 1, 'x': 10}, 'C': {'y': 2, 'x': 9}, 'T': {'y': 78, 'x': 40}, 'A': {'y': 20, 'x': 12}, 'B': {'y': 21, 'x': 39}, 'N': {'y': 37, 'x': 67}, 'S': {'y': 92, 'x': 56}, 'Q': {'y': 7, 'x': 62}, 'D': {'y': 18, 'x': 4}, 'E': {'y': 0, 'x': 38}, 'Z': {'y': 92, 'x': 46}, 'H': {'y': 30, 'x': 32}, 'I': {'y': 21, 'x': 35}, 'U': {'y': 71, 'x': 51}, 'L': {'y': 1, 'x': 96}, 'W': {'y': 99, 'x': 59}, 'F': {'y': 10, 'x': 14}, 'O': {'y': 16, 'x': 97}, 'J': {'y': 37, 'x': 76}, 'X': {'y': 86, 'x': 49}, 'Y': {'y': 67, 'x': 50}, 'P': {'y': 17, 'x': 76}, 'M': {'y': 32, 'x': 88}, 'R': {'y': 6, 'x': 70}}
return clusters
# 兩點間的距離公式/歐式距離
def distance(x1, x2, y1, y2):
distan = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
return distan
# 計算各個分簇直到達到分簇的效果
def splitcluster(clusters):
dict = {}
newdict = {}
arr = []
i = 1
for key1 in clusters:
temp = {}
for key2 in clusters:
if key1 != key2:
if key1 in arr or key2 in arr:
pass
else:
name = str(key1 + "->" + key2)
temp[name] = distance(clusters[key1]["x"], clusters[key2]["x"], clusters[key1]["y"],
clusters[key2]["y"])
arr.append(key1)
arr.append(key2)
if temp:
# reverse=False值按照從小到大排序
temp = sorted(temp.items(), key=lambda d: d[1], reverse=False)
newdict[temp[0][0]] = temp[0][1]
newdict = sorted(newdict.items(), key=lambda d: d[1], reverse=False)
for item in newdict:
name = "cluster" + str(i)
i += 1
dict[name] = item[0]
# {'cluster13': 'B->T', 'cluster11': 'U->M', 'cluster10': 'Z->H', 'cluster5': 'L->D', 'cluster1': 'F->E', 'cluster4': 'G->A', 'cluster12': 'I->S', 'cluster3': 'W->V', 'cluster8': 'C->R', 'cluster9': 'P->X', 'cluster2': 'K->N', 'cluster7': 'O->Q', 'cluster6': 'Y->J'}
return dict
# 判斷分簇
def judgecluster(clusters, firstcluster, K):
dict = {}
i = 1
arr = []
for item in firstcluster:
temparr = firstcluster[item].split("->")
distan = {}
for judge in temparr:
if judge in arr:
pass
else:
for value in clusters:
if value in temparr:
pass
elif value in arr:
pass
else:
for key in temparr:
name = value + "->" + key
distan[name] = distance(clusters[key]["x"], clusters[value]["x"], clusters[key]["y"],
clusters[value]["y"])
if key in arr:
pass
else:
arr.append(key)
if distan:
distan = sorted(distan.items(), key=lambda d: d[1], reverse=False)
# print(distan)
element = distan[0][0].split("->")[0]
for ele in firstcluster:
elearr = firstcluster[ele].split("->")
if element in elearr:
values = firstcluster[item]
for va in elearr:
values = values + "->" + va
arr.append(va)
cluster = "cluster" + str(i)
i += 1
dict[cluster] = values
if len(arr) != 26:
# 生成26個字母
letters = [chr(i) for i in range(ord('A'), ord('Z') + 1)]
# 得到剩下沒有被放到dict的字母
remain = []
for letter in letters:
if letter in arr:
pass
else:
remain.append(letter)
dis = {}
for letter in remain:
for item in dict:
elearr = dict[item].split("->")
for ele in elearr:
name = letter + "->" + ele
dis[name] = distance(clusters[letter]["x"], clusters[ele]["x"], clusters[letter]["y"],
clusters[ele]["y"])
if dis:
dis = sorted(dis.items(), key=lambda d: d[1], reverse=False)
element = dis[0][0].split("->")
for cluster in dict:
array = dict[cluster].split("->")
for item in element:
if item in array:
values = "->".join(remain)
dict[cluster] = dict[cluster] + "->" + values
if len(dict) == K:
print(dict)
# {'cluster1': 'M->X->P->Y->J->U->T->R->L->O', 'cluster3': 'V->B->W->N->E->A->I->G', 'cluster2': 'C->H->Q->F->D->S->Z->K'}
return dict
else:
judgecluster(clusters, dict, K)
if __name__ == '__main__':
K = 3
clusters = buildclusters()
firstcluster = splitcluster(clusters)
judgecluster(clusters, firstcluster, K)
結果如下：
![XGBoost Plotting API以及GBDT組合特征實踐 XGBoost Plotting API以及GBDT組合特征實踐[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)