[發(fā)明專利]一種基于哈希方法的多標(biāo)記學(xué)習(xí)的學(xué)習(xí)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510089183.3
• 申請(qǐng)日: 2015-02-27
• 公開(kāi)（公告）號(hào): CN104715021B
• 公開(kāi)（公告）日: 2018-09-11
• 發(fā)明（設(shè)計(jì)）人: 吳建盛;孫永;胡海峰
• 申請(qǐng)（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 南京知識(shí)律師事務(wù)所 32207
• 代理人: 汪旭東

1.一種基于哈希方法的多標(biāo)記學(xué)習(xí)的學(xué)習(xí)方法，其特征在于，所述方法包括如下步驟：

步驟1：給定輸入多標(biāo)記訓(xùn)練數(shù)據(jù)集D＝{(x_i,Y_i)|1≤i≤m}以及測(cè)試樣例x_t，Y_i為所對(duì)應(yīng)樣本x_i的標(biāo)記集向量；訓(xùn)練集樣本集合X(N×m,N是樣本個(gè)數(shù)，m是樣本屬性的維度)；訓(xùn)練集標(biāo)記集合Y(N×q,q是標(biāo)簽的數(shù)量)；

步驟2：對(duì)于訓(xùn)練數(shù)據(jù)集的標(biāo)記集合執(zhí)行MinHash降維算法，將原始的標(biāo)記集合矩陣由N×q維為壓縮為p×q維矩陣

步驟3：對(duì)樣本集合X_N×m和新的標(biāo)記集合分別執(zhí)行LSH算法，計(jì)算出每個(gè)樣本的近鄰N(x_i)和每個(gè)標(biāo)記的近鄰N(y_j)；

步驟4：對(duì)于測(cè)試樣例x_t，執(zhí)行LSH計(jì)算出x_t的近鄰N(x_t)；

步驟5：計(jì)算每個(gè)標(biāo)記y_j,j＝1,2,…,q的后驗(yàn)概率，所述后驗(yàn)概率是基于標(biāo)記相關(guān)性擴(kuò)展的后驗(yàn)概率公式進(jìn)行計(jì)算；

步驟6：根據(jù)多標(biāo)記學(xué)習(xí)算法構(gòu)建多標(biāo)記分類器；根據(jù)多標(biāo)記分類器，得到預(yù)測(cè)的標(biāo)記集合，即：分類結(jié)果；

所述方法的MinHash降維算法，對(duì)標(biāo)記空間進(jìn)行降維，其標(biāo)記向量是利用樣本來(lái)表示的，是一個(gè)N×1維的向量，具體為：如果x_i具有標(biāo)記y_j，則y_j(i)＝1，否則y_j(i)＝0；

所述方法包括：多標(biāo)記算法的標(biāo)記相關(guān)性擴(kuò)展、多標(biāo)記算法的MinHash降維、基于LSH的近鄰查找，其中標(biāo)記相關(guān)性擴(kuò)展，是將標(biāo)記之間的相關(guān)性引入到算法中，通過(guò)標(biāo)記之間的相互影響更好的進(jìn)行分類，MinHash降維，利用MinHash算法對(duì)標(biāo)記空間進(jìn)行降維，LSH近鄰查找可以在低時(shí)間復(fù)雜度的情況下獲取近鄰，將算法的計(jì)算復(fù)雜度充分降低，使其可擴(kuò)展到大規(guī)模數(shù)據(jù)情況的多標(biāo)記學(xué)習(xí)中；標(biāo)記相關(guān)性擴(kuò)展包括：

在基于貝葉斯統(tǒng)計(jì)學(xué)理論的多標(biāo)記學(xué)習(xí)算法中，一個(gè)重要的步驟是計(jì)算后驗(yàn)概率，給定多標(biāo)記訓(xùn)練集D＝{(x_i,Y_i)|1≤i≤m}以及測(cè)試樣例x，Y_i為所對(duì)應(yīng)樣本x_i的標(biāo)記集向量，對(duì)于第j個(gè)類別y_j(1≤j≤q)，基于貝葉斯定理的計(jì)算后驗(yàn)概率的公式如下：

