3

我正在尝试使用 sklearn 对某些数据集进行 K 均值聚类。问题是其中一个维度是一天中的小时：一个从 0 到 23 的数字，因此距离算法认为 0 离 23 很远，因为从绝对意义上来说它是。实际上，出于我的目的，0 小时非常接近 23 小时。有没有办法让距离算法进行某种形式的环绕，以便计算更“真实”的时差。我正在做一些简单的事情，类似于以下内容：

from sklearn.cluster import KMeans

clusters = KMeans(n_clusters = 2)
data = vstack(data)
fit = clusters.fit(data)
classes = fit.predict(data)

data元素看起来像[22, 418, 192]第一个元素是小时。

有任何想法吗？

4

3 回答 3

3

即使@elyase 的答案被接受，我认为这不是正确的方法。

是的，要使用这样的距离，你必须改进你的距离测量等等 - 使用不同的库。但更重要的是 - k-means 中使用的均值概念不适合循环维度。让我们考虑以下示例：

#current cluster X,, based on centroid position Xc=24
x1=1
x2=24

#current cluster Y, based on centroid position Yc=10
y1=12
y2=13

计算简单算术平均值会将质心放在Xc=12.5,Yc=12.5中，从循环测量的角度来看，这是不正确的，它应该是Xc=0.5, Yc=12.5。如您所见，基于循环距离度量的分配与简单的均值运算不“兼容”，并导致奇怪的结果。

  • 简单的 k-means 将导致聚类{x1,y1}, {x2,y2}
  • 简单的 k--means + 距离测量导致退化的超级集群{x1,x2,y1,y2}
  • 正确的聚类将是{x1,x2},{y1,y2}

解决这个问题需要检查一个 if（是否更好地测量“简单平均值”或将其中一个点表示为x'=x-24）。不幸的是，给n定点它提供了2^n可能性。

这似乎是内核化 k-means的一个用例，您实际上是在由内核（“相似性度量”，内部一些向量空间的乘积）。

这里给出了内核 k-means的详细信息

于 2013-09-09T05:41:27.227 回答
1

为什么 k-means 不适用于任意距离

K-means 不是基于距离的算法。

K-means 最小化了簇内平方和，这是一种方差（它大致是所有簇的加权平均方差，其中每个对象和维度都被赋予相同的权重）。

为了使 Lloyds 算法收敛，您需要让两个步骤都优化相同的函数：

  • 重新分配步骤
  • 质心更新步骤

现在“均值”函数是最小二乘估计器。即在步骤 2 中选择平均值对于 WCSS 目标是最佳的。在步骤 1 中通过最小二乘偏差（= 平方欧几里得距离，单调到欧几里得距离）分配对象也可以保证收敛。平均值正是您的环绕式想法会崩溃的地方。

如果您按照@elyase k-means 的建议插入随机的其他距离函数，则可能不再收敛。

适当的解决方案

对此有多种解决方案：

  • 使用 K-medoids (PAM)。通过选择中心点而不是平均值，您确实可以保证在任意距离处收敛。然而，计算中心点相当昂贵。
  • 将数据转换为内核空间，您可以在该空间中最小化平方和。例如，您可以将小时转换sin(hour / 12 * pi), cos(hour / 12 * pi)为适合 SSQ 的时间。
  • 使用其他基于距离的聚类算法。K-means 很老，从那时起就有很多关于聚类的研究。您可能想从层次聚类（实际上与 k-means 一样古老）开始，然后尝试 DBSCAN 及其变体。
于 2013-09-09T06:51:02.543 回答
0

对我来说，最简单的方法是通过计算维度的“循环平均值”来调整 K-means 算法环绕维度。当然，您还需要相应地更改距质心的距离计算。

#compute the mean of hour 0 and 23
import numpy as np
hours = np.array(range(24))
#hours to angles
angles = hours/24 * (2*np.pi)

sin = np.sin(angles)
cos = np.cos(angles)

a = np.arctan2(sin[23]+sin[0], cos[23]+cos[0])
if a < 0: a += 2*np.pi

#angle back to hour
hour = a * 24 / (2*np.pi)
#23.5
于 2019-09-08T16:48:53.997 回答