7,129
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − {{Redirect|SLINK|the online magazine|Slink}} − {{Short description|A statistical method of analysis which seeks to build a hierarchy of clusters}}+ − {{Machine learning bar}}+ − + − − In [[data mining]] and [[statistics]], '''hierarchical clustering''' (also called '''hierarchical cluster analysis''' or '''HCA''') is a method of [[cluster analysis]] which seeks to build a [[hierarchy]] of clusters. Strategies for hierarchical clustering generally fall into two types:<ref name="clusteringMethods">Rokach, Lior, and Oded Maimon. "Clustering methods." Data mining and knowledge discovery handbook. Springer US, 2005. 321-352.</ref> − − In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types: − − 在数据挖掘和统计学中，'''<font color="#ff8000"> 层次聚类Hierarchical clustering</font>'''(也被称为层次数据聚类或HCA)是一种数据聚类的方法，它旨在建立一个集群层次结构。'''<font color="#ff8000"> 实现层次聚类Hierarchical clustering</font>'''的方法通常有两种: − − * '''Agglomerative''': This is a "[[Top-down and bottom-up design|bottom-up]]" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. − − 补充翻译：凝聚聚类：这是一种“自上而下又自下而上/纵向”的方法：每个被观察数据从自己的簇类中开始，当一个观察组数据向上层移动时，成对的簇类集群被合并。 − − − − 补充翻译：分裂聚类：这是一种“自上而下”的方法：所有的被观察数据都从一个簇类集群中开始，当一个簇类向下移动时，整个观察组数据群会递归地执行分割。 − − In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering<ref>{{cite book | author=Frank Nielsen | title=Introduction to HPC with MPI for Data Science | year=2016 | publisher=Springer | − 一般来说，合并和分裂是以使用者希望的方式决定的。'''<font color="#ff8000"> 而层次聚类Hierarchical clustering</font>'''的结果 < ref > { cite book | author = Frank Nielsen | title = Introduction to HPC with MPI for Data Science | year = 2016 | publisher = Springer | + − − − chapter=Chapter 8: Hierarchical Clustering | url=https://www.springer.com/gp/book/9783319219028 |chapter-url=https://www.researchgate.net/publication/314700681 }}</ref> are usually presented in a dendrogram. − 正如在第八章: '''<font color="#ff8000"> 层次聚类Hierarchical clustering</font>''' | url = https://www.springer.com/gp/book/9783319219028 | Chapter-url = https://www.researchgate.net/publication/314700681} </ref > 中所言，通常在树状图中呈现。+ − − − The standard algorithm for '''hierarchical agglomerative clustering''' (HAC) has a [[time complexity]] of <math>\mathcal{O}(n^3)</math> and requires <math>\mathcal{O}(n^2)</math> memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of complexity <math>\mathcal{O}(n^2)</math>) are known: '''SLINK'''<!--boldface per WP:R#PLA--><ref name="SLINK">{{cite journal | author=R. Sibson | title=SLINK: an optimally efficient algorithm for the single-link cluster method | journal=The Computer Journal | volume=16 | issue=1 | pages=30–34 | year=1973 | publisher=British Computer Society | url=http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf | doi=10.1093/comjnl/16.1.30}}</ref> for [[Single-linkage clustering|single-linkage]] and CLINK<ref name="CLINK">{{cite journal | author=D. Defays | title=An efficient algorithm for a complete-link method | journal=The Computer Journal | volume=20 | issue=4 | pages=364–366 | year=1977 | publisher=British Computer Society | url=http://comjnl.oxfordjournals.org/content/20/4/364.abstract | doi=10.1093/comjnl/20.4.364| doi-access=free }}</ref> for [[complete-linkage clustering]]. With a [[heap (data structure)|heap]] the runtime of the general case can be reduced to <math>\mathcal{O}(n^2 \log n)</math> at the cost of further increasing the memory requirements. In many cases, the memory overheads of this approach are too large to make it practically usable. − − The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of <math>\mathcal{O}(n^3)</math> and requires <math>\mathcal{O}(n^2)</math> memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of complexity <math>\mathcal{O}(n^2)</math>) are known: SLINK<!--boldface per WP:R#PLA--> for single-linkage and CLINK for complete-linkage clustering. With a heap the runtime of the general case can be reduced to <math>\mathcal{O}(n^2 \log n)</math> at the cost of further increasing the memory requirements. In many cases, the memory overheads of this approach are too large to make it practically usable. − − '''<font color="#ff8000"> 层次凝聚聚类Hierarchical agglomerative clustering</font>'''(HAC)的标准算法的时间复杂度为 < math > mathical { o }(n ^ 3) </math > ，并且需要 < math > mathcal { o }(n ^ 2) </math > 占用内存，这使得它对于中等数据集来说效率太低了。然而，对于某些特殊情况，已知的最佳有效凝聚方法(复杂度 < math > mathcal { o }(n ^ 2) </math >)是: 单连锁的 SLINK < ! ——粗体 wp: r # pla-- > 和完全连锁的 CLINK。对于数据群而言，一般情况下的运行时可以缩减为 < math > mathcal { o }(n ^ 2 log n) </math > ，代价是进一步增加内存需求。在多数情况下，这种方法的内存开销太大，并不实用。 − − − − Except for the special case of single-linkage, none of the algorithms (except exhaustive search in <math>\mathcal{O}(2^n)</math>) can be guaranteed to find the optimum solution. − 除了单链路的特殊情况外，所有算法(除了 < math > mathcal { o }(2 ^ n) </math > 数学中的穷举搜索)都不能保证找到最优解。+ − − Divisive clustering with an exhaustive search is <math>\mathcal{O}(2^n)</math>, but it is common to use faster heuristics to choose splits, such as k-means.+ − 穷举搜索的分裂群集是 < math > mathcal { o }(2 ^ n) </math > ，但是通常使用运算速度更快的探索法来选择分裂，比如 k-means。 − + 第71行：
第38行： − + − + − {{Further information|Metric (mathematics)}} − − − − The choice of an appropriate metric will influence the shape of the clusters, as some elements may be close to one another according to one distance and farther away according to another. For example, in a 2-dimensional space, the distance between the point (1,0) and the origin (0,0) is always 1 according to the usual norms, but the distance between the point (1,1) and the origin (0,0) can be 2 under Manhattan distance, <math>\scriptstyle\sqrt{2}</math> under Euclidean distance, or 1 under maximum distance. 第84行：
第46行： − + − Some commonly used metrics for hierarchical clustering are:<ref>{{cite web | title=The DISTANCE Procedure: Proximity Measures | url=https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/statug_distance_sect016.htm | work=SAS/STAT 9.2 Users Guide | publisher= [[SAS Institute]] | date= | accessdate=2009-04-26}}</ref> − − Some commonly used metrics for hierarchical clustering are: − − 一些常用的'''<font color="#ff8000"> 层次聚类Hierarchical clustering</font>'''指标如下: − − {|class="wikitable" − + − { | class = “ wikitable”+ − − ! Names − − ! Names − − − − ! Formula − − ! Formula − − − − + − |- − − |- − − − − | Euclidean distance − − | Euclidean distance − − − | <math> \|a-b \|_2 = \sqrt{\sum_i (a_i-b_i)^2} </math> − − | < math > | a-b | _ 2 = sqrt { sum _ i (a _ i-b _ i) ^ 2} </math > − − |- − − + − |- − − | Squared Euclidean distance − − | Squared Euclidean distance − − − − − | <math> \|a-b \|_2^2 = \sum_i (a_i-b_i)^2 </math> − − | < math > | a-b | 2 ^ 2 = sum _ i (a _ i-b _ i) ^ 2 − − + − |- − − |- − − − − | Manhattan distance − − | 曼哈顿距离 − − | <math> \|a-b \|_1 = \sum_i |a_i-b_i| </math> − − − [数学][数学][数学] − − + − |- − − |- − − − − | Maximum distance − − | 最大距离 − − − | <math> \|a-b \|_\infty = \max_i |a_i-b_i| </math> − − [数学][数学][数学] − − + + − − |- − − | [[Mahalanobis distance]] − − | Mahalanobis distance − − 马氏距离 − − | <math> \sqrt{(a-b)^{\top}S^{-1}(a-b)} </math> where ''S'' is the [[Covariance matrix]] − − | <math> \sqrt{(a-b)^{\top}S^{-1}(a-b)} </math> where S is the Covariance matrix − − | < math > sqrt {(a-b) ^ { top } s ^ {-1}(a-b)} </math > 其中 s 是协方差矩阵 − − |- − − |- − − |- − − |} − − |} − − − 对于文本文字或其他非数字数据，常常使用汉明距离或莱文斯坦距离等度量标准。+ − + + + − A review of cluster analysis in health psychology research found that the most common distance measure in published studies in that research area is the Euclidean distance or the squared Euclidean distance. − 通过对数据聚类健康心理学研究的回顾发现，在该研究领域已发表的研究中，最常见的距离测量方法是欧几里得度量距离或欧几里得度量距离的平方。 − − The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations. 第235行：
第90行： − + − − Some commonly used linkage criteria between two sets of observations A and B are: − − 两组观测值 a 和 b 之间一些常用的联系标准如下: − + − + − { | class = “ wikitable”+ − − ! Names − − ! Names − − − − ! Formula − − ! Formula − − − − |- − − |- − − |- − − | Maximum or [[complete-linkage clustering]] − − | Maximum or complete-linkage clustering − − | 最大或完全链接群集 − − | <math> \max \, \{\, d(a,b) : a \in A,\, b \in B \,\}. </math> − − | <math> \max \, \{\, d(a,b) : a \in A,\, b \in B \,\}. </math> − − | < math > max，{ ，d (a，b) : a 在 a，b 在 b，}。数学 − − |- − − |- − − |- − − | Minimum or [[single-linkage clustering]] − − | Minimum or single-linkage clustering − − | 最小或单链接群集 − − | <math> \min \, \{\, d(a,b) : a \in A,\, b \in B \,\}. </math> − − | <math> \min \, \{\, d(a,b) : a \in A,\, b \in B \,\}. </math> − − | < math > min，{ ，d (a，b) : a in a，，b in b，}.数学 − − |- − − + + − + − + − − | Unweighted average linkage clustering (or UPGMA) − − | Unweighted average linkage clustering (或 UPGMA) − − − − | <math> \frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b). </math> − − | < math > frac {1}{ | a | cdot | b | } sum _ { a } sum _ { b } d (a，b).数学 − − + − |-+ − − − − | Weighted average linkage clustering (or [[WPGMA]]) − − | Weighted average linkage clustering (or WPGMA) − − | 加权平均数链接聚类(或 WPGMA) − − − − − − | < math > d (i cup j，k) = frac { d (i，k) + d (j，k)}{2}.数学 − − |- − − |- − − |- − − | Centroid linkage clustering, or UPGMC − − | Centroid linkage clustering, or UPGMC − − | 质心链接集群，或 UPGMC − − | <math> \|c_s - c_t \| </math> where <math>c_s</math> and <math>c_t</math> are the centroids of clusters ''s'' and ''t'', respectively. − − | <math> \|c_s - c_t \| </math> where <math>c_s</math> and <math>c_t</math> are the centroids of clusters s and t, respectively. − − | < math > | c _ s-c _ t | </math > 其中 < math > c _ s </math > 和 < math > c _ t </math > 分别是集群 s 和 t 的中心。 − − + + − + + − + − − − | Minimum energy clustering − − | 最小能量聚类 − − − | <math> \frac {2}{nm}\sum_{i,j=1}^{n,m} \|a_i- b_j\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \|a_i-a_j\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \|b_i-b_j\|_2 </math> − − | < math > frac {2}{ nm } sum { i，j = 1}{ n，m } | a _ i-b _ j | 2-frac {1}{ n ^ 2} sum { i，j = 1}{ n } | a _ i-a _ j | 2-frac {1}{ m ^ 2} sum { i，j = 1 ^ { m } | b _ i-b _ j | 2 </math > − − |} − − |}+ − − where ''d'' is the chosen metric. Other linkage criteria include: − − where d is the chosen metric. Other linkage criteria include: − − 其中 d 是选定的度量单位。其他联系准则包括: − − 此处后准则无翻译 − − * The sum of all intra-cluster variance. − − 补充翻译 所有簇内方差之和。 − − * The increase in variance for the cluster being merged ([[Ward's method|Ward's criterion]]).<ref name="wards method">{{cite journal − − 补充翻译 合并中的簇的方差相加 − − |doi=10.2307/2282967 − − |doi=10.2307/2282967 − − 10.2307/2282967 − − |last=Ward |first=Joe H. − − |last=Ward |first=Joe H. − − | last = Ward | first = Joe h. − − |title=Hierarchical Grouping to Optimize an Objective Function − − |title=Hierarchical Grouping to Optimize an Objective Function − − | title = 用于优化目标函数的层次分组 − − |journal=Journal of the American Statistical Association − − |journal=Journal of the American Statistical Association − − 美国统计协会杂志 − − |volume=58 |issue=301 |year=1963 |pages=236–244 − − |volume=58 |issue=301 |year=1963 |pages=236–244 − − 58 | issue = 301 | year = 1963 | pages = 236-244 − − |mr=0148188 − − |mr=0148188 − − 0148188先生 − |jstor=2282967+ − |jstor=2282967+ − 2282967+ − + − }}</ref>+ − } </ref > − * The probability that candidate clusters spawn from the same distribution function (V-linkage).+ − 补充翻译 候选数据群从同一分布函数（V-连锁）中产生的概率。+ − * The product of in-degree and out-degree on a k-nearest-neighbour graph (graph degree linkage). − 补充翻译 *k-最近邻图（图度连锁）上的入度与出度的乘积 − − <ref>{{Cite journal|last=Zhang|first=Wei|last2=Wang|first2=Xiaogang|last3=Zhao|first3=Deli|last4=Tang|first4=Xiaoou|date=2012|editor-last=Fitzgibbon|editor-first=Andrew|editor2-last=Lazebnik|editor2-first=Svetlana|editor3-last=Perona|editor3-first=Pietro|editor4-last=Sato|editor4-first=Yoichi|editor5-last=Schmid|editor5-first=Cordelia|title=Graph Degree Linkage: Agglomerative Clustering on a Directed Graph|journal=Computer Vision – ECCV 2012|series=Lecture Notes in Computer Science|language=en|publisher=Springer Berlin Heidelberg|volume=7572|pages=428–441|doi=10.1007/978-3-642-33718-5_31|isbn=9783642337185|arxiv=1208.5092|bibcode=2012arXiv1208.5092Z}} See also: https://github.com/waynezhanghk/gacluster</ref> − − * The increment of some cluster descriptor (i.e., a quantity defined for measuring the quality of a cluster) after merging two clusters. − − 补充翻译 在合并了两个数据群之后，某个群的定义符号（即为度量一个簇的质量而定义的一个量）的增量。 − − <ref>Zhang, et al. "Agglomerative clustering via maximum incremental path integral." Pattern Recognition (2013).</ref><ref>Zhao, and Tang. "Cyclizing clusters via zeta function of a graph."Advances in Neural Information Processing Systems. 2008.</ref><ref>Ma, et al. "Segmentation of multivariate mixed data via lossy data coding and compression." IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(9) (2007): 1546-1562.</ref> − − == Discussion 讨论== − − Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances. − − Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances. − − '''<font color="#ff8000"> 层次聚类Hierarchical clustering</font>'''具有明显的优势，它可以使用任何有效的距离度量。事实上，观测本身也并不是必需的，层次聚类所需要用的只是一个距离矩阵。 + + − [[Image:Clusters.svg|frame|none|Raw data]] − − Raw data − − 原始数据 − − − − For example, suppose this data is to be clustered, and the [[Euclidean distance]] is the [[Metric (mathematics)|distance metric]]. − − For example, suppose this data is to be clustered, and the Euclidean distance is the distance metric. − − 例如，假设要对这些数据进行聚类，欧几里得距离就是距离度量。 − − − − The hierarchical clustering [[dendrogram]] would be as such: − − The hierarchical clustering dendrogram would be as such: − − 系统聚类树状图如下: − − − − [[Image:Hierarchical clustering simple diagram.svg|frame|none|Traditional representation]] − − Traditional representation − − 传统展现法 + − + − Cutting the tree at a given height will give a partitioning clustering at a selected precision. In this example, cutting after the second row (from the top) of the dendrogram will yield clusters {a} {b c} {d e} {f}. Cutting after the third row will yield clusters {a} {b c} {d e f}, which is a coarser clustering, with a smaller number but larger clusters. − − 在给定的高度切割树状图中，将以选定的精度提供分区聚类。在这个示例中，在树状图的第二行(从顶部开始)之后切割将产生集群{ a }{ b }{ d }{ f }。在第三行之后进行切割将产生集群{ a }{ b }{ d e f } ，这是一个较为粗略的但元素更繁多的集群，然而它的数量也较小。 第507行：
第153行： − This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.+ − − 第515行：
第159行： − Optionally, one can also construct a distance matrix at this stage, where the number in the i-th row j-th column is the distance between the i-th and j-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of caching distances between clusters. A simple agglomerative clustering algorithm is described in the single-linkage clustering page; it can easily be adapted to different types of linkage (see below).+ − 还可以选择在这个阶段构造一个距离矩阵，其中第i行第j列中的数字是i和j，即为两个元素之间的距离。然后，随着集群的进展，在合并集群和更新距离时合并行和列。这是实现此类集群的常用方法，并且具有缓存集群之间的距离的优点。在单链接聚类页面中描述了一个简单的凝聚聚类算法; 它适用于很多链接(见下文)。 − − − − Suppose we have merged the two closest elements ''b'' and ''c'', we now have the following clusters {''a''}, {''b'', ''c''}, {''d''}, {''e''} and {''f''}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters. − + 第531行：
第170行： − 通常情况下，两组数字之间的距离是下列数字之一:+ 第537行：
第176行： − <math> \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\}. </math> − − < math > max { ，d (x，y) : x in mathcal { a } ，，y in mathcal { b } ，}.数学 第545行：
第181行： − <math> \min \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B} \,\}. </math> − − < math > min { ，d (x，y) : x in mathcal { a } ，，y in mathcal { b } ，}.数学 第553行：
第186行： − <math> {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y). </math> − − {1 over { | mathcal { a } | cdot | mathcal { b } | } sum { x in mathcal { a } sum { y in mathcal { b } d (x，y)).数学 + + − + − In case of tied minimum distances, a pair is randomly chosen, thus being able to generate several structurally different dendrograms. Alternatively, all tied pairs may be joined at the same time, generating a unique dendrogram.+ − 在系结最小距离的情况下，一对元素是随机选择的，因此能够产生几个结构不同的树状图。或者，所有的绑定对可以在同一时间结合，产生一个唯一的树状图。 − + − One can always decide to stop clustering when there is a sufficiently small number of clusters (number criterion). Some linkages may also guarantee that agglomeration occurs at a greater distance between clusters than the previous agglomeration, and then one can stop clustering when the clusters are too far apart to be merged (distance criterion). However, this is not the case of, e.g., the centroid linkage where the so-called reversals (inversions, departures from ultrametricity) may occur.+ − 当有一个足够少的群集(数目标准)时，人们总是可以决定停止聚合。有些联系还可能保证集群之间的距离大于以前的集群，然后当集群之间的距离太远而无法合并时，就可以停止集群。然而，也有例外，如在质心链接的情况下，所谓的逆转(反转，偏离超节拍)就可能发生。 − − The basic principle of divisive clustering was published as the DIANA (DIvisive ANAlysis Clustering) algorithm.<ref>Kaufman, L., & Roussew, P. J. (1990). Finding Groups in Data - An Introduction to Cluster Analysis. A Wiley-Science Publication John Wiley & Sons.</ref> Initially, all data is in the same cluster, and the largest cluster is split until every object is separate. − + − Because there exist <math>O(2^n)</math> ways of splitting each cluster, heuristics are needed. DIANA chooses the object with the maximum average dissimilarity and then moves all objects to this cluster that are more similar to the new cluster than to the remainder.+ − 因为存在拆分每个集群的步骤，所以需要探索试算法。DIANA 选择平均差异最大的对象，然后将所有与新集群相似的对象移动到这个集群中取代移动到其余的对象的方法。 − − − − + − − − − Hierarchical clustering [[dendrogram of the Iris dataset (using R). [https://cran.r-project.org/web/packages/dendextend/vignettes/Cluster_Analysis.html Source] ]] − − 层次聚类[[虹膜数据集的树状图(使用 r)]。[ https://cran.r-project.org/web/packages/dendextend/vignettes/cluster_analysis.html 来源] − − − Orange data mining suite.]] − − 橙色数据挖掘套件] − 第655行：
第267行： − + 第693行：
第305行： − + − + − + 第702行：
第314行： − + 第710行：
第322行： − {{DEFAULTSORT:Hierarchical Clustering}} − − [[Category:Network analysis]] − − Category:Network analysis − − 分类: 网络分析 − − [[Category:Cluster analysis algorithms]] − − Category:Cluster analysis algorithms − − 类别: 数据聚类算法 − − <noinclude> − <small>This page was moved from [[wikipedia:en:Hierarchical clustering]]. Its edit history can be viewed at [[层次聚类/edithistory]]</small></noinclude>+ − +
无编辑摘要
此词条暂由水流心不竞翻译，未经审校，带来阅读不便，请见谅。由CecileLi初步审校。翻译评级：B
此词条暂由水流心不竞翻译，未经审校，带来阅读不便，请见谅。由CecileLi初步审校。翻译评级：B
在[[数据挖掘]]和[[统计学]]中，'''<font color="#ff8000"> 层次聚类 Hierarchical clustering</font>'''(也被称为“层次数据聚类或”“HCA”)是一种通过建立一个集群层次结构来[[聚类分析]]的方法。实现层次聚类的方法通常有两种:<ref name="clusteringMethods">Rokach, Lior, and Oded Maimon. "Clustering methods." Data mining and knowledge discovery handbook. Springer US, 2005. 321-352.</ref>
* '''凝聚聚类 Agglomerative'''：这是一种“自上而下又自下而上/纵向”的方法：每个被观察数据从自己的簇类中开始，当一个观察组数据向上层移动时，成对的簇类集群被合并。
* '''分裂聚类 Divisive''': 这是一种“自上而下”的方法：所有的被观察数据都从一个簇类集群中开始，当一个簇类向下移动时，整个观察组数据群会递归地执行分割。
* '''Divisive''': This is a "[[Top-down and bottom-up design|top-down]]" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.
In general, the merges and splits are determined in a [[greedy algorithm|greedy]] manner. The results of hierarchical clustering<ref>{{cite book | author=Frank Nielsen | title=Introduction to HPC with MPI for Data Science | year=2016 | publisher=Springer |
In general, the merges and splits are determined in a [[greedy algorithm|greedy]] manner. The results of hierarchical clustering<ref>{{cite book | author=Frank Nielsen | title=Introduction to HPC with MPI for Data Science | year=2016 | publisher=Springer |
补充：此处翻译编辑视图内有显示阅读视图中无。
补充：此处翻译编辑视图内有显示阅读视图中无。
一般来说，合并和分裂是以使用者希望的方式决定的。而层次聚类的结果 <ref>{{cite book | author=Frank Nielsen | title=Introduction to HPC with MPI for Data Science | year=2016 | publisher=Springer |chapter=Chapter 8: Hierarchical Clustering | url=https://www.springer.com/gp/book/9783319219028 |chapter-url=https://www.researchgate.net/publication/314700681 }}</ref> 通常在树状图中呈现。
chapter=Chapter 8: Hierarchical Clustering | url=https://www.springer.com/gp/book/9783319219028 |chapter-url=https://www.researchgate.net/publication/314700681 }}</ref> are usually presented in a [[dendrogram]].
'''<font color="#ff8000"> 层次凝聚聚类 Hierarchical agglomerative clustering</font>'''（HAC）的标准算法的[[时间复杂度]]为<math>\mathcal{O}(n^3)</math> ，并且需要 <math>\mathcal{O}(n^2)</math> 占用内存，这使得它对于中等数据集来说效率太低了。然而，对于某些特殊情况，已知的最有效凝聚方法(复杂度 <math>\mathcal{O}(n^2)</math>)是: SLINK 用于单连接<ref name="SLINK">{{cite journal | author=R. Sibson | title=SLINK: an optimally efficient algorithm for the single-link cluster method | journal=The Computer Journal | volume=16 | issue=1 | pages=30–34 | year=1973 | publisher=British Computer Society | url=http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf | doi=10.1093/comjnl/16.1.30}}</ref> for [[Single-linkage clustering|single-linkage]]， CLINK用于完全连接<ref name="CLINK">{{cite journal | author=D. Defays | title=An efficient algorithm for a complete-link method | journal=The Computer Journal | volume=20 | issue=4 | pages=364–366 | year=1977 | publisher=British Computer Society | url=http://comjnl.oxfordjournals.org/content/20/4/364.abstract | doi=10.1093/comjnl/20.4.364| doi-access=free }}</ref>[[complete-linkage clustering]]。一般情况下的运行时可以缩减为 <math>\mathcal{O}(n^2 \log n)</math> ，代价是进一步增加内存需求。在多数情况下，这种方法的内存消耗太大，并不实用。
Except for the special case of single-linkage, none of the algorithms (except exhaustive search in <math>\mathcal{O}(2^n)</math>) can be guaranteed to find the optimum solution.
Except for the special case of single-linkage, none of the algorithms (except exhaustive search in <math>\mathcal{O}(2^n)</math>) can be guaranteed to find the optimum solution.
除了单连接的特殊情况外，所有算法（除了<math>\mathcal{O}(2^n)</math>数学中的穷举搜索）都不能保证找到最优解。
Divisive clustering with an exhaustive search is <math>\mathcal{O}(2^n)</math>, but it is common to use faster heuristics to choose splits, such as k-means.
Divisive clustering with an exhaustive search is <math>\mathcal{O}(2^n)</math>, but it is common to use faster heuristics to choose splits, such as k-means.
穷举搜索的分裂群集是 <math>\mathcal{O}(2^n)</math>，但是通常使用运算速度更快的探索法来选择分裂，比如[[k-means]]。
== Cluster dissimilarity 簇异性==
==簇异性 Cluster dissimilarity==
In order to decide which clusters should be combined (for agglomerative), or where a cluster should be split (for divisive), a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate [[metric (mathematics)|metric]] (a measure of [[distance]] between pairs of observations), and a linkage criterion which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets.
In order to decide which clusters should be combined (for agglomerative), or where a cluster should be split (for divisive), a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate [[metric (mathematics)|metric]] (a measure of [[distance]] between pairs of observations), and a linkage criterion which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets.
=== Metric 度量标准===
===度量标准 Metric===
''更多信息请查看[[度量标准 Metric]]''
The choice of an appropriate metric will influence the shape of the clusters, as some elements may be close to one another according to one distance and farther away according to another. For example, in a 2-dimensional space, the distance between the point (1,0) and the origin (0,0) is always 1 according to the usual norms, but the distance between the point (1,1) and the origin (0,0) can be 2 under Manhattan distance, <math>\scriptstyle\sqrt{2}</math> under Euclidean distance, or 1 under maximum distance.
The choice of an appropriate metric will influence the shape of the clusters, as some elements may be close to one another according to one distance and farther away according to another. For example, in a 2-dimensional space, the distance between the point (1,0) and the origin (0,0) is always 1 according to the usual norms, but the distance between the point (1,1) and the origin (0,0) can be 2 under Manhattan distance, <math>\scriptstyle\sqrt{2}</math> under Euclidean distance, or 1 under maximum distance.
一些常用的'''<font color="#ff8000"> 层次聚类 Hierarchical clustering</font>'''指标如下:<ref>{{cite web | title=The DISTANCE Procedure: Proximity Measures | url=https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/statug_distance_sect016.htm | work=SAS/STAT 9.2 Users Guide | publisher= [[SAS Institute]] | date= | accessdate=2009-04-26}}</ref>
{|class="wikitable"
{|class="wikitable"
! 名字
! 公式
!名字
!方程式
|-
|-
| [[欧氏距离 Euclidean distance]]
| [[Euclidean distance]]
| <math> \|a-b \|_2 = \sqrt{\sum_i (a_i-b_i)^2} </math>
| <math> \|a-b \|_2 = \sqrt{\sum_i (a_i-b_i)^2} </math>
|-
|-
| 平方欧氏距离 Squared Euclidean distance
| Squared Euclidean distance
| <math> \|a-b \|_2^2 = \sum_i (a_i-b_i)^2 </math>
| <math> \|a-b \|_2^2 = \sum_i (a_i-b_i)^2 </math>
|-
|-
| [[曼哈顿距离 Manhattan distance]]
| [[Manhattan distance]]
| <math> \|a-b \|_1 = \sum_i |a_i-b_i| </math>
| <math> \|a-b \|_1 = \sum_i |a_i-b_i| </math>
|-
|-
| [[最大距离 Maximum distance]]
| [[Uniform norm|Maximum distance]]
| <math> \|a-b \|_\infty = \max_i |a_i-b_i| </math>
| <math> \|a-b \|_\infty = \max_i |a_i-b_i| </math>
|-
|-
| [[马氏距离 Mahalanobis distance]]
| <math> \sqrt{(a-b)^{\top}S^{-1}(a-b)} </math> 其中''S''是[[协方差矩阵]]
|-
|-
|}
|}
For text or other non-numeric data, metrics such as the [[Hamming distance]] or [[Levenshtein distance]] are often used.
For text or other non-numeric data, metrics such as the [[Hamming distance]] or [[Levenshtein distance]] are often used.
For text or other non-numeric data, metrics such as the Hamming distance or Levenshtein distance are often used.
For text or other non-numeric data, metrics such as the Hamming distance or Levenshtein distance are often used.
对于文本文字或其他非数字数据，常常使用[[汉明距离 Hamming distance]]或[[编辑距离 Levenshtein distance]]等度量标准。
A review of cluster analysis in health psychology research found that the most common distance measure in published studies in that research area is the Euclidean distance or the squared Euclidean distance.{{Citation needed|date=April 2009}}
A review of cluster analysis in health psychology research found that the most common distance measure in published studies in that research area is the Euclidean distance or the squared Euclidean distance.
通过对数据聚类健康心理学研究的回顾发现，在该研究领域已发表的研究中，最常见的距离测量方法是欧几里得度量距离或欧几里得度量距离的平方。{{Citation needed|date=April 2009}}
=== Linkage criteria 连接准则===
=== Linkage criteria 连接准则===
The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations.
The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations.
Some commonly used linkage criteria between two sets of observations ''A'' and ''B'' are:<ref>{{cite web | title=The CLUSTER Procedure: Clustering Methods | url=https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/statug_cluster_sect012.htm | work=SAS/STAT 9.2 Users Guide | publisher= [[SAS Institute]] | date= | accessdate=2009-04-26}}</ref><ref>{{cite journal |last=Székely |first=G. J. |last2=Rizzo |first2=M. L. |year=2005 |title=Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method |journal=Journal of Classification |volume=22 |issue=2 |pages=151–183 |doi=10.1007/s00357-005-0012-9 }}</ref>
Some commonly used linkage criteria between two sets of observations ''A'' and ''B'' are:
{|class="wikitable"
两组观测值''A''和''B''之间一些常用的连接标准如下:<ref>{{cite web | title=The CLUSTER Procedure: Clustering Methods | url=https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/statug_cluster_sect012.htm | work=SAS/STAT 9.2 Users Guide | publisher= [[SAS Institute]] | date= | accessdate=2009-04-26}}</ref><ref>{{cite journal |last=Székely |first=G. J. |last2=Rizzo |first2=M. L. |year=2005 |title=Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method |journal=Journal of Classification |volume=22 |issue=2 |pages=151–183 |doi=10.1007/s00357-005-0012-9 }}</ref>
{|class="wikitable"
{|class="wikitable"
! 名字
! 公式
!名字
!方程式
|-
|-
| 最大或完全连接聚类
| <math> \max \, \{\, d(a,b) : a \in A,\, b \in B \,\}</math>
|-
|-
| 最小或单连接聚类
| Unweighted average linkage clustering (or [[UPGMA]])
| <math> \min \, \{\, d(a,b) : a \in A,\, b \in B \,\}</math>
| <math> \frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b). </math>
|-
|-
| 未加权平均链接聚类 Unweighted average linkage clustering (or [[UPGMA]])
| <math> \frac{1}{|A|\cdot|B|} \sum_{a \in A }\sum_{ b \in B} d(a,b)</math>
|-
| <math> d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}. </math>
| <math> d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}. </math>
|-
|-
| 加权平均数链接聚类 Weighted average linkage clustering (or [[WPGMA]])
| <math> d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}
|-
|-
| 质心链接集群 Centroid linkage clustering, or UPGMC
| <math> \|c_s - c_t \| </math> where <math>c_s</math> and <math>c_t</math> 分别是 ''s''类和 ''t''类的中心.
|-
|-
| 最小能量聚类[[Energy distance|Minimum energy clustering]]
| [[Energy distance|Minimum energy clustering]]
| <math> \frac {2}{nm}\sum_{i,j=1}^{n,m} \|a_i- b_j\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \|a_i-a_j\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \|b_i-b_j\|_2 </math>
| <math> \frac {2}{nm}\sum_{i,j=1}^{n,m} \|a_i- b_j\|_2 - \frac {1}{n^2}\sum_{i,j=1}^{n} \|a_i-a_j\|_2 - \frac{1}{m^2}\sum_{i,j=1}^{m} \|b_i-b_j\|_2 </math>
|}
|}
其中 ''d'' 是选定的度量单位。其他连接准则包括:
* The sum of all intra-cluster variance.所有簇内方差之和。
* The increase in variance for the cluster being merged 合并中的簇的方差相加([[Ward标准]])<ref name="wards method">{{cite journal|doi=10.2307/2282967|last=Ward |first=Joe H. |title=Hierarchical Grouping to Optimize an Objective Function |journal=Journal of the American Statistical Association |volume=58 |issue=301 |year=1963 |pages=236–244}}</ref>.
* The probability that candidate clusters spawn from the same distribution function (V-linkage).候选数据群从同一分布函数（V-连锁）中产生的概率。
}}</ref>
* The product of in-degree and out-degree on a k-nearest-neighbour graph (graph degree linkage).k-最近邻图（图度连锁）上的入度与出度的乘积<ref>{{Cite journal|last=Zhang|first=Wei|last2=Wang|first2=Xiaogang|last3=Zhao|first3=Deli|last4=Tang|first4=Xiaoou|date=2012|editor-last=Fitzgibbon|editor-first=Andrew|editor2-last=Lazebnik|editor2-first=Svetlana|editor3-last=Perona|editor3-first=Pietro|editor4-last=Sato|editor4-first=Yoichi|editor5-last=Schmid|editor5-first=Cordelia|title=Graph Degree Linkage: Agglomerative Clustering on a Directed Graph|journal=Computer Vision – ECCV 2012|series=Lecture Notes in Computer Science|language=en|publisher=Springer Berlin Heidelberg|volume=7572|pages=428–441|doi=10.1007/978-3-642-33718-5_31|isbn=9783642337185|arxiv=1208.5092|bibcode=2012arXiv1208.5092Z}} See also: https://github.com/waynezhanghk/gacluster</ref>
* The increment of some cluster descriptor (i.e., a quantity defined for measuring the quality of a cluster) after merging two clusters.在合并了两个数据群之后，某个群的定义符号（即为度量一个簇的质量而定义的一个量）的增量。<ref>Zhang, et al. "Agglomerative clustering via maximum incremental path integral." Pattern Recognition (2013).</ref><ref>Zhao, and Tang. "Cyclizing clusters via zeta function of a graph."Advances in Neural Information Processing Systems. 2008.</ref><ref>Ma, et al. "Segmentation of multivariate mixed data via lossy data coding and compression." IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(9) (2007): 1546-1562.</ref>
==讨论==
层次聚类具有明显的优势，它可以使用任何有效的距离度量。事实上，观测本身也并不是必需的，层次聚类所需要用的只是一个距离矩阵。
== Agglomerative clustering example 凝聚聚类实例==
== Agglomerative clustering example 凝聚聚类实例==
[[Image:Clusters.svg|frame|none|原始数据]]
例如，假设要对这些数据进行聚类，将欧式距离作为度量。系统聚类[[树状图]]如下:
[[Image:Hierarchical clustering simple diagram.svg|frame|none|传统展现法]]
Cutting the tree at a given height will give a partitioning clustering at a selected precision. In this example, cutting after the second row (from the top) of the [[dendrogram]] will yield clusters {a} {b c} {d e} {f}. Cutting after the third row will yield clusters {a} {b c} {d e f}, which is a coarser clustering, with a smaller number but larger clusters.
Cutting the tree at a given height will give a partitioning clustering at a selected precision. In this example, cutting after the second row (from the top) of the [[dendrogram]] will yield clusters {a} {b c} {d e} {f}. Cutting after the third row will yield clusters {a} {b c} {d e f}, which is a coarser clustering, with a smaller number but larger clusters.
在给定的高度切割树状图中，将以选定的精度提供分区聚类。在这个示例中，在树状图的第二行(从顶部开始)之后切割将产生类别{a} {b c} {d e} {f}。在第三行之后进行切割将产生类别{a} {b c} {d e f} ，这是一个较为粗略的但元素更繁多的类别，然而它的数量也较小。
This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.
This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.
此方法通过逐步合并集群，从单个元素构建层次结构。在我们的示例中，有六个元素{a} {b} {c} {d} {e}和{f}。第一步是确定在集群中合并哪些元素。通常，我们希望根据选定的距离获取两个最接近的元素。
此方法通过逐步合并集群，从单个元素构建层次结构。在我们的示例中，有六个元素{ a }{ b }{ c }{ d }{ e }和{ f }。第一步是确定在集群中合并哪些元素。通常，我们希望根据选定的距离获取两个最接近的元素。
Optionally, one can also construct a [[distance matrix]] at this stage, where the number in the ''i''-th row ''j''-th column is the distance between the ''i''-th and ''j''-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of caching distances between clusters. A simple agglomerative clustering algorithm is described in the [[single-linkage clustering]] page; it can easily be adapted to different types of linkage (see below).
Optionally, one can also construct a [[distance matrix]] at this stage, where the number in the ''i''-th row ''j''-th column is the distance between the ''i''-th and ''j''-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of caching distances between clusters. A simple agglomerative clustering algorithm is described in the [[single-linkage clustering]] page; it can easily be adapted to different types of linkage (see below).
还可以选择在这个阶段构造一个[[距离矩阵]]，其中第i行第j列中的数字是 ''i''和''j''，即为两个元素之间的距离。然后，随着集群的进展，在合并集群和更新距离时合并行和列。这是实现此类集群的常用方法，并且具有缓存集群之间的距离的优点。在单链接聚类页面中描述了一个简单的凝聚聚类算法; 它适用于很多连接(见下文)。
Suppose we have merged the two closest elements b and c, we now have the following clusters {a}, {b, c}, {d}, {e} and {f}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters.
Suppose we have merged the two closest elements b and c, we now have the following clusters {a}, {b, c}, {d}, {e} and {f}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters.
假设我们已经合并了两个最接近的元素 b 和 c，现在我们有以下集群{ a }、{ b、 c }、{ d }、{ e }和{ f } ，并希望进一步合并它们。为此，我们需要计算{ a }和{ b c }之间的距离，从而定义两个集群之间的距离。
假设我们已经合并了两个最接近的元素 ''b'' 和''c''，现在我们有以下集群{''a''}, {''b'', ''c''}, {''d''}, {''e''} 和{''f''} ，并希望进一步合并它们。为此，我们需要计算 {a} 和 {b c}之间的距离，从而定义两个集群之间的距离。
Usually the distance between two clusters <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is one of the following:
Usually the distance between two clusters <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is one of the following:
Usually the distance between two clusters <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is one of the following:
Usually the distance between two clusters <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is one of the following:
通常情况下，两个类别<math>\mathcal{A}</math>和 <math>\mathcal{B}</math>之间的距离是下列数字之一:
* The maximum distance between elements of each cluster (also called [[complete-linkage clustering]]):
* The maximum distance between elements of each cluster (also called [[complete-linkage clustering]]):
::<math> \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\}. </math>
::<math> \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\}. </math>
* The minimum distance between elements of each cluster (also called [[single-linkage clustering]]):
* The minimum distance between elements of each cluster (also called [[single-linkage clustering]]):
::<math> \min \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B} \,\}. </math>
::<math> \min \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B} \,\}. </math>
* The mean distance between elements of each cluster (also called average linkage clustering, used e.g. in [[UPGMA]]):
* The mean distance between elements of each cluster (also called average linkage clustering, used e.g. in [[UPGMA]]):
::<math> {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y). </math>
::<math> {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y). </math>
* The sum of all intra-cluster variance.
* The sum of all intra-cluster variance.
*所有集群内方差之和。
*所有集群内方差之和。
* The increase in variance for the cluster being merged ([[Ward's method]]<ref name="wards method"/>)
* The increase in variance for the cluster being merged ([[Ward's method]]<ref name="wards method"/>)
*合并的聚类的方差增加([[离差平方和法]]<ref name="离差平方和法"/>)。
*合并的聚类的方差增加([[离差平方和法]]<ref name="离差平方和法"/>)。
* The probability that candidate clusters spawn from the same distribution function (V-linkage).
* The probability that candidate clusters spawn from the same distribution function (V-linkage).
*候选集群从相同的分布函数中产生的概率（V—链路）。
*候选集群从相同的分布函数中产生的概率（V—链路）。
In case of tied minimum distances, a pair is randomly chosen, thus being able to generate several structurally different dendrograms. Alternatively, all tied pairs may be joined at the same time, generating a unique dendrogram.<ref>{{cite journal | doi=10.1007/s00357-008-9004-x | last1=Fernández | first1=Alberto | last2=Gómez | first2=Sergio | title=Solving Non-uniqueness in Agglomerative Hierarchical Clustering Using Multidendrograms | journal=Journal of Classification | volume=25 | year=2008 | issue=1 | pages=43–65| arxiv=cs/0608049 }}</ref>
In case of tied minimum distances, a pair is randomly chosen, thus being able to generate several structurally different dendrograms. Alternatively, all tied pairs may be joined at the same time, generating a unique dendrogram.
在系结最小距离的情况下，一对元素是随机选择的，因此能够产生几个结构不同的树状图。或者，所有的绑定对可以在同一时间结合，产生一个唯一的树状图。<ref>{{cite journal | doi=10.1007/s00357-008-9004-x | last1=Fernández | first1=Alberto | last2=Gómez | first2=Sergio | title=Solving Non-uniqueness in Agglomerative Hierarchical Clustering Using Multidendrograms | journal=Journal of Classification | volume=25 | year=2008 | issue=1 | pages=43–65| arxiv=cs/0608049 }}</ref>
One can always decide to stop clustering when there is a sufficiently small number of clusters (number criterion). Some linkages may also guarantee that agglomeration occurs at a greater distance between clusters than the previous agglomeration, and then one can stop clustering when the clusters are too far apart to be merged (distance criterion). However, this is not the case of, e.g., the centroid linkage where the so-called reversals<ref>{{Cite book | last1= Legendre | first1 = P. | first2 = L. | last2=Legendre | title= Numerical Ecology | publisher=Elsevier Science BV | date=2003}}</ref> (inversions, departures from ultrametricity) may occur.
One can always decide to stop clustering when there is a sufficiently small number of clusters (number criterion). Some linkages may also guarantee that agglomeration occurs at a greater distance between clusters than the previous agglomeration, and then one can stop clustering when the clusters are too far apart to be merged (distance criterion). However, this is not the case of, e.g., the centroid linkage where the so-called reversal (inversions, departures from ultrametricity) may occur.
当有一个足够少的群集(数目标准)时，人们总是可以决定停止聚合。有些联系还可能保证集群之间的距离大于以前的集群，然后当集群之间的距离太远而无法合并时，就可以停止集群。然而，也有例外，如在质心链接的情况下，所谓的逆转(反转，偏离超节拍)就可能发生<ref>{{Cite book | last1= Legendre | first1 = P. | first2 = L. | last2=Legendre | title= Numerical Ecology | publisher=Elsevier Science BV | date=2003}}</ref>。
== Divisive clustering分裂聚类 ==
== Divisive clustering分裂聚类 ==
The basic principle of divisive clustering was published as the DIANA (DIvisive ANAlysis Clustering) algorithm. Initially, all data is in the same cluster, and the largest cluster is split until every object is separate.
The basic principle of divisive clustering was published as the DIANA (DIvisive ANAlysis Clustering) algorithm. Initially, all data is in the same cluster, and the largest cluster is split until every object is separate.
分裂聚类的基本原理被公布为 DIANA (分裂分析聚类)算法。最初，所有数据都位于同一个集群中，然后最大的集群被拆分，依此类推，直到每个元素都是独立的。
分裂聚类的基本原理被公布为 DIANA (分裂分析聚类)算法<ref>Kaufman, L., & Roussew, P. J. (1990). Finding Groups in Data - An Introduction to Cluster Analysis. A Wiley-Science Publication John Wiley & Sons.</ref>。最初，所有数据都位于同一个集群中，然后最大的集群被拆分，依此类推，直到每个元素都是独立的。
Because there exist <math>O(2^n)</math> ways of splitting each cluster, heuristics are needed. DIANA chooses the object with the maximum average dissimilarity and then moves all objects to this cluster that are more similar to the new cluster than to the remainder.
Because there exist <math>O(2^n)</math> ways of splitting each cluster, heuristics are needed. DIANA chooses the object with the maximum average dissimilarity and then moves all objects to this cluster that are more similar to the new cluster than to the remainder.
因为存在拆分每个集群的步骤是<math>O(2^n)</math>，所以需要探索试算法。DIANA 选择平均差异最大的对象，然后将所有与新集群相似的对象移动到这个集群中取代移动到其余的对象的方法。
== Software 软件==
== Software 软件==
=== Open source implementations 开源工具===
=== Open source implementations 开源工具===
[[File:Iris dendrogram.png|thumb|Hierarchical clustering [[dendrogram]] of the [[Iris flower data set|Iris dataset]] (using |R]]).层次聚类[[鸢尾花数据集]]的树状图(使用R语言) [https://cran.r-project.org/web/packages/dendextend/vignettes/Cluster_Analysis.html Source] ]]
[[File:Iris dendrogram.png|thumb|Hierarchical clustering [[dendrogram]] of the [[Iris flower data set|Iris dataset]] (using [[R (programming language)|R]]). [https://cran.r-project.org/web/packages/dendextend/vignettes/Cluster_Analysis.html Source] ]]
[[File:Orange-data-mining-hierarchical-clustering.png|thumb|Hierarchical clustering and interactive dendrogram visualization in [[Orange (software)|Orange data mining suite]].]]
[[File:Orange-data-mining-hierarchical-clustering.png|thumb|Hierarchical clustering and interactive dendrogram visualization in [[Orange (software)|Orange data mining suite]].]]
*[[CrimeStat]]包括一个能够为地理位置提供图形输出的最近邻层次聚类算法。
*[[CrimeStat]]包括一个能够为地理位置提供图形输出的最近邻层次聚类算法。
== See also又及 ==
== 参见 ==
{{Div col|colwidth=20em}}
{{Div col|colwidth=20em}}
* [[Statistical distance]]
* [[Statistical distance]]
[[统计距离]]
[[统计距离]]
* [[Persistent homology]]{{div col end}}
* [[Persistent homology]]
[[持续同调]]{{div col end}}
[[持续同调]]
== References 参考文献==
== 参考文献==
{{reflist|30em}}
{{reflist|30em}}
== Further reading 延伸阅读==
== 进一步阅读==
* {{cite book |last1=Kaufman |first1=L. |last2=Rousseeuw |first2=P.J. |year=1990 |title=Finding Groups in Data: An Introduction to Cluster Analysis |edition=1 |isbn=0-471-87876-6 |publisher=John Wiley |location=New York |url-access=registration |url=https://archive.org/details/findinggroupsind00kauf }}
* {{cite book |last1=Kaufman |first1=L. |last2=Rousseeuw |first2=P.J. |year=1990 |title=Finding Groups in Data: An Introduction to Cluster Analysis |edition=1 |isbn=0-471-87876-6 |publisher=John Wiley |location=New York |url-access=registration |url=https://archive.org/details/findinggroupsind00kauf }}
[[Category:网络分析]]
[[Category:待整理页面]]
[[Category:数据聚类算法]]