一、聚類的目標
使同一類對象的相似度盡可能地大；不同類對象之間的相似度盡可能地小。
二、聚類算法分類
1.基于劃分
給定一個有N個元組或者紀錄的數(shù)據(jù)集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。
特點：計算量大。很適合發(fā)現(xiàn)中小規(guī)模的數(shù)據(jù)庫中小規(guī)模的數(shù)據(jù)庫中的球狀簇。
算法：K-MEANS算法、K-MEDOIDS算法、CLARANS算法
2.基于層次
對給定的數(shù)據(jù)集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。
特點：較小的計算開銷。然而這種技術不能更正錯誤的決定。
算法：BIRCH算法、CURE算法、CHAMELEON算法
3.基于密度
只要一個區(qū)域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。
特點：能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。
算法：DBSCAN算法、OPTICS算法、DENCLUE算法
4.基于網(wǎng)格
將數(shù)據(jù)空間劃分成為有限個單元（cell）的網(wǎng)格結構,所有的處理都是以單個的單元為對象的。
特點：處理速度很快，通常這是與目標數(shù)據(jù)庫中記錄的個數(shù)無關的，只與把數(shù)據(jù)空間分為多少個單元有關。
算法：STING算法、CLIQUE算法、WAVE-CLUSTER算法
三、DBscan聚類
1.算法原理
DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一種典型的基于密度的聚類算法，在DBSCAN算法中將數(shù)據(jù)點分為一下三類：
核心點：在半徑Eps內(nèi)含有超過MinPts數(shù)目的點
邊界點：在半徑Eps內(nèi)點的數(shù)量小于MinPts，但是落在核心點的鄰域內(nèi)
噪音點：既不是核心點也不是邊界點的點
在這里有兩個量，一個是半徑Eps，另一個是指定的數(shù)目MinPts
2.代碼
# encoding=utf-8
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
class DBScan (object):
"""
the class inherits from object, encapsulate the DBscan algorithm
"""
def __init__(self, p, l_stauts):
self.point = p
self.labels_stats = l_stauts
self.db = DBSCAN(eps=0.2, min_samples=10).fit(self.point)
def draw(self):
coreSamplesMask = np.zeros_like(self.db.labels_, dtype=bool)
coreSamplesMask[self.db.core_sample_indices_] = True
labels = self.db.labels_
nclusters = jiangzao(labels)
# 輸出模型評估參數(shù)，包括估計的集群數(shù)量、均勻度、完整性、V度量、
# 調整后的蘭德指數(shù)、調整后的互信息量、輪廓系數(shù)
print('Estimated number of clusters: %d' % nclusters)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(self.labels_stats, labels))
print("Completeness: %0.3f" % metrics.completeness_score(self.labels_stats, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(self.labels_stats, labels))
print("Adjusted Rand Index: %0.3f"
% metrics.adjusted_rand_score(self.labels_stats, labels))
print("Adjusted Mutual Information: %0.3f"
% metrics.adjusted_mutual_info_score(self.labels_stats, labels))
print("Silhouette Coefficient: %0.3f"
% metrics.silhouette_score(self.point, labels))
# 繪制結果
# 黑色被移除，并被標記為噪音。
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
for k, col in zip(unique_labels, colors):
if k == -1:
# 黑色用于噪聲
col = 'k'
classMemberMask = (labels == k)
# 畫出分類點集
xy = self.point[classMemberMask & coreSamplesMask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=6)
# 畫出噪聲點集
xy = self.point[classMemberMask & ~coreSamplesMask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=3)
# 加標題，顯示分類數(shù)
plt.title('Estimated number of clusters: %d' % nclusters)
plt.show()
def jiangzao (labels):
# 標簽中的簇數(shù)，忽略噪聲（如果存在）
clusters = len(set(labels)) - (1 if -1 in labels else 0)
return clusters
def standar_scaler(points):
p = StandardScaler().fit_transform(points)
return p
if __name__ == "__main__":
"""
test class dbScan
"""
centers = [[1, 1], [-1, -1], [-1, 1], [1, -1]]
point, labelsTrue = make_blobs(n_samples=2000, centers=centers, cluster_std=0.4,
random_state=0)
point = standar_scaler(point)
db = DBScan(point, labelsTrue)
db.draw()
3.圖形輸出
如圖算法自動將數(shù)據(jù)集分成了4簇，用四種顏色代表。每一簇內(nèi)較大的點代表核心對象，較小的點代表邊界點（與簇內(nèi)其他點密度相連，但是自身不是核心對象）。黑色的點代表離群點或者叫噪聲點。
4.控制臺輸出
Estimated number of clusters: 4
Homogeneity: 0.928
Completeness: 0.862
V-measure: 0.894
Adjusted Rand Index: 0.928
Adjusted Mutual Information: 0.862
Silhouette Coefficient: 0.584
四、K-means聚類
1.算法原理
2.代碼
#coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
#從磁盤讀取城市經(jīng)緯度數(shù)據(jù)
X = []
f = open('city.txt')
for v in f:
X.append([float(v.split(',')[1]), float(v.split(',')[2])])
#轉換成numpy array
X = np.array(X)
#類簇的數(shù)量
n_clusters = 5
#現(xiàn)在把數(shù)據(jù)和對應的分類書放入聚類函數(shù)中進行聚類
cls = KMeans(n_clusters).fit(X)
#X中每項所屬分類的一個列表
cls.labels_
#畫圖
markers = ['^', 'x', 'o', '*', '+']
for i in range(n_clusters):
members = cls.labels_ == i
plt.scatter(X[members, 0], X[members, 1], s=60, marker=markers[i], c='b', alpha=0.5)
plt.title(' ')
plt.show()
3.圖像輸出
五、層次聚類
1.算法簡介
凝聚層次聚類：所謂凝聚的，指的是該算法初始時，將每個點作為一個簇，每一步合并兩個最接近的簇。另外即使到最后，對于噪音點或是離群點也往往還是各占一簇的，除非過度合并。對于這里的“最接近”，有下面三種定義。我在實現(xiàn)是使用了MIN，該方法在合并時，只要依次取當前最近的點對，如果這個點對當前不在一個簇中，將所在的兩個簇合并就行：
單鏈(MIN):定義簇的鄰近度為不同兩個簇的兩個最近的點之間的距離。
全鏈(MAX):定義簇的鄰近度為不同兩個簇的兩個最遠的點之間的距離。
組平均：定義簇的鄰近度為取自兩個不同簇的所有點對鄰近度的平均值。
2.代碼
# scoding=utf-8
# Agglomerative Hierarchical Clustering(AHC)
import pylab as pl
from operator import itemgetter
from collections import OrderedDict,Counter
points = [[int(eachpoint.split('#')[0]), int(eachpoint.split('#')[1])] for eachpoint in open("points","r")]
# 初始時每個點指派為單獨一簇
groups = [idx for idx in range(len(points))]
# 計算每個點對之間的距離
disP2P = {}
for idx1,point1 in enumerate(points):
for idx2,point2 in enumerate(points):
if (idx1 < idx2):
distance = pow(abs(point1[0]-point2[0]),2) + pow(abs(point1[1]-point2[1]),2)
disP2P[str(idx1)+"#"+str(idx2)] = distance
# 按距離降序將各個點對排序
disP2P = OrderedDict(sorted(disP2P.iteritems(), key=itemgetter(1), reverse=True))
# 當前有的簇個數(shù)
groupNum = len(groups)
# 過分合并會帶入噪音點的影響，當簇數(shù)減為finalGroupNum時，停止合并
finalGroupNum = int(groupNum*0.1)
while groupNum > finalGroupNum:
# 選取下一個距離最近的點對
twopoins,distance = disP2P.popitem()
pointA = int(twopoins.split('#')[0])
pointB = int(twopoins.split('#')[1])
pointAGroup = groups[pointA]
pointBGroup = groups[pointB]
# 當前距離最近兩點若不在同一簇中，將點B所在的簇中的所有點合并到點A所在的簇中，此時當前簇數(shù)減1
if(pointAGroup != pointBGroup):
for idx in range(len(groups)):
if groups[idx] == pointBGroup:
groups[idx] = pointAGroup
groupNum -= 1
# 選取規(guī)模最大的3個簇，其他簇歸為噪音點
wantGroupNum = 3
finalGroup = Counter(groups).most_common(wantGroupNum)
finalGroup = [onecount[0] for onecount in finalGroup]
dropPoints = [points[idx] for idx in range(len(points)) if groups[idx] not in finalGroup]
# 打印規(guī)模最大的3個簇中的點
group1 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[0]]
group2 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[1]]
group3 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[2]]
pl.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], 'or')
pl.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], 'oy')
pl.plot([eachpoint[0] for eachpoint in group3], [eachpoint[1] for eachpoint in group3], 'og')
# 打印噪音點，黑色
pl.plot([eachpoint[0] for eachpoint in dropPoints], [eachpoint[1] for eachpoint in dropPoints], 'ok')
pl.show()
3.圖像輸出
