聚类的边界条件

数据挖掘 k-均值
2021-09-30 09:46:42

我有一些数据想用 k-means 进行聚类。

其中一项功能是一天中的小时。

问题是小时'23'被认为远离小时'0'。

如何映射数据以使边界是循环的?

3个回答

由于您接受了另一个答案,该答案表示无法完成,因此我正在对其进行编辑以包含一个正在完成的示例。希望这可以帮助!

原答案:

将小时转换为最合乎逻辑的方法是将时间转换为两个在汇中来回摆动的变量。想象一下 24 小时制时针末端的位置。位置随着x位置来回摆动出水槽y对于 24 小时制,您可以使用x=sin(2pi*hour/24),来完成此操作y=cos(2pi*hour/24)

您需要这两个变量,否则会丢失正确的时间运动。这是因为 sin 或 cos 的导数随时间变化,而(x,y)位置在绕单位圆行进时平滑变化。

这种方法非常适用于聚类并在欧几里得空间中保持午夜后 15 分钟和午夜前 5 分钟之间的距离“关闭”。所有的模数建议都没有实现这一点,而且它们实现的循环表示非常笨拙。

最后,考虑是否值得添加第三个特性来跟踪线性时间,它可以由从第一条记录开始的小时(或分钟或秒)或 Unix 时间戳或类似的东西构成。然后,这三个特征为时间的循环和线性进展提供了代理,例如,您可以提取循环现象,如人们运动中的睡眠周期,以及人口与时间的线性增长。

希望这可以帮助!

如果完成的例子:

# Enable inline plotting
%matplotlib inline

#Import everything I need...

import numpy as np
import matplotlib as mp

import matplotlib.pyplot as plt
import pandas as pd

# Grab some random times from here: https://www.random.org/clock-times/
# put them into a csv.
from pandas import DataFrame, read_csv
df = read_csv('/Users/angus/Machine_Learning/ipython_notebooks/times.csv',delimiter=':')
df['hourfloat']=df.hour+df.minute/60.0
df['x']=np.sin(2.*np.pi*df.hourfloat/24.)
df['y']=np.cos(2.*np.pi*df.hourfloat/24.)

df

在此处输入图像描述

def kmeansshow(k,X):

    from sklearn import cluster
    from matplotlib import pyplot
    import numpy as np

    kmeans = cluster.KMeans(n_clusters=k)
    kmeans.fit(X)

    labels = kmeans.labels_
    centroids = kmeans.cluster_centers_
    #print centroids

    for i in range(k):
        # select only data observations with cluster label == i
        ds = X[np.where(labels==i)]
        # plot the data observations
        pyplot.plot(ds[:,0],ds[:,1],'o')
        # plot the centroids
        lines = pyplot.plot(centroids[i,0],centroids[i,1],'kx')
        # make the centroid x's bigger
        pyplot.setp(lines,ms=15.0)
        pyplot.setp(lines,mew=2.0)
    pyplot.show()
    return centroids

现在让我们试一试:

kmeansshow(6,df[['x', 'y']].values)

在此处输入图像描述

您几乎看不到午夜之前的绿色集群中包含一些午夜之后的时间。现在让我们减少集群的数量,并更详细地显示午夜之前和之后可以连接到一个集群中:

kmeansshow(3,df[['x', 'y']].values)

在此处输入图像描述

看看蓝色集群如何包含从午夜之前和之后聚集在同一个集群中的时间......

QED!

K-means 使用均值

K-means 是为最小二乘而设计的。它仅适用于平方欧几里得距离(= 平方偏差之和)的(变体)。

反例:

假设你有两个小时 0 和 23。

如果它们被分配到同一个集群,k-means 将计算平均值

这两个值的平均值是 11.5。不是23.5。

使用循环“距离”滥用 k-means 可能不再收敛,并且会返回无意义的结果。

但是在更多情况下,集群中心的概念在循环数据上是不可行的。例如,给定一个整小时的事件,中心是什么算术平均值为 12 - 但如果您每小时都考虑循环空间,那么在循环空间中也是一个同样好的选择因此,循环空间中的“中心”概念是脆弱的。

替代聚类算法

您可以尝试使用适当的相似性度量,例如 PAM 或 DBSCAN。

投影技术

正如其他答案所指出的,您可以通过 sin/cos(time/24*2pi) 将时间投影到单位圆。通过计算质心的角度,您可以将其映射回某个时间点。但是,一旦您需要其他属性,就很难对数据进行有意义的规范化(以组合属性),并且您可以获得未定义的时间(例如,如果集群中有两个点,一个在 6 点,一个在 18 点)。我没有讨论这个,因为我想指出修改距离函数对于 k-means 来说不是一个好主意。

模数运算。一般来说你会做end - start mod 24

julia> mod(-23,24)
1

我似乎记得一些编程语言以不同的方式处理负数的 mod,所以首先检查你的实现。