data-mining - 如何在字符串数据上实现k-means算法

Question

我正在尝试在下面的数据集上实现 K-means 算法。它是直接计算任意两个数字属性之间的距离，但如何计算两个字符串之间的距离以及如何总结所有距离(即字符串属性之间的距离和数字属性之间的距离。)请告诉我。谢谢。

Answer 1

K-means 是为欧几里德距离而设计的。您不能只插入任意其他距离函数。这可能会导致 k-means 不再收敛。

所需的属性是均值必须最小化方差。如果你不能保证这个属性(字符串的意思到底是什么？)，那么你就失去了保证的收敛性。

从技术上讲，k-means 甚至不基于欧几里德距离，但它最大限度地减少了方差，而方差恰好与平方欧几里德距离相同；如果你最小化这些正方形，你也会最小化欧几里德距离。但该算法真正旨在最小化的是 Var(Attribute 1, Cluster 1) + Var(Attribute 2, Cluster 1) + ... + Var(Attribute n, Cluster k)。

您可能想研究 k 中位数，它通过使用中心点而不是均值，避免了计算均值的需要，并且据我所知可以为任意距离提供收敛保证。

但是，您可能想要研究真正基于距离的算法，包括各种基于密度的聚类算法，这些算法通常也是基于距离的。