基于模糊多特征遞歸分組算法的隱樹結構圖模型學習

李宏偉 文成林*② 徐曉濱

?

基于模糊多特征遞歸分組算法的隱樹結構圖模型學習

李宏偉①文成林*①②徐曉濱①

①(杭州電子科技大學自動化學院 杭州 310018)②(河南工業(yè)大學電氣工程學院 鄭州 450001)

隱樹結構圖模型通過引入了隱藏節(jié)點來描述變量之間的潛在關系，因而可以更好地對變量之間的相關性進行建模。樹模型學習過程中，從變量觀測數(shù)據(jù)所提取的有用特征數(shù)量，決定了該模型對變量間深層關系的建模能力；而現(xiàn)有學習算法都是對觀測數(shù)據(jù)直接計算統(tǒng)計量來進行模型學習，未能按觀測數(shù)據(jù)中的特征分類處理。針對現(xiàn)有算法對觀測數(shù)據(jù)中信息利用不充分的不足，該文提出基于模糊多特征遞歸分組算法的隱樹模型學習方法。首先，將變量的原始觀測數(shù)據(jù)通過反映其特征的模糊隸屬度函數(shù)轉化成多個模糊特征，并構造多維模糊特征向量；其次，計算兩兩變量模糊特征向量之間的距離，并將其綜合得到所有變量之間的模糊特征向量距離矩陣；最后，基于該距離矩陣，利用遞歸分組算法學習隱樹模型。該文還將所提算法應用于股票收益數(shù)據(jù)和氣溫數(shù)據(jù)建模，驗證了該文算法的實用性和有效性。

信息處理；圖模型；隱樹模型；信息距離；模糊多特征

1 引言

圖模型[1]是描述大量隨機變量之間條件獨立結構的一個強有力框架，具有簡潔、緊湊、直觀等特點，一直是統(tǒng)計建模領域研究的熱點[2,3]。樹結構圖模型是節(jié)點之間具有樹形連接結構，且滿足馬爾科夫性的圖模型，具有易于學習、推理效率高等優(yōu)勢，促使人們在該領域進行了廣泛的研究與應用[4,5]。而隱樹模型是包含隱節(jié)點的樹結構圖模型[6]，由隱節(jié)點表示的隱變量可更好地對變量之間潛在相關性進行建模，顯著增強了樹模型的建模能力。隱樹模型已在一些領域得到了廣泛的應用，在生物信息學領域，利用隱樹學習算法從已滅絕物種的基因數(shù)據(jù)中推理得到物種進化樹[7,8]；計算機圖像領域，通過對圖像中物體位置關系建模得到層級上下文樹(hierarchical context tree)用于對待檢圖像中的物體進行檢測與識別[9]；此外，隱樹模型也常應用于圖像分割與標記[10]；在經(jīng)濟領域，可采用樹模型對經(jīng)濟數(shù)據(jù)建模，幫助人們更好地決策和投資等[11,12]。

現(xiàn)有的隱樹模型研究通常假設只有葉子節(jié)點是觀測節(jié)點，并且除了根節(jié)點之外的隱節(jié)點都具有相同的度。其中最為著名的隱樹模型學習算法是文獻[8]提出的鄰接算法(neighbor-joining)，該算法遞歸地將節(jié)點集合中最鄰近節(jié)點聚在一起并引入隱父節(jié)點直至形成完整的隱樹模型。文獻[13]于2010年提出了遞歸分組隱樹模型學習算法，該算法放寬了已有算法中只有葉子節(jié)點是觀測節(jié)點的限制，在算法執(zhí)行的過程中，可在樹模型內(nèi)部動態(tài)引入隱節(jié)點用于表示潛在的變量，提高了樹模型的建模能力以及適用范圍。隱樹模型學習算法基于統(tǒng)計距離框架，以上算法在計算變量之間距離時都是對觀測數(shù)據(jù)在整個采樣區(qū)間上直接計算統(tǒng)計量用于隱樹模型學習，未能針對觀測數(shù)據(jù)的特征進行分類處理，在學習過程中不能夠充分利用原始數(shù)據(jù)中的有用信息，所得到的隱樹模型不能很好反映觀測變量之間的相關性。

