请教一个聚类的问题 - CS版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

CS版 - 请教一个聚类的问题

相关主题
● 求助关于聚类问题	● 做过搜索结果排序算法的，咨询下。。。
● 这里有熟悉 spectral clustering 的吗？	● CS害了CS
● 请教minimum set cover Problem	● 请问怎么计算两种clustering之间的差异
● 有没有一种算法，能够实现分布式等分？	● 有无这种聚类的算法？
● 求最优价格的算法	● 有人做fuzzy clustering的么？ (转载)
● 问个在图中删除边和点的算法问题 (转载)	● 请教！关于clustering,可否实现这个？
● 数学算法	● [合集] fuzzy clustering, soft clustering 区别？
● 有没有啥好点的DAG的clustering 的算法啊？	● 有没有这样的 clustering 算法？

相关话题的讨论汇总
话题: bit话题: string话题: cluster话题: 聚类话题: 最优

进入CS版参与讨论

(共1页)

j*****h
发帖数: 62

假如我现在有n个bit string. (每个string由m个非0即1的bit组成)。任意两个
bit string之间的距离定义为他们xor以后结果的bit string中出现1的次数。
多个bit string可以通过bit or操作聚成一个bit string cluster.请问如何
设计一个算法，给定n个这样的bit string，以及给定k个cluster数目限制，
找到最优的聚类，使得所有的n个bit string到他们各自的聚类以后，对应的
bit string cluster的距离之和最小。
我想到用bottom up的用贪婪算法heuristic。初始的时候，每个bit string代表一个
cluster. 然后每一步迭代，找出距离最近的两个cluster，or成一个新的
cluster,这样cluster数目减少一个。迭代直到cluster 总数等于k结束。
可是数学上我不知道如何证明这个算法得到的是否是最优解，如果不是，这
个approximation离最优解有多大差距。

(共1页)

进入CS版参与讨论

相关主题
● 有没有这样的 clustering 算法？	● 求最优价格的算法
● how to find a cluster	● 问个在图中删除边和点的算法问题 (转载)
● 请问这样的distance怎么计算？	● 数学算法
● k-means怎样改进能使cluster大小大致一样	● 有没有啥好点的DAG的clustering 的算法啊？
● 求助关于聚类问题	● 做过搜索结果排序算法的，咨询下。。。
● 这里有熟悉 spectral clustering 的吗？	● CS害了CS
● 请教minimum set cover Problem	● 请问怎么计算两种clustering之间的差异
● 有没有一种算法，能够实现分布式等分？	● 有无这种聚类的算法？

相关话题的讨论汇总
话题: bit话题: string话题: cluster话题: 聚类话题: 最优

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天