r****o
发帖数: 1950 | 1 直线上n个点，如何在该直线上找出k个点来，让这n个点各自映射到离自己最近的k个点
中的某个点，使得总距离最小?
注：这k个点可能从n个点中取，也可能不从n个点中取。 |
l***i
发帖数: 632 | |
r****o
发帖数: 1950 | 3 你确定是DP题吗？
能否给出解法?
【在 l***i 的大作中提到】
: 为啥这里这么流行DP题
|
c*****g
发帖数: 1137 | 4 常见的算法中DP算最难的了吧
【在 l***i 的大作中提到】
: 为啥这里这么流行DP题
|
l*****k
发帖数: 1059 | 5 第一感觉，这是个clustering问题。
至少可以用LBG(Linde-Buzo-Gray) clustering algorithms
【在 r****o 的大作中提到】
: 直线上n个点，如何在该直线上找出k个点来，让这n个点各自映射到离自己最近的k个点
: 中的某个点，使得总距离最小?
: 注：这k个点可能从n个点中取，也可能不从n个点中取。
|
r****o
发帖数: 1950 | 6 谢谢，请问，最优结果中的k个点是不是一定要从n个点中取呢?
【在 l*****k 的大作中提到】
: 第一感觉，这是个clustering问题。
: 至少可以用LBG(Linde-Buzo-Gray) clustering algorithms
|
m*****f
发帖数: 1243 | 7 一个简单的性质，假设最左边点坐标为A1=0, 然后依次为A2, A3....An
如果 k=1, 可以证明k必然在Am和A(m+1)之间 （m = n/2， n为偶数)， 或k和A(m+1)重
合(n为奇数). 也就是说左边和右边的点个数相等,
用data mining中的k-means方法， k已经给定， 初始聚类点为
A(n/2k), A(3*n/2k)....A((2k-1)n/2k)
其实就是把n个点分成K段然后取中点， 利用了上述性质
最后算法给出K个cluster 中心点即为答案
【在 r****o 的大作中提到】
: 直线上n个点，如何在该直线上找出k个点来，让这n个点各自映射到离自己最近的k个点
: 中的某个点，使得总距离最小?
: 注：这k个点可能从n个点中取，也可能不从n个点中取。
|
H*M
发帖数: 1268 | 8 check k-means clustering with k known
【在 r****o 的大作中提到】
: 直线上n个点，如何在该直线上找出k个点来，让这n个点各自映射到离自己最近的k个点
: 中的某个点，使得总距离最小?
: 注：这k个点可能从n个点中取，也可能不从n个点中取。
|
A********l
发帖数: 184 | 9 k-means 是近似， 不能保证是最优解，结果依赖于初值的选取
【在 m*****f 的大作中提到】
: 一个简单的性质，假设最左边点坐标为A1=0, 然后依次为A2, A3....An
: 如果 k=1, 可以证明k必然在Am和A(m+1)之间 （m = n/2， n为偶数)， 或k和A(m+1)重
: 合(n为奇数). 也就是说左边和右边的点个数相等,
: 用data mining中的k-means方法， k已经给定， 初始聚类点为
: A(n/2k), A(3*n/2k)....A((2k-1)n/2k)
: 其实就是把n个点分成K段然后取中点， 利用了上述性质
: 最后算法给出K个cluster 中心点即为答案
|
m*****f
发帖数: 1243 | 10 是啊， 所以我已经利用性质选初值了， 还有更好的选取方法么?
【在 A********l 的大作中提到】
: k-means 是近似， 不能保证是最优解，结果依赖于初值的选取
|
B***i
发帖数: 724 | 11
如何证明？ 好像反例很容易举呀
【在 m*****f 的大作中提到】
: 一个简单的性质，假设最左边点坐标为A1=0, 然后依次为A2, A3....An
: 如果 k=1, 可以证明k必然在Am和A(m+1)之间 （m = n/2， n为偶数)， 或k和A(m+1)重
: 合(n为奇数). 也就是说左边和右边的点个数相等,
: 用data mining中的k-means方法， k已经给定， 初始聚类点为
: A(n/2k), A(3*n/2k)....A((2k-1)n/2k)
: 其实就是把n个点分成K段然后取中点， 利用了上述性质
: 最后算法给出K个cluster 中心点即为答案
|
