计算集群的中心点 (Python)
Calculating medoid of a cluster (Python)
所以我是 运行 KNN 以创建集群。我想从每个集群中获取集群的中心点。
我正在使用分数距离度量来计算距离:
其中d是维数,第一个数据点的坐标是x^i,第二个数据点的坐标是y^i,f是0到1之间的任意数
然后我会将中心点计算为:
其中 S 是数据点集,δ 是上面使用的距离度量的绝对值。
我在网上查找 medoid 的实现无济于事(即使使用其他距离度量,但大多数都是特定的 k-means 或 k-medoid,[我认为] 与我想要的相对不同.
从本质上讲,这归结为我无法将数学转化为有效的编程。任何帮助或指向正确方向的指示将不胜感激!这是我目前所拥有的简短列表:
- 我已经弄清楚如何计算分数距离度量(第一个等式),所以我觉得我很擅长。
- 我知道 numpy 有一个 argmin() 函数(已记录 here)。
- 在不缺乏准确性的情况下提高效率的加分项(我试图不通过计算每个分数距离度量来蛮力(因为点对的数量可能导致阶乘复杂性......)。
- 计算成对距离矩阵
- 计算列或行总和
- argmin 找到中心点索引
即numpy.argmin(distMatrix.sum(axis=0))
或类似。
所以我在这里接受了答案,但我想如果其他人试图做类似的事情,我会提供我的实现:
(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 [如果大于,我 运行 进入溢出错误......我仍在努力那个位是非常诚实...]):
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)
有什么问题,欢迎留言!
如果您不介意使用蛮力,这可能会有所帮助:
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, :]
我会说你只需要计算中位数。
np.median(np.asarray(points), axis=0)
你的中位数是中心性最大的点。
注意:如果您使用的距离不同于欧几里德距离,则不成立。
这里是一个用欧几里德距离计算单个簇的中心点的例子。
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
您还可以使用以下程序包为一个或多个集群计算中心点
!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]
所以我是 运行 KNN 以创建集群。我想从每个集群中获取集群的中心点。
我正在使用分数距离度量来计算距离:
其中d是维数,第一个数据点的坐标是x^i,第二个数据点的坐标是y^i,f是0到1之间的任意数
然后我会将中心点计算为:
其中 S 是数据点集,δ 是上面使用的距离度量的绝对值。
我在网上查找 medoid 的实现无济于事(即使使用其他距离度量,但大多数都是特定的 k-means 或 k-medoid,[我认为] 与我想要的相对不同.
从本质上讲,这归结为我无法将数学转化为有效的编程。任何帮助或指向正确方向的指示将不胜感激!这是我目前所拥有的简短列表:
- 我已经弄清楚如何计算分数距离度量(第一个等式),所以我觉得我很擅长。
- 我知道 numpy 有一个 argmin() 函数(已记录 here)。
- 在不缺乏准确性的情况下提高效率的加分项(我试图不通过计算每个分数距离度量来蛮力(因为点对的数量可能导致阶乘复杂性......)。
- 计算成对距离矩阵
- 计算列或行总和
- argmin 找到中心点索引
即numpy.argmin(distMatrix.sum(axis=0))
或类似。
所以我在这里接受了答案,但我想如果其他人试图做类似的事情,我会提供我的实现:
(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 [如果大于,我 运行 进入溢出错误......我仍在努力那个位是非常诚实...]):
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)
有什么问题,欢迎留言!
如果您不介意使用蛮力,这可能会有所帮助:
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, :]
我会说你只需要计算中位数。
np.median(np.asarray(points), axis=0)
你的中位数是中心性最大的点。
注意:如果您使用的距离不同于欧几里德距离,则不成立。
这里是一个用欧几里德距离计算单个簇的中心点的例子。
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
您还可以使用以下程序包为一个或多个集群计算中心点
!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]