李學(xué)貴 許少華,2 李 娜 于文韜

(1.東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318； 2.山東科技大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266590；3.中國石油大慶油田化工有限責(zé)任公司東昊分公司，黑龍江 大慶 163312)

一種基于多示例學(xué)習(xí)的動(dòng)態(tài)樣本集半監(jiān)督聚類算法

李學(xué)貴1許少華1,2李 娜3于文韜1

(1.東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318； 2.山東科技大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266590；3.中國石油大慶油田化工有限責(zé)任公司東昊分公司，黑龍江 大慶 163312)

針對(duì)時(shí)域空間動(dòng)態(tài)樣本模式分類和標(biāo)記信息的有效利用問題，提出了一種基于多示例學(xué)習(xí)的動(dòng)態(tài)樣本半監(jiān)督聚類算法。根據(jù)時(shí)間信號(hào)的結(jié)構(gòu)關(guān)系和模態(tài)特征，建立動(dòng)態(tài)樣本的多示例信息表示模型；通過定義一種可度量時(shí)變函數(shù)樣本包間近似度的廣義Hausdorff距離和基于近鄰傳播的聚類原則，構(gòu)建多示例動(dòng)態(tài)樣本包的半監(jiān)督聚類算法。算法利用樣本包的類別先驗(yàn)知識(shí)構(gòu)建樣本集初始劃分種子簇并探索樣本的分布特征，采用基于廣義Hausdorff距離的近鄰傳播策略調(diào)整樣本包聚類，突出動(dòng)態(tài)指標(biāo)局部模態(tài)變化特征在樣本分類中的差異性。以油田地質(zhì)研究中測(cè)井曲線油層水淹狀況判別為例，驗(yàn)證了模型和算法的有效性。

油層水淹狀況判別 聚類算法 時(shí)變函數(shù)集合 半監(jiān)督學(xué)習(xí) 多示例模型

非平穩(wěn)動(dòng)態(tài)信號(hào)的分類和辨識(shí)一直是信息處理方法研究中的一個(gè)重要方向。由于實(shí)際中時(shí)變采樣信號(hào)模態(tài)變化的多樣性和隨機(jī)性，一些非線性系統(tǒng)產(chǎn)生的過程信號(hào)常常表現(xiàn)出多峰性、交遇性和整體特征的模糊性，給信號(hào)的識(shí)別和分析帶來困難。一些情況下，同類動(dòng)態(tài)信號(hào)樣本模態(tài)特征之間有著較大的歧義性或存在反例，而不同類信號(hào)樣本的形態(tài)特征差異卻很小，致使現(xiàn)有許多自動(dòng)分析方法和模型的魯棒性和辨識(shí)精度低、泛化性質(zhì)不穩(wěn)定。因此，如何突出并拾取信號(hào)樣本特征的差異性，有效利用標(biāo)記樣本的先驗(yàn)知識(shí)，已成為復(fù)雜信號(hào)分類處理中一個(gè)迫切需要解決的問題[1,2]。

近幾年，多示例和半監(jiān)督的學(xué)習(xí)方法受到廣泛關(guān)注，在細(xì)節(jié)分析、局部特征提取及標(biāo)記信息的有效利用等方面表現(xiàn)出優(yōu)勢(shì)，并成功應(yīng)用于藥物分子的活性分析、圖像識(shí)別與檢索及文本分類與模式匹配等實(shí)際領(lǐng)域[3～9]。如果將多示例和半監(jiān)督的學(xué)習(xí)機(jī)制與動(dòng)態(tài)信號(hào)模式識(shí)別方法相結(jié)合，建立起一種融合不同方法優(yōu)勢(shì)的信息模型，則在機(jī)制上可提高對(duì)非平穩(wěn)復(fù)雜信號(hào)的辨識(shí)和分析能力。

