由买买提看人间百态

topics

全部话题 - 话题: medoids
(共0页)
a***n
发帖数: 404
1
金山词霸末有,webster online字典也没有找到这个词。。晕阿。
l****g
发帖数: 761
2
米多埃得?
w***g
发帖数: 5958
3
来自主题: Programming版 - 最小Manhattan距离
你这个问题用专有名词讲叫 find the medoid under Manhattan/L1 distance。如果对
Manhattan distance做K-Medoid聚类的话是一个超频繁调用的操作。不知道你的最小生
成树的解法是从哪儿看来的。前面database指出了解这个问题的关键,就是在
Manhattan distance下X和Y独立。不过他的解法我实在没有看明白,只能猜一下。
我们的目标是任意给P点中的一点可以用O(1)算出所有点(P到自己的距离是0,包不包含
无所谓)到该点的距离之和sum(P)。这样所有点过一遍用O(n)就可以找出最优点。
这个sum(P)又可以分解 sum_x(P_x)+sum_y(P_y)。 sum_x和sum_y的算法相同。下面用
计算sum_x加以说明。
加入有一串值x1, x2, ...,要计算任意一个xi的sum_x(xi)值。可以对所有x排序O(
nlogn)。
x1, x2, x3, ...
然后对各个i计算 left_i = x1 + x2 + ... + xi-1
right_i = x{i+1}... 阅读全帖
k**********g
发帖数: 989
4
来自主题: Programming版 - 最小Manhattan距离

actually,
Sum of mht from arbitrary point T to every point in set
= Sum of vertical distance from T to every point *above* T
+ Sum of vertical distance from T to every point *below* T
+ Sum of horizontal distance from T to every point *left of* T
+ Sum of horizontal distance from T to every point *right of* T
So, maybe the number of items (points) in each criterion do not equal,
despite point T being the "median / medoid point"
y*****d
发帖数: 82
5
简单? 把weight看成第3维(每个点的高度),在3维空间中做K-means, K-medoids 或其他
算法.
(共0页)