Re: [問題] 問一個分群的問題

看板CSSE (電腦科學及軟體工程)作者clliu168 (風)時間12年前 (2011/08/27 13:34)推噓0(0推 0噓 2→)

留言2則, 1人參與討論串2/2 (看更多)

※ 引述《Arim (Arim5566)》之銘言： : 各位板友好 : 小弟最近碰到一個分群的問題 : 首先我有一個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)這一群並不是最大的...請問有什麼有效率的演算法有辦法 : 解決目前我遇到的這個問題嘛？ : 謝謝指教 How about Agglomerative Hierarchical Clustering? 因為你的問題有 constraints，所以從底下開始 merge 的時候，只有 similarity 超過門檻才做 merge，等於是稍微修改一下 Hierarchical Clustering 演算法。我沒仔細去 trace 過，不過應該是可行 -- My Blog: http://webapp-tech.blogspot.com/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.188.212