领导聚类算法解释

Question

我试图理解这个算法,但无法获得适当的文档和解释.有人可以帮我理解这种聚类算法.

Answer 1

发布答案,以便对其他人有所帮助.

Leader算法是一种增量聚类算法,通常用于聚类大数据集.该算法是顺序依赖的,并且可以基于向算法提供数据集的顺序形成不同的簇.该算法包括以下步骤.

步骤1:将第一个数据项P1分配给集群C1.该数据集将成为集群C1的领导者.

步骤2:现在移动到下一个数据项,说P2并计算它与领导者P1的距离.如果P2和引导器P1之间的距离小于用户指定的阈值(t),则将数据点P2分配给该簇(簇C1).如果领导者P1和数据项P2之间的距离大于用户指定的阈值t,则形成新的聚类C2并将P2分配给该新聚类.P2将成为集群C2的领导者.

步骤3:对于所有剩余数据项,计算数据点与簇的前导之间的距离.如果数据项与任何领导者之间的距离小于用户指定的阈值,则将数据点分配给该群集.但是,如果数据点与任何群集的领导者之间的距离大于用户指定的阈值,则会创建一个新群集,并将该特定数据点分配给该群集,并将其视为群集的领导者.

步骤4:重复步骤3,直到所有数据项都分配给集群.

让理论清晰的例子.

考虑模式位于

A (1, 1),B(1, 2), C(2, 2), D(6, 2), E(7, 2), F(6, 6), G(7, 6)

让数据的顺序进行处理A, B, C, D, E, F and G,并且用户指定的阈值T是3. A(1, 1)是第一个处理过的数据项,它被分配给集群C1,也成为了集群的领导者C1.

对于第二点B,A计算它与领导者的距离.使用欧氏距离公式(Distance(a, b)) = ?(x - a)² + (y - b)²),我们得到的距离为?(1 - 1)² + (1 - 2)² = 1,小于用户指定的阈值3,因此B分配给群集1.

对于第三点C(2, 2),计算A(1, 1)簇C1 与点的前导之间的距离C.使用欧几里德公式,距离?(1 - 2)² + (1 - 2)² = 1.41小于阈值,因此C也分配给C1.A和D之间的距离(√(1 - 6)²+(1 - 2)²= 5.099)大于用户指定的阈值3,因此创建一个新的簇并将D分配给簇C2.D是该集群的领导者.

对于这一点E,计算它与A(领导者C1)和D(领导者C2)的距离.由于Distance(D,E)小于用户指定的阈值3,因此将其分配给群集2.

距离A(C1的领导者)的距离是(7.07和DC2的领导者)是4.这两个距离都高于阈值,因此F被放入新的集群中C3,并成为该集群的领导者.对于G的Distance(A,G),Distance(D,G)并且Distance(F,G)是7.81,6.41和1分别.由于Distance(F,G)少于用户指定,3因此将其分配给群集3.

可以看出,如果数据以不同的顺序处理,则集群领导者将会有所不同 - 甚至集群也可能不同.如果C发生前 A和B,然后C就一直是领导者C1.如果D发生之前和之间的距离C,并D为小于阈值,它会一直在C1.如果A是领导者,这可能不会发生.因此,领导者算法是依赖于顺序的,并且可以基于处理顺序给出不同的结果.