針對遞歸分組算法對觀測數(shù)據(jù)中信息利用不充分的不足，本文給出一種基于模糊多特征的遞歸分組隱樹模型學習方法，實現(xiàn)了從觀測數(shù)據(jù)中提取多個模糊特征用于變量關系的建模。本文還將所提算法應用于股票數(shù)據(jù)分類和城市氣溫數(shù)據(jù)建模，與原有基于觀測數(shù)據(jù)直接學習樹模型的方法相比，基于多維模糊特征建立的樹模型能夠更加完善地反映股票之間的相互關系和氣候的區(qū)域相關性。

2 樹結構圖模型簡介

2.1 無向圖和樹

2.2 樹結構圖模型

3 遞歸分組隱樹模型學習算法

3.1信息距離的計算

隱樹模型學習算法是基于統(tǒng)計距離框架的，本文采用信息距離(information distance)[6]作為變量之間相關性的度量。當觀測變量服從高斯分布時，模型中任意兩個相鄰節(jié)點和之間的信息距離為

圖1 經(jīng)典遞歸分組隱樹模型學習方法流程圖

事實上，由2.2節(jié)中無向圖模型的局部馬爾科夫性可以很容易地得到該性質(zhì)。

3.2基于信息距離學習隱樹結構圖模型

遞歸分組隱樹模型學習算法以自底向上的方式遞歸地對節(jié)點進行家庭分組，并通過動態(tài)引入隱節(jié)點來完成隱樹模型學習。遞歸分組算法的一個關鍵步驟是確定節(jié)點之間的關系，由家庭分組定理給出。

遞歸分組隱樹模型學習算法詳細步驟如下：

4 基于模糊多特征的遞歸分組隱樹模型學習算法

經(jīng)典遞歸分組算法直接對節(jié)點觀測采樣序列計算樣本統(tǒng)計量來計算變量之間的信息距離，沒有針對原始數(shù)據(jù)中的特征進行分類處理，未能充分利用原始數(shù)據(jù)中的有效信息，所得到的隱樹模型并不能很好地反映變量之間的相關性。

圖2 遞歸分組隱樹模型學習算法示意圖

事實上，觀測節(jié)點采樣的不同取值區(qū)間對于數(shù)據(jù)分析具有不同的意義。受勒貝格積分原理啟發(fā)，根據(jù)變量的特征對其采樣的取值區(qū)間進行劃分，不同的取值區(qū)間代表了觀測變量的不同特征。例如，對于表示某觀測對象變化速率的變量，可對采樣值劃分為“增速快”、“增速慢”等特征區(qū)間；然后分別計算兩兩觀測變量在對應特征上的距離，最后將所有特征上的距離融合用于隱樹模型學習。

在計算某個特征上的變量之間距離時，需要把觀測采樣值映射到對應特征區(qū)間上。文獻[16]在處理沖突性區(qū)間證據(jù)融合問題時采用區(qū)間模糊集歸一化的方法，本文在計算多個特征上的距離時采用了類似方法：首先對每個特征求取模糊隸屬度函數(shù)，然后對觀測采樣進行模糊化處理轉化成不同特征上的隸屬度，最后計算兩兩變量在每個特征上的距離。

本節(jié)提出的基于模糊多特征遞歸分組隱樹模型學習方法流程圖如圖3所示。

4.1 構造特征的模糊隸屬度函數(shù)

4.2 計算加權模糊信息距離矩陣

融合后的信息距離仍滿足命題1的可加性。事實上，對于融合后隱樹模型中任意兩個節(jié)點,W，二者距離為

將式(12)代入式(11)可得

由命題1可知，融合后的信息距離仍然滿足可加性。

4.3 .隱樹模型的結構學習和參數(shù)學習

最大化式(13)可獲得隱樹模型參數(shù)的最大似然估計。

5 實驗及分析