聚類分析是一種典型的非監(jiān)督機(jī)器學(xué)習(xí)和數(shù)據(jù)分析方法，在工程領(lǐng)域和科學(xué)研究中有著廣泛的應(yīng)用[10,11]。筆者將半監(jiān)督與多示例的學(xué)習(xí)框架向時(shí)域空間擴(kuò)展，針對(duì)動(dòng)態(tài)樣本的聚類和分類問題，提出一種基于多示例學(xué)習(xí)的時(shí)變函數(shù)樣本集半監(jiān)督聚類算法。首先根據(jù)系統(tǒng)時(shí)間信號(hào)的結(jié)構(gòu)特征，建立動(dòng)態(tài)樣本的多示例信息表示模型；然后針對(duì)多示例模型，構(gòu)建一種可度量動(dòng)態(tài)函數(shù)樣本包間距離的廣義Hausdorff測(cè)度范數(shù)，并基于該泛數(shù)和近鄰傳播策略建立多示例動(dòng)態(tài)樣本的半監(jiān)督聚類算法。算法利用已標(biāo)記樣本的類別信息構(gòu)建動(dòng)態(tài)樣本集不相交的初始劃分種子簇，采用近鄰傳播策略實(shí)現(xiàn)樣本的聚類分類和未標(biāo)記樣本的標(biāo)識(shí)。以石油地質(zhì)研究中基于測(cè)井曲線的油層水淹狀況判別為例，實(shí)際資料處理結(jié)果表明，該算法有效提高了聚類判別的準(zhǔn)確性。

1 動(dòng)態(tài)樣本的多示例表示模型和半監(jiān)督學(xué)習(xí)

1.1 動(dòng)態(tài)樣本的多示例表示模型

多示例學(xué)習(xí)(Multiple-Instance Learning,MIL)被認(rèn)為是和監(jiān)督學(xué)習(xí)、非監(jiān)督學(xué)習(xí)、強(qiáng)化學(xué)習(xí)并列的一種學(xué)習(xí)框架[12]。在多示例學(xué)習(xí)中，樣本被分割為由多個(gè)示例構(gòu)成的樣本包，每個(gè)示例展現(xiàn)了樣本不同方面的性質(zhì)。集合中只有包具有標(biāo)記，而示例不具備標(biāo)簽。MIL針對(duì)樣本包中每個(gè)示例進(jìn)行學(xué)習(xí)，在機(jī)制上可有效突出指標(biāo)變量的細(xì)節(jié)特征并濾除包中反例引起的歧義性。

筆者將多示例學(xué)習(xí)框架推廣到時(shí)域空間。對(duì)于時(shí)變函數(shù)集合，多示例模型是將每個(gè)時(shí)間數(shù)據(jù)對(duì)象表示為包含多個(gè)時(shí)間過程示例的樣本包，訓(xùn)練為針對(duì)每個(gè)時(shí)間函數(shù)示例的學(xué)習(xí)過程，如圖1所示。

圖1 動(dòng)態(tài)樣本多示例學(xué)習(xí)模型

圖1中，A(t)為時(shí)變函數(shù)樣本包，Ai(t)為包中示例，f(·)為變換函數(shù)，y(·)為輸出。

時(shí)域空間的多示例學(xué)習(xí)可描述為：設(shè)某一時(shí)變函數(shù)樣本包集合S={Bi(t)}，其中Bi(t)為時(shí)變函數(shù)包，每個(gè)Bi(t)具有mi個(gè)示例，記為Bi1(t),Bi2(t),…,Bimi(t)，而Bij(t)為一個(gè)時(shí)間函數(shù)向量。包Bi(t)所獲得的觀察結(jié)果記為f(Bi(t))，這里函數(shù)f表示某一未知的學(xué)習(xí)過程。多示例學(xué)習(xí)的目標(biāo)是通過對(duì)樣本集合的不斷訓(xùn)練，最終得到未知函數(shù)映射f的一個(gè)最佳逼近F。完整的訓(xùn)練樣例可形式化地表示為〈{Bi1(t),Bi2(t),…,Bimi(t)},f(Bi(t))〉。

1.2動(dòng)態(tài)樣本集的半監(jiān)督學(xué)習(xí)

