基于啟發(fā)式算法的CP-nets學(xué)習(xí)研究

仲兆琳 信統(tǒng)昌

摘 要：CP-nets（條件偏好網(wǎng)）是定性表達(dá)偏好關(guān)系的一種圖形工具，作為一種表達(dá)能力的工具，CP-nets功能強大，能直觀、自然地表達(dá)用戶的偏好信息。但是對于CP-nets學(xué)習(xí)的研究還不夠深入，在實際應(yīng)用中，由于用戶行為或者觀測誤差的隨機性，可能導(dǎo)致數(shù)據(jù)集中存在噪聲數(shù)據(jù)，使得許多傳統(tǒng)的學(xué)習(xí)方法無法得到最優(yōu)的CP-nets結(jié)構(gòu)。本文提出基于啟發(fā)式算法的學(xué)習(xí)方法來解決CP-nets的結(jié)構(gòu)學(xué)習(xí)問題。與傳統(tǒng)方法中直接學(xué)習(xí)CP-nets結(jié)構(gòu)不同，本文將CP-nets的結(jié)構(gòu)學(xué)習(xí)問題轉(zhuǎn)化為尋找最短路徑問題，利用啟發(fā)式算法的能力來尋找最優(yōu)的CP-nets。

關(guān)鍵詞： 條件偏好網(wǎng)（CP-nets）;啟發(fā)式算法;結(jié)構(gòu)學(xué)習(xí)

文章編號： 2095-2163（2019）03-0100-03?中圖分類號： TP181?文獻(xiàn)標(biāo)志碼： A

0?引?言

傳統(tǒng)的商業(yè)研究是一個通過人工分析數(shù)據(jù)來探索和研究定義的各種因素之間關(guān)系的過程，但是，即使有強大的計算機和統(tǒng)計軟件，許多隱藏的和潛在的有用信息還是無法被分析師挖掘出來。如今，這樣的問題更加尖銳，因為許多企業(yè)會在短時間內(nèi)產(chǎn)生大量的數(shù)據(jù)，面對數(shù)據(jù)的爆炸性增長，需要一種有效的方法來挖掘數(shù)據(jù)庫中有用的知識。通過數(shù)據(jù)挖掘，可以發(fā)現(xiàn)各種因素之間的復(fù)雜關(guān)系。提取出的有用的知識，可以提高決策的效率和質(zhì)量。

條件偏好網(wǎng)（CP-nets） [1-4]是一種圖模型，能夠表示變量之間的關(guān)系。CP-nets的學(xué)習(xí)問題是通過觀察用戶的查詢記錄來提取偏好結(jié)構(gòu)和多個偏好參數(shù)。準(zhǔn)確地提取和排序這些偏好是困難的，不僅是對于無環(huán)CP-nets[5-6]，對二進制CP-nets和可分離CP-nets也很困難。這一過程涉及到CP-nets的學(xué)習(xí)方法，例如利用假設(shè)檢驗的方法學(xué)習(xí)CP-nets[7]、基于CP-nets誘導(dǎo)圖的學(xué)習(xí)[8]等。CP-nets能夠發(fā)現(xiàn)決策變量中的定性偏好或者是變量之間的依賴關(guān)系，使得決策工具能夠快速發(fā)展，并且具有高效的決策能力，這使CP-nets在決策論[9-11]中大量使用。

1?問題描述

要得到CP-nets準(zhǔn)確的圖模型是比較困難的，存在2個主要問題：維度問題和噪聲數(shù)據(jù)。首先，隨著CP-nets中的結(jié)點數(shù)目的增加，CP-nets的數(shù)量呈指數(shù)型增加，所以CP-nets學(xué)習(xí)屬于NP-Complete問題。其次，在處理數(shù)據(jù)集時經(jīng)常出現(xiàn)的一個問題是噪音數(shù)據(jù)。有時收集數(shù)據(jù)時會存在誤差導(dǎo)致噪聲數(shù)據(jù)的產(chǎn)生，從而對學(xué)習(xí)方法產(chǎn)生影響，因此，有必要對學(xué)習(xí)算法的魯棒性進行評估。針對以上問題，本文采用啟發(fā)式算法來開展研究。在狀態(tài)空間搜索圖中，找到一條最短路徑，路徑上的結(jié)點中包含的變量關(guān)系就是最佳的CP-nets。因此，找到最短路徑，就能得到最佳CP-nets結(jié)構(gòu)。

2?CP-nets學(xué)習(xí)的相關(guān)概念

