基于距离的分类

Question

我有三维整数数组(~4000 x 6000 x 3),我需要以特定的方式进行分类.我希望有类似k-means聚类方法的东西,但不是输入我希望输入簇的最大半径的簇数.

换句话说,给定一个定义大小的球体,我想找到覆盖所有数据的最小数量的非空球体并相应地对点进行分类.

虽然我对该领域知之甚少,但我一直在研究聚类算法一段时间,并没有找到一个可以实现这一点的算法.

例如,给定一个随机数据集:

import numpy as np

randomArray = np.random.rand(10,10,3)*500

Out[8]: 
array([[[ 256.68932025,  153.07151992,  196.19477623],
        [  48.05542231,  346.1289173 ,  327.44694932],
        [ 427.87340594,  197.26882283,  402.41558648],
        [ 192.50462233,  408.31800086,   81.66016443],
        [  64.15373494,   34.96971099,  446.55362458]],

       [[ 376.55003794,   70.09514697,  242.08947306],
        [ 194.86207829,  379.90969257,  439.47043484],
        [ 102.99922513,   98.57769429,  415.5059223 ],
        [ 464.65318671,  223.60061654,  417.52758666],
        [  53.68383153,  205.32517075,  299.83858164]],

       [[ 364.80957874,   14.26150931,  264.01568428],
        [ 295.75617954,  107.52678922,   87.89830525],
        [  57.90617865,  409.54132373,   54.36940482],
        [ 217.35951975,  345.7892723 ,  301.07031811],
        [ 295.98999071,   27.17772152,  182.58776469]],

       [[ 291.69513153,  466.03218019,  279.25794618],
        [ 179.60152364,  161.64966386,  269.34221176],
        [ 374.78609278,  259.18286321,  459.8037004 ],
        [ 458.51249648,   87.05600447,  268.12588338],
        [ 152.54500603,  472.36773898,    1.15894726]],

       [[  35.43731854,  163.42770568,  131.77683448],
        [  14.36039625,  390.33409364,  314.56443073],
        [  71.47211566,  109.78613335,  345.57021076],
        [  74.62340632,  328.51303903,  341.97344285],
        [ 205.02121677,  235.71812371,   32.91252756]]])

和最大半径

R = 35

我想输出一个相同高度和宽度的2D数组,其中标记表示3D阵列中每个点的球体被分类.没有两个具有相同标签的点应该具有大于最大半径的欧几里德距离,不sphere应为空,算法应使用尽可能少的球体来完成此操作.

Answer 1

您可以在 scikit learn 中使用基于亲和力的聚类的变体；基本指南，示例，集群对象。您必须修改距离度量/矩阵以确保球体半径小于最大半径。基于亲和性和密度的 (DBSCAN) 聚类是唯一不需要预定义聚类数量的无监督机器学习方法。

亲和聚类图像

我不推荐 DBSCAN 的原因是有些点不属于簇。通过亲和性聚类，所有点都将成为聚类的一部分。亲和聚类可能需要很长时间才能收敛，O(N^2 * T)，其中“N”是样本数，“T”是收敛的迭代次数。来自亲和力聚类的“信号”可以代表您的半径。由于默认值affinity表示如何计算点之间的信号，它是欧氏距离的变体，因此您可以快速开始计算聚类。

affinity : 字符串，可选，默认='euclidean'

使用哪个亲和力。目前支持预计算和欧几里德。欧氏距离使用点之间的负平方欧氏距离。

此外，您可以使用preference输入对不同点进行加权。当您迭代/收敛集群数量时，您将查看affinity_matrix_和cluster_centers_属性以确定所有点是否都在您的最大半径内。当您迭代不同的聚类变体以指示该点最有可能属于哪个聚类时，每个点的偏好可能会发生变化。

偏好：类似数组，形状（n_samples，）或浮点数，可选

每个点的偏好 - 偏好值较大的点更有可能被选为样本。样本的数量（即簇的数量）受输入偏好值的影响。如果偏好不作为参数传递，它们将被设置为输入相似度的中值。

如果您想尝试 DBSCAN，三个主要指标是 EPS（两个样本之间的最大距离）、形成聚类的最小点数和距离指标DBSCAN 聚类对象、基本指南、示例。

DBSCAN 聚类图像

您可能不需要像使用 Affinity 那样迭代 DBSCAN。您将能够快速测试所选择的最大距离是否可行，因为-1如果样本不属于该距离处的簇的一部分，则 DBSCAN 中的簇标签将是。对于大型数据集，您的内存消耗会很高。

DBSCAN算法中存在三种类型的点/样本：

• 核心样本：

数据集中的一个样本，使得在min_samples以下距离内存在其他样本eps

• 边缘样品：

是簇中核心样本的邻居但本身不是核心样本的样本；翻译是这个样本在eps 距离之内，但没有min_samples周围的东西（小于 eps距离）

• 异常值：

不是核心样本，并且至少eps与任何核心样本有一定距离

DBSCAN 簇仅由核心样本定义。这可能会让人感到困惑，但 scikit learn 在解释算法方面做得非常好。

我认为您的问题没有一个简单的实现方法。Affinity 和 DBSCAN 都有各自的优点和缺点。我认为 Affinity 将是您最初的最佳选择，因为 DBSCAN 可能会令人困惑，并且可能会给您带来内存错误，具体取决于样本矩阵的大小。

我希望这有帮助。这是一个非常有趣的问题。我会尝试使用 Affinity 的变体来最初解决这个问题。