numpy 计算集群的medoid(Python)

tmb3ates  于 2023-10-19  发布在  Python
关注(0)|答案(6)|浏览(93)

所以我运行KNN来创建集群。从每个群集中,我想获得群集的medoid。
我使用分数距离度量来计算距离:

其中d是维数,第一个数据点的坐标是x^i,第二个数据点的坐标是y^i,f是0到1之间的任意数
然后我将计算medoid为:

其中S是数据点的集合,δ是上面使用的距离度量的绝对值。
我在网上找过medoid的实现,但没有结果(即使有其他距离度量,但大多数都是专门的k-means或k-medoid,[我认为]与我想要的相对不同。
从本质上讲,这归结为我无法将数学转化为有效的编程。任何帮助或在正确的方向指针将不胜感激!以下是我迄今为止的简短列表:

  • 我已经找到了如何计算分数距离度量(第一个等式),所以我认为我在那里很好。
  • 我知道numpy有一个argmin()函数(文档here)。
  • 额外的点数可以提高效率而不缺乏准确性(我试图不通过计算每一个分数距离度量来进行蛮力计算(因为点对的数量可能会导致阶乘复杂度...)。
5tmbdcev

5tmbdcev1#

1.计算成对距离矩阵
1.计算列和或行和

  1. argmin查找medoid索引
    numpy.argmin(distMatrix.sum(axis=0))或类似。
8qgya5xd

8qgya5xd2#

所以我接受了这里的答案,但我想如果其他人试图做类似的事情,我会提供我的实现:
(1)这是距离函数:

def fractional(p_coord_array, q_coord_array):
  # f is an arbitrary value, but must be greater than zero and 
  # less than one. In this case, I used 3/10. I took advantage
  # of the difference of cubes in this case, so that I wouldn't
  # encounter an overflow error.

  a = np.sum(np.array(p_coord_array, dtype=np.float64))
  b = np.sum(np.array(q_coord_array, dtype=np.float64))
  a2 = np.sum(np.power(p_coord_array, 2))
  ab = np.sum(p_coord_array) * np.sum(q_coord_array)
  b2 = np.sum(np.power(p_coord_array, 2))
  diffab = a - b
  suma2abb2 = a2 + ab + b2

  temp_dist = abs(diffab * suma2abb2)
  temp_dist = np.power(temp_dist, 1./10)

  dist = np.power(temp_dist, 10./3)
  return dist

(2)medoid函数(如果数据集的长度小于6000 [如果大于6000,我会遇到溢出错误.我仍然在努力工作,这一点是完全诚实的...]):

def medoid(dataset):

  point = []
  w = len(dataset)

  if(len(dataset) < 6000):
    h = len(dataset)
    dist_matrix = [[0 for x in range(w)] for y in range(h)]

    list_combinations = [(counter_1, counter_2, data_1, data_2) for counter_1, data_1 in enumerate(dataset) for counter_2, data_2 in enumerate(dataset) if counter_1 < counter_2]

    for counter_3, tuple in enumerate(list_combinations):
      temp_dist = fractional(tuple[2], tuple[3])
      dist_matrix[tuple[0]][tuple[1]] = abs(temp_dist)
      dist_matrix[tuple[1]][tuple[0]] = abs(temp_dist)

任何问题,请随时发表评论!

qzwqbdag

qzwqbdag3#

如果你不介意使用暴力,这可能会有所帮助:

def calc_medoid(X, Y, f=2):
    n = len(X)
    m = len(Y)
    dist_mat = np.zeros((m, n))
    # compute distance matrix
    for j in range(n):
        center = X[j, :]
        for i in range(m):
            if i != j:
                dist_mat[i, j] = np.linalg.norm(Y[i, :] - center, ord=f)

    medoid_id = np.argmin(dist_mat.sum(axis=0))  # sum over y

    return medoid_id, X[medoid_id, :]
z6psavjg

z6psavjg4#

下面是一个用欧氏距离计算单个聚类的中心点的例子。

import numpy as np, pandas as pd, matplotlib.pyplot as plt
a, b, c, d = np.array([0,1]), np.array([1, 3]), np.array([4,2]), np.array([3, 1.5])
vCenroid = np.mean([a, b, c, d], axis=0)

def GetMedoid(vX):
  vMean = np.mean(vX, axis=0)                               # compute centroid
  return vX[np.argmin([sum((x - vMean)**2) for x in vX])]   # pick a point closest to centroid

vMedoid = GetMedoid([a, b, c, d])

print(f'centroid = {vCenroid}')
print(f'medoid = {vMedoid}')

df = pd.DataFrame([a, b, c, d], columns=['x', 'y'])
ax = df.plot.scatter('x', 'y', grid=True, title='Centroid in 2D plane', s=100);
plt.plot(vCenroid[0], vCenroid[1], 'ro', ms=10);   # plot centroid as red circle
plt.plot(vMedoid[0], vMedoid[1], 'rx', ms=20);     # plot medoid as red star

还可以使用以下包为一个或多个集群计算medoid

!pip -q install scikit-learn-extra > log
from sklearn_extra.cluster import KMedoids
GetMedoid = lambda vX: KMedoids(n_clusters=1).fit(vX).cluster_centers_
GetMedoid([a, b, c, d])[0]

yftpprvb

yftpprvb5#

一个简单的(但简单的)方法是仅仅平均集群中的向量(质心),然后找到集群中接近质心的向量吗?

import numpy as np
import faiss

vectors = np.array([...], dtype=np.float32)

# Using FAISS to build the vector index

vector_dimension = vectors.shape[1] # assume vectors
index = faiss.IndexFlatL2(vector_dimension)
faiss.normalize_L2(vectors)
index.add(vectors)

# find the mediod, closest to centroid?

centroid = np.array(vectors).mean(axis=0)
faiss.normalize_L2(centroid)
distances, indices = index.search(centroid, 2)

medoid = vectors[indices[0][0]]
ajsxfq5m

ajsxfq5m6#

我会说你只需要计算中位数。
np.median(np.asarray(points), axis=0)
你的中位数是最大的中心点。
注意:如果你使用的距离不同于欧几里德,这是不成立的。

相关问题