半監(jiān)督學(xué)習(xí)的基本思想是借助數(shù)據(jù)集分布上的模型假設(shè)，通過構(gòu)建機(jī)器學(xué)習(xí)模型來針對(duì)少量已標(biāo)記樣本和大量未標(biāo)記樣本進(jìn)行學(xué)習(xí)與訓(xùn)練[13]。半監(jiān)督聚類是利用樣本集合中已標(biāo)記樣本的類別信息來輔助指導(dǎo)非監(jiān)督聚類的過程。將數(shù)據(jù)集上的半監(jiān)督學(xué)習(xí)機(jī)制進(jìn)行推廣，動(dòng)態(tài)樣本集的半監(jiān)督學(xué)習(xí)問題可描述為：給定動(dòng)態(tài)函數(shù)樣本集S=L∪U，其中，L={(x1(t),y1),(x2(t),y2),…,(xl(t),yl)}?X(t)×Y是有標(biāo)記樣本集，Y為標(biāo)簽集合；U={xl+1(t),xl+2(t),…,xN(t)}?X(t)是未標(biāo)記樣本集，t∈[0,T]。半監(jiān)督學(xué)習(xí)的問題是利用樣本集L的標(biāo)記信息，指導(dǎo)構(gòu)建時(shí)變過程函數(shù)的學(xué)習(xí)模型，對(duì)未標(biāo)記樣本集U中的樣本進(jìn)行分析處理。

2 動(dòng)態(tài)樣本包間距離的度量

基于多示例表示的動(dòng)態(tài)樣本集合的聚類，應(yīng)首先構(gòu)建可度量時(shí)變函數(shù)樣本包間距離的泛數(shù)，使它能夠有效計(jì)算出不同樣本包之間的近似度。

2.1Hausdorff距離

Hausdorff距離是一種度量數(shù)據(jù)集合之間距離的范數(shù)[14]。在多示例學(xué)習(xí)中，由于處理的對(duì)象和目標(biāo)是數(shù)據(jù)包和數(shù)據(jù)包之間的廣義距離關(guān)系，因此，引入一種Hausdorff距離[15]來度量包集合間的相似度：

(1)

其中，a和b分別為包A和包B中的示例元素，NA和NB為集合的測(cè)度。從拓?fù)鋷缀谓Y(jié)構(gòu)分析，H(A，B)為泛數(shù)空間中某一包中示例與另一包中距它最近的示例之間距離的平均值，這樣定義包間的距離反映了包間示例的幾何關(guān)系。

2.2時(shí)變函數(shù)樣本包間的廣義Hausdorff距離

基于多示例模型的動(dòng)態(tài)樣本聚類分析的對(duì)象為時(shí)變函數(shù)樣本包，為此，將Hausdorff距離H(A,B)推廣到時(shí)變函數(shù)空間，建立一種可度量時(shí)變函數(shù)樣本包間性質(zhì)近似度的廣義Hausdorff距離。

設(shè)兩個(gè)時(shí)變函數(shù)樣本包分別為：

A(t)={a1(t),a2(t),…,am(t)}

B(t)={b1(t),b2(t),…,bn(t)}

其中，ai(t)=[ai,1(t),ai,2(t),…,ai,d(t)]T,bj(t)=[bj,1(t),bj,2(t),…,bj,d(t)]T,t∈[0,T],1≤i≤m,1≤j≤n,1≤k≤d。

考慮包A(t)、B(t)中的示例元素ai,k(t)、bj,k(t)，這兩個(gè)函數(shù)差的2范數(shù)反映了函數(shù)間模態(tài)特征(形態(tài)、幅值等)的近似度。示例ai(t)與bj(t)之間的距離范數(shù)定義為：

(2)

當(dāng)ai，k(t)、bj，k(t)為時(shí)間區(qū)間[0,T]上的離散數(shù)據(jù)點(diǎn)時(shí)，采用切比雪夫范數(shù)來度量示例ai(t)與bj(t)之間的距離：

(3)

由式(1)得到多示例時(shí)變函數(shù)樣本集合的一種廣義Hausdorff距離：

(4)

3 多示例函數(shù)樣本集的半監(jiān)督聚類算法

3.1設(shè)計(jì)思路

