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 中位数，它通过使用中心点而不是均值，避免了计算均值的需要，并且据我所知可以为任意距离提供收敛保证。

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

Answer 2

要计算字符串之间的距离，您可以使用Levenshtein 距离（又名编辑距离）。

为了规范字符串和数字属性之间的值，您可以尝试将属性表示为百分比：找到每种类型属性的最小值和最大值，然后对于给定的数据实例，计算其在相应范围内的百分比。