【火炉炼AI】机器学习023-使用层次聚类算法构建模型

【火炉炼AI】机器学习023-使用层次聚类算法构建模型

(本文所使用的Python库和版本号: Python 3.6, Numpy 1.14, scikit-learn 0.19, matplotlib 2.2 )

聚类的算法有很多种，前面我们讲解了k-means算法和均值漂移算法，此处我们继续讲解层次聚类算法。

k-means是一种分散性聚类算法，以空间中K个点为中心进行聚类，将最靠近他们的样本收归门下。k-means的优势在于简单快速，对于大数据集，该算法仍然可以保持可伸缩性和高效率，对于密集型的数据集，效果非常好。缺点也很明显：必须事先给出K值，而且对初值敏感，对于不同的初始值，可能会产生不同结果；对于非密集型数据集，比如非凸形状的簇或者大小差别很大的簇，可能不太适用；而且k-means对噪声和孤立点数据比较敏感。

正是因为k-means有上述优点，所以它才能够经久不衰，也正是因为它有上述缺点，所以它才没有一统天下。

1. 层次聚类算法简介

层次聚类，顾名思义，就是一层一层的进行聚类，通常，我们可以把整个数据集看成一颗树，每一个数据点就是该树的叶子，而一个节点就是该节点下的叶子总数。故而，对这个数据集进行聚类分析，就相当于找到各种叶子对应的节点，这种寻找方式就是层次聚类算法。

一般的，层次聚类算法有两种：自下而上的算法和自上而下的算法。在自下而上的算法中，刚开始每个数据点（即每个叶子）都被看成一个单独的集群，然后将这些集群不断的合并，直到所有的集群都合并成一个巨型集群，这种自下而上的合并算法也叫做凝聚层次聚类算法。

而相反的，在自上而下的算法中，刚开始所有的叶子被当做一个巨型集群，然后对这个集群进行不断的分解，直到所有的集群都变成一个个单独的数据点，即巨型集群被分解成单独的叶子节点，这种自上而下的的分解算法也叫做分裂层次聚类算法。

目前应用最多的还是凝聚层次聚类算法，故而下面只对该算法进行介绍。

凝聚层次聚类算法的核心思想如上图所示，由叶子逐步合并成根节点。

凝聚法的具体计算过程可以描述为：

1，将数据集中的所有的数据点都当做一个独立的集群
2，计算两两之间的距离，找到距离最小的两个集群，并合并这两个集群为一个集群，认为距离越小，两者之间的相似度越大，越有可能是一个集群。
3，重复上面的步骤2，直到聚类的数目达到设定的条件，表示聚类过程完成。

上面的计算过程看似简单，但有一个关键的难点在于：数据点或集群之间的距离计算，这种集群间距离的计算方法有很多种，下面几种比较常见的计算方法：

1，SingleLinkage: 又叫做nearest-neighbor，其本质就是取两个集群中距离最近的两个样本的距离作为这两个集群的距离。这种方式有一个缺点，会造成一种Chaning的效果，即明明两个集群相距甚远，但由于其中个别点的距离比较近而把他们计算成距离比较近。

2，CompleteLinkage: 这种计算方式是上面的SingleLinkage算法的反面，即取两个集群中距离最远的两个点的距离作为这两个集群的距离，所以它的缺点也和上面的算法类似。

3，AverageLinkage: 由于上面两种算法都存在一定的问题，都会被离群点带到沟里去，所以本算法就考虑整体的平均值，即把两个集群中的点两两的距离都计算出来后求平均值，作为两个集群的距离。有的时候，并不是计算平均值，而是取中值，其背后的逻辑也是类似的，但取中值更加能够避免个别离群数据点对结果的干扰。

一旦我们通过上面的公式计算出来两个集群的相似度，我们就可以对这两个集群进行合并。

上面的部分内容来源于聚类系列-层次聚类 和Kmeans聚类与层次聚类, 聚类(2)——层次聚类，在此表示感谢。

2. 准备数据集

下面我们自己构建一个数据集，我们定义了一个函数prepare_dataset()专门用来准备数据集，此处的数据集是分布比较特殊的样本点，如下为这个准备数据集的函数的代码

# 准备数据集
def prepare_dataset(sample_num,data_type,noise_amplitude):
    '''prepare special kinds of dataset,
        params:
        sample_num: sample numbers in this prepared dataset,
        data_type: must be one of ['rose','spiral','hypotrochoid'],
        noise_amplitude: how much noise add to the dataset. 
            normally, range from 0-0.5
        return:
        the prepared dataset in numpy.ndarray format
    '''
    def add_noise(x, y, amplitude):
        X = np.concatenate((x, y))
        X += amplitude * np.random.randn(2, X.shape[1])
        return X.T

    def get_spiral(t, noise_amplitude=0.5):
        r = t
        x = r * np.cos(t)
        y = r * np.sin(t)
        return add_noise(x, y, noise_amplitude)

    def get_rose(t, noise_amplitude=0.02):
        k = 5       
        r = np.cos(k*t) + 0.25 
        x = r * np.cos(t)
        y = r * np.sin(t)
        return add_noise(x, y, noise_amplitude)

    def get_hypotrochoid(t, noise_amplitude=0):
        a, b, h = 10.0, 2.0, 4.0
        x = (a - b) * np.cos(t) + h * np.cos((a - b) / b * t) 
        y = (a - b) * np.sin(t) - h * np.sin((a - b) / b * t) 
        return add_noise(x, y, 0)

    X=2.5*np.pi*(1+2*np.random.rand(1,sample_num))
    if data_type=='hypotrochoid':
        return get_hypotrochoid(X,noise_amplitude)
    elif data_type=='spiral':
        return get_spiral(X,noise_amplitude)
    else:
        return get_rose(X,noise_amplitude)

