a***n
发帖数: 404 | 1 金山词霸末有，webster online字典也没有找到这个词。。晕阿。 |
|
|
w***g
发帖数: 5958 | 3 你这个问题用专有名词讲叫 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
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 或其他
算法. |
|
