如何在 python 中绘制 k 距离图

Question

如何在 DBSCAN 中绘制（在 python 中）给定最小点值的距离图？？？

我正在寻找膝盖和相应的 epsilon 值。

在 sklearn 中，我没有看到任何 return 这样的距离的方法....我错过了什么吗？

Answer 1

要获取距离，您可以使用此函数：

import numpy as np
import pandas as pd
import math

def k_distances(X, n=None, dist_func=None):
    """Function to return array of k_distances.

    X - DataFrame matrix with observations
    n - number of neighbors that are included in returned distances (default number of attributes + 1)
    dist_func - function to count distance between observations in X (default euclidean function)
    """
    if type(X) is pd.DataFrame:
        X = X.values
    k=0
    if n == None:
        k=X.shape[1]+2
    else:
        k=n+1

    if dist_func == None:
        # euclidean distance square root of sum of squares of differences between attributes
        dist_func = lambda x, y: math.sqrt(
            np.sum(
                np.power(x-y, np.repeat(2,x.size))
            )
        )

    Distances = pd.DataFrame({
        "i": [i//10 for i in range(0, len(X)*len(X))],
        "j": [i%10 for i in range(0, len(X)*len(X))],
        "d": [dist_func(x,y) for x in X for y in X]
    })
    return np.sort([g[1].iloc[k].d for g in iter(Distances.groupby(by="i"))])

X 应该是 pandas.DataFrame 或 numpy.ndarray。 n 是 d-neighborhood 中的邻居数。你应该知道这个数字。默认情况下是属性数 + 1.

要绘制这些距离，您可以使用以下代码：

import matplotlib.pyplot as plt

d = k_distances(X,n,dist_func)
plt.plot(d)
plt.ylabel("k-distances")
plt.grid(True)
plt.show()

Answer 2

您可能想使用 numpy 提供的矩阵运算来加速您的距离矩阵计算。

def k_distances2(x, k):
    dim0 = x.shape[0]
    dim1 = x.shape[1]
    p=-2*x.dot(x.T)+np.sum(x**2, axis=1).T+ np.repeat(np.sum(x**2, axis=1),dim0,axis=0).reshape(dim0,dim0)
    p = np.sqrt(p)
    p.sort(axis=1)
    p=p[:,:k]
    pm= p.flatten()
    pm= np.sort(pm)
    return p, pm
m, m2= k_distances2(X, 2)
plt.plot(m2)
plt.ylabel("k-distances")
plt.grid(True)
plt.show()

Answer 3

首先你可以定义一个函数来计算每个点到它的第k个最近邻点的距离：

def calculate_kn_distance(X,k):

    kn_distance = []
    for i in range(len(X)):
        eucl_dist = []
        for j in range(len(X)):
            eucl_dist.append(
                math.sqrt(
                    ((X[i,0] - X[j,0]) ** 2) +
                    ((X[i,1] - X[j,1]) ** 2)))

        eucl_dist.sort()
        kn_distance.append(eucl_dist[k])

    return kn_distance

然后，定义函数后，您可以选择 k 值并绘制直方图以找到拐点以定义合适的 epsilon值。

eps_dist = calculate_kn_distance(X[1],4)
plt.hist(eps_dist,bins=30)
plt.ylabel('n');
plt.xlabel('Epsilon distance');

在上面的示例中，绝大多数点都位于距离第 4 个最近邻点 0.12 个单位的范围内。因此，启发式方法可以选择 0.12 作为 epsilon 参数。

Answer 4

我会尽力为未来的观众做一个广泛的指南
简而言之，这些步骤是（使用 distance matrix）

获取排序后的距离矩阵
获取第k列（第k列表示与第k个邻居的距离）
将第 k 列降序排列
在 y 轴上绘制它，在 x 轴上绘制 (0-n)

让我们拿一个 n = 7 的简单数据集

   x,   y
1  1,   1
2  1.5, 1.5
3  1.25,1.25
4  1.5, 1
5  1,   1.5
6  1.75,1.75
7  3,   2

The sorted distance matrix
[[0, 0.353, 0.5,   0.5,   0.707, 1.061, 2.236]
 [0, 0.353, 0.353, 0.5,   0.5,   0.707, 1.581]
 [0, 0.353, 0.353, 0.353, 0.353, 0.707, 1.904]
 [0, 0.353, 0.5,   0.5,   0.707, 0.791, 1.803]
 [0, 0.353, 0.5,   0.5,   0.707, 0.791, 2.062]
 [0, 0.353, 0.707, 0.791, 0.791, 1.061, 1.275]
 [0, 1.273, 1.581, 1.803, 1.904, 2.062, 2.236]]  

 The sorted kth (k=4) Column (5th column)  
 [1.904,0.791,0.707,0.707,0.707,0.5,0.353]

现在绘制这将产生

plt.plot([0,1,2,3,4,5,6],[1.904,0.791,0.707,0.707,0.707,0.5,0.353])

如您所见，在 0.79 处有一个强烈的弯曲。因此，对于 k/minpts = 4，任何具有第 k 个邻域距离 > 0.79 的点都将被视为 noise/non-core 点。

当然不能保证图中会有强烈的弯曲甚至完全弯曲，这完全取决于数据的分布
The original paper

如何在 python 中绘制 k 距离图

how to plot a k-distance graph in python

python

cluster-analysis

dbscan