[發明專利]一種基于貪心策略和啟發式算法搜索候選類別的方法

在審

• 申請號: 201310405219.5
• 申請日: 2013-09-06
• 公開（公告）號: CN103488707A
• 公開（公告）日: 2014-01-01
• 發明（設計）人: 何力;賈焰;楊樹強;周斌;韓偉紅;李愛平;韓毅;李莎莎;丁兆云
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

1.一種基于貪心策略和啟發式算法搜索候選類別的方法，用以從測試文檔中搜索出候選類別，其特征在于，其包括以下步驟：

步驟S01、輸入已知信息：提供樣本集合I＝{d₁,d₂,...,d_n}，特征集合F＝{f₁,f₂,...f_m}，類別集合L＝{l₁,l₂,...l_r}；

步驟S02、初始化評價指標V_k及特征權重矩陣G：采用詞頻向量初始化類別的特征權重矩陣G，通過統計每個詞在同一類別l_i所有文檔中的出現次數得到該類別的詞頻向量，從而,為每個類別l_i建立一個詞頻向量w_i，w_ij為特征f_j關于類別l_i的權重，并對詞頻向量進行標準化，使得每個詞頻向量w_i滿足通過對樣本集合I進行一次遍歷即可生成初始類別的特征權重矩陣G＝{w₁,w₂,...,w_i...w_r}^T，并計算出初始評價指標V_k值；

步驟S03、采用貪心策略和啟發式算法更新評價指標V_k及特征權重矩陣G，并求出具有最大V_k值的特征權重矩陣G，具體包括以下步驟：

S031、啟發式優化解：采用步驟S02求得的初始類別的特征權重矩陣G依次對每個樣本文本d進行候選搜索測試，計算樣本文本d的候選類別集合E(d)，如果即當前解不能正確搜索到樣本文本d的候選類別，則按照權重更新方法Correct-Error(c,d)更新G，通過運行Correct-Error(c,d)，可以保證c∈E(d),即通過執行該更新算法，使當前樣本文本能夠被正確地搜索到其候選類別，其中，Correct-Error包括三步：（1）計算樣本最大類別相關性得分(score(d)_max)和樣本類別相關性得分(score_c(d))之差Δ＝score(d)_max-score_c(d)；（2）計算樣本類別的每個特征值的并用g(Δ，t_j)對樣本類別的特征向量進行更新w_cj’＝w_cj+g(Δ,t_j)；（3）對更新后的向量進行標準化其中，所述類別相關性得分采用內積或者余弦相似度計算，采用詞頻向量〈t₁,t₂,...t_m〉表示樣本文本d，d的真實類別為c，d關于類別c的相似性得分為score_c，d在所有類別L＝{l₁,l₂,...l_r}中的最高的相似性得分為score_max,Δ是二者的分差，g(Δ，t_j)是更新w_cj時的增加量，ρ是調節因子且默認取值為1；

S032、迭代終止判定：在每次遍歷整個樣本集合I之后計算V_k，如果得到了一個可接受的解V_k即該V_k大于或等于一常數，或者迭代次數達到設定上限值，則迭代終止；

步驟S04、根據步驟S03得出的最大V_k值的特征權重矩陣G，計算出相應的候選類別集合，即為要找到候選類別集合；

其中，其中，|I|為樣本總數，V_k(d_i)可根據以下算出：對于候選搜索算法Γ和測試文檔d，由算法Γ搜索的候選類別集合為E，假設E的大小為k，對于單標簽分類問題，如果E包含d的真實類別，則V_k(d)=1，否則為0；對于多標簽分類問題，如果E中包含a個d的真實類別，則V_k(d)＝a/l_d，其中,l_d是d的真實類別數目。