下面我们用这个函数准备三个数据集，分别是spiral_dataset， rose_dataset, hypo_dataset，其代码为：

spiral_dataset=prepare_dataset(600,'spiral',0.5)
rose_dataset=prepare_dataset(600,'rose',0.02)
hypo_dataset=prepare_dataset(600,'hypotrochoid',0)

然后我们用前面文章中提到的函数visual_2D_dataset_dist()可以查看无标签数据集的分布情况，如下图所示为这三个数据集的二维分布情况。

########################小**********结###############################

1，此处我们自己创建了一些具有特殊分布的数据集，想用这些特殊分布的数据集来考察凝聚层次聚类算法的优虐。

2，数据集的产生是通过一些数学函数来实现的，这些函数在网上可以找到成熟的数学公式。

#################################################################

3. 使用凝聚层次聚类算法构建模型

为了更好地比较模型在不同数据集上的效果，我们将模型的构建函数和模型在不同数据集上的表现都整合到一个函数中，该函数名称为：perform_plot_clustering()，在以后只需要调用该函数就可以分别对这三个数据集进行训练和绘制训练后效果图。如下为代码：

from sklearn.cluster import AgglomerativeClustering
from sklearn.neighbors import kneighbors_graph

# 建立一个函数，用来构建聚类模型，并绘图展示聚类效果
def perform_plot_clustering(dataset,none_cluster_num=3,kneighbors_num=10):
    assert dataset.shape[1]==2,'only support dataset with 2 features'

    # 构建凝聚层次聚类模型，并用数据集对其进行训练
    none_model=AgglomerativeClustering(n_clusters=none_cluster_num)
    none_model.fit(dataset) # 构建无connectivity的model

    connectivity = kneighbors_graph(dataset, kneighbors_num, 
                                    include_self=False)
    conn_model=AgglomerativeClustering(n_clusters=kneighbors_num,
                                       connectivity=connectivity)
    conn_model.fit(dataset)# 构建kneighbors_graph connectivity的model

    def visual_2D_dataset(plt,dataset_X,dataset_y):
        '''将二维数据集dataset_X和对应的类别dataset_y显示在散点图中'''
        assert dataset_X.shape[1]==2,'only support dataset with 2 features'
        classes=list(set(dataset_y)) 
        markers=['.',',','o','v','^','<','>','1','2','3','4','8'
                 ,'s','p','*','h','H','+','x','D','d','|']
        # colors=['b','c','g','k','m','w','r','y']
        colors=['tab:blue', 'tab:orange', 'tab:green', 'tab:red', 'tab:purple', 
                'tab:brown', 'tab:pink', 'tab:gray', 'tab:olive', 'tab:cyan']
        for class_id in classes:
            one_class=np.array([feature for (feature,label) in 
                       zip(dataset_X,dataset_y) if label==class_id])
            plt.scatter(one_class[:,0],one_class[:,1],marker=markers[class_id%len(markers)],
                        c=colors[class_id%len(colors)],label='class_'+str(class_id))
        plt.legend()

    # 以下是绘图
    def plot_model_graph(plt,model,title):
        labels=model.labels_
        # 将数据集绘制到图表中
        visual_2D_dataset(plt,dataset,labels)
        plt.title(title)
        plt.xlabel('feature_0')
        plt.ylabel('feature_1')
        return plt

    plt.figure(12,figsize=(25,10))
    plt.subplot(121)
    plot_model_graph(plt,none_model,'none_connectivity')

    plt.subplot(122)
    plot_model_graph(plt,conn_model,'kneighbors_connectivity')
    plt.show()

使用这个函数来查看凝聚层次聚类算法在这三个数据集上的效果，可以得到如下结果图：

从上面这三幅图中可以看出，在没有使用kneighbors connectivity的图中，凝聚层次算法倾向于把位置相近的一些点聚集到一个类别，而不考虑这些数据点之间是否连续，是否有数据之间的连接。而用kneighbors作connectivity之后，算法倾向于把有连接的一些数据划分为一类，而没有连接的划分为另外一类，这样的划分方法更具有逻辑性。

也有人会问，是不是因为在第一幅图中我们把类别设置为3类，所以算法在划分时将很多距离较远的没有连接的样本划分为同一个类了？那么我们可以试一下同样的将none_connectivity的类别设置为10，再对比以下两者的效果，如下为结果图：

########################小**********结###############################

1，凝聚层次聚类算法的构建和训练比较简单，和其他聚类算法没有太大区别，直接构建AgglomerativeClustering对象并训练即可。

2，在构建凝聚层次聚类算法时，有一个connectivity的参数是选择的难点，此处我比较了不使用connectivity参数和使用kneighbors connectivity参数的区别，发现两者在聚类时有一些不同。

3，在不使用connectivity参数时，凝聚层次算法倾向于把位置相近的一些点聚集到一个类别，而不考虑这些数据点之间是否连续，是否有数据之间的连接。

4，而用kneighbors作connectivity之后，算法倾向于把有连接的一些数据划分为一类，而没有连接的划分为另外一类。在实际项目中，应该怎么使用这个connectivity参数，应该根据具体的数据集特性来选择。

#################################################################

注：本部分代码已经全部上传到（我的github）上，欢迎下载。

参考资料:

1, Python机器学习经典实例，Prateek Joshi著，陶俊杰，陈小莉译