設(shè)動(dòng)態(tài)函數(shù)樣本包集合中的元素有K個(gè)類標(biāo)簽。首先，將具有相同標(biāo)簽的函數(shù)樣本包聚合成一個(gè)聚類子集，共得到K個(gè)不相交子集，再把其他無標(biāo)簽樣本包歸類為一個(gè)子集，實(shí)現(xiàn)對(duì)集合的初始劃分；然后，以K+1個(gè)子集的質(zhì)心作為初始聚類中心點(diǎn)，通過設(shè)置聚類參數(shù)和距離閾值，基于廣義Hausdorff距離，采用近鄰傳播策略[16]，對(duì)無標(biāo)簽樣本包子集進(jìn)行劃分。在聚類參數(shù)控制下，即可將無標(biāo)簽樣本歸類為有標(biāo)簽的子集，也可生成新的聚類子集，聚類結(jié)果應(yīng)滿足所有樣本到最近的聚類中心的相似度之和最大的原則。同時(shí)，每一步劃分也要滿足具有不同標(biāo)簽的樣本包不能劃分到同一子類的約束條件。在聚類過程中，考慮兩種情況：樣本包集合的聚類數(shù)與標(biāo)簽類別數(shù)相同和樣本包標(biāo)簽類別數(shù)小于實(shí)際樣本包集合的聚類數(shù)。

3.2實(shí)際聚類數(shù)與標(biāo)簽類別數(shù)相同時(shí)的聚類

若根據(jù)先驗(yàn)知識(shí)，已知集合的聚類數(shù)與樣本包標(biāo)簽的類別數(shù)相同。在這種情況下，只需將無標(biāo)簽樣本劃分到已標(biāo)記樣本子集即可。

具體步驟如下：

b. 從樣本集U中將數(shù)據(jù)包Bi(t)(i=1,2,…,NU)加入子類Gh(h=1,2,…,K)中。

3.3樣本包標(biāo)簽類別數(shù)小于實(shí)際樣本包集合的聚類

這種情況下，設(shè)定3個(gè)聚類參數(shù)：初始聚類數(shù)目K、樣本包間廣義Hausdorff距離閾值θ和類間距離閾值R。在上節(jié)算法基礎(chǔ)上，進(jìn)行如下改進(jìn)：

a. 將集合中非標(biāo)識(shí)函數(shù)樣本包依次計(jì)算與每個(gè)初始聚類中心Ci(t)之間的廣義Hausdorff距離。若最小距離大于θ，則以該函數(shù)樣本包作為成員形成一個(gè)新類，并以該包作為新類的聚類中心，K+1→K；否則，將該樣本歸于廣義Hausdorff距離最小的一類，并重新計(jì)算聚類中心。

b. 計(jì)算K個(gè)聚類兩兩之間的類距離。若其中一個(gè)子類中所有樣本均無標(biāo)簽，且兩個(gè)類的類間距離小于R，則將這兩個(gè)類合并，重新計(jì)算聚類中心；若兩類類間距離大于R，則聚類不做改變；若兩類中均包含有標(biāo)簽樣本，則聚類不做改變。

c. 執(zhí)行步驟a和b后，若聚類數(shù)發(fā)生改變，則以新的分類個(gè)數(shù)替代K；如果聚類結(jié)果(包括聚類數(shù)和函數(shù)樣本包的具體分類)改變，則返回步驟a繼續(xù)執(zhí)行；如果聚類結(jié)果不再變化，則聚類完成。

在上述聚類算法中，由于廣義Hausdorff距離是基于函數(shù)樣本包中的示例進(jìn)行距離計(jì)算的，因而突出了過程函數(shù)樣本指標(biāo)變量模態(tài)特征變化在聚類中的差異性。

4 在測(cè)井曲線油層水淹狀況判別中的應(yīng)用

