层次聚类

对给定的数据集进行层次分解或者合并直到某个条件结束

层次聚类算法分为两大类
1 凝聚的层次聚类(AGNES算法) 采用自底向上的策略最初每个对象作为一个簇然后簇根据某些准则一步一步合并,两个簇间的距离可以由这两个不同簇的最近的数据点的相似度来确定，聚类的合并过程反复进行直到所有的对象满足簇的数目。

2 分裂的层次聚类(DIANA算法) 采用自顶向下的策略首先将所有对象置于一个簇中，然后按照某种特定的规则逐渐细分为越来越小的簇直到某个条件(簇的数目或者达到阈值)结束

AGNES,DIANA算法的优缺点

简单，容易理解
合并/分裂点不好选择
合并/分裂点选择了，不能撤销
大数据集不太适合(数据量大内存爆了)
执行效率低 O(t**n^2) t 为迭代次数 n 为样本数

AGNES算法中簇间距离

最小距离(SL聚类)
两个聚簇中最近的两个样本间的距离（问题: 最终得到的模型容易形成链式结构）
linkage = 'ward'
ac = AgglomerativeClustering(n_clusters=n_clusters, affinity='euclidean',
connectivity=connectivity, linkage=linkage)
最大距离(CL聚类)
两个聚簇中最远的两个样本的距离 (问题: 如果存在异常值那么构建的模型结构不稳定)
linkage = 'complete'
ac = AgglomerativeClustering(n_clusters=n_clusters, affinity='euclidean',
connectivity=connectivity, linkage=linkage)
平均距离(AL聚类) （1 两个聚簇样本的两两距离的平均值 2 两个聚簇样本间的两两距离的中值）
linkage = 'average'(均值) 或者 linkage = 'median'(中值)
ac = AgglomerativeClustering(n_clusters=n_clusters, affinity='euclidean',
connectivity=connectivity, linkage=linkage)

# -*- coding: utf-8 -*-
# @Time    : 2019/1/26 3:37 PM
# @Author  : scl
# @Email   : 1163820757@qq.com
# @File    : 层次聚类.py
# @Software: PyCharm

import matplotlib
matplotlib.use("TkAgg")
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from sklearn.neighbors import kneighbors_graph ## KNN的K近邻计算
import sklearn.datasets as ds
import warnings

## 设置属性防止中文乱码及拦截异常信息
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
warnings.filterwarnings(action='ignore', category=UserWarning)


np.random.seed(0)
n_clusters = 4
centers = [(-1, 1), (1, 1), (1, -1), (-1, -1)]
N = 3000
X1,Y1 = ds.make_blobs(n_samples=N,centers=centers,cluster_std=0.5,random_state=12)

n_noise = int(0.1*N)
print(n_noise)
r = np.random.rand(n_noise,2)
min1,min2 = np.min(X1,axis=0)
max1,max2 = np.max(X1,axis=0)
r[:,0] = r[:,0] * (max1-min1)+ min1
r[:,1] = r[:,1] * (max2-min2) + min2


data1_noise = np.concatenate((X1,r),axis=0)
y1_noise = np.concatenate((Y1,[4]*n_noise))


# 模拟月牙形数据
X2,Y2 = ds.make_moons(n_samples=N,noise=0.05)
X2 = np.array(X2)

n_noise = int(0.1*N)
r = np.random.rand(n_noise,2)
min1,min2 = np.min(X2,axis=0)
max1,max2 = np.max(X2,axis=0)
r[:,0] = r[:,0] * (max1-min1)+ min1
r[:,1] = r[:,1] * (max2-min2) + min2

data2_noise = np.concatenate((X2,r),axis=0)
y2_noise = np.concatenate((Y2,[3] * n_noise))

def expandBorder(a,b):
    d = (b - a) * 0.1
    return a-d,b+d;

# 绘图
cm = mpl.colors.ListedColormap(['#FF0000', '#00FF00',  '#0000FF', '#ffd966', '#5c5a5a'])
plt.figure(figsize=(14,12),facecolor='w')
linkages = ("ward", "complete", "average")#把几种距离方法，放到list里，后面直接循环取值 建议使用word策略对样本进行分类。

# (4: 表示 4个簇中心 2: 表示 2个簇中心)
for index,(n_clusters,data,y) in enumerate(((4, X1, Y1), (4, data1_noise, y1_noise),
                                           (2, X2, Y2), (2, data2_noise, y2_noise))):


    plt.subplot(4,4,4*index+1) #前面的两个4表示几行几列 第三个参数表示第几个图(从1开始数 从左到右)
    plt.scatter(data[:,0],data[:,1],c = y,cmap=cm)
    plt.title(u'原始数据',fontsize = 11)
    plt.grid(b=True,ls=':')
    min1,min2 = np.min(data,axis=0)
    max1,max2 = np.max(data,axis=0)
    plt.xlim(expandBorder(min1,max1))
    plt.ylim(expandBorder(min2,max2))

    # 计算类别与类别的距离(只计算最接近的七个样本的距离) -- 希望在agens算法中，在计算过程中不需要重复性的计算点与点之间的距离
    connectivity = kneighbors_graph(data, n_neighbors=7, mode='distance', metric='minkowski', p=2, include_self=False)
    connectivity = (connectivity + connectivity.T)
    for i, linkage in enumerate(linkages):
        ##进行建模，并传值
        print(n_clusters)
        ac = AgglomerativeClustering(n_clusters=n_clusters, affinity='euclidean',
                                     connectivity=connectivity, linkage=linkage)
        ac.fit(data)
        # 获取得到训练数据data所对应的标签值
        y = ac.labels_

        plt.subplot(4, 4, i+2+4*index)
        plt.scatter(data[:, 0], data[:, 1], c=y, cmap=cm)
        plt.title(linkage, fontsize=11)
        plt.grid(b=True, ls=':')
        plt.xlim(expandBorder(min1, max1))
        plt.ylim(expandBorder(min2, max2))


plt.suptitle(u'AGNES层次聚类的不同合并策略', fontsize=15)
plt.tight_layout(0.5, rect=(0, 0, 1, 0.95))
plt.show()

效果: