精华内容
下载资源
问答
  • 层次聚类算法原理

    千次阅读 2018-09-21 10:15:11
    层次聚类算法原理及实现Hierarchical Clustering 2016年4月19日 BY 蓝鲸 5 COMMENTS 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。...

    层次聚类算法的原理及实现Hierarchical Clustering

    2016年4月19日 BY 蓝鲸 5 COMMENTS

    层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法,本篇文章介绍合并方法。

    hierarchicalcluster

    层次聚类的合并算法

    层次聚类的合并算法通过计算两类数据点间的相似性,对所有数据点中最为相似的两个数据点进行组合,并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性,距离越小,相似度越高。并将距离最近的两个数据点或类别进行组合,生成聚类树。

    欧几里德距离矩阵

    层次聚类使用欧式距离来计算不同类别数据点间的距离(相似度)。我们在前面的几篇文章中都曾经介绍过欧氏距离的计算方法,本篇文章将通过创建一个欧式距离矩阵来计算和对比不同类别数据点间的距离,并对距离值最小的数据点进行组合。以下是欧式距离的计算公式。

    Euclidean distance

    以下为示例数据,我们通过欧氏距离计算下面A到G的欧式距离矩阵,并通过合并的方法将相似度最高的数据点进行组合,并创建聚类树。

    数据

    创建欧式距离矩阵的方法很简单,将每个类别的数据点分别与A-G中的每个数据点计算距离值,其中A—>B表示数据点A到数据点B的距离,B—>A则代表数据点B到数据点A的距离。这两个距离值是相同的,因此欧式距离矩阵呈对角线对称(绿色部分和蓝色部分)。其中对角线的0值是数据点与自己的距离值。我们将所有数据点间的距离结果进行对比,选择其中距离最近的两个数据点进行组合,并迭代这一过程。下图显示了欧式矩阵的逻辑和计算方法。

    欧式距离矩阵1

    数据点之间的距离    

    对于示例中的数据点,我们通过计算获得了下面的欧式距离矩阵。其中数据点B到数据点C的距离在所有的距离值中最小,为1.00。以下为数据点间距离值的计算公式。

    BtoA

    经过计算数据点B和数据点C与其他数据点相比有最高的相似度。因此,我们将数据点B和数据点C进行组合。并再次计算其他数据点间的距离。

    距离矩阵1

    数据点与组合数据点间的距离

    将数据点B与数据点C进行组合后,重新计算各类别数据点间的距离矩阵。数据点间的距离计算方式与之前的方法一样。这里需要说明的是组合数据点(B,C)与其他数据点间的计算方法。当我们计算(B,C)到A的距离时,需要分别计算B到A和C到A的距离均值。

    BCtoA

    经过计算数据点D到数据点E的距离在所有的距离值中最小,为1.20。这表示在当前的所有数据点中(包含组合数据点),D和E的相似度最高。因此我们将数据点D和数据点E进行组合。并再次计算其他数据点间的距离。

    距离矩阵2

    后面的工作就是不断的重复计算数据点与数据点,数据点与组合数据点间的距离。这个步骤应该由程序来完成。这里由于数据量较小,我们手工计算并列出每一步的距离计算和数据点组合的结果。

    这一步中,数据点A和数据点F的距离值在所有距离值中最小,因此我们将A和F进行组合,生成组合数据点(A,F)。

    距离矩阵3

    到此为止除了数据点G以外,其他的数据点都已经根据距离值(相似度)进行了组合。聚类树的最底层已经完成。下面我们将继续计算组合数据点间的距离,并对相似度最高的组合数据点进行合并。

    两个组合数据点间的距离

    计算两个组合数据点间距离的方法有三种,分别为Single Linkage,Complete Linkage和Average Linkage。在开始计算之前,我们先来介绍下这三种计算方法以及各自的优缺点。

    Single Linkage

    Single Linkage的计算方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

    Complete Linkage

    Complete Linkage的计算方法与Single Linkage相反,将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反,两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

    Average Linkage

    Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大,但结果比前两种方法更合理。

    我们使用Average Linkage计算组合数据点间的距离。下面是计算组合数据点(A,F)到(B,C)的距离,这里分别计算了(A,F)和(B,C)两两间距离的均值。

     

    AFtoBC

    通过计算及对比不同组合数据点间间的距离。(A,F)到(B,C)的距离在所有组合数据点间最小,为13.25。说明(A,F)到(B,C)相似度最高。因此,将(A,F)到(B,C)组合为(A,F,B,C)。

    距离矩阵4

    使用与之前相同的方法计算出组合数据点(D,E)和G的距离在目前所有组合数据点中最小。为34.70。将(D,E)和G组合为(D,E,G)。

    距离矩阵5

    最终,通过计算和合并,我们获得了两个组合数据点(A,F,B,C)和(D,E,G)。这也是聚类树的最顶层的两个数据点。下面,我们按之前的计算步骤来构建聚类树。

    距离矩阵6

     

    层次聚类树状图

    将前面的每一步的计算结果以树状图的形式展现出来就是层次聚类树。最底层是原始A到G的7个数据点。依照7个数据点间的相似度组合为聚类树的第二层(A,F),(B,C),(D,E)和G。以此类推生成完整的层次聚类树状图。以下为简单的示意图。

    Hierarchical Clustering



    Read more: http://bluewhale.cc/2016-04-19/hierarchical-clustering.html#ixzz5RhN1UuTH

    展开全文
  • 从而形成树形的聚类结构,层次聚类一般有两种划分策略:自底向上的聚合(agglomerative)策略和自顶向下的分拆(divisive)策略,本文对层次聚类算法原理进行了详细总结。目录1. 层次聚类算法原理2. 簇间相似度的计算...

    层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据,从而形成树形的聚类结构,层次聚类一般有两种划分策略:自底向上的聚合(agglomerative)策略和自顶向下的分拆(divisive)策略,本文对层次聚类算法原理进行了详细总结。

    目录


    1. 层次聚类算法原理

    2. 簇间相似度的计算方法

    3. 层次聚类算法的复杂度计算

    4. 层次聚类算法的优化方法

    5. 层次聚类算法的优缺点

    1. 层次聚类算法原理

    层次聚类根据划分策略包括聚合层次聚类和拆分层次聚类,由于前者较后者有更广泛的应用且算法思想一致,因此本节重点介绍聚合层次聚类算法。

    聚合层次聚类算法假设每个样本点都是单独的簇类,然后在算法运行的每一次迭代中找出相似度较高的簇类进行合并,该过程不断重复,直到达到预设的簇类个数K或只有一个簇类。

    聚合层次聚类的基本思想:

    1)计算数据集的相似矩阵;

    2)假设每个样本点为一个簇类;

    3)循环:合并相似度最高的两个簇类,然后更新相似矩阵;

    4)当簇类个数为1时,循环终止;

    为了更好的理解,我们对算法进行图示说明,假设我们有6个样本点{A,B,C,D,E,F}。

    第一步:我们假设每个样本点都为一个簇类(如下图),计算每个簇类间的相似度,得到相似矩阵;

    ed1fdc827c091ce986ec36564dcba8a8.png

    第二步:若B和C的相似度最高,合并簇类B和C为一个簇类。现在我们还有五个簇类,分别为A,BC,D,E,F。

    25f2e4ea6f8895d0b55a62a2cccbed8b.png

    第三步:更新簇类间的相似矩阵,相似矩阵的大小为5行5列;若簇类BC和D的相似度最高,合并簇类BC和D为一个簇类。现在我们还有四个簇类,分别为A,BCD,E,F。

    605724e85c431a11f84ffe3ca40f0d66.png

    第四步:更新簇类间的相似矩阵,相似矩阵的大小为4行4列;若簇类E和F的相似度最高,合并簇类E和F为一个簇类。现在我们还有3个簇类,分别为A,BCD,EF。

    b808a1dd8aaed01e6ae6d8678f233da9.png

    第五步:重复第四步,簇类BCD和簇类EF的相似度最高,合并该两个簇类;现在我们还有2个簇类,分别为A,BCDEF。

    2399c91e0d101637e318026b49ec69a8.png

    第六步:最后合并簇类A和BCDEF为一个簇类,层次聚类算法结束。

    de1f0ebd48de551275f6391c22119850.png

    树状图是类似树(tree-like)的图表,记录了簇类聚合和拆分的顺序。我们根据上面的步骤,使用树状图对聚合层次聚类算法进行可视化:

    95fb32e543d93da49e6c691a7fbb50f9.png

    也可用下面的图记录簇类聚合和拆分的顺序:

    82f08cb6a9a10548ce0e27e24329cd19.png

    拆分层次聚类算法假设所有数据集归为一类,然后在算法运行的每一次迭代中拆分相似度最低的样本,该过程不断重复,最终每个样本对应一个簇类。简单点说,拆分层次聚类是聚合层次聚类的反向算法,读者可通过树状图去加强理解,一个是自底向上的划分,一个是自顶向下的划分。

    2. 簇间相似度的计算方法

    由上节知道,合并或拆分层次聚类算法都是基于簇间相似度进行的,每个簇类包含了一个或多个样本点,通常用距离评价簇间或样本间的相似度,即距离越小相似度越高,距离越大相似度越低。因此我们首先假设样本间的距离为:dist(Pi,Pj),其中Pi,Pj为任意两个样本,下面介绍常用的簇间相似度计算方法

    • 最小距离

    • 最大距离

    • 平均距离

    • 中心距离

    • 最小方差法

    最小距离:也称为单链接算法(single linkage algorithm),含义为簇类C1和C2的距离由该两个簇的最近样本决定,数学表达式写为:

    3f65e4e13098d9c83aa344847ab9e877.png

    算法也可用下图表示,其中红色线表示簇类C1和C2的距离。

    6057e01d79cca147f56a376ab4acc385.png

    优点

    只要两个簇类的间隔不是很小,单链接算法可以很好的分离非椭圆形状的样本分布。

    如下图的两个聚类例子,其中不同颜色表示不同的簇类:

    371276d47d1b4e7216f622f22097a7b8.png

    例1

    1f3429a9ffc5806b651b0c5fabc1643a.png

    例2

    缺点:

    单链接算法不能很好的分离簇类间含有噪声的数据集,如下图:

    b7f9226248667881c74d3a213df7c7b0.png

    最大距离:也称为全链接算法(complete linkage algorithm),含义为簇类C1和C2的距离由该两个簇的最远样本决定,与单链接算法的含义相反,数学表达式写为:

    7437db770172ef4fa19be399791f14b1.png

    算法也可用如下图表示,其中红色线表示簇类C1和C2的距离。

    6af32c0bf2ff2d7d2d94a170b579daa9.png

    优点:

    全链接算法可以很好的分离簇类间含有噪声的数据集,如下图:

    e864358b36b776b68c70c95b47f03441.png

    缺点:

    全链接算法对球形数据集的分离会产生偏差,如下图:

    868bcb8ce92025cafc05beb1f0397831.png

    平均距离:也称为均链接算法(average-linkage algorithm),含义为簇类C1C2的距离等于两个簇类所有样本对的距离平均,数学表达式为:

    55c2f60bd633485bbf5da896c139b06d.png

    其中|C1|,|C2|分别表示簇类的样本个数。

    均链接算法也可用如下图表示:

    3932129ecbd8e10effcfeaa0ca314a47.png

    所有连线的距离求和平均即为簇类C1C2的距离。

    优点:

    均链接算法可以很好的分离簇类间有噪声的数据集。

    缺点:

    均链接算法对球形数据集的分离会产生偏差。

    中心距离:簇类C1C2的距离等于该两个簇类中心间的距离,如下图:

    752e37f8c8667a8163018981535222af.png

    其中红色点表示簇类的中心,红色线表示簇类C1和C2的距离。这种计算簇间距离的方法非常少用,个人不建议使用这一算法。

    离差平方和:簇类C1C2的距离等于两个簇类所有样本对距离平方和的平均,与均链接算法很相似,数学表达式为:

    9263af86415a741726d70e6e1ccaa322.png

    优点:

    离差平方和可以很好的分离簇间有噪声的数据集。

    缺点:

    离差平方和对球形数据集的分离会产生偏差。

    我们已经知道了如何通过样本间的距离来评估簇间的距离,本节只剩下最后一个问题了,如何计算样本间的距离,假设样本是n维,常用的距离计算方法有:

    1)欧拉距离(Euclidean distance):

    7ef80983aeccf77138cf6426bdead3ec.png

    2)平方欧式距离(Squared Euclidean distance):

    3aa12b09cd73825a5940b61bfeea93b9.png

    3)曼哈顿距离(Manhattan distance):

    b8f95d7686d4e0aebdd784c18c4643ee.png

    4)切比雪夫距离(Chebyshev distance):

    f6152aad57b8dc8bb9d6b1e663d654ef.png

    5)马氏距离(Mahalanobis distance):

    ae14d91da23d67ee70ac2131e00724a6.png

    其中S为协方差矩阵。

    对于文本或非数值型的数据,我们常用汉明距离(Hamming distance)和编辑距离(Levenshtein distance)表示样本间的距离。

    不同的距离度量会影响簇类的形状,因为样本距离因距离度量的不同而不同,如点(1.1)和(0,0)的曼哈顿距离是2,欧式距离是sqrt(2),切比雪夫距离是1。

    3. 层次聚类算法的复杂度计算

    空间复杂度:当样本点数目很大时,层次聚类需要较大的空间存储相似矩阵,相似矩阵的大小是样本个数的平方,因此空间复杂度是n的平方阶次,即空间复杂度=O(n^2)

    间复杂度:层次聚类算法需要进行n次迭代,每次迭代都需要更新并存储相似矩阵,所以时间复杂度是样本个数n的立方阶次,即时间复杂度=O(n^3)

    4.层次聚类算法的优化方法

    上节介绍数据量较大时,层次聚类算法的空间复杂度和时间复杂度较高,我们可以通过连通性约束(connectivity constraint)降低算法复杂度,甚至提高聚类结果。

    连通性约束是通过连通性矩阵(connectivity matrix)实现的,连通性矩阵的元素只有10两种结果,1表示两个样本是连通的,0表示两个样本不连通,我们只对连通性的样本进行距离计算并融合,这一过程大大降低了计算量,常采用sklearn.neighbors.kneighbors_graph来构建连接矩阵。

    我们构建了容量为15000的瑞士卷(swiss roll dataset)数据集:

    # 生成瑞士卷数据集,容量为15000n_samples = 15000noise = 0.05X, _ = make_swiss_roll(n_samples, noise)# 减小瑞士卷的厚度X[:, 1] *= .5

    用离差平方和的层次聚类算法建模,可视化聚类结果并输出算法运行时间。

    print("Compute unstructured hierarchical clustering...")st = time.time()ward = AgglomerativeClustering(n_clusters=6, linkage='ward').fit(X)elapsed_time = time.time() - stlabel = ward.labels_# 运行时间print("Elapsed time: %.2fs" % elapsed_time)print("Number of points: %i" % label.size)# ############################################################################## 可视化结果fig = plt.figure()ax = p3.Axes3D(fig)ax.view_init(7, -80)for l in np.unique(label):ax.scatter(X[label == l, 0], X[label == l, 1], X[label == l, 2],color=plt.cm.jet(np.float(l) / np.max(label + 1)),s=20, edgecolor='k')plt.title('Without connectivity constraints (time %.2fs)' % elapsed_time)

    结果:

    a53f9488dfa61f0f41859f438d2b7a82.png

    我们在构建层次聚类算法模型前,先定义数据集的连通矩阵

    # 定义不包含样本点在内的10个最近邻的连通样本点from sklearn.neighbors import kneighbors_graphconnectivity = kneighbors_graph(X, n_neighbors=10, include_self=False)

    用离差平方和的层次聚类算法建模,可视化聚类结果并输出算法运行时间:

    print("Compute structured hierarchical clustering...")st = time.time()ward = AgglomerativeClustering(n_clusters=6, connectivity=connectivity,linkage='ward').fit(X)elapsed_time = time.time() - stlabel = ward.labels_print("Elapsed time: %.2fs" % elapsed_time)print("Number of points: %i" % label.size)# ############################################################################## Plot resultfig = plt.figure()ax = p3.Axes3D(fig)ax.view_init(7, -80)for l in np.unique(label):ax.scatter(X[label == l, 0], X[label == l, 1], X[label == l, 2],color=plt.cm.jet(float(l) / np.max(label + 1)),s=20, edgecolor='k')plt.title('With connectivity constraints (time %.2fs)' % elapsed_time)plt.show()

    结果:

    99396b0cfa0c012c468e2b998ff12586.png

    由上面例子可知:大数据量的情况下,增加连通性约束矩阵可以降低算法的运行时间,若只关注数据集的局部信息,连通性约束也能提高算法性能。

    6. 层次聚类算法的优缺点

    优点:

    算法简单,易于理解

    树状图包含了整个算法过程的信息;

    缺点:

    选择合适的距离度量与簇类的链接准则较难;

    高的时间复杂度和空间复杂度;

    参考:

    https://towardsdatascience.com

    https://scikit-learn.org/stable/

    推荐阅读

    k-means聚类算法原理总结

    聚类 | 超详细的性能度量和相似度方法总结

    8137f6e6e1fb3a9203e3290f18da52c6.png

    展开全文
  • 层次聚类算法原理及实现

    万次阅读 2017-12-21 17:29:32
    一、聚类算法介绍  层次法聚类和点分配法聚类。 1.1 点、空间和距离 点集是一种适合于聚类的数据集,每个点都是某空间下的对象。一般意义上,空间只是点的全集,也就是说数据集中的点从该集合中抽样而成。特别...

    聚类

             聚类是对点集进行考察并按照某种距离测度将他们聚成多个“簇”的过程。聚类的目标是使得同一簇内的点之间的距离较短,而不同簇中点之间的距离较大。

    一、聚类算法介绍

         层次法聚类和点分配法聚类。

    1.1     点、空间和距离

    点集是一种适合于聚类的数据集,每个点都是某空间下的对象。一般意义上,空间只是点的全集,也就是说数据集中的点从该集合中抽样而成。特别地,欧式空间下的点就是实数向量。向量的长度就是空间的维度数,而向量的分量通常称为所表示点的坐标(coordinate)

    能够进行聚类的所有空间下都有一个距离测度,即给出空间下任意两点的距离。一般的欧氏距离(点的坐标在各个维度上差值的平方和的算术平方根)可以作为所有欧式空间下的距离测度。

    现代聚类问题可能并不这么简单。他们可能牵涉非常高维的欧式空间或者根本不在欧式空间下聚类。比如,基于文档间高频区分词的共现情况来依据主题对文档聚类。而按照电影爱好者所喜欢的电影类别对他们进行聚类。

    1.2     聚类策略

    按照聚类算法使用的两种不同的基本策略,可以将聚类算法分成两类。

    1)   层次(hierarchical)或凝聚式(agglomerative)算法。

    这类算法一开始将每个点都看成簇。簇与簇之间按照接近度(closeness)来组合,接近度可以按照“接近”的不同含义采用不同的定义。当进一步的组合导致多个原因之下的非期望结果时,上述组合过程结束。比如停止条件为:达到预先给定的簇数目,或者使用簇的紧密度测度方法,一旦两个小簇组合之后得到簇内的点分散的区域较大就停止簇的构建。

    2)   点分配过程算法。按照某个顺序依次考虑每个点,并将它分配到最适合的簇中。该过程通常有一个短暂的初始簇估计阶段。一些变形算法允许临时的簇合并或分裂的过程,或者当点为离群点时允许不将该点分配到任何簇中。

    聚类算法也可以使用如下方式分类:

    1)   欧式空间下,我们可以将点集合概括为其质心,即点的平均。而在非欧式空间下根本没有质心的概念,因此需要其他的簇概括方法

    2)   算法是否假设数据足够小的能够放入内存?或者说数据是否必须主要存放在二次存储器?由于不能将所有簇的所有点都同时放入内存,所以我们将簇的概括表示存放在内存中也是必要的。

    1.3     维数灾难

    “灾难”的一个体现是,在高维空间下,几乎所有点对之间的距离都差不多相等。另一个表现是,几乎任意的两个向量之间都近似正交。

    1.        高维空间下的距离分布

    一个d维欧式空间,假设在一个单位立方体内随机选择n个点,每个点可以表示成[x1,x2,…,xd],其每个xi都是01之间。假定d非常大,两个随机点[x1,x2,…,xd][y1,y2,…,yd]之间的欧式距离为

                                                                                                                        

      上述基于随机数据的论证结果表明,在这么多所有距离近似相等的点对之中发现聚类是很难的一件事。

    2.        向量之间的夹角

    d维空间的随机点ABC,其中d很大。AC可以在任意位置,而B处于坐标原点。那么夹角ABC的余弦为:

     

                                                                                                     

    d不断增长时,分母会随d线性增长,但是分子却是随机值之和,可能为正也可能为负。分子期望为0,分子最大值为 。所以对于很大的d而言,任意两个向量的夹角余弦值几乎肯定接近为0,即夹角近似度等于90度。

    推论为:如果dAB = d1, dBC=d2,dAC≈ 。

    二、层次聚类

    首先考虑欧式空间下的层次聚类。该算法仅可用于规模相对较小的数据集。层次聚类用于非欧式空间时,还有一些与层次聚类相关的额外问题需要考虑。因此,当不存在簇质心或者说簇平均点时,可以考虑采用簇中心点(clustroid)来表示一个簇。

    2.1     欧式空间下的层次聚类

    首先,每个点看作一个簇,通过不断的合并小簇而形成大簇。我们需要提前确定

    (1)         簇如何表示?

    (2)         如何选择哪两个簇进行合并?

    (3)         簇合并何时结束?

    对于欧式空间,(1)通过簇质心或者簇内平均点来表示簇。对于单点的簇,该点就是簇质心。可以初始化簇数目为欧式空间点的数目Cnumber=n。簇之间的距离为质心之间的欧式距离,

    2)选择具有最短距离(或者其他方式)的两个簇进行合并。

    例如,有如下12个点,首先我们将每一个点看做一个簇。

                                                               

    point.txt文件

    4 10
    4 8
    7 10
    6 8
    3 4
    2 2
    5 2
    9 3
    10 5
    11 4
    12 3
    12 6

    1. #include <iostream>  
    2. #include <vector>  
    3. #include <algorithm>  
    4. #include <fstream>  
    5. using namespace std;  
    6. const int iniClusNum = 12;  
    7. const int stopNum = 3;  
    8.   
    9. class Point  
    10. {  
    11. public:  
    12.     double x;  
    13.     double y;  
    14.     int NumPBelong;  
    15.     Point()  
    16.     {  
    17.         x=0;  
    18.         y=0;  
    19.         NumPBelong = -1;  
    20.     }  
    21.     Point(double x1, double y1, int f=-1):x(x1),y(y1),NumPBelong(f){}  
    22.     const Point& operator=(const Point& p)  
    23.     {  
    24.         x = p.x;  
    25.         y=p.y;  
    26.         NumPBelong = p.NumPBelong;  
    27.         return *this;  
    28.     }  
    29. };  
    30.   
    31. class ManagerP  
    32. {  
    33. public:  
    34.     double getDistance(const Point& p1, const Point& p2)  
    35.     {  
    36.         return sqrt(pow((p1.x-p2.x),2)+pow((p1.y-p2.y),2));  
    37.     }  
    38.     Point getMean(const Point& p1, const Point& p2)  
    39.     {  
    40.         Point p;  
    41.         p.x = (p1.x+p2.x)/2;  
    42.         p.y=(p1.y+p2.y)/2;  
    43.         return p;  
    44.     }  
    45. };  
    46. class ManagerC  
    47. {  
    48. public:  
    49.     Point Cluster[iniClusNum];  
    50.     vector<int> ClusterLast[iniClusNum];  
    51.     bool isIndexClose[iniClusNum];  
    52.     bool isIndexClose2[iniClusNum];  
    53.     void initCluster()//use txt to init, import txt  
    54.     {  
    55.         ifstream  myfile ( "point.txt" ) ;  
    56.         if  ( !myfile )   
    57.         {   
    58.             cout << "cannot open file." ;   return  ;   
    59.         }  
    60.   
    61.         Point p;  
    62.         int x,y;    
    63.         int i=0;  
    64.         while(!myfile.eof())  
    65.         {  
    66.             myfile>>x>>y;  
    67.             p.x=x;  
    68.             p.y=y;  
    69.             Cluster[i]=p;  
    70.             i++;  
    71.         }  
    72.         myfile.close();  
    73.     }  
    74.     void initIndexClose()  
    75.     {  
    76.             for(int i=0;i<iniClusNum;i++)  
    77.             {  
    78.                 isIndexClose[i]=false;  
    79.                 isIndexClose2[i]=false;  
    80.             }  
    81.     }  
    82.     void print()  
    83.     {  
    84.         for(int i =0;i<iniClusNum;i++)  
    85.         {  
    86.             if(ClusterLast[i].empty())  
    87.             {  
    88.                 continue;  
    89.             }  
    90.             cout<<"cluster "<<i+1<<endl;  
    91.             vector<int>::iterator ite=ClusterLast[i].begin();  
    92.             for(;ite!= ClusterLast[i].end();ite++)  
    93.             {  
    94.                 cout<<*ite<<"\t";  
    95.             }  
    96.             cout<<endl;  
    97.   
    98.         }  
    99.         cout<<endl;  
    100.     }  
    101.         void ClusterAlgo()//use minheap to realize, to optimize  
    102.     {  
    103.   
    104.         int ClustNum = iniClusNum;  
    105.         int clus_index =0;  
    106.         while(ClustNum>stopNum)  
    107.         {  
    108.   
    109.             double min=INT_MAX;  
    110.             int x=-1,y=-1;  
    111.             ManagerP mp;  
    112.             for(int i=0;i<iniClusNum;i++)  
    113.             {  
    114.                 if(isIndexClose[i])  
    115.                 {  
    116.                     continue;  
    117.                 }  
    118.                 for(int j=i+1;j<iniClusNum;j++)  
    119.                 {  
    120.                     if(isIndexClose[j])  
    121.                     {  
    122.                         continue;  
    123.                     }  
    124.   
    125.                     double new_d = mp.getDistance(Cluster[i],Cluster[j]);  
    126.                     if(new_d < min)  
    127.                     {  
    128.                         min = new_d;  
    129.                         x=i;y=j;  
    130.   
    131.                     }  
    132.                 }  
    133.             }  
    134.             if(x==-1 || y==-1)  
    135.             {  
    136.                 break;  
    137.             }  
    138.   
    139.             Point p = mp.getMean(Cluster[x],Cluster[y]);  
    140.             //x<y    store the result  
    141.             if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong==-1)  
    142.             {  
    143.                 cout<<"a0"<<endl;  
    144.                 ClusterLast[clus_index].push_back(x);//xchange to p, y close  
    145.                 ClusterLast[clus_index].push_back(y);  
    146.                 p.NumPBelong = clus_index;  
    147.                 isIndexClose[y]=true;//y is closed  
    148.                 Cluster[x]=p;//new p is open  
    149.                 isIndexClose[x]=false;  
    150.                 isIndexClose2[x]=true;  
    151.                 isIndexClose2[y]=true;  
    152.                 clus_index++;  
    153.   
    154.             }  
    155.             else if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong!=-1)//already exists one cluster  
    156.             {  
    157.                 cout<<"a1"<<endl;  
    158.                 ClusterLast[Cluster[y].NumPBelong].push_back(x);  
    159.                 isIndexClose[x]=true;//x is closed  
    160.                 p.NumPBelong = Cluster[y].NumPBelong;  
    161.                 Cluster[y]=p;//new p is open  
    162.                 isIndexClose2[x]=true;  
    163.             }  
    164.             else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong==-1)  
    165.             {  
    166.                 cout<<"a2"<<endl;  
    167.                 ClusterLast[Cluster[x].NumPBelong].push_back(y);  
    168.                 isIndexClose[y]=true;//y is closed  
    169.                 p.NumPBelong = Cluster[x].NumPBelong;  
    170.                 Cluster[x]=p;//new p is open  
    171.                 isIndexClose2[y]=true;  
    172.             }  
    173.             else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong!=-1)//both are clusteroid  
    174.             {  
    175.                 cout<<"a3"<<endl;  
    176.                 vector<int>::iterator ite = ClusterLast[Cluster[y].NumPBelong].begin();//put y's node in x  
    177.                 for(;ite!=ClusterLast[Cluster[y].NumPBelong].end();ite++)  
    178.                 {  
    179.                     ClusterLast[Cluster[x].NumPBelong].push_back(*ite);  
    180.                 }  
    181.                 ClusterLast[Cluster[y].NumPBelong].clear();  
    182.                 isIndexClose[y]=true;//y is closed  
    183.                 p.NumPBelong = Cluster[x].NumPBelong;  
    184.                 Cluster[x]=p;//new p is open  
    185.                               
    186.             }  
    187.             ClustNum--;  
    188.         }  
    189.         int total_size =0;  
    190.         for(int i=0;i<stopNum;i++)  
    191.         {  
    192.             total_size+=ClusterLast[i].size();  
    193.         }  
    194.         if(total_size<iniClusNum)  
    195.         {  
    196.             int j=0;  
    197.             for(int i=0;i<iniClusNum;i++)  
    198.             {  
    199.                 if(isIndexClose2[i]==false)  
    200.                 {  
    201.                     ClusterLast[stopNum-1-j].push_back(i);  
    202.                     j++;  
    203.                 }  
    204.             }  
    205.   
    206.         }  
    207.     }  
    208.   
    209. };  
    210. int main()  
    211. {  
    212.     ManagerC M;  
    213.     M.initCluster();  
    214.     M.initIndexClose();  
    215.     M.ClusterAlgo();  
    216.     M.print();  
    217.   
    218.     system("pause");  
    219. }  
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <fstream>
    using namespace std;
    const int iniClusNum = 12;
    const int stopNum = 3;
    
    class Point
    {
    public:
    	double x;
    	double y;
    	int NumPBelong;
    	Point()
    	{
    		x=0;
    		y=0;
    		NumPBelong = -1;
    	}
    	Point(double x1, double y1, int f=-1):x(x1),y(y1),NumPBelong(f){}
    	const Point& operator=(const Point& p)
    	{
    		x = p.x;
    		y=p.y;
    		NumPBelong = p.NumPBelong;
    		return *this;
    	}
    };
    
    class ManagerP
    {
    public:
    	double getDistance(const Point& p1, const Point& p2)
    	{
    		return sqrt(pow((p1.x-p2.x),2)+pow((p1.y-p2.y),2));
    	}
    	Point getMean(const Point& p1, const Point& p2)
    	{
    		Point p;
    		p.x = (p1.x+p2.x)/2;
    		p.y=(p1.y+p2.y)/2;
    		return p;
    	}
    };
    class ManagerC
    {
    public:
    	Point Cluster[iniClusNum];
    	vector<int> ClusterLast[iniClusNum];
    	bool isIndexClose[iniClusNum];
    	bool isIndexClose2[iniClusNum];
    	void initCluster()//use txt to init, import txt
    	{
    		ifstream  myfile ( "point.txt" ) ;
    		if  ( !myfile ) 
    		{ 
    			cout << "cannot open file." ;   return  ; 
    		}
    
    		Point p;
    		int x,y;  
    		int i=0;
    		while(!myfile.eof())
    		{
    			myfile>>x>>y;
    			p.x=x;
    			p.y=y;
    			Cluster[i]=p;
    			i++;
    		}
    		myfile.close();
    	}
    	void initIndexClose()
    	{
    			for(int i=0;i<iniClusNum;i++)
    			{
    				isIndexClose[i]=false;
    				isIndexClose2[i]=false;
    			}
    	}
    	void print()
    	{
    		for(int i =0;i<iniClusNum;i++)
    		{
    			if(ClusterLast[i].empty())
    			{
    				continue;
    			}
    			cout<<"cluster "<<i+1<<endl;
    			vector<int>::iterator ite=ClusterLast[i].begin();
    			for(;ite!= ClusterLast[i].end();ite++)
    			{
    				cout<<*ite<<"\t";
    			}
    			cout<<endl;
    
    		}
    		cout<<endl;
    	}
    		void ClusterAlgo()//use minheap to realize, to optimize
    	{
    
    		int ClustNum = iniClusNum;
    		int clus_index =0;
    		while(ClustNum>stopNum)
    		{
    
    			double min=INT_MAX;
    			int x=-1,y=-1;
    			ManagerP mp;
    			for(int i=0;i<iniClusNum;i++)
    			{
    				if(isIndexClose[i])
    				{
    					continue;
    				}
    				for(int j=i+1;j<iniClusNum;j++)
    				{
    					if(isIndexClose[j])
    					{
    						continue;
    					}
    
    					double new_d = mp.getDistance(Cluster[i],Cluster[j]);
    					if(new_d < min)
    					{
    						min = new_d;
    						x=i;y=j;
    
    					}
    				}
    			}
    			if(x==-1 || y==-1)
    			{
    				break;
    			}
    
    			Point p = mp.getMean(Cluster[x],Cluster[y]);
    			//x<y	store the result
    			if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong==-1)
    			{
    				cout<<"a0"<<endl;
    				ClusterLast[clus_index].push_back(x);//xchange to p, y close
    				ClusterLast[clus_index].push_back(y);
    				p.NumPBelong = clus_index;
    				isIndexClose[y]=true;//y is closed
    				Cluster[x]=p;//new p is open
    				isIndexClose[x]=false;
    				isIndexClose2[x]=true;
    				isIndexClose2[y]=true;
    				clus_index++;
    
    			}
    			else if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong!=-1)//already exists one cluster
    			{
    				cout<<"a1"<<endl;
    				ClusterLast[Cluster[y].NumPBelong].push_back(x);
    				isIndexClose[x]=true;//x is closed
    				p.NumPBelong = Cluster[y].NumPBelong;
    				Cluster[y]=p;//new p is open
    				isIndexClose2[x]=true;
    			}
    			else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong==-1)
    			{
    				cout<<"a2"<<endl;
    				ClusterLast[Cluster[x].NumPBelong].push_back(y);
    				isIndexClose[y]=true;//y is closed
    				p.NumPBelong = Cluster[x].NumPBelong;
    				Cluster[x]=p;//new p is open
    				isIndexClose2[y]=true;
    			}
    			else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong!=-1)//both are clusteroid
    			{
    				cout<<"a3"<<endl;
    				vector<int>::iterator ite = ClusterLast[Cluster[y].NumPBelong].begin();//put y's node in x
    				for(;ite!=ClusterLast[Cluster[y].NumPBelong].end();ite++)
    				{
    					ClusterLast[Cluster[x].NumPBelong].push_back(*ite);
    				}
    				ClusterLast[Cluster[y].NumPBelong].clear();
    				isIndexClose[y]=true;//y is closed
    				p.NumPBelong = Cluster[x].NumPBelong;
    				Cluster[x]=p;//new p is open
    							
    			}
    			ClustNum--;
    		}
    		int total_size =0;
    		for(int i=0;i<stopNum;i++)
    		{
    			total_size+=ClusterLast[i].size();
    		}
    		if(total_size<iniClusNum)
    		{
    			int j=0;
    			for(int i=0;i<iniClusNum;i++)
    			{
    				if(isIndexClose2[i]==false)
    				{
    					ClusterLast[stopNum-1-j].push_back(i);
    				    j++;
    				}
    			}
    
    		}
    	}
    
    };
    int main()
    {
    	ManagerC M;
    	M.initCluster();
    	M.initIndexClose();
    	M.ClusterAlgo();
    	M.print();
    
    	system("pause");
    }
      如果仔细观察数据的数据在坐标系的分布,可以分成3簇。于是我们使StopNum =3;输出如下,采用的是输入数据的索引

                                                                    


     

     

    展开全文
  • 常用的聚类算法类型有:划分方法(k-means),层次方法,基于密度的方法,基于网格的方法。聚类算法选取取决于数据的类型和聚类的目的。二、各类算法基本原理及优缺点(一)划分算法1.算法原理K-means聚类,原理是随...

    对于聚类的了解可以从最简单最常用的k-means开始。

    旧梦:常用聚类算法k-means总结zhuanlan.zhihu.com

    一、什么是聚类算法

    聚类的目的是把长得相似的样本放在一起。常用的聚类算法类型有:划分方法(k-means),层次方法,基于密度的方法,基于网格的方法。聚类算法选取取决于数据的类型和聚类的目的。

    二、各类算法基本原理及优缺点

    (一)划分算法

    1.算法原理

    K-means聚类,原理是随机选取k个对象,实例距离哪个点近就更可能是哪一类,将每个类的中心点作为新的对象,不断迭代,直到分类完成。算法简单容易实现,但是需要预先确定k值,比较受初始值的影响,且非常受噪声和离群点的影响,最终得到的结果是局部最优。

    k-means对离群点敏感,k-中心则是在k-means基础上的改进,主要是中心点的选取方面有所不同,中心点选择的是距离其他点距离之和最近的点作为中心点。改进之后减少了噪声和离群点的影响,但是计算也变得非常复杂,适合小规模数据。

    (二)层次聚类算法

    划分方法需要指定类的个数即k值,层次聚类则解决了这个问题。层次分析法有两种,一种是凝聚方法,一种是分裂方法。

    1.层次法的原理

    凝聚方法:先计算样本之间的距离。每次将距离最近的点合并到同一类。然后再计算类与类之间的距离,将距离最近的类合并为一个大类。不停的合并,直到合并成一个类或满足终止条件。

    分裂方法:与凝聚方法相反,开始样本被视为一个大类,然后将最远的类分裂,不停的分裂,直至每个个体都成为一类或满足终止条件。

    2.基本步骤

    • 将每个对象看作一类,计算两两之间的最小距离
    • 将距离最小的两个类合并成一个新类
    • 重新计算新类与所有类之间的距离
    • 重复2、3步,直到所有类最后合并成一类

    3.优缺点

    优点:

    • 距离和规则的相似度容易定义,限制少
    • 不需要预先制定聚类数
    • 可以发现类的层次关系
    • 可以聚类成其他形状

    缺点:

    • 计算复杂度太高
    • 奇异值也能产生很大的影响
    • 算法可能聚成链状

    (三)基于密度的方法

    绝大多数划分方法只能发现球状的簇,而不能发现任意形状的簇,就有了基于密度的聚类。

    1.基于密度方法的主要思想

    定一个距离半径,在这个圈里面至少要有几个点,然后把可以到达的点都连接起来视为同类。

    其中要定义两个参数:圈的半径和点数,这两个参数的设置非常敏感。之后提出的算法是优先对高密度进行搜索,根据高密度的特点设置参数,改善了这个问题。

    基于密度的方法可以过滤噪声或离群点,发现任意形状的簇。

    (四)基于网格的方法

    1.基本原理

    在时间维度上的改进,把对象空间量化为有限个单元,形成一个网格结构,所有聚类操作都在网格结构上进行。这种方法的优点是处理时间快。可以和其他算法进行合并运用。

    2.优缺点:

    优点:

    处理速度快,其处理时间独立于数据对象数,而仅依赖于量化空间中的每一维的单元数

    缺点:

    在处理高纬度数据时,网格单元的数目会随着属性维数的增长而成指数级增长。

    某书对四种方法的基本描述如下:

    8bc97595b74a789a6e5439734b7d4a1c.png

    三、聚类效果如何衡量

    1.外在方法:

    有基准可用时,可以用它与聚类进行比较,来评估聚类。

    BCubed根据基准,对给定数据集上聚类中的每个对象估计精度和召回率。一个对象的精度指示同一簇中有多少个其他对象与该对象同属一个类别。一个对象的召回率反映有多少同一类别的对象被分配在相同的簇中。其实质就是分析分错了和分对了的比例来衡量聚类效果。

    2.内在方法:

    数据集无基准可用,需要用内在方法评估,通过考察簇的分离情况和紧凑情况来评估聚类。

    轮廓系数:衡量了每个簇中的紧凑度,以及簇间的距离。当每个簇中距离越紧凑,每个簇间距离越远则认为聚类效果优秀。

    a4dfff4b536afd39792a8d8831b27917.png
    展开全文
  • 层次聚类算法原理

    2017-08-29 16:17:35
    层次聚类算法原理及实现Hierarchical Clustering 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的...
  • 层次聚类算法原理及python实现

    万次阅读 多人点赞 2018-01-05 11:27:52
    层次聚类(Hierarchical Clustering)是一种聚类算法,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。
  • 层次聚类算法原理及实现Hierarchical Clustering

    万次阅读 多人点赞 2016-12-07 21:41:48
    层次聚类算法原理及实现Hierarchical Clustering 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的...
  • 聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类 K均值聚类算法的python实现,以及聚类算法与EM最大算法的关系 参考引用 先上一张gif的k均值聚类算法动态图片,让大家对算法有个感性认识: ...
  • 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有...
  • 层次聚类算法

    万次阅读 2016-06-05 09:23:29
    层次聚类算法是一个应用广泛的算法,小编最近要做对比实验,实现了其中一个版本,为了验证实验效果,结合我国各...所有本文从3部分来介绍,首先简介层次聚类算法,然后讲解其实现原理,最后结合一个实例进行分析对比。
  • GMM是一种聚类算法,每个component就是一个聚类中心 。即在只有样本点,不知道样本分类(含有隐含变量)的情况下,计算出模型参数(π,u和Σ)----这显然可以用EM算法来求解。再用训练好的模型去差别样本所属的分类...
  • 层次聚类算法分析

    2018-12-28 16:00:52
    层次聚类算法原理及实现Hierarchical Clustering 2016年4月19日 BY 蓝鲸 5 COMMENTS 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。...
  • 写在前面:健忘星人自学笔记,仅供参考简单易懂的阅读资料层次聚类-概念全解 - 万勇's Blog - CSDN博客​blog.csdn.net前面的文章我们...正文:一、层次聚类基本原理层次的聚类方法(Hierarchical Clustering),从...
  • 主要介绍了Python聚类算法之凝聚层次聚类原理与具体使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • BIRCH聚类算法原理

    千次阅读 2019-09-03 15:39:59
      在K-Means聚类算法原理中,我们讲到了K-Means和Mini Batch K-Means的聚类原理。这里我们再来看看另外一种常见的聚类算法BIRCH。BIRCH算法比较适合于数据量大,类别数K也比较多的情况。它运行速度很快,只需要单...
  • 聚类算法原理及python实现

    万次阅读 多人点赞 2017-11-13 20:52:18
    聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类 K均值聚类算法的python实现,以及聚类算法与EM最大算法的关系 参考引用 先上一张gif的k均值聚类算法动态图片,让大家对算法有个感性认识: 其中...
  • 在K-Means聚类算法原理中,我们讲到了K-Means和Mini Batch K-Means的聚类原理。这里我们再来看看另外一种常见的聚类算法BIRCH。BIRCH算法比较适合于数据量大,类别数K也比较多的情况。它运行速度很快,只需要单遍...
  • 参数:k(聚类个数) 随机选取K个中心点。(KMEANS++会在选取一个中心点后更倾向于去选择离选定中心点更远的) 计算其他点离哪个中心点更近,就算做哪一簇。 计算每个新簇的新中心点(取平均)。 重新调整除中心点...
  • 层次聚类算法及其实现

    千次阅读 2016-03-10 19:57:41
    层次聚类算法分为合并算法和分裂算法。合并算法会在每一步减少聚类中心的数量,聚类产生的结果来自前一步的两个聚类的合并;分裂算法与合并算法原理相反,在每一步增加聚类的数量,每一步聚类产生的结果都将是前一步...
  • 聚类算法(4)--Hierarchical clustering层次聚类

    万次阅读 多人点赞 2018-11-07 17:45:47
    1、层次聚类原理及分类 2、层次聚类的流程 3、层次聚类的优缺点 二、python实现 1、sklearn实现 2、scipy实现 树状图分类判断 一、层次聚类 1、层次聚类原理及分类 1)层次法(Hierarchicalmethods)先...
  • 层次聚类算法(HCA)是一种聚类分析方法,它通过层次结构搜索聚类的最佳分布。层次聚类的策略通常有两种类型:使用自下而上的过程进行聚集,而使用自上而下的过程进行分裂。但是,大多数聚类方法都有两个缺点:使用...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 219
精华内容 87
关键字:

层次聚类算法原理