測(cè)井曲線的油層水淹狀況判別是油田注水開發(fā)階段一項(xiàng)重要的研究工作。水淹層判別主要依據(jù)的是反映油層物理性質(zhì)隨深度變化的多條測(cè)井曲線的形態(tài)、幅值特征及其組合關(guān)系，水淹狀況分為未水淹、弱水淹、中水淹和強(qiáng)水淹4個(gè)等級(jí)，一般采用自然電位SP、2.5m電阻率R25、微電極之差(Rmt-Rmd)3條測(cè)井曲線和小層厚度共4個(gè)變量進(jìn)行判別。在實(shí)際中，一個(gè)油田開發(fā)區(qū)塊一般只有20%的檢查井進(jìn)行巖心樣品的取心工作，可通過實(shí)驗(yàn)室分析直接確定油層的水淹程度，其余的井是根據(jù)所獲得的測(cè)井曲線進(jìn)行人工解釋來判斷油層的水淹情況。如果將油層所對(duì)應(yīng)的測(cè)井曲線看作是隨深度變化的過程函數(shù)樣本，則可利用筆者建立的多示例半監(jiān)督聚類算法進(jìn)行油層水淹判別。

選取某油田開發(fā)區(qū)塊中23口井192個(gè)油層樣本的實(shí)際測(cè)井曲線作為實(shí)驗(yàn)數(shù)據(jù)，每米20個(gè)采樣點(diǎn)，其中4口檢查井中37個(gè)油層樣本具有水淹程度標(biāo)記，覆蓋了4種水淹類型。以每個(gè)油層對(duì)應(yīng)的測(cè)井變量隨深度變化的連續(xù)采樣數(shù)據(jù)(函數(shù))作為示例，則該示例反映了測(cè)井變量在小層上的幅值和形態(tài)特征，以4個(gè)測(cè)井變量形成的小層4維過程數(shù)據(jù)(即4個(gè)示例)構(gòu)成樣本包。對(duì)于取心井中的油層樣本包有標(biāo)簽，但示例無標(biāo)簽；而非取心井的小層樣本包和示例均無標(biāo)簽。在聚類過程中，以標(biāo)記樣本的類別代表分組類別。實(shí)際資料處理時(shí)，將不同油層樣本歸一化處理[17]為[0,1]區(qū)間上的函數(shù)，使每個(gè)油層對(duì)應(yīng)的測(cè)井曲線具有統(tǒng)一的過程區(qū)間。以歸一化后的SP、R25、Rmt-Rmd共3條測(cè)井曲線和油層厚度作為油層樣本包中的示例。利用筆者建立的動(dòng)態(tài)聚類算法對(duì)192個(gè)油層樣本進(jìn)行聚類分析，經(jīng)過52次迭代調(diào)整后分類結(jié)果不再變化，同時(shí)滿足同一聚類中不出現(xiàn)兩種不同標(biāo)記樣本的約束。經(jīng)與分層試油資料對(duì)比，無標(biāo)簽樣本的正確識(shí)別率達(dá)到83.87%，這在水淹層自動(dòng)判別中是一個(gè)較好的結(jié)果。

5 結(jié)束語

建立的基于多示例模型的時(shí)變函數(shù)樣本集半監(jiān)督聚類算法，通過構(gòu)建可度量時(shí)變函數(shù)樣本包間相似性的廣義距離，并有效利用標(biāo)記樣本的先驗(yàn)知識(shí)和分布特征，可直接針對(duì)時(shí)域空間中的過程信號(hào)進(jìn)行聚類分析，實(shí)際資料處理結(jié)果也驗(yàn)證了該方法的可行性和有效性。采用多示例模型，可突出指標(biāo)變量模態(tài)特征的差異性，對(duì)于復(fù)雜時(shí)間信號(hào)樣本的模式分類和判別問題具有較好的適應(yīng)性。

[1] 汪小龍,葛運(yùn)建,江劍.信息獲取科學(xué)與技術(shù)中信號(hào)處理體系的研究與建立[J].信息與控制，2004,33(2)：172～176.

[2] 周治宇,陳豪.盲信號(hào)分離技術(shù)研究與算法綜述[J].計(jì)算機(jī)科學(xué)，2009,36(10):16～20.

[3] Bennett K P,Demiriz A.Semi-supervised Support Vector Machines[C].Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems II.Cambridge: MIT Press,1998:368～374.

[4] Decomain C,Wrobel S.Advances in Intelligent Data Analysis[M].Heidelberg：Springer,2001:309～318.

[5] Zhu X J, Ghahramani Z,Lafferty J.Semi-supervised Learning Using Gaussian Fields and Harmonic Functions[C].Proceedings of the Twentieth International Conference.Washington,DC：ICML，2003：912～919.