本節(jié)對兩組實際數(shù)據(jù)進行隱樹模型建模，并通過定性分析和參數(shù)指標對比來說明本文算法的有效性。實驗環(huán)境為Matlab，所用計算機的處理器為Intel Core?2 6400，主頻2.13 GHz，內(nèi)存2 GB。其中經(jīng)典遞歸分組算法參考了文獻[6]所提供的代碼。

當前，服務已經(jīng)成為企業(yè)開發(fā)市場的核心競爭力。楊福旺表示：“我們提出，所有銷售人員都是農(nóng)化服務人員，必須有服務能力。我們必須走價值營銷的理念，通過我們對最終客戶的服務來體現(xiàn)客戶的價值，讓產(chǎn)品提高產(chǎn)量、提高品質(zhì)。”

5.1 股票收盤指數(shù)變化趨勢的隱樹模型學習

實驗通過對股票收盤數(shù)據(jù)進行隱樹模型建模，來分析股票之間的潛在關系。觀測采樣是來自于國內(nèi)20只股票在2001年到2011年每月股票收盤數(shù)據(jù)，為便于表述，每5只股票為一組，將其列在一張子圖中，對應曲線如圖4所示。

圖4 20家公司在2001~2011年間股票收盤數(shù)據(jù)變化曲線

得到隱樹模型之后，再按照4.3節(jié)所介紹算法對模型參數(shù)進行學習。模型參數(shù)學習結果可以通過模型的似然度以及貝葉斯信息準則(BIC)得分進行評價。對數(shù)似然度是參數(shù)恢復過程中得到的，可由式(13)計算得到，較大的對數(shù)似然度表示所得到的模型能夠更好地逼近潛在的模型。BIC得分則可以在評價模型恢復效果的同時對模型的復雜度進行懲罰，防止模型的過擬合，其表達式為

圖5 20家公司股票收盤數(shù)據(jù)隱樹模型學習結果

表1 20家公司股票收盤數(shù)據(jù)所學習隱藏樹的對數(shù)似然度、BIC得分、參數(shù)個數(shù)及運行時間比較

從隱樹模型結構中可以直觀看到節(jié)點之間的相關性。鄰近的節(jié)點具有相似的變化趨勢，而隱節(jié)點則一般可表示為家庭內(nèi)節(jié)點所屬的“類別”，隱節(jié)點的存在增強了樹模型的建模能力和表達能力。從圖5(a)中可以看出，“深發(fā)展A”和“浦發(fā)銀行”，“小天鵝A”和“美的電器”，“中國醫(yī)藥”和“同仁堂”等都在一個家庭內(nèi)，我們可以命名相應隱父節(jié)點為“銀行類”，“電器類”，“醫(yī)藥類”。圖5(b)是采用經(jīng)典遞歸分組算法學習得到的樹模型，同樣反映了“深發(fā)展A”和“浦發(fā)銀行”等具有相似變化趨勢，但對于“中國醫(yī)藥”和“同仁堂”，僅僅通過隱節(jié)點1聯(lián)系在一起，未能反應出之間的相似性。

5.2 中國城市歷年氣溫數(shù)據(jù)的隱樹模型學習

表2是模型參數(shù)指標對比，從表中可看出，本文算法相對于經(jīng)典遞歸分組算法具有更高的對數(shù)似然度和BIC得分，說明本文算法所得到的隱樹模型能夠更好地逼近潛在的概率分布。兩個算法所學模型的參數(shù)個數(shù)接近，運行時間上可以看到本文算法略微慢于經(jīng)典遞歸分組算法，但比較接近。這和5.1節(jié)的實驗分析結果一致，當節(jié)點增多時樹模型遞歸構建算法部分運算量將占主導地位，此時兩種算法會有相近的運行時間。

表2 34個城市歷年溫度數(shù)據(jù)所學習隱藏樹的對數(shù)似然度、BIC得分、參數(shù)個數(shù)及運行時間比較