CP-nets是一個關(guān)于頂點V的帶有有向邊的圖模型，包括2部分：圖G和條件偏好表（CPT）。其中，圖G包括變量集V={X1，X2，…，Xn}和有向邊集CE，變量之間的有向邊代表變量間的依賴關(guān)系。每個變量Xi對應(yīng)一個條件偏好表CPT（Xi），用來表示偏好關(guān)系。條件偏好表用來表示變量Xi在Pare（Xi）的不同取值下，用戶對Dom（Xi）集合中的偏好。Pare（Xi）的取值不同，用戶對Dom（Xi）集合中的偏好也會發(fā)生變化。

用于學(xué)習(xí)CP-nets的狀態(tài)空間搜索圖是屬性域集合的所有子集的哈斯圖。具有4個變量的狀態(tài)空間搜索圖如圖1所示，在第一層為空集的結(jié)點為初始結(jié)點，第n+1層包含所有變量的結(jié)點為目標(biāo)結(jié)點，其中n為變量總數(shù)。

目前，針對解決最短路徑問題的研究方法有很多，在本文中，考慮運用啟發(fā)式算法中的動態(tài)規(guī)劃算法、遺傳算法和A*算法來解決這一問題。

3?基于啟發(fā)式算法學(xué)習(xí)CP-nets

3.1?基于動態(tài)規(guī)劃方法學(xué)習(xí)CP-nets

采用動態(tài)規(guī)劃方法進行CP-nets學(xué)習(xí)，動態(tài)規(guī)劃方法從狀態(tài)空間圖的第一層開始掃描，并對層與層之間的每條路徑進行評估，選出上下兩層之間的最佳路徑，為搜索圖中的每個結(jié)點包含的變量找到最佳子網(wǎng)。掃描到最后一層結(jié)點的時候，一定能找到一條最佳路徑對應(yīng)于一個最佳CP-nets。但是，隨著變量數(shù)目的增加，算法的運行時間將呈指數(shù)型增長，動態(tài)規(guī)劃方法變得不可行。

3.2?基于遺傳算法學(xué)習(xí)CP-nets

采用遺傳算法進行CP-nets學(xué)習(xí)，遺傳算法是一種搜索啟發(fā)式算法，在人工智能領(lǐng)域中，用于解決最優(yōu)化問題。本文要求解最佳CP-nets結(jié)構(gòu)，因此可以通過遺傳算法來解決這一問題。通過進行選擇、交叉和變異的一系列遺傳操作，找到最短路徑，進而得到最佳CP-nets結(jié)構(gòu)。

遺傳算法的核心是遺傳操作和適應(yīng)度函數(shù)（打分），遺傳操作即選擇算子、交叉算子和變異算子。在遺傳算法學(xué)習(xí)CP-nets過程中，產(chǎn)生一個由隨機路徑組成的初始種群，通過適應(yīng)度函數(shù)得出所有路徑的得分。然后進行遺傳操作，運用選擇算子，選擇出其中一部分路徑作為父本和母本;運用交叉算子，對選擇出來的路徑（父本、母本）進行交叉操作，產(chǎn)生一個后代種群，對后代種群中的路徑進行適應(yīng)度計算得到分?jǐn)?shù);運用變異算子，對后代種群中的路徑隨機發(fā)生變異，并對變異后的路徑進行適應(yīng)度計算得到分?jǐn)?shù);在初始種群和后代種群中，根據(jù)選擇算子選擇出得分高的“精英”路徑組成下一次循環(huán)迭代的種群，依次循環(huán)，最終得到最優(yōu)的路徑，即最短路徑，進而得到最佳CP-nets結(jié)構(gòu)。

3.3?基于A*算法學(xué)習(xí)CP-nets

采用A算法進行CP-nets學(xué)習(xí)，A算法是一種典型的啟發(fā)式搜索算法，A*算法運用的思路是：定義一個評價函數(shù)f，f（n） = g（n）+h（n），對當(dāng)前的搜索狀態(tài)進行評估，找出一個最有希望的結(jié)點來擴展。定義評價函數(shù)的參考原則有：一個結(jié)點在最佳路徑上的可能性;根據(jù)格局或狀態(tài)的特點來打分。

