1

我能找到的关于“调整后的完整”链接的唯一描述是这样的：“与完整链接相同，但在集群距离内最大”

“在集群距离内”是什么意思？

最终如何使用这种链接方法计算两个集群之间的距离？

感谢您的回复！

4

1 回答 1

1

开源软件的一大优点是您可以准确了解该软件的工作原理。下面的代码显示了Weka 的算法源代码，HierarchicalClusterer更具体地说，它显示了实现COMPLETEandADJCOMPLETE功能的部分。区别如下：

  • 就像COMPLETE链接方法一样，计算集群 1 的一个节点与集群 2 的一个节点之间的最大距离，并将其存储在fBestDist
  • 然后，找到集群 1 或集群 2 中节点之间的最大距离并将其存储在fMaxDist
  • fMaxDist最后减去fBestDist

ADJCOMPLETE因此，使用as计算的两个集群之间的距离linkType对应于COMPLETE距离减去集群 1 或集群 2 中 2 个节点之间的最大距离。

Adjusted Complete-Link在以下论文中提出：

Sepandar Kamvar、Dan Klein 和 Christopher Manning (2002)。使用基于模型的方法解释和扩展经典凝聚聚类算法。在第 19 届机器学习国际会议论文集中 (ICML-2002)

根据它（第 4.2 节），如果集群具有不同的半径，则应使用其Adjusted Complete-Link版本（参见图 10）。Complete-Link

case COMPLETE:
case ADJCOMLPETE:
  // find complete link distance aka maximum link, which is the largest distance between
  // any item in cluster1 and any item in cluster2
  fBestDist = 0;
  for (int i = 0; i < cluster1.size(); i++) {
    int i1 = cluster1.elementAt(i);
    for (int j = 0; j < cluster2.size(); j++) {
      int i2 = cluster2.elementAt(j);
      double fDist = fDistance[i1][i2];
      if (fBestDist < fDist) {
        fBestDist = fDist;
      }
    }
  }
  if (m_nLinkType == COMPLETE) {
    break;
  }
  // calculate adjustment, which is the largest within cluster distance
  double fMaxDist = 0;
  for (int i = 0; i < cluster1.size(); i++) {
    int i1 = cluster1.elementAt(i);
    for (int j = i+1; j < cluster1.size(); j++) {
      int i2 = cluster1.elementAt(j);
      double fDist = fDistance[i1][i2];
      if (fMaxDist < fDist) {
        fMaxDist = fDist;
      }
    }
  }
  for (int i = 0; i < cluster2.size(); i++) {
    int i1 = cluster2.elementAt(i);
    for (int j = i+1; j < cluster2.size(); j++) {
      int i2 = cluster2.elementAt(j);
      double fDist = fDistance[i1][i2];
      if (fMaxDist < fDist) {
        fMaxDist = fDist;
      }
    }
  }
  fBestDist -= fMaxDist;
  break;
于 2012-08-09T16:54:03.603 回答