作者Arim (Arim5566)
看板CSSE
标题[问题] 问一个分群的问题
时间Fri Aug 26 23:07:42 2011
各位板友好
小弟最近碰到一个分群的问题
首先我有一个term-by-document的matrix
假设我有8个term是A B C D E F G H
想利用cos similarity对这8个term做分群
分群的条件是群内的任两个term的cos similarity都大於等於门槛值
例如最後分出来的最大的两群为(A B C D) 以及 (F G H)
群内的任意两个term的cos similarity都大於等於门槛值
但是目前能想到的方法只有暴力法
例如先找跟A的cos similarity大於等於门槛值的term
可以先找到(A B C D E)这一个群，这时候就跑回圈检查B C D E的相似度
在回圈的过程中发现B跟E不相似，所以要把E或B拿掉，如果把E拿掉的话，
会变成(A B C D)，之後检查C跟D也符合条件，就输出(A B C D)这一个群，
但如果把B拿掉的话，会变成(A C D E)，但可能之後的检查过程中发
现C跟E又不相似，之後把C拿掉，接着D跟E又不相似，之後把D拿掉，到最後只会
剩下(A E)，但是(A E)这一群并不是最大的...请问有什麽有效率的演算法有办法
解决目前我遇到的这个问题嘛？
谢谢指教
--
~宅男的四个徵兆~
∠□ ○ ！ * \○/ ★ (○ ？
╦╦└□ " ○□═ □ □>
║║√√ ╦══╦ ∥ |\
一回家就上PTT 每天想正妹 以当好人为乐 忘记正妹亏欠自己
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.32.197.57
※ 编辑: Arim 来自: 114.32.197.57 (08/26 23:09)
※ 编辑: Arim 来自: 114.32.197.57 (08/26 23:10)
※ 编辑: Arim 来自: 114.32.197.57 (08/26 23:11)
※ 编辑: Arim 来自: 114.32.197.57 (08/26 23:13)
※ 编辑: Arim 来自: 114.32.197.57 (08/26 23:13)
※ Arim:转录至看板 Prob_Solve 08/26 23:16
1F：推 cansas:其实同样的问题我用过一个超简单的方法 每次都合并最像的词 10/26 01:28
2F：→ cansas:汇 先两两都比过 把最像的合起来 变成 一个群 再重复相同方 10/26 01:30
3F：→ cansas:法 直到剩下指定的群数 就完成了 10/26 01:30
4F：→ cansas:相似度可以简单定成 (A内积B)/|A|*|B| A与B为词汇向量 10/26 01:33
5F：→ cansas:当然这是一个超阳春的方法 有人用DP解 但你是词汇分群 建议 10/26 01:33
6F：→ cansas:用一些分群演算法 WEKA有 还很多 10/26 01:34