8

我有一个不透明对象的列表。我只能计算它们之间的距离（不是真的，只是为问题设置条件）：

class Thing {
    public double DistanceTo(Thing other);
}

我想对这些对象进行聚类。我想控制集群的数量，并且我希望“关闭”对象位于同一个集群中：

List<Cluster> cluster(int numClusters, List<Thing> things);

任何人都可以建议（并链接到;-)）一些聚类算法（越简单越好！）或可以帮助我的库？

澄清大多数聚类算法要求对象被布置在一些 N 维空间中。该空间用于查找集群的“质心”。就我而言，我不知道 N 是什么，也不知道如何从对象中提取坐标系。我只知道两个物体相距多远。我想找到一个只使用该信息的好的聚类算法。

想象一下，您正在根据对象的“气味”进行聚类。您不知道如何在 2D 平面上放置“气味”，但您确实知道两种气味是否相似。

4

5 回答 5

6

我认为您正在寻找K-Medoids。就像 K-means 一样，您可以预先指定聚类的数量K，但它不需要像 K-means 那样具有“平均”聚类对象的概念。

相反，每个集群都有一个代表medoid，它是最靠近中间的集群的成员。您可以将其视为 K-means 的一个版本，它查找“中位数”而不是“均值”。您所需要的只是一个距离度量来聚类事物，我在自己的一些工作中使用了它，原因与您引用的完全相同。

Naive K-medoids 不是最快的算法，但有一些快速变体可能足以满足您的目的。以下是算法的描述以及它们在R中实现的文档链接：

  1. PAM是 K-medoids 的基本 O(n^2) 实现。
  2. CLARA是 PAM 的一个更快的采样版本。它通过使用 PAM 对随机采样的对象子集进行聚类并根据子集对整个对象集进行分组来工作。你应该仍然能够快速获得非常好的集群。

如果您需要更多信息，这里有一篇论文概述了这些和其他 K-medoids 方法。

于 2009-04-04T21:21:47.740 回答
3

这是一个聚类算法的大纲，它没有找到质心的 K-means 要求。

  1. 确定所有对象之间的距离。记录n 个最独立的对象。
    [找到我们集群的根，时间 O(n^2) ]
  2. 将这n 个随机点中的每一个分配给n 个新的不同簇。
  3. 对于每个其他对象：
    [将对象分配给集群，时间 O(n^2) ]
    1. 对于每个集群：
      1. 通过平均集群中每个对象到对象的距离来计算从集群到该对象的平均距离。
    2. 将对象分配给最近的集群。

该算法肯定会对对象进行聚类。但它的运行时间是O(n^2)。另外，它由选择的前n个点引导。

任何人都可以改进这一点（更好的运行时性能，更少依赖初始选择）？我很想看看你的想法。

于 2009-03-28T19:54:03.070 回答
2

这是一个快速算法。

While (points_left > 0) {
 Select a random point that is not already clustered
 Add point and all points within x distance 
   that aren't already clustered to a new cluster.
}

或者，阅读维基百科页面。K-means 聚类是一个不错的选择：

K-means 算法将每个点分配给其中心（也称为质心）最近的集群。中心是集群中所有点的平均值——也就是说，它的坐标是集群中所有点的每个维度的算术平均值。

算法步骤为：

* Choose the number of clusters, k.
* Randomly generate k clusters and determine the cluster centers, or
  directly generate k random points as cluster centers.
* Assign each point to the nearest cluster center.
* Recompute the new cluster centers.
* Repeat the two previous steps until some convergence criterion is
  met (usually that the assignment hasn't changed).

该算法的主要优点是其简单性和速度，使其能够在大型数据集上运行。它的缺点是每次运行都不会产生相同的结果，因为生成的集群取决于初始随机分配。它最小化集群内方差，但不能确保结果具有全局最小方差。另一个缺点是要求均值的概念是可定义的，但情况并非总是如此。对于此类数据集，k-medoids 变体是合适的。

于 2009-03-28T00:59:58.350 回答
1

这种方法怎么样：

  1. 将所有对象分配给一个集群。
  2. 找到两个对象a和b，它们在同一个簇k中，并且相距最大。为了澄清，整个集合应该有一个a和b ，而不是每个集群都有一个a和b。
  3. 将集群k分成两个集群，k1和k2，一个与对象a，一个与对象b。
  4. 对于集群k中的所有其他对象，通过确定与该集群中所有其他对象的最小平均距离，将它们添加到k1或k2 。
  5. 重复步骤 2-5，直到形成 N 个簇。

我认为这个算法应该给你一个相当好的聚类，虽然效率可能很差。为了提高效率，您可以更改第 3 步，以便仅找到与启动集群的原始对象的最小距离，而不是与集群中已存在的所有对象的平均距离。

于 2009-03-28T21:28:13.920 回答
1

系统发育 DNA 序列分析通常在文本字符串上使用层次聚类，并使用 [对齐] 距离矩阵。这是一个不错的 R 聚类教程：

（快捷方式：直接进入“分层凝聚”部分...）

以下是一些其他 [语言] 库：

这种方法可以帮助确定有多少 [k] 个“自然”簇，以及哪些对象用作上述 k 均值方法的根。

于 2009-04-04T20:36:44.667 回答