A算法有一個OPEN集合來存儲搜索邊界，還有一個CLOSED集合來存儲擴展結(jié)點。算法運行之初，OPEN集合中只有初始空間結(jié)點，CLOSED集合中是空的。在每個搜索步驟中，從OPEN 集合中找出最小f值的空間結(jié)點為U，選擇該節(jié)點用于擴展以生成其后繼結(jié)點。但是，在擴展U之前，需要首先檢查該節(jié)點是否是目標(biāo)節(jié)點。如果是，說明找到了到達(dá)目標(biāo)的最短路徑，可以從此路徑構(gòu)造一個CP-nets并終止搜索;如果U不是目標(biāo)結(jié)點，將其擴展生成后繼節(jié)點后，在每個后繼結(jié)點S中加入一個新的變量X，S作為現(xiàn)有的網(wǎng)絡(luò)變量U的一個子結(jié)點，即S=U∪{X}。檢查CLOSED列表中是否已經(jīng)存在該結(jié)點，如果存在的話，將進一步檢查該結(jié)點是否具有比S更小的g值，若該結(jié)點具有比S更小的g值，那就刪除S，因為這時的S代表路徑不是最優(yōu)的;若該結(jié)點具有的g值沒有比S的更小，那么該結(jié)點將會從CLOSED集合中刪掉，并且將S放入OPEN集合中。如果在CLOSED集合中不存在該結(jié)點，接下來直接掃描OPEN集合，若該結(jié)點不在OPEN集合中，只需將S添加到OPEN集合中;若該結(jié)點在OPEN集合中，將該結(jié)點的g值與S的g值相比較，如果該結(jié)點的g值小，將OPEN列表中的S刪除;如果S的g值小，該結(jié)點將被S替換掉。在生成所有的后繼結(jié)點之后，將結(jié)點U放入CLOSED集合中，說明該結(jié)點已經(jīng)擴展完成。此時，從起始狀態(tài)到目標(biāo)狀態(tài)的最短路徑被找到。從目標(biāo)結(jié)點開始，追蹤最短路徑直至到達(dá)起始結(jié)點，從而得到新的CP-nets圖模型。路徑上的每個結(jié)點都存儲一個變量，這些變量組成了CP-nets 中的頂點集。

4?結(jié)束語

在人工智能的研究中，對偏好學(xué)習(xí)的研究在實踐中具有重要的價值。本文提出學(xué)習(xí)方法不直接學(xué)習(xí)CP-nets，而是將學(xué)習(xí)問題轉(zhuǎn)化為最短路徑發(fā)現(xiàn)問題。使用狀態(tài)空間圖表示學(xué)習(xí)問題的求解空間，利用啟發(fā)式算法尋找求解空間中的最短路徑。在啟發(fā)式函數(shù)的指導(dǎo)下，啟發(fā)式算法通過搜索求解空間中最優(yōu)部分來構(gòu)建最優(yōu)的CP-nets。

本文中的學(xué)習(xí)方法仍有局限性，當(dāng)頂點數(shù)目過多時，求解空間將呈指數(shù)倍增大，導(dǎo)致運行時間增加。今后的工作將致力于學(xué)習(xí)算法的改進，進一步提高學(xué)習(xí)方法的性能。

參考文獻(xiàn)

[1]BOUTILIER C， BRAFMAN R I， DOMSHLAK C， et al. CP-nets： A tool for representing and reasoning with conditional ceteris paribus preference statements[J]. Journal of Artificial Intelligence Research， 2011， 21（1）： 135-191.

[2]LIU Jinglei. Research on CP-nets and its expressive power[J]. Acta Automatica Sinica， 2011， 37（3）： 290-302.

[3]LIU Jinglei， LIAO Shizhong， Zhang Wei. On the completeness and consistency for CP-nets[J]. Journal of Software， 2012， 23（6）： 1531-1541.

[4]GOLDSMITH J， LANG J， TRUSZCZYN[DD（]′[DD）]SKI M， et al. The computational complexity of dominance and consistency in CP-Nets[J]. Journal of Artificial Intelligence Research， 2008， 33（1）： 403-432.

[5]ALANAZI E， MOUHOUB M， ZILLES S. The complexity of learning acyclic CP-nets[C]// Proceedings of the 25th International Joint Conference on Artificial Intelligence（JICAI 2016）. Palo Alto， CA， USA：AAAI， 2016：1361-1367.

[6]CORNELIO C， GRANDI U， GOLDSMITH J， et al. Voting with CP-nets using a probabilistic preference structure[C]//Proceedings of COMSOC. Pittsburgh， Pennsylvania：IEEE， 2014： 1-15.

[7]LIU Juntao， YAO Zhijun， XIONG Yi， et al. Learning conditional preference network from noisy samples using hypothesis testing[J]. Knowledge-Based Systems， 2013， 40（1）： 7-16.

[8]LIU Juntao， XIONG Yi， WU Caihua， et al. Learning conditional preference networks from inconsistent examples[J]. IEEE Transactions on Knowledge & Data Engineering， 2013， 26（2）： 376-390.

[9]XU Zeshui， ZHAO Na. Information fusion for intuitionistic fuzzy decision making： An overview[J]. Information Fusion， 2015， 28（C）： 10-23.

[10]ALLEN T E. CP-nets： From theory to practice[C]// 4th International Conference on Algorithmic Decision Theory. Lexington， KY， USA：Springer International Publishing， 2015： 555-560.

[11]CONITZER V. Making decisions based on the preferences of multiple agents[J]. Communications of the ACM， 2010，53（3）： 84-94.