精华内容
下载资源
问答
  • 单链接层次聚类算法
    千次阅读
    2020-08-06 13:33:09

    层次聚类算法 算法

    Take a look at the image below. It’s a collection of bugs and creepy-crawlies of different shapes and sizes. Take a moment to categorize them by similarity into a number of groups.

    看看下面的图片。 它是各种形状和大小的错误和令人毛骨悚然的爬行动物的集合。 花一点时间按照相似性将它们分为多个组。

    This isn’t a trick question. Start with grouping the spiders together.

    这不是一个技巧性的问题。 首先将蜘蛛分组在一起。

    Done? While there’s not necessarily a “correct” answer here, it’s most likely you split the bugs into four clusters. The spiders in one cluster, the pair of snails in another, the butterflies and moth into one, and the trio of wasps and bees into one more.

    做完了吗 虽然这里一定不是一个“正确”的答案,这是最有可能拆分的错误分为四个集群 。 蜘蛛在一个簇中,成对的蜗牛在另一个簇中,蝴蝶和飞蛾成一团,WaSP和蜜蜂三人成群。

    That wasn’t too bad, was it? You could probably do the same with twice as many bugs, right? If you had a bit of time to spare — or a passion for entomology — you could probably even do the same with a hundred bugs.

    还不错吧? 您可能会用两倍多的错误来做同样的事情,对不对? 如果您有空余时间-或对昆虫学充满热情-您甚至可以用一百个bug来做同样的事情。

    For a machine though, grouping ten objects into however many meaningful clusters is no small task, thanks to a mind-bending branch of maths called combinatorics, which tells us that are 115,975 different possible ways you could have grouped those ten insects together.

    但是对于一台机器来说,将十个对象分组到许多有意义的簇中并不是一件容易的事,这要归功于一个名为combinatorics的弯弯曲曲的数学分支,该分支告诉我们,有115,975种不同的可能方式可以将这十个昆虫分组在一起。

    Had there been twenty bugs, there would have been over fifty trillion possible ways of clustering them.

    如果有二十个错误,那么将有超过五十万亿种可能的方法将它们聚类。

    With a hundred bugs — there’d be many times more solutions than there are particles in the known universe.

    有一百个错误-解决方案的数量比已知宇宙中存在的粒子多很多倍。

    How many times more? By my calculation, approximately five hundred million billion billion times more. In fact, there are more than four million billion googol solutions (what’s a googol?).

    还有多少倍? 根据我的计算,大约是五千亿亿倍 。 实际上,有超过四十亿个googol解决方案( 什么是googol? )。

    For just a hundred objects.

    仅用于一百个对象。

    Almost all of those solutions would be meaningless — yet from that unimaginable number of possible choices, you pretty quickly found one of the very few that clustered the bugs in a useful way.

    几乎所有这些解决方案都是毫无意义的-但是,从众多难以想象的可能选择中,您很快就找到了以有用的方式对错误进行聚类的少数几个。

    Us humans take it for granted how good we are categorizing and making sense of large volumes of data pretty quickly. Whether it’s a paragraph of text, or images on a screen, or a sequence of objects — humans are generally fairly efficient at making sense of whatever data the world throws at us.

    我们人类理所当然地认为我们在分类和快速理解大量数据方面有多出色。 无论是一段文字,还是屏幕上的图像,还是一系列对象,人类通常都能有效地理解世界向我们提供的任何数据。

    Given that a key aspect of developing A.I. and machine learning is getting machines to quickly make sense of large sets of input data, what shortcuts are there available?

    鉴于开发AI和机器学习的关键方面是使机器快速理解大量输入数据,有哪些捷径可用?

    Here, you can read about three clustering algorithms that machines can use to quickly make sense of large datasets. This is by no means an exhaustive list — there are other algorithms out there — but they represent a good place to start!

    在这里,您可以了解机器可以用来快速理解大型数据集的三种聚类算法。 这绝不是一个详尽的清单-那里还有其他算法-但这是一个不错的起点!

    You’ll find for each a quick summary of when you might use them, a brief overview of how they work, and a more detailed, step-by-step worked example. I believe it helps to understand an algorithm by actually carrying out yourself.

    您将找到每种使用时间的快速摘要,它们如何工作的简要概述以及更详细的分步工作示例。 我相信通过实际执行自己的算法有助于理解算法。

    If you’re really keen, you’ll find the best way to do this is with pen and paper. Go ahead — nobody will judge!

    如果您真的很热衷 ,您会发现使用笔和纸是实现此目的的最佳方法。 继续-没有人会判断!

    K均值聚类 (K-means clustering)

    在...时使用 (Use when...)

    …you have an idea of how many groups you’re expecting to find a priori.

    …您对希望找到先验的小组有一个想法。

    这个怎么运作 (How it works)

    The algorithm randomly assigns each observation into one of k categories, then calculates the mean of each category. Next, it reassigns each observation to the category with the closest mean before recalculating the means. This step repeats over and over until no more reassignments are necessary.

    该算法将每个观察随机分配到k个类别之一,然后计算每个类别的平均值 。 接下来,它将在重新计算均值之前将每个观察值分配给具有最均值的类别。 重复这一步骤,直到不再需要重新分配为止。

    工作实例 (Worked Example)

    Take a group of 12 football (or ‘soccer’) players who have each scored a certain number of goals this season (say in the range 3–30). Let’s divide them into separate clusters — say three.

    以一组12名足球(或“足球”)球员为例,他们每个赛季都进球数(例如3-30)。 让我们将它们分为单独的集群-说三个。

    Step 1 requires us to randomly split the players into three groups and calculate the means of each.

    步骤1要求我们将参与者随机分为三组,并计算每组的均值。

    Group 1
      Player A (5 goals),
      Player B (20 goals),
      Player C (11 goals)
    Group Mean = (5 + 20 + 11) / 3 = 12 goals
    
    Group 2
      Player D (5 goals),
      Player E (3 goals),
      Player F (19 goals)
    Group Mean = 9 goals
    
    Group 3
      Player G (30 goals),
      Player H (3 goals),
      Player I (15 goals)
    Group Mean = 16 goals

    Step 2: For each player, reassign them to the group with the closest mean. E.g., Player A (5 goals) is assigned to Group 2 (mean = 9). Then recalculate the group means.

    步骤2:对于每位玩家,将他们重新分配给具有最接近均值的组。 例如,玩家A(5个进球)被分配给第2组(平均值= 9)。 然后重新计算组均值。

    Group 1 (Old Mean = 12 goals)
      Player C (11 goals)
    New Mean = 11 goals
    
    Group 2 (Old Mean = 9 goals)
      Player A (5 goals),
      Player D (5 goals),
      Player E (3 goals),
      Player H (3 goals)
    New Mean = 4 goals
    
    Group 3 (Old Mean = 16 goals)
      Player G (30 goals),
      Player I (15 goals),
      Player B (20 goals),
      Player F (19 goals)
    New Mean = 21 goals

    Repeat Step 2 over and over until the group means no longer change. For this somewhat contrived example, this happens on the next iteration. Stop! You have now formed three clusters from the dataset!

    一遍又一遍地重复步骤2,直到组的含义不再改变为止。 对于这个有些人为的例子,这发生在下一次迭代中。 停止! 现在,您已经从数据集中形成了三个聚类!

    Group 1 (Old Mean = 11 goals)
      Player C (11 goals),
      Player I (15 goals)
    Final Mean = 13 goals
    
    Group 2 (Old Mean = 4 goals)
      Player A (5 goals),
      Player D (5 goals),
      Player E (3 goals),
      Player H (3 goals)
    Final Mean = 4 goals
    
    Group 3 (Old Mean = 21 goals)
      Player G (30 goals),
      Player B (20 goals),
      Player F (19 goals)
    Final Mean = 23 goals

    With this example, the clusters could correspond to the players’ positions on the field — such as defenders, midfielders and attackers.

    在这个例子中,集群可以对应于球员在场上的位置,例如防守者,中场球员和进攻者。

    K-means works here because we could have reasonably expected the data to fall naturally into these three categories.

    K均值之所以在这里起作用,是因为我们可以合理地预期数据自然会落入这三类。

    In this way, given data on a range of performance statistics, a machine could do a reasonable job of estimating the positions of players from any team sport — useful for sports analytics, and indeed any other purpose where classification of a dataset into predefined groups can provide relevant insights.

    这样,给定一系列性能统计数据,一台机器就可以合理地估算出任何团队运动项目中球员的位置,这对运动分析非常有用,并且在将数据集分类为预定义组的其他任何目的上都非常有用提供相关见解。

    更细的细节 (Finer details)

    There are several variations on the algorithm described here. The initial method of ‘seeding’ the clusters can be done in one of several ways.

    这里描述的算法有几种变体。 可以通过以下几种方式之一来完成“播种”群集的初始方法。

    Here, we randomly assigned every player into a group, then calculated the group means. This causes the initial group means to tend towards being similar to one another, which ensures greater repeatability.

    在这里,我们将每个玩家随机分配到一个组中,然后计算组均值。 这导致初始组手段趋于彼此相似,从而确保了更大的可重复性。

    An alternative is to seed the clusters with just one player each, then start assigning players to the nearest cluster. The returned clusters are more sensitive to the initial seeding step, reducing repeatability in highly variable datasets.

    另一种选择是给每个只有一个玩家的集群播种,然后开始将玩家分配到最近的集群。 返回的簇对初始播种步骤更加敏感,从而降低了高度可变的数据集中的可重复性。

    However, this approach may reduce the number of iterations required to complete the algorithm, as the groups will take less time to diverge.

    但是,这种方法可能会减少完成算法所需的迭代次数,因为组将花费更少的时间进行分离。

    An obvious limitation to K-means clustering is that you have to provide a priori assumptions about how many clusters you’re expecting to find.

    K均值聚类的一个明显限制是,您必须提供关于要找到多少个聚类的先验假设。

    There are methods to assess the fit of a particular set of clusters. For example, the Within-Cluster Sum-of-Squares is a measure of the variance within each cluster.

    有一些方法可以评估特定集群集的拟合度。 例如,集群内平方和是每个集群内方差的度量。

    The ‘better’ the clusters, the lower the overall WCSS.

    群集越“好”,则总体WCSS越低。

    层次聚类 (Hierarchical clustering)

    在...时使用 (Use when...)

    …you wish to uncover the underlying relationships between your observations.

    …您希望揭示观察结果之间的潜在关系。

    这个怎么运作 (How it works)

    A distance matrix is computed, where the value of cell (i, j) is a distance metric between observations i and j.

    计算距离矩阵,其中像元( i,j)的值是观测值ij之间的距离度量。

    Then, pair the closest two observations and calculate their average. Form a new distance matrix, merging the paired observations into a single object.

    然后,将最接近的两个观测值配对并计算它们的平均值。 形成一个新的距离矩阵,将成对的观测值合并为一个对象。

    From this distance matrix, pair up the closest two observations and calculate their average. Repeat until all observations are grouped together.

    从这个距离矩阵中,配对最接近的两个观测值并计算它们的平均值。 重复直到将所有观察结果分组在一起。

    工作的例子 (Worked example)

    Here’s a super-simplified dataset about a selection of whale and dolphin species. As a trained biologist, I can assure you we normally use much more detailed datasets for things like reconstructing phylogeny.

    这是有关鲸和海豚物种选择的超级简化数据集。 作为一名训练有素的生物学家,我可以向您保证,我们通常使用更详细的数据集来重建系统发育

    For now though, we’ll just look at the typical body lengths for these six species. We’ll be using just two repeated steps.

    现在,我们只看这六个物种的典型体长。 我们将仅使用两个重复步骤。

    Species          Initials  Length(m)
    Bottlenose Dolphin     BD        3.0
    Risso's Dolphin        RD        3.6
    Pilot Whale            PW        6.5
    Killer Whale           KW        7.5
    Humpback Whale         HW       15.0
    Fin Whale              FW       20.0

    Step 1: compute a distance matrix between each species. Here, we’ll use the Euclidean distance — how far apart are the data points?

    步骤1:计算每个物种之间的距离矩阵。 在这里,我们将使用欧几里得距离 -数据点相距多远?

    Read this exactly as you would a distance chart in a road atlas. The difference in length between any pair of species can be looked up by reading the value at the intersection of the relevant row and column.

    就像在道路地图集上绘制距离图一样,仔细阅读本章。 可以通过读取相关行和列相交处的值来查找任意一对物种之间的长度差异。

    BD   RD   PW   KW   HW
    RD  0.6                    
    PW  3.5  2.9               
    KW  4.5  3.9  1.0          
    HW 12.0 11.4  8.5  7.5     
    FW 17.0 16.4 13.5 12.5  5.0

    Step 2: Pair up the two closest species. Here, this will be the Bottlenose & Risso’s Dolphins, with an average length of 3.3m.

    步骤2:配对两个最接近的物种。 在这里,这将是宽吻海豚和海豚的海豚,平均长度为3.3m。

    Repeat Step 1 by recalculating the distance matrix, but this time merge the Bottlenose & Risso’s Dolphins into a single object with length 3.3m.

    通过重新计算距离矩阵来重复步骤1,但是这次将宽吻瓶和里索的海豚合并为一个长度为3.3m的单个对象。

    [BD, RD]   PW   KW   HW
    PW       3.2               
    KW       4.2   1.0          
    HW      11.7   8.5  7.5     
    FW      16.7  13.5 12.5  5.0

    Next, repeat Step 2 with this new distance matrix. Here, the smallest distance is between the Pilot & Killer Whales, so we pair them up and take their average — which gives us 7.0m.

    接下来 ,使用这个新的距离矩阵重复步骤2。 在这里,飞行员与虎鲸之间的距离最小,因此我们将它们配对并取它们的平均值,即为7.0m。

    Then, we repeat Step 1 — recalculate the distance matrix, but now we’ve merged the Pilot & Killer Whales into a single object of length 7.0m.

    然后 ,我们重复步骤1-重新计算距离矩阵,但是现在我们将“飞行员与杀人鲸”合并为一个长度为7.0m的对象。

    [BD, RD] [PW, KW]   HW
     [PW, KW]      3.7              
     HW           11.7      8.0     
     FW           16.7     13.0   5.0

    Next, repeat Step 2 with this distance matrix. The smallest distance (3.7m) is between the two merged objects — so now merge them into an even bigger object, and take the average (which is 5.2m).

    接下来 ,使用此距离矩阵重复步骤2。 最小的距离(3.7m)在两个合并的对象之间-现在将它们合并成更大的对象,并取平均值(即5.2m)。

    Then, repeat Step 1 and compute a new distance matrix, having merged the Bottlenose & Risso’s Dolphins with the Pilot & Killer Whales.

    然后 ,重复步骤1并计算新的距离矩阵,将宽吻鼻和里索的海豚与飞行员和虎鲸合并。

    [[BD, RD] , [PW, KW]]    HW
    HW                   9.8    
    FW                  14.8   5.0

    Next, repeat Step 2. The smallest distance (5.0m) is between the Humpback & Fin Whales, so merge them into a single object, and take the average (17.5m).

    接下来 ,重复步骤2。座头鲸和鳍鲸之间的最小距离(5.0m),因此将它们合并为一个对象,并取其平均值(17.5m)。

    Then, it’s back to Step 1 — compute the distance matrix, having merged the Humpback & Fin Whales.

    然后 ,返回到步骤1-合并了座头鲸和鳍鲸,计算距离矩阵。

    [[BD, RD] , [PW, KW]]
    [HW, FW]                  12.3

    Finally, repeat Step 2 — there is only one distance (12.3m) in this matrix, so pair everything into one big object. Now you can stop! Look at the final merged object:

    最后,重复步骤2-这个矩阵只有一个距离(12.3m),因此将所有东西配对成一个大物体。 现在您可以停止! 查看最终的合并对象:

    [[[BD, RD],[PW, KW]],[HW, FW]]

    It has a nested structure (think JSON), which allows it to be drawn up as a tree-like graph, or 'dendrogram'.

    它具有嵌套结构(例如JSON ),可以将其绘制为树状图或“树状图”。

    It reads in much the same way a family tree might. The nearer two observations are on the tree, the more similar or closely-related they are taken to be.

    它的读取方式与家谱的读取方式几乎相同。 树上的两个观测值越接近,它们被认为越相似或紧密相关。

    The structure of the dendrogram gives insight into how the dataset is structured.

    树状图的结构使您可以深入了解数据集的结构。

    In this example, there are two main branches, with Humpback Whale and Fin Whale on one side, and the Bottlenose Dolphin/Risso’s Dolphin and Pilot Whale/Killer Whale on the other.

    在此示例中,有两个主要分支,一侧是座头鲸和鳍鲸,另一侧是宽吻海豚/里索的海豚和领航鲸/杀人鲸。

    In evolutionary biology, much larger datasets with many more specimens and measurements are used in this way to infer taxonomic relationships between them.

    在进化生物学中,以这种方式使用具有更多标本和测量值的更大的数据集来推断它们之间的分类学关系。

    Outside of biology, hierarchical clustering has applications in data mining and machine learning contexts.

    在生物学之外,层次聚类在数据挖掘和机器学习环境中具有应用。

    The cool thing is that this approach requires no assumptions about the number of clusters you’re looking for.

    有趣的是,这种方法无需假设您要寻找的群集数量。

    You can split the returned dendrogram into clusters by “cutting” the tree at a given height. This height can be chosen in a number of ways, depending on the resolution at which you wish to cluster the data.

    您可以通过以指定高度“切割”树来将返回的树状图拆分为簇。 可以通过多种方式选择此高度,具体取决于您希望对数据进行聚类的分辨率。

    For instance, looking at the dendrogram above, if we draw a horizontal line at height = 10, we’d intersect the two main branches, splitting the dendrogram into two sub-graphs. If we cut at height = 2, we’d be splitting the dendrogram into three clusters.

    例如,查看上面的树状图,如果我们在height = 10处绘制一条水平线,我们将与两个主要分支相交,将树状图分为两个子图。 如果我们在高度= 2处进行切割,我们会将树状图分成三个簇。

    更细的细节 (Finer details)

    There are essentially three aspects in which hierarchical clustering algorithms can vary to the one given here.

    从本质上讲,层次聚类算法可以在三个方面与此处给出的算法有所不同。

    Most fundamental is the approach — here, we have used an agglomerative process, whereby we start with individual data points and iteratively cluster them together until we’re left with one large cluster.

    最基本的方法是这种方法-在这里,我们使用了一个凝聚过程,即从单个数据点开始,然后将它们迭代地聚类在一起,直到剩下一个大的聚类。

    An alternative (but more computationally intensive) approach is to start with one giant cluster, and then proceed to divide the data into smaller and smaller clusters until you’re left with isolated data points.

    另一种替代方法(但计算量更大)是从一个巨型群集开始,然后将数据分成越来越小的群集,直到剩下孤立的数据点为止。

    There are also a range of methods that can be used to calculate the distance matrices. For many purposes, the Euclidean distance (think Pythagoras’ Theorem) will suffice, but there are alternatives that may be more applicable in some circumstances.

    还有多种方法可用于计算距离矩阵。 对于许多目的,欧几里德距离(认为毕达哥拉斯定理)就足够了,但是有些替代方法可能在某些情况下更适用。

    Finally, the linkage criterion can also vary. Clusters are linked according to how close they are to one another, but the way in which we define ‘close’ is flexible.

    最后, 链接标准也可以变化。 群集根据彼此之间的接近程度进行链接,但是我们定义“关闭”的方式很灵活。

    In the example above, we measured the distances between the means (or ‘centroids’) of each group and paired up the nearest groups. However, you may want to use a different definition.

    在上面的示例中,我们测量了每个组的均值(或“质心”)之间的距离,并将最接近的组配对。 但是,您可能要使用其他定义。

    For example, each cluster is made up of several discrete points. You could define the distance between two clusters to be the minimum (or maximum) distance between any of their points — as illustrated in the figure below.

    例如,每个群集由几个离散点组成。 您可以将两个聚类之间的距离定义为它们的任意点之间的最小(或最大)距离,如下图所示。

    There are still other ways of defining the linkage criterion, which may be suitable in different contexts.

    还有其他定义链接标准的方式,可能适用于不同的上下文。

    图社区检测 (Graph Community Detection)

    使用时 (Use when)

    …you have data that can be represented as a network, or ‘graph’.

    …您拥有可以表示为网络或“图形”的数据。

    这个怎么运作 (How it works)

    A graph community is very generally defined as a subset of vertices which are more connected to each other than with the rest of the network.

    通常将图社区定义为顶点的子集,这些顶点彼此之间的联系比与网络其余部分的联系更多。

    Various algorithms exist to identify communities, based upon more specific definitions. Algorithms include, but are not limited to: Edge Betweenness, Modularity-Maximsation, Walktrap, Clique Percolation, Leading Eigenvector…

    基于更具体的定义,存在各种算法来标识社区。 算法包括但不限于:边缘中间性,模块化最大化,Walktrap,集团渗透,前导特征向量…

    工作的例子 (Worked example)

    Graph theory, or the mathematical study of networks, is a fascinating branch of mathematics that lets us model complex systems as an abstract collection of ‘dots’ (or vertices) connected by ‘lines’ (or edges).

    图论或网络的数学研究是数学的一个引人入胜的分支,它使我们可以将复杂的系统建模为由“线”(或 )连接的“点”(或顶点 )的抽象集合。

    Perhaps the most intuitive case-studies are social networks.

    也许最直观的案例研究是社交网络。

    Here, the vertices represent people, and edges connect vertices who are friends/followers. However, any system can be modelled as a network if you can justify a method to meaningfully connect different components.

    在这里,顶点代表人,边连接作为朋友/跟随者的顶点。 但是,如果可以证明一种方法有意义地连接不同的组件,则可以将任何系统建模为网络。

    Among the more innovative applications of graph theory to clustering include feature extraction from image data, and analysing gene regulatory networks.

    图论在聚类中的更多创新应用包括从图像数据中提取特征以及分析基因调控网络。

    As an entry-level example, take a look at this quickly put-together graph. It shows the eight websites I most recently visited, linked according to whether their respective Wikipedia articles link out to one another.

    作为入门级示例,请看一下此快速汇总的图表。 它显示了我最近访问的八个网站,这些网站根据各自的Wikipedia文章是否相互链接而链接在一起。

    You could assemble this data manually, but for larger-scale projects, it’s much quicker to write a Python script to do the same. Here’s one I wrote earlier.

    您可以手动组装此数据,但是对于大型项目,编写Python脚本来完成此操作要快得多。 这是我之前写的

    The vertices are colored according to their community membership, and sized according to their centrality. See how Google and Twitter are the most central?

    顶点根据其社区成员资格进行着色,并根据其中心性进行大小调整。 看看Google和Twitter是最核心的吗?

    Also, the clusters make pretty good sense in the real-world (always an important performance indicator).

    此外,集群在现实世界中非常有意义(始终是重要的性能指标)。

    The yellow vertices are generally reference/look-up sites; the blue vertices are all used for online publishing (of articles, tweets, or code); and the red vertices include YouTube, which was of course founded by former PayPal employees. Not bad deductions for a machine.

    黄色顶点通常是参考/查找站点; 蓝色顶点全部用于在线发布(文章,推文或代码的发布); 红色顶点包括YouTube,它当然是由前PayPal员工创立的。 对机器的扣减还不错。

    Aside from being a useful way to visualize large systems, the real power of networks comes from their mathematical analysis. Let’s start by translating our nice picture of the network into a more mathematical format. Below is the adjacency matrix of the network.

    除了是可视化大型系统的有用方法之外,网络的真正功能还在于它们的数学分析。 让我们首先将网络的漂亮图片转换成更数学的格式。 下面是网络的邻接矩阵

    GH Gl  M  P  Q  T  W  Y
    GitHub    0  1  0  0  0  1  0  0  
    Google    1  0  1  1  1  1  1  1
    Medium    0  1  0  0  0  1  0  0
    PayPal    0  1  0  0  0  1  0  1
    Quora     0  1  0  0  0  1  1  0
    Twitter   1  1  1  1  1  0  0  1
    Wikipedia 0  1  0  0  1  0  0  0
    YouTube   0  1  0  1  0  1  0  0

    The value at the intersection of each row and column records whether there is an edge between that pair of vertices.

    每行和列的交点处的值记录该对顶点之间是否存在边。

    For instance, there is an edge between Medium and Twitter (surprise, surprise!), so the value where their rows/columns intersect is 1. Similarly, there is no edge between Medium and PayPal, so the intersection of their rows/columns returns 0.

    例如,Medium和Twitter之间有一条边(惊讶,令人惊讶!),因此它们的行/列相交的值是1。类似地,Medium和PayPal之间没有边,因此它们的行/列的交点返回0。

    Encoded within the adjacency matrix are all the properties of this network — it gives us the key to start unlocking all manner of valuable insights.

    该网络的所有属性都编码在邻接矩阵中-它为我们提供了开始解锁各种有价值的见解的关键。

    For a start, summing any column (or row) gives you the degree of each vertex — i.e., how many others it is connected to. This is commonly denoted with the letter k.

    首先,求和任何列(或行)的总和即可得出每个顶点的度数 ,即它与多少个顶点相连。 通常用字母k表示。

    Likewise, summing the degrees of every vertex and dividing by two gives you L, the number of edges (or ‘links’) in the network. The number of rows/columns gives us N, the number of vertices (or ‘nodes’) in the network.

    同样,将每个顶点的度数相加并除以2可得到L ,即网络中边(或“链接”)的数量。 行数/列数为N ,即网络中的顶点数(或“节点”)。

    Knowing just k, L, N and the value of each cell in the adjacency matrix A lets us calculate the modularity of any given clustering of the network.

    只需知道kL,N和邻接矩阵A中每个像元的值,就可以计算模块化 网络的任何给定群集。

    Say we’ve clustered the network into a number of communities. We can use the modularity score to assess the ‘quality’ of this clustering.

    假设我们已将网络聚集到多个社区中。 我们可以使用模块化评分来评估该聚类的“质量”。

    A higher score will show we’ve split the network into ‘accurate’ communities, whereas a low score suggests our clusters are more random than insightful. The image below illustrates this.

    较高的分数将表明我们已将网络划分为“准确的”社区,而较低的分数表明我们的集群比有见地的更为随机。 下图说明了这一点。

    Modularity can be calculated using the formula below:

    模块化可以使用以下公式计算:

    That’s a fair amount of math, but we can break it down bit by bit and it’ll make more sense.

    这是相当多的数学运算,但是我们可以一点一点地分解它,这将更有意义。

    M is of course what we’re calculating — modularity.

    M当然是我们正在计算的-模块化。

    1/2L tells us to divide everything that follows by 2L, i.e., twice the number of edges in the network. So far, so good.

    1/2 L告诉我们将其后的所有内容除以2 L ,即网络中边数的两倍。 到目前为止,一切都很好。

    The Σ symbol tells us we’re summing up everything to the right, and lets us iterate over every row and column in the adjacency matrix A.

    Σ符号告诉我们我们在右边汇总所有内容,并让我们遍历邻接矩阵A中的每一行和每一列。

    For those unfamiliar with sum notation, the i, j = 1 and the N work much like nested for-loops in programming. In Python, you’d write it as follows:

    对于那些不熟悉总和表示法的人, i,j = 1N的工作方式很像编程中的嵌套for循环。 在Python中,您可以这样编写:

    sum = 0
    for i in range(1,N):
        for j in range(1,N):
            ans = #stuff with i and j as indices 
        sum += ans

    So what is #stuff with i and j in more detail?

    那么, #stuff with i and j是什么呢?

    Well, the bit in brackets tells us to subtract ( k_i k_j ) / 2L from A_ij.

    好吧,方括号中的位告诉我们从A_ij减去( k_i k_j)/ 2L

    A_ij is simply the value in the adjacency matrix at row i, column j.

    A_ij仅是第i j列的邻接矩阵中的值。

    The values of k_i and k_j are the degrees of each vertex — found by adding up the entries in row i and column j respectively. Multiplying these together and dividing by 2L gives us the expected number of edges between vertices i and j if the network were randomly shuffled up.

    k_ik_j的值是每个顶点的度数-通过分别将第i行和第j列中的条目相加得出。 如果将网络随机改组,则将它们相乘并除以2 L可得到顶点ij之间的预期边数。

    Overall, the term in the brackets reveals the difference between the network’s real structure and the expected structure it would have if randomly reassembled.

    总体而言,方括号中的术语揭示了网络的实际结构与如果随机重组将具有的预期结构之间的差异。

    Playing around with the values shows that it returns its highest value when A_ij = 1, and ( k_i k_j ) / 2L is low. This means we see a higher value if there is an ‘unexpected’ edge between vertices i and j.

    数值的计算表明,当A_ij = 1且( k_i k_j)/ 2L为低时,它将返回其最大值。 这意味着如果在顶点ij之间存在“意外”边缘,则我们看到一个更高的值

    Finally, we multiply the bracketed term by whatever the last few symbols refer to.

    最后,我们将括号中的术语乘以最后几个符号所指的内容。

    The ?c_i, c_j is the fancy-sounding but totally harmless Kronecker-delta function. Here it is, explained in Python:

    ?c _i, c _j是听起来很花哨但完全无害的Kronecker-delta函数。 在Python中进行了解释:

    def kroneckerDelta(ci, cj):
        if ci == cj:
            return 1
        else:
            return 0
            
    kroneckerDelta("A","A")
    #returns 1
    
    kroneckerDelta("A","B")
    #returns 0

    Yes — it really is that simple. The Kronecker-delta function takes two arguments, and returns 1 if they are identical, otherwise, zero.

    是的-真的就是这么简单。 Kronecker-delta函数采用两个参数,如果相同则返回1,否则返回零。

    This means that if vertices i and j have been put in the same cluster, then ?c_i, c_j = 1. Otherwise, if they are in different clusters, the function returns zero.

    这意味着,如果将顶点ij放在同一簇中,则?c _i, c _j = 1 。 否则,如果它们位于不同的群集中,则该函数将返回零。

    As we are multiplying the bracketed term by this Kronecker-delta function, we find that for the nested sum Σ, the outcome is highest when there are lots of ‘unexpected’ edges connecting vertices assigned to the same cluster.

    当我们将括号中的项乘以该Kronecker-delta函数时,我们发现对于嵌套的总和Σ ,当有很多“意外”边缘连接分配给同一聚类的顶点时,结果最高。

    As such, modularity is a measure of how well-clustered the graph is into separate communities.

    因此,模块化是衡量图表在不同社区中的聚集程度的一种度量。

    Dividing by 2L bounds the upper value of modularity at 1. Modularity scores near to or below zero indicate the current clustering of the network is really no use. The higher the modularity, the better the clustering of the network into separate communities.

    除以2L会将模块性的上限定为1。接近或低于零的模块性分数表明该网络的当前集群实际上没有用。 模块化程度越高,将网络更好地聚集到单独的社区中就越好。

    By maximising modularity, we can find the best way of clustering the network.

    通过最大程度地提高模块化,我们可以找到群集网络的最佳方法。

    Notice that we have to pre-define how the graph is clustered to find out how ‘good’ that clustering actually is.

    注意,我们必须预先定义图的聚类方式,以找出聚类的实际效果。

    Unfortunately, employing brute force to try out every possible way of clustering the graph to find which has the highest modularity score would be computationally impossible beyond a very limited sample size.

    不幸的是,在非常有限的样本量之外,采用蛮力尝试对图进行聚类以找到具有最高模块化得分的所有可能方法,在计算上都是不可能的。

    Combinatorics tells us that for a network of just eight vertices, there are 4140 different ways of clustering them. A network twice the size would have over ten billion possible ways of clustering the vertices.

    组合法告诉我们,对于只有八个顶点的网络,有4140种不同的方法将它们聚类。 两倍大小的网络将有超过一百亿种可能的顶点聚类方法。

    Doubling the network again (to a very modest 32 vertices) would give 128 septillion possible ways, and a network of eighty vertices would be cluster-able in more ways than there are atoms in the observable universe.

    将网络再次加倍(到非常适度的32个顶点)将提供128亿种可能的方式,并且与可观察的宇宙中存在的原子相比,具有80个顶点的网络将以更多的方式可集群。

    Instead, we have to turn to a heuristic method that does a reasonably good job at estimating the clusters that will produce the highest modularity score, without trying out every single possibility.

    取而代之的是,我们必须转向一种启发式方法,该方法在估计将产生最高模块性得分的集群方面做得相当好,而无需尝试每种可能性。

    This is an algorithm called Fast-Greedy Modularity-Maximization, and it’s somewhat analogous to the agglomerative hierarchical clustering algorithm describe above. Instead of merging according to distance, ‘Mod-Max’ merges communities according to changes in modularity.

    这是一种称为快速贪婪模块化最大化的算法它有点类似于上面描述的聚集层次聚类算法。 'Mod-Max'并非根据距离进行合并,而是根据模块化的变化来合并社区。

    Here’s how it goes:

    这是怎么回事:

    Begin by initially assigning every vertex to its own community, and calculating the modularity of the whole network, M.

    首先将每个顶点分配给它自己的社区,然后计算整个网络的模块化M。

    Step 1 requires that for each community pair linked by at least a single edge, the algorithm calculates the resultant change in modularity ΔM if the two communities were merged into one.

    步骤1要求,对于至少由一条边链接的每个社区对,如果将两个社区合并为一个社区,该算法将计算模块性ΔM的最终变化。

    Step 2 then takes the pair of communities that produce the biggest increase in ΔM, which are then merged. Calculate the new modularity M for this clustering, and keep a record of it.

    然后, 步骤2选取产生最大ΔM的一对社区,然后将其合并。 计算该集群的新模块性M ,并对其进行记录。

    Repeat steps 1 and 2 — each time merging the pair of communities for which doing so produces the biggest gain in ΔM, then recording the new clustering pattern and its associated modularity score M.

    重复步骤1和2-每次合并一对社区,这样做会在ΔM中产生最大的收益然后记录新的聚类模式及其相关的模块化评分M。

    Stop when all the vertices are grouped into one giant cluster. Now the algorithm checks the records it kept as it went along, and identifies the clustering pattern that returned the highest value of M. This is the returned community structure.

    所有顶点分组为一个大簇时停止 。 现在,该算法检查其保留的记录,并确定返回最大M值的聚类模式。 这是返回的社区结构。

    更细的细节 (Finer details)

    Whew! That was computationally intensive, at least for us humans.

    ew! 这是计算密集型的,至少对于我们人类而言。

    Graph theory is a rich source of computationally challenging, often NP-hard problems — yet it also has incredible potential to provide valuable insights into complex systems and datasets.

    图论是计算难题(通常是NP难题)的丰富来源,但它也具有令人难以置信的潜力,可以为复杂的系统和数据集提供有价值的见解。

    Just ask Larry Page, whose eponymous PageRank algorithm — which helped propel Google from start-up to basically world domination in less than a generation — was based entirely in graph theory.

    只需问问拉里·佩奇(Larry Page),他的同名PageRank算法完全基于图论,该算法在不到一代人的时间里就将Google从新兴企业推向了世界统治。

    Community detection is a major focus of current research in graph theory, and there are plenty of alternatives to Modularity-Maximization, which while useful, does have some drawbacks.

    社区检测是当前图论研究的主要重点,模块化最大化有许多替代方案,尽管它们很有用,但确实存在一些缺点。

    For a start, its agglomerative approach often sees small, well-defined communities swallowed up into larger ones. This is known as the resolution limit — the algorithm will not find communities below a certain size.

    首先,它的聚集方法通常会看到小型的,定义明确的社区被吞并为较大的社区。 这称为分辨率限制 -算法将找不到小于特定大小的社区。

    Another challenge is that rather than having one distinct, easy-to-reach global peak, the Mod-Max approach actually tends to produce a wide ‘plateau’ of many similar high modularity scores — making it somewhat difficult to truly identify the absolute maximum score.

    另一个挑战是,Mod-Max方法并没有产生一个清晰易懂的全球峰值,而是趋向于产生许多相似的高模块评分的宽广的“平台”,这使得真正识别绝对最大评分有些困难。

    Other algorithms use different ways to define and approach community detection.

    其他算法使用不同的方式来定义和处理社区检测。

    Edge-Betweenness is a divisive algorithm, starting with all vertices grouped in one giant cluster. It proceeds to iteratively remove the least ‘important’ edges in the network, until all vertices are left isolated. This produces a hierarchical structure, with similar vertices closer together in the hierarchy.

    Edge-Betweenness是一种分割算法,从将所有顶点分组到一个巨型簇中开始。 进行迭代地删除网络中最不重要的边缘,直到所有顶点都保持隔离。 这将产生一个层次结构,相似的顶点在层次结构中靠得更近。

    Another algorithm is Clique Percolation, which takes into account possible overlap between graph communities.

    另一个算法是Clique Percolation ,它考虑了图社区之间可能的重叠。

    Yet another set of algorithms are based on random-walks across the graph, and then there are spectral clustering methods which start delving into the eigendecomposition of the adjacency matrix and other matrices derived therefrom. These ideas are used in feature extraction in, for example, areas such as computer vision.

    另一组算法是基于整个图的随机游动 ,然后是频谱聚类方法,它们开始研究邻接矩阵和从中得出的其他矩阵的特征分解。 这些想法用于例如计算机视觉等领域的特征提取。

    It’d be well beyond the scope of this article to give each algorithm its own in-depth worked example. Suffice to say that this is an active area of research, providing powerful methods to make sense of data that even a generation ago would have been extremely difficult to process.

    为每个算法提供自己的深入工作示例将远远超出本文的范围。 可以说这是一个活跃的研究领域,它提供了强大的方法来理解数据,即使是一代人以前也很难处理这些数据。

    结论 (Conclusion)

    Hopefully this article has informed and inspired you to better understand how machines can make sense of data. The future is a rapidly changing place, and many of those changes will be driven by what technology becomes capable of in the next generation or two.

    希望本文能为您提供启发并启发您更好地了解机器如何理解数据。 未来是一个瞬息万变的地方,其中许多变化将取决于下一代技术的能力。

    As outlined in the introduction, machine learning is an extraordinarily ambitious field of research, in which massively complex problems require solving in as accurate and as efficient a way possible. Tasks that come naturally to us humans require innovative solutions when taken on by machines.

    正如导言中概述的那样,机器学习是一个非常宏大的研究领域,其中庞大的复杂问题需要以尽可能准确和有效的方式来解决。 对于人类来说,自然而然的任务需要由机器承担的创新解决方案。

    There’s still plenty of progress to be made, and whoever contributes the next breakthrough idea will no doubt be generously rewarded. Maybe someone reading this article will be behind the next powerful algorithm?

    仍有大量的进步,无论谁贡献下一个突破性的想法,无疑都会得到丰厚的回报。 也许有人读这篇文章会成为下一个强大算法的幕后推手?

    All great ideas have to start somewhere!

    所有好主意都必须从某个地方开始!

    翻译自: https://www.freecodecamp.org/news/how-machines-make-sense-of-big-data-an-introduction-to-clustering-algorithms-4bd97d4fbaba/

    层次聚类算法 算法

    更多相关内容
  • 层次聚类算法的实现

    千次阅读 多人点赞 2022-04-12 16:00:32
    层次聚类算法介绍2.1 层次聚类算法原理2.2 层次聚类算法步骤2.3 层次聚类算法分类3.层次聚类算法实现(代码如下)3.1 相关包导入3.2 生成测试数据集3.3 层次聚类实现&画出树状图3.4 获取聚类结果3.5 对比不同方法...

    1.作者介绍

    杨金花,女,西安工程大学电子信息学院,21级硕士研究生
    研究方向:基于学习方法的运动目标检测
    电子邮件:2902551510@qq.com

    孟莉苹,女,西安工程大学电子信息学院,2021级硕士研究生,张宏伟人工智能课题组
    研究方向:机器视觉与人工智能
    电子邮件:2425613875@qq.com

    2.层次聚类算法介绍

    2.1 层次聚类算法原理

     聚类就是对大量未知标注的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据比较相似,类别之间的数据相似度比较小。
     层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。算法流程展示如图所示。
    

    在这里插入图片描述

    2.2 层次聚类算法步骤

    假设有6个样本点{A,B,C,D,E,F},对于层次聚类来说,步骤如下:
    (1)假设每个样本点都为一个簇类,计算每个簇类间的相似度,得到相似矩阵;
    (2)寻找各个类之间最近的两个类,即若B和C的相似度最高,合并簇类B和C为一个簇类。现在我们还有五个簇类,分别为A,BC,D,E,F;
    (3)更新簇类间的相似矩阵,若簇类BC和D的相似度最高,合并簇类BC和D为一个簇类。现在我们还有四个簇类,分别为A,BCD,E,F;
    (4)更新簇类间的相似矩阵,若簇类E和F的相似度最高,合并簇类E和F为一个簇类。现在我们还有3个簇类,分别为A,BCD,EF。
    (5)重复第四步,簇类BCD和簇类EF的相似度最高,合并该两个簇类,现在我们还有2个簇类,分别为A,BCDEF。
    (6)最后合并簇类A和BCDEF为一个簇类,层次聚类算法结束。
    层次聚类实现过程如图2所示。

    图2. 层次聚类实现过程示例图

    2.3 层次聚类算法分类

    自顶向下的层次聚类算法(Divisive):
    Divisive 层次聚类:又称自顶向下(top-down)的层次聚类,最开始所有的对象均属于一个cluster,每次按一定的准则将某个cluster 划分为多个cluster,如此往复,直至每个对象均属于某一个cluster。实现过程示意图如下。

    图3. Divisive实现过程示例图

    自底向上的层次聚类算法(Agglomerative):
    Agglomerative 层次聚类:又称自底向上(bottom-up)的层次聚类,每一个对象最开始都是一个cluster,每次按一定的准则将最相近的两个cluster合并生成一个新的cluster,如此往复,直至最终所有的对象都属于一个cluster。

    图4. Divisive实现过程示例图

    3.层次聚类算法实现(代码如下)

    3.1 相关包导入

    from scipy.cluster.hierarchy import linkage     #导入linage函数用于层次聚类
    from scipy.cluster.hierarchy import dendrogram  #dendrogram函数用于将聚类结果绘制成树状图
    from scipy.cluster.hierarchy import fcluster    #fcluster函数用于提取出聚类的结果
    from sklearn.datasets import make_blobs         #make_blobs用于生成聚类算法的测试数据
    from sklearn.cluster import AgglomerativeClustering  #自底向上层次聚类算法
    import matplotlib.pyplot as plt                 #导入matplotlib绘图工具包
    

    3.2 生成测试数据集

    #生成测试数据
    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c='b')
    plt.show()
    #from scipy.cluster.hierarchy import linkage
    

    图5. 测试数据可视化展示

    3.3 层次聚类实现&画出树状图

    #层次聚类实现
    #from scipy.cluster.hierarchy import dendrogram
    Z = linkage(X,  method='ward', metric='euclidean')
    print(Z.shape)
    print(Z[: 5])
    
    #画出树状图
    #from scipy.cluster.hierarchy import fcluster
    plt.figure(figsize=(10, 8))
    dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15,
               show_contracted=True)
    plt.show()
    

    图6. 树状图可视化展示

    3.4 获取聚类结果

    #根据临界距离返回聚类结果
    d = 15
    labels_1 = fcluster(Z, t=d, criterion='distance')
    print(labels_1[: 100])  # 打印聚类结果
    print(len(set(labels_1)))  # 看看在该临界距离下有几个 cluster
    
    #根据聚类数目返回聚类结果
    k = 3
    labels_2 = fcluster(Z, t=k, criterion='maxclust')
    print(labels_2[: 100])
    list(labels_1) == list(labels_2)  # 看看两种不同维度下得到的聚类结果是否一致
    
    #聚类的结果可视化,相同的类的样本点用同一种颜色表示
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism')
    plt.show()
    

    图7. 聚类结果可视化展示

    3.5完整代码

    from scipy.cluster.hierarchy import linkage     #导入linage函数用于层次聚类
    from scipy.cluster.hierarchy import dendrogram  #dendrogram函数用于将聚类结果绘制成树状图
    from scipy.cluster.hierarchy import fcluster    #fcluster函数用于提取出聚类的结果
    from sklearn.datasets import make_blobs         #make_blobs用于生成聚类算法的测试数据
    from sklearn.cluster import AgglomerativeClustering  #自底向上层次聚类算法
    import matplotlib.pyplot as plt                 #导入matplotlib绘图工具包
    
    #生成测试数据
    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c='b')
    plt.show()
    #from scipy.cluster.hierarchy import linkage
    
    #层次聚类实现
    #from scipy.cluster.hierarchy import dendrogram
    Z = linkage(X,  method='ward', metric='euclidean')
    print(Z.shape)
    print(Z[: 5])
    
    
    #画出树状图
    #from scipy.cluster.hierarchy import fcluster
    plt.figure(figsize=(10, 8))
    dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15,
               show_contracted=True)
    plt.show()
    
    # 根据临界距离返回聚类结果
    d = 15
    labels_1 = fcluster(Z, t=d, criterion='distance')
    print(labels_1[: 100])  # 打印聚类结果
    print(len(set(labels_1)))  # 看看在该临界距离下有几个 cluster
    
    # 根据聚类数目返回聚类结果
    k = 3
    labels_2 = fcluster(Z, t=k, criterion='maxclust')
    print(labels_2[: 100])
    list(labels_1) == list(labels_2)  # 看看两种不同维度下得到的聚类结果是否一致
    
    # 聚类的结果可视化,相同的类的样本点用同一种颜色表示
    plt.figure(figsize=(10, 8))
    plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism')
    plt.show()
    
    

    3.6 对比不同方法聚类效果

    from time import time
    import numpy as np
    from sklearn.datasets import make_blobs
    from scipy.cluster.hierarchy import linkage, fcluster
    from sklearn.metrics.cluster import adjusted_mutual_info_score
    import matplotlib.pyplot as plt
    
    #生成样本点
    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels = make_blobs(n_samples=750, centers=centers,
                           cluster_std=0.4, random_state=0)
    
    
    #可视化聚类结果
    def plot_clustering(X, labels, title=None):
        plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='prism')
        if title is not None:
            plt.title(title, size=17)
        plt.axis('off')
        plt.tight_layout()
    
    #进行 Agglomerative 层次聚类
    linkage_method_list = ['single', 'complete', 'average', 'ward']
    
    plt.figure(figsize=(10, 8))
    ncols, nrows = 2, int(np.ceil(len(linkage_method_list) / 2))
    plt.subplots(nrows=nrows, ncols=ncols)
    for i, linkage_method in enumerate(linkage_method_list):
        print('method %s:' % linkage_method)
        start_time = time()
        Z = linkage(X, method=linkage_method)
        labels_pred = fcluster(Z, t=3, criterion='maxclust')
        print('Adjust mutual information: %.3f' % adjusted_mutual_info_score(labels, labels_pred))
        print('time used: %.3f seconds' % (time() - start_time))
        plt.subplot(nrows, ncols, i + 1)
        plot_clustering(X, labels_pred, '%s linkage' % linkage_method)
    plt.show()
    

    图8. 不同聚类方法结果展示

    AMI评估结果
    该量越接近于 1 则说明聚类算法产生的类越接近于真实情况。从右图的AMI量的表现来看,Single-link 方法下的层次聚类结果最差,它几乎将所有的点都聚为一个 cluster,而其他两个 cluster 则都仅包含个别稍微有点偏离中心的样本点,而另外三种聚类方法效果都还可以。结果如下图

    图9. AMI评估结果

    4.参考链接

    博客参考链接:
    https://cloud.tencent.com/developer/article/1800586

    展开全文
  • 层次聚类算法原理总结

    千次阅读 2022-01-16 01:19:58
    点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据,从而形成树形的聚类结构...

    点击上方“小白学视觉”,选择加"星标"或“置顶

    重磅干货,第一时间送达

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

    目录


    1. 层次聚类算法原理

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

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

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

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

    1.层次据类算法原理

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

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

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

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

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

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

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

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

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

    597a3a2d2f28640dbe15e99cc8902931.png

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

    b50426c74eb3b6b75e667066a43c8f01.png

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

    eb75dbfd4e32225ffeb080b7643f904c.png

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

    61578ddd10dfeee8b77912086bd5d1ce.png

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

    8a73175fb3104b7d5617a91d771e3d41.png

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

    1f12e0645a5ce29b79e0eb6e01ef7e69.png

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

    a20bb9f062245150aef80423178c143f.png

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

    3bda0dd6128bfa292385bd100c0d1067.png

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

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

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

    • 最小距离

    • 最大距离

    • 平均距离

    • 中心距离

    • 最小方差法

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

    768b712e135664c23937902d05ab0308.png

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

    ba102675d8681a34658323ee4b906fc3.png

    优点:

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

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

    ce8a924e99390d093de84f7bd02854cf.png

    例1

    04eb556efd7ac572d497590e091384d1.png

    例2

    缺点:

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

    a39c7504631584ee3b94d4f9999187dd.png

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

    3c4e2a4a2740454c6d700fb3aa37101d.png

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

    8661560baf9eeb87dc280feabb5dee94.png

    优点:

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

    fd17e817be0504933f3d78cef6aa7d08.png

    缺点:

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

    fe5ab9ad074dad3c76ed93630c30ec73.png

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

    278f01ad0b1abf5af20c7e19694daf9d.png

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

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

    d2df0ed83d7765e41e9abd0a47e75492.png

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

    优点:

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

    缺点:

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

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

    23eeaf1f614a4e4aec32f43261bf5eaf.png

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

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

    8fa189579a8104bd9b68ad1f3c4be50e.png

    优点:

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

    缺点:

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

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

    1)欧拉距离(Euclidean distance):

    3f46451dc5ab3b40979c1cb26729c7dc.png

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

    2e5a7600589146692454abdaae31ca3a.png

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

    50949946e84cf6e1297a633d96a6d182.png

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

    a47760bdf820f0a2e8b592e7d24c6984.png

    5)马氏距离(Mahalanobis distance):

    eb65ac1a88057595eabce7e63e49ec98.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)实现的,连通性矩阵的元素只有1和0两种结果,1表示两个样本是连通的,0表示两个样本不连通,我们只对连通性的样本进行距离计算并融合,这一过程大大降低了计算量,常采用sklearn.neighbors.kneighbors_graph来构建连接矩阵。

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

    # 生成瑞士卷数据集,容量为15000
    n_samples = 15000
    noise = 0.05
    X, _ = 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() - st
    label = 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)

    结果:

    a64d91ca077e7deb855ff592e4309db1.png

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

    # 定义不包含样本点在内的10个最近邻的连通样本点
    from sklearn.neighbors import kneighbors_graph
    connectivity = 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() - st
    label = ward.labels_
    print("Elapsed time: %.2fs" % elapsed_time)
    print("Number of points: %i" % label.size)
    
    # #############################################################################
    # Plot result
    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(float(l) / np.max(label + 1)),
                   s=20, edgecolor='k')
    plt.title('With connectivity constraints (time %.2fs)' % elapsed_time)
    
    plt.show()

    结果:

    3064f4b6be85fa04db9669a1b03dc380.png

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

    6.层次聚类算法的优点

    优点:

    算法简单,易于理解

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

    缺点:

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

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

    参考:

    https://towardsdatascience.com

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

    下载1:OpenCV-Contrib扩展模块中文版教程

    在「小白学视觉」公众号后台回复:扩展模块中文教程即可下载全网第一份OpenCV扩展模块教程中文版,涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

    下载2:Python视觉实战项目52讲

    在「小白学视觉」公众号后台回复:Python视觉实战项目即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目,助力快速学校计算机视觉。

    下载3:OpenCV实战项目20讲

    在「小白学视觉」公众号后台回复:OpenCV实战项目20讲即可下载含有20个基于OpenCV实现20个实战项目,实现OpenCV学习进阶。

    交流群

    欢迎加入公众号读者群一起和同行交流,目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~

    4842929f1a8ec135e5b883b40de507a4.png

    6c2ce3a3e888c39069ac1473771629ba.png

    展开全文
  • 层次聚类算法介绍

    千次阅读 2020-07-15 00:23:38
    层次聚类算法介绍1层次聚类的定义思考示例问题:2距离与相似性2.1常用的计算距离的方法2.2计算指标相似性的方法1)余弦计算公式:![000](https://img-blog.csdnimg.cn/20200714234628463.png)2)相关计算公式:3合并...


    1.本博客是观看清风数学建数学建模课程后有所感想记录的笔记,有想要深入学习的朋友可以购买观看课程:https://weidian.com/?userid=1372657210
    2.感兴趣的推荐看B站数学建模试看课程:
    https://www.bilibili.com/video/av20238704

    1层次聚类的定义

    聚类就是对大量未知标注的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据比较相似,类别之间的数据相似度比较小,属于无监督学习。
    层次聚类的合并算法通过计算两类数据点间的距离,对最为接近的两类数据点进行组合,并反复迭代这一过程,直到将所有数据点合成一类,并生成聚类谱系图。
    数学建模
    层次聚类

    思考示例问题:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2距离与相似性

    2.1常用的计算距离的方法

    在这里插入图片描述
    Ps:其中绝对值距离一般应用于网状道路距离,一般采用欧氏距离。

    2.2计算指标相似性的方法

    1)余弦计算公式:000

    2)相关计算公式:

    在这里插入图片描述在这里插入图片描述

    3合并算法思想

    思想:将两个簇合成为一个簇,计算这个簇与其他簇之间的距离,再进行合并。
    簇与簇之间的常用距离:重心法,最短距离法,最长距离法,组间平均连接法,组内平均链接法(下图顺序一致)

    1)重心法

    在这里插入图片描述

    2)最短距离法

    在这里插入图片描述

    3)最长距离法

    在这里插入图片描述

    4)组间平均连接法

    在这里插入图片描述

    5)组内平均链接法

    在这里插入图片描述

    4算法流程

    程序执行过程:

    	系统(层次)聚类的算法流程:
    	1.将每个对象看作一类,计算两两之间的最小距离;
    	2.将距离最小的两个类合并成一个新类;
    	3.新计算新类与所有类之间的距离;
    	4.重复2、3两步,直到所有类最后合并成一类;
    	5.结束。
    

    程序流程图

    5 示例与分析

    根据所给的图,以及距离矩阵,求解聚类结果:
    题目信息

    5.1基于最小值的层次聚类

    计算结果如下:
    最小值层次聚类结果

    优缺点

    优点:可以处理非椭圆形状
    在这里插入图片描述
    缺点:对噪声点和异常值敏感

    5.2 基于最大值的层次聚类

    计算结果如下:
    最大值层次聚类结果

    优缺点

    优点:不容易受噪声点和异常值影响
    缺点:1.往往打破大聚类 2.偏向球状星团
    在这里插入图片描述

    5.3基于组平均

    计算结果如下:
    组平均层次聚类

    优缺点 (MIN和MAX之间的折中)

    优点:不易受噪声和异常值影响
    缺点:偏向球状星团

    6需注意的问题

    1.对于一个实际问题要根据分类的目的来选取指标,指标选取的不同分类结果一般也不同。
    2.样品间距离定义方式的不同,聚类结果一般也不同。
    3.聚类方法的不同,聚类结果一般也不同 (尤其是样品特别多的时候)。最好能通过各种方法找出其中的共性。
    4.要注意指标的量纲,量纲差别太大会导致聚类结果不合理。
    5.聚类分析的结果可能不令人满意,因为我们所做的是一个数学的处理,对于结果我们要找到一个合理的解释。
    

    对比Kmean算法

    k均值需要定义聚类簇数k,而层次聚类不需要,层次聚类可以根据聚类谱系图选择聚类的簇个数。

    展开全文
  • 层次聚类matlab代码层次聚类算法 matlab代码,采用了单链接,完全链接和平均链接算法的层次聚类算法
  • 先介绍下聚类的不同类型,通常有以下几种:(1)层次的与划分的:如果允许簇具有子簇,则我们得到一个层次聚类层次聚类是嵌套簇的集族,组织成一棵树。划分聚类简单地将数据对象划分成不重叠的子集(簇),使得每个...
  • 层次聚类算法及通过sklearn调用方式
  • 机器学习实战——层次聚类算法

    千次阅读 2019-01-24 16:02:27
    机器学习实战——层次聚类算法1 层次聚类概述2 sklearn中的实现 1 层次聚类概述 层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构。 数据集的划分可采用"自底向上"的聚合策略,也可采用&...
  • 尽管基于划分的聚类算法能够实现把数据集划分成指定数量的簇,但是在某些情况下,需要把数据集划分成不同层上的簇:比如,作为一家公司的人力资源部经理,你可以把所有的雇员组织成较大的簇,如主管、经理和职员;...
  • 聚类算法(4)--Hierarchical clustering层次聚类

    万次阅读 多人点赞 2018-11-07 17:45:47
    一、层次聚类 1、层次聚类的原理及分类 2、层次聚类的流程 3、层次聚类的优缺点 二、python实现 1、sklearn实现 2、scipy实现 树状图分类判断 一、层次聚类 1、层次聚类的原理及分类 1)层次法...
  • 该记录链接工具基于单链接层次聚类。 您可以阅读题为的论文。 要运行桌面工具,我们需要一个配置文件,其中配置了输入数据文件。 这里我们放了一个示例配置文件。 我们鼓励您使用。 但是如果你随意使用 .xml 文件,...
  • 1. 层次聚类 1.1 层次聚类的原理及分类 1)层次法(Hierarchicalmethods):先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算类与类之间的距离,将距离最近的类合并为一个大类。不停的合并...
  • 关于聚类算法的一些理论和定义,请参照博客点击打开链接http://blog.sina.com.cn/s/blog_62f3c4ef01014uhe.html 和 点击打开链接http://blog.csdn.net/a1b2c3d4123456/article/details/45966429 这两篇文章。 ...
  • 聚类算法层次聚类

    千次阅读 2019-05-02 21:41:54
    一. 层次聚类 层次聚类(hierarchical ...层次聚类算法的优势在于,可以通过绘制树状图(dendrogram),帮助我们使用可视化的方式来解释聚类结果。层次聚类的另一个优点就是,它不需要事先指定簇的数量。 二. ...
  • 小白都能了解的聚类算法之三(层次聚类)

    千次阅读 多人点赞 2020-03-29 12:07:22
    层次聚类(Hierarchical Clustering)通过计算各类别中数据之间的相似度,最终创建一棵有层次的嵌套聚类树。起核心思想是基于各"簇"之间的相似度,在不同层次上分析数据,得到最终的树形聚类结构。 2.agglomerative与...
  • 在之前的系列中,大部分都是关于监督学习(除了PCA那一节),接下来的几篇主要分享一下关于非监督学习中的聚类算法(clustering algorithms)。 一、先了解一下聚类分析(clustering analysis) Cluster analysis or...
  • 层次聚类算法

    2021-12-04 22:24:25
    相比于k-means算法,层次聚类算法无需人为的划分k值,也就是分为几个簇。而是通过计算各点间的距离,最后再将其划分为一类。如此循环迭代,最终实现无监督学习的自行分类。具有很好的识别性以及科学性,该算法中....
  • 关于层次聚类(hierarchical clustering)的基本步骤: 1、假设每个样本为一类,计算每个类的距离,也就是相似度 2、把最近的两个合为一新类,这样类别数量就少了一个 ...本资源详细介绍层次聚类算法
  • 凝聚聚类与层次聚类

    2022-03-06 10:48:28
    凝聚聚类(agglomerative clustering)指的是许多基于相同原则构建的聚类算法,这一原则是:算法首先声明每个点是自己的簇,然后合并两个最相似的簇,直到满足某种停止准则为止。scikit-learn 中实现的停止准则是簇...
  • 本篇文章我们继续介绍另一种聚类算法——Birch模型,相对于K-means和DBSCAN,Birch的应用并没有那么广泛,不过它也有一些独特的优势,Birch算法比较适合于数据量大,类别数K也比较多的情况,它运行速度很快,只需要...
  • 聚类算法——python实现层次聚类(AGNES)

    万次阅读 多人点赞 2017-05-15 20:39:35
    AGNES算法是自底向上的层次聚类算法。开始时将数据集中的每个样本初始化为一个簇,然后找到距离最近的两个簇,将他们合并,不断重复这个过程,直达到到预设的聚类数目为止。 计算距离的三个公式: AGNES算法...
  • 分布式类支持向量机聚类算法研究.pdf
  • Python学习3-层次聚类

    千次阅读 2021-12-08 20:37:38
    0.层次聚类的概念 层次聚类和k-means一样都是很常用的聚类方法。...关于层次聚类算法的python实现 - 简书 (jianshu.com)https://www.jianshu.com/p/916aab25cda7 0.1 聚合层次聚类 每一个点初始为1类,得到N(样本
  • 聚类算法(二)--层次聚类

    千次阅读 2017-11-29 12:19:32
    本文主要介绍层次聚类法的基本原理、距离计算方法、算法的优缺点,以及R语言实战。
  • 看了西关书的聚类算法,算法原理很容易明白,接下来就是整理成自己的理解思路,然后一步一步来实现算法,那么就来做吧。 hierarchyClustering算法 思想 不同层次对数据集进行划分,AGENS是一种自底而上的聚合策略...
  • 目录层次聚类分类自底向上聚合:AGNES自顶向下分拆下面介绍AGNES算法。思路:先将每个样本看作一个初始聚类簇,在算法运行每一步中找出距离最近的两个聚类簇进行合并,重复该过程,知道达到预设的聚类簇个数。计算簇...
  • 详细介绍了聚类分析的分类以及优缺点
  • 常见聚类算法汇总

    万次阅读 2021-07-12 18:01:45
    原文链接:https://blog.csdn.net/weixin_41690708/article/details/95480399 3.层次聚类 AGNES 算法流程: (1) 将每个对象看作一类,计算两两之间的最小距离; (2) 将距离最小的两个类合并成一个新类; (3) 重新...
  • BIRCH算法简介BIRCH算法的全称是Balanced Iterative Reducing and Clustering using Hierarchies,它使用聚类特征来表示一个簇,使用聚类特征树(CF-树)来表示聚类层次结构,算法思路也是“自底向上”的。...
  • HypHC:双曲层次聚类

    2021-04-01 01:14:42
    基于相似性的层次聚类(HC)是一种经典的无监督机器学习算法,传统上已使用诸如平均链接之类的启发式算法进行了求解。 最近,Dasgupta通过引入衡量给定树质量的全局成本函数,将HC重新构架为离散的优化问题。 在这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,054
精华内容 2,821
热门标签
关键字:

单链接层次聚类算法