在學習得到的隱樹模型中，同一家庭內(nèi)的節(jié)點具有最為相似的氣候特征。圖6(a)是采用本文算法學習得到的隱樹模型，隱節(jié)點3的子節(jié)點都是沿海城市，隱節(jié)點5下面的幾個城市則都地處北方靠近內(nèi)陸，隱節(jié)點7的子節(jié)點“昆明”和“拉薩”則地處中國西南內(nèi)陸等。隱樹模型基本符合中國的氣候特征地理分布，且其中的隱節(jié)點可以命名為地理區(qū)域。采用經(jīng)典遞歸分組算法得到的隱樹模型如圖6(b)所示，其中一些家庭符合地域特征，如隱節(jié)點3下的后代。但是模型中存在一些混亂的組合，例如“濟南”和“拉薩”、“福州”和“青島”、“桂林”節(jié)點的后代等。模型未能很好反映氣候與地域特征，建模效果不如前者。

圖6 34個城市歷年溫度數(shù)據(jù)隱樹模型學習結果

通過以上兩個實驗分析可知，基于模糊多特征的遞歸分組算法與原始遞歸分組算法相比，學習所得到的隱樹模型能夠更好地逼近潛在的圖模型，并且具有更好的分類效果。

6 結束語

本文提出了一種基于模糊多特征的遞歸分組隱樹模型學習算法，克服了原有算法未能充分利用數(shù)據(jù)有效信息的不足，通過模糊隸屬度來表示數(shù)據(jù)的多個特征，更好地利用了數(shù)據(jù)中的有效信息來學習隱樹模型。文中同樣存在一些不足和亟待改進的地方。首先是變量的特征選取問題，本文采用了直接按照數(shù)據(jù)變化趨勢來劃分的處理方法，可以進一步考慮采用主元分析[19]等方法來進行特征選??；其次，對于多個特征上信息距離融合未充分考慮對各個特征進行加權處理，下一步工作中可按照類似于文獻[20]中基于樣本距離和樣本離散度加權等方法，對多特征信息距離據(jù)融合步驟進行改進。

[1] Lauritzen S L. Graphical Models[M]. Oxford University Press, Oxford, U K, 1996: 21-31.

[2] 程強, 陳峰, 董建武, 等. 概率圖模型中的變分近似推理方法[J]. 自動化學報, 2012, 38(11): 1721-1734.

Cheng Qiang, Chen Feng, Dong Jian-wu,.. Variational approximate inference methods for graphical models[J]., 2012, 38(11): 1721-1734.

[3] Manohar Shamaiah, Sang Hyun Lee, and Haris Vikalo. Graphical models and inference on graphs in genomics[J]., 2012, 29(1): 50-65.

[4] Willsky A S. Multiresolution markov models for signal and image processing[J]., 2002, 90(8): 1396-1458.

[5] Srinivas Umamahesh and Yi Chen. Exploiting sparsity in hyperspectral image classification via graphical models[J]., 2013, 10(3): 505-509.

[6] Choi M J, Tan Vincent Y F, Anandkumar A,.. Learning latent tree graphical models[J]., 2011, 12: 1771-1812.

[7] Chang J T and Hartigan J A. Reconstruction of evolutionary trees from pairwise distributions on current species[C]. Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, Seattle, USA, 1991: 254-257.

[8] Saitou N and Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees[J]., 1987, 4(4): 406-425.

[9] Choi M J, Lim J J, Torralba A,.. Context models and out-of-context objects[J]., 2012, 33(7): 853-862.

[10] Schwing A G, Hazan T, Pollefeys M,.. Efficient structured prediction with latent variables for general graphical models[C]. In Proceedings of the International Conference on Machine Learning (ICML), 2012: 11-18.

[11] Takai K. Exploration of dependencies among sections in a supermarket using a tree-Structured undirected graphical model[C]. 2012 IEEE 12th International Conference on Data Mining Workshops (ICDMW), Brussels, Belgium, 2012: 324-331.

[12] Eddie Chi-man Hui. An enhanced implied tree model for option pricing: a study on Hong Kong property stock options[J].&. 2006, 15(3): 324-345.

[13] Choi M J. Consistent and efficient reconstruction of latent tree models[C]. 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, USA, 2010: 719-725.

