python - Python 中的线性/保序聚类

Question

我想根据数字与其邻居相比的“大”程度对列表中的数字进行分组，但我想连续进行，并尽可能通过聚类进行。为了澄清，让我举个例子:

假设你有列表

lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]

那么，如果我们有 3 个组，那么如何聚类就很明显了。从 sklearn 运行 k-means 算法(见代码)证实了这一点。但是，当列表中的数字不是那么“方便”时，我就遇到了麻烦。假设您有列表:

lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]

我现在的问题有两个:

1. 我想要某种“保序、线性”聚类，它会考虑数据的顺序。对于上面的列表，聚类算法应该给我一个期望的输出形式

   lst = [0,0,1,1,1,1,1,1,2,2]
   

2. 如果您查看上面的输出，您还会看到我希望将值 6.2 聚类到第二个聚类中，即我希望聚类算法将其视为异常值，而不是一个全新的聚类.

3. 编辑 为了澄清起见，我希望能够指定线性聚类过程中的聚类数量，即聚类的“最终总数”。

代码:

import numpy as np
from sklearn.cluster import KMeans

lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]

km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 2]: OK output

lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]
km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 1 1 0 0]. Desired output: [0 0 1 1 1 1 1 1 2 2]

Answer 1

如前所述，我认为获得所需结果的一种直接(大概)方法是使用普通的 K 均值聚类，然后根据需要修改生成的输出。
说明: 这个想法是获取 K-means 输出，然后遍历它们:跟踪先前项目的集群组和当前集群组，并控制根据条件创建的新集群。代码中的解释。

import numpy as np
from sklearn.cluster import KMeans

lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]

km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 2]: OK output

lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]
km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 1 1 0 0]. Desired output: [0 0 1 1 1 1 1 1 2 2]


def linear_order_clustering(km_labels, outlier_tolerance = 1):
    '''Expects clustering outputs as an array/list'''
    prev_label = km_labels[0] #keeps track of last seen item's real cluster
    cluster = 0 #like a counter for our new linear clustering outputs
    result = [cluster] #initialize first entry
    for i, label in enumerate(km_labels[1:]):
        if prev_label == label: 
            #just written for clarity of control flow, 
            #do nothing special here
            pass 
        else: #current cluster label did not match previous label
            #check if previous cluster label reappears 
            #on the right of current cluster label position 
            #(aka current non-matching cluster is sandwiched 
            #within a reasonable tolerance)
            if (outlier_tolerance and 
                prev_label in km_labels[i + 1: i + 2 + outlier_tolerance]):                     label = prev_label #if so, overwrite current label
            else:
                cluster += 1 #its genuinely a new cluster
        result.append(cluster)
        prev_label = label
    return result

请注意，我只对 1 个异常值的容忍度进行了测试，不能保证它在所有情况下都能正常工作。不过，这应该可以帮助您入门。

输出:

print(km.labels_)
result = linear_order_clustering(km.labels_)
print(result)
[1 1 0 0 0 2 0 0 1 1]
[0, 0, 1, 1, 1, 1, 1, 1, 2, 2]