[6] Blum A,Chawla S.Learning from Labeled and Unlabeled Data Using Graph Min-cuts[C].Proceedings of the Eighteenth International Conference on Machine Learning. San Francisco:Morgan Kaufmann Publishers Inc,2001：19～26.

[7] Dietterich T G,Lathrop R H,Lozano-Pérez T.Solving the Multiple Instance Problem with Axis-parallel Rectangles[J].Artificial Intelligence,1997,89(12):31～71.

[8] 葛永,吳秀清,洪日昌.基于多示例學(xué)習(xí)的遙感圖像檢索[J].中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2009，39(2):132～136.

[9] 李杰，程義民，葛仕明，等．基于顯著點(diǎn)特征多示例學(xué)習(xí)的圖像檢索方法[J].光電子·激光，2008，19(10):1405～1409．

[10] 楊一鳴,潘嶸,潘嘉林，等.時(shí)間序列分類問題的算法比較[J].計(jì)算機(jī)學(xué)報(bào)，2007,30(8):1259～1266.

[11] Pursley M B,Royster T C.High-rate Direct-sequence Spread Spectrum with Error-control Coding[J].IEEE Trans on Commun,2006,54(9):1693～1702.

[12] 蔡自興,李枚毅.多示例學(xué)習(xí)及其研究現(xiàn)狀[J].控制與決策，2004，19(6)：607～610．

[13] 周志華．半督學(xué)習(xí)的協(xié)同訓(xùn)練算法[M].北京：清華大學(xué)出版社，2007：259～275．

[14] Edgar G A. Measure,Topology,and Fractal Geometry[M].New York:Springer,1995.

[15] 謝紅薇，李曉亮．基于多示例的K-means聚類學(xué)習(xí)算法[J]．計(jì)算機(jī)工程，2009，35(22)：179～181．

[16] 肖宇,于劍.基于近鄰傳播算法的半監(jiān)督聚類[J]．軟件學(xué)報(bào)，2008，19(11)：2803～2813．

[17] 許少華,劉揚(yáng),何新貴.基于過程神經(jīng)網(wǎng)絡(luò)的水淹層自動(dòng)識(shí)別系統(tǒng)[J].石油學(xué)報(bào)，2004，25(4):54～57.

ASemi-supervisedDynamicSampleSetClusteringAlgorithmBasedOnMulti-instanceLearning

LI Xue-gui1, XU Shao-hua1,2, LI Na3, YU Wen-tao1

(1.CollegeofComputerScience&InformationTechnology,NortheastPetroleumUniversity,Daqing163318,China;2.CollegeofInformationScienceandEngineering,ShandongUniversityofScienceandTechnology,Qingdao266590,China;3.DonghaoBranchCompany,CNPCDaqingOilfieldChemicalCo.,Ltd.,Daqing163312,China)

Aiming at the effective use of time-domain space dynamic sample’s pattern classification and mark information in time-domain space, a multi-instance learning-based semi-supervised dynamic sample clustering algorithm was proposed. Basing on both structural relationship and modal characteristics of time signals, the multi-instance information model for dynamic samples was established; through defining a generalized Hausdorff distance which measures the similarity among time-varying function samples and considering affinity propagation-based clustering principle, a semi-supervised clustering algorithm for multi-instance dynamic samples was founded. This algorithm adopts category priori knowledge to build sample set’s initially-partitioned seed cluster and to explore samples’ distribution characteristics; and it adjusts sample clustering dynamically by adopting the generalized Hausdorff distance-based affinity propagation strategy so as to highlight dynamic index modal feature’s individual difference in sample classification. Taking the recognition of oil layer’s water flooded condition in well logging as an example, both model and algorithm’s effectiveness was proved.

clustering algorithm for discriminating oil layer’s water flooded condition, time-varying function set, semi-supervised learning, multi-instance model

TP14

A

1000-3932(2016)11-1153-05

2016-09-30(修改稿)

國家自然科學(xué)基金項(xiàng)目(61170132)；中國石油科技創(chuàng)新基金項(xiàng)目(2010D-5006-0302)