作者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