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

李宏偉 文成林*② 徐曉濱

?

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

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

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

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

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

1 引言

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

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

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

2 樹結構圖模型簡介

2.1 無向圖和樹

2.2 樹結構圖模型

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

3.1信息距離的計算

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

圖1 經典遞歸分組隱樹模型學習方法流程圖

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

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

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

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

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

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

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

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

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

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

4.1 構造特征的模糊隸屬度函數

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

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

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

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

4.3 .隱樹模型的結構學習和參數學習

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

5 實驗及分析

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

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

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

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

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

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

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

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

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

5.2 中國城市歷年氣溫數據的隱樹模型學習

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

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

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

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

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

6 結束語

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

[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]. 電子與信息學報, 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] 姜園, 張朝陽, 仇佩亮, 等. 用于數據挖掘的聚類算法[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] 文成林, 胡靜, 王天真, 等. 相對主元分析及其在數據壓縮和故障診斷中的應用研究[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年生，副教授，研究方向為不確定性信息融合、系統可靠性評估與故障診斷.

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)資助課題