[14] Jordan M I and Weiss Y. Graphical Models: Probabilistic Inference[M]. Cambridge, MA: MIT Press, 1999: 243-266.

[15] Wainwright M J, Jaakkola T S, and Willsky A S. Tree-based reparameterization framework for analysis of sum-product and related algorithms[J]., 2003, 49(5): 1120-1146.

[16] 馮海山, 徐曉濱, 文成林. 基于證據(jù)相似性度量的沖突性區(qū)間證據(jù)融合方法[J]. 電子與信息學報, 2012, 34(4): 851-857.

Feng Hai-shan, Xu Xiao-bin, and Wen Cheng-lin. A new fusion method of conflicting interval evidence based on the similarity measure of evidence[J].&, 2012, 34(4): 851-857.

[17] 姜園, 張朝陽, 仇佩亮, 等. 用于數(shù)據(jù)挖掘的聚類算法[J]. 電子與信息學報, 2005, 27(4): 655-662.

Jiang Yuan, Zhang Zhao-yang, Qiu Pei-liang,.. Clustering algorithms used in data mining[J].&, 2005, 27(4): 655-662.

[18] Neal R and Hinton G. A View of the EM Algorithm that Justifies Incremental, Sparse, and Other Variants[M]. Learning in Graphical Models, Cambridge, MA: MIT Press, 1999: 355-368.

[19] 文成林, 胡靜, 王天真, 等. 相對主元分析及其在數(shù)據(jù)壓縮和故障診斷中的應用研究[J]. 自動化學報, 2008, 34(9): 1128-1139.

Wen Cheng-lin, Hu Jing, Wang Tian-zhen,.. Relative PCA with application of data compression and fault diagnosis[J]., 2008, 34(9): 1128-1139.

[20] 黃劍華, 丁建睿, 劉家鋒, 等. 基于局部加權的Citation-kNN算法[J]. 電子與信息學報, 2013, 35(3): 627-632.

Huang Jian-hua, Ding Jian-rui, Liu Jia-feng,.. Citation-kNN algorithm based on locally-weighting[J].&, 2013, 35(3): 627-632.

李宏偉： 男，1987年生，碩士生，研究方向為圖模型與信息融合.

文成林： 男，1963年生，教授，博士生導師，研究方向為多尺度估計理論、多尺度信息融合、故障診斷技術.

徐曉濱： 男，1980年生，副教授，研究方向為不確定性信息融合、系統(tǒng)可靠性評估與故障診斷.

Learning Latent Tree-structured Graphical Models Based on Fuzzy Multi-features Recursive-grouping Algorithm

Li Hong-wei①Wen Cheng-lin①②Xu Xiao-bin①

①(,,310018,)②(,,450001,)

Latent tree-structured graphical models explore the latent relationships among variables by introducing hidden nodes, therefore they can better model the correlations among variables. In the learning process of tree-structured graphical models, the quantity of useful features extracted from observation data of variables reflects the model’s capability to model the deep relationships among variables. However, the excised algorithms learn the hidden tree only by the statics which are directly computed from observation data and ignore the different features among data. For the insufficiency of these algorithms in exploring the information, a new algorithm is proposed for learning the latent tree-structured graphical model based on fuzzy multi-features recursive-grouping. First, original observation data is transformed to multi-features by fuzzy membership functions and construct multi-dimensional fuzzy feature vectors. Then, the distance between each fuzzy feature vectors is computed and synthesized to get the fuzzy multi-features distance matrix of all variables. Finally, based on the distance matrix, the latent tree graphical model is constructed by the recursive-grouping algorithm. The proposed algorithm is applied to stock return data modeling and temperature data modeling, which demonstrate the effectiveness of the algorithm.

Information processing; Graphical model; Latent tree model; Information distance; Fuzzy multi-feature

TP18

A

1009-5896(2014)06-1312-09

10.3724/SP.J.1146.2013.00860

文成林 wencl@hdu.edu.cn

2013-06-14收到，2013-12-26改回

國家自然科學基金重點項目(60934009)和國家自然科學基金(61004070, 61203094)資助課題