其中，H_j代表x具有類別標(biāo)記y_j這一事件，P(H_j|C_j)代表當(dāng)N(x)中有C_j個(gè)樣本具有類別標(biāo)記y_j時(shí)，H_j成立的后驗(yàn)概率，相應(yīng)的，P(-H_j|C_j)代表當(dāng)N(x)中有C_j個(gè)樣本具有類別標(biāo)記y_j時(shí)，H_j不成立的后驗(yàn)概率，N(x)代表x在訓(xùn)練集中的近鄰樣本構(gòu)成的集合，通過(guò)貝葉斯定理轉(zhuǎn)換為求先驗(yàn)概率和條件概率，P(H_j)與P(-H_j)分別代表事件H_j成立與不成立的先驗(yàn)概率，P(C_j|H_j)與P(C_j|-H_j)分別代表事件H_j成立與不成立時(shí)，N(x)中有C_j個(gè)樣本具有類別標(biāo)記y_j的條件概率，先驗(yàn)概率和條件概率可以通過(guò)對(duì)訓(xùn)練集合進(jìn)行統(tǒng)計(jì)分析得到；

基于貝葉斯統(tǒng)計(jì)學(xué)算法采用了一階策略來(lái)求解多標(biāo)記學(xué)習(xí)問(wèn)題對(duì)標(biāo)記y_j訓(xùn)練時(shí)，后驗(yàn)概率的公式中P(H_j|C_j)只考慮了N(x)中的樣本具有類別標(biāo)記y_j的情況，并沒(méi)有考慮其他標(biāo)記對(duì)標(biāo)記y_j的影響，即在模型構(gòu)建過(guò)程中忽略標(biāo)記之間的相互影響；

所述方法將標(biāo)記之間的相關(guān)性考慮在內(nèi)，將后驗(yàn)概率公式擴(kuò)展為：

f(x,y_j)＝P(H_j|C₁,C₂,…,C_q)/P(-H_j|C₁,C₂,…,C_q) (2)

式中將其他標(biāo)記引入后驗(yàn)概率的計(jì)算公式，充分考慮了標(biāo)記之間的相互影響；

在式(2)中對(duì)標(biāo)記y_j訓(xùn)練時(shí)，將所有標(biāo)記y_j都加入到了后驗(yàn)概率的計(jì)算中，在標(biāo)記集合中，其他標(biāo)記對(duì)標(biāo)記y_j的影響并不相同，有些標(biāo)記甚至?xí)a(chǎn)生負(fù)的影響，此外，將所有標(biāo)記加入計(jì)算公式中，計(jì)算復(fù)雜度也會(huì)提高，因此，為了解決這種問(wèn)題，對(duì)式(2)中的后驗(yàn)概率公式進(jìn)行了進(jìn)一步的改進(jìn)，考慮到標(biāo)記集合中其他標(biāo)記對(duì)標(biāo)記y_j的影響并不相同，對(duì)后驗(yàn)概率中加入的其他標(biāo)記進(jìn)行改進(jìn)，只考慮將部分標(biāo)記考慮到后驗(yàn)概率中，其中，標(biāo)記向量利用樣本來(lái)表示，假設(shè)樣本數(shù)量為N，則標(biāo)記向量y_j則是一個(gè)N×1維的(0,1)向量，具體表示為：

通過(guò)對(duì)標(biāo)記向量求近鄰，然后選取近鄰加入到后驗(yàn)概率的計(jì)算中，在算法的訓(xùn)練階段中，對(duì)訓(xùn)練數(shù)據(jù)集的樣本和標(biāo)記進(jìn)行統(tǒng)計(jì)，對(duì)其k近鄰進(jìn)行統(tǒng)計(jì)與分析，對(duì)標(biāo)記y_j訓(xùn)練時(shí)，通過(guò)對(duì)標(biāo)記y_j求近鄰獲取標(biāo)記y_j的前k個(gè)近鄰標(biāo)記，在后驗(yàn)概率的計(jì)算中，根據(jù)預(yù)先得到標(biāo)記的k近鄰集合，選取合適的標(biāo)記加入到后驗(yàn)概率的公式中，實(shí)現(xiàn)為：

假設(shè)標(biāo)記y_j的k近鄰集合為N(y_j)＝{i|y_i是y_j的近鄰標(biāo)記，1≤i≤q}，即N(y_j)中是標(biāo)記y_j的K個(gè)近鄰標(biāo)記的下標(biāo)，對(duì)標(biāo)記y_j進(jìn)行訓(xùn)練時(shí)，后驗(yàn)概率的計(jì)算公式變?yōu)椋?/p>

通過(guò)對(duì)標(biāo)記進(jìn)行選擇可以更好的考慮標(biāo)記之間的相關(guān)性，并且可以減少后驗(yàn)概率的計(jì)算復(fù)雜度。