相容關系三支聚類的治略效果評估研究

張?zhí)祺? 李英梅

摘? 要：三支決策是一種符合人類認知的“三分而治”模型，衡量“治”的效果需基于特定的“分”法?，F有的對“治”的研究往往基于等價類進行三分。本文基于相容關系進行三支聚類，根據聚類假設對數據對象進行“治”略，提出一種測量治略效果的算法——3WC-BC。通過“治”前后的比較表明“治”略的意義和有效性。實驗結果表明，三支決策中“治”略的研究具有較大意義，能夠為選擇合理的或最大效益的“治”略選擇提供方法，與傳統(tǒng)的離散表格索引的選擇方法比較減少了因索引錯誤而造成的誤差。

關鍵詞：三支決策;相容關系;三支聚類;行動;行動規(guī)則

中圖分類號：TP391? ? ?文獻標識碼：A

Measure Effectiveness of Action and Strategy in Three-way?Clustering Based on Compatible Relationship

ZHANG Tianqi，LI Yingmei

（School of Computer Science and Information Engineering，Harbin Normal University，Harbin 150025，China）

Abstract：The three-way decisions are a trisecting-and-acting model that conforms to human cognition.Measuring the effectiveness of action and strategy needs to consider the specific way of secting.The existing research on action is often based on equivalence classes for three points.An algorithm of 3WC-BC is proposed for measuring effectiveness of acting in three-way clustering based on compatible relationships.The comparison between before and after action and strategy? shows the significance and effectiveness of action and strategy.Experimental results show that the study of action and strategy in three-way decisions has a great significance and further provide a method for choosing reasonable or most effective actions，which reduces deviation caused by indexing error compared with traditional discrete table index method.

Keywords：three-way decisions;compatible relation;three-way cluster;action;rule of action

1? ?引言（Introduction）

三支決策是從粗糙集理論逐漸演變成的一種符合廣義思考的“分而治之”模型[1，2]，在已有的一系列相關理論中，三支決策可以形式化的表示為“trisecting-and-acting”這樣一個兩步走的活動[3-6]。目前在三支決策的研究領域中多數的研究集中于對三分法的研究[7-11]，對在不同區(qū)域采取適合的行動策略的研究相對較少。在本文中，將三支決策的思想與行動規(guī)則的策略結合起來[12]，建立一個三支決策行動策略的模型。

在本文中，主要考慮對三支決策中治略模型的研究，并使用在有限成本下獲得最大效益的決策模型來檢驗其有效性。本文是按以下邏輯展開的：第2章對三支治略前后三支聚類的變化情況進行了描述，同時對三支治略的有效性進行了檢驗。第3章對所做的實驗進行了簡要介紹并對提出的算法性能進行了評估。

2? ?治略模型（Action model）

本文提出的治略模型分為三部分，一是在對數據集進行基于相容關系的三支聚類，二是對聚類結果的三支治略，三是將治略后的聚類結果與原結果進行對比。

在已有理論的支撐下，本章提出一種基于相容關系的三支聚類結果的治略模型對效益和成本進行分析，通過治略前后的對比，評估治略的有效性。

定義1：一個決策表可以用公式（1）表達：

三個域分別對應上文所定義的正域結果對象所在的域，邊界域結果對象所在的域，負域結果對象所在的域。如果x與y兩個對象之間的相容度小于γ，則稱兩者之間存在相容關系。

根據三個域的特點可以構造三個關于行動策略的子集——DES、UND、IND。分別代表渴望的行動策略，不渴望的行動策略，不產生效益的行動策略，

在三支治略前首先要進行的是基于相容關系的三支聚類，選取合適的閾值α、β、γ且滿足，算法的基本思想如下：

①構造相容簇的POS域：從數據集中選取任一決策屬性值為0的數據對象當作中心對象，然后找出所有滿足與中心對象相容度小于的數據對象，此時檢查選取的數據對象，若所有數據對象的決策屬性都為0，對所有選取的數據對象進行標記，進行下一步，否則重新選取中心對象。

②構造相容簇的BND域：從數據集中找出所有滿足與中心對象相容度大于、小于且決策屬性為1的數據對象，標記選取的所有對象并進行下一步。

③構造相容簇的NEG域：從數據集中找出所有滿足與中心對象相容度大于、小于且決策屬性為2的數據對象，標記選取的所有對象并進行下一步。

④檢查數據集中是否還有決策屬性為0且未被標記的數據對象，若存在，則重復第一步，若不存在，則檢查數據集中是否還有未被標記的對象，若還有，則標記為離散對象。

接下來要進行基于三支聚類的治略，根據定義描述，給定DES、UND、IND。可以確定的是，在一個相容簇中，所有不屬于正域的數據對象都擁有其DES，本文的治略算法給定的行動也都是滿足DES的行動。使用Axy表示從x域到y(tǒng)域的行動，則用AND表示從NEG域到POS域的DES，用ABP表示從BND域到POS域的DES，給出3WC-AS算法，算法的基本思想如下：

①查找DES：從三支聚類得到的相容簇集SC中取出一個相容簇，找出所有DES。

②對邊界域中的數據對象進行治略行動：根據已知的DES，將該相容簇邊界域中的所有數據對象使用行動轉移至正域。

③對負域中的數據對象進行治略行動：根據已知的DES，將該相容簇負域中的所有數據對象使用行動轉移至正域。

④檢索相容簇集SC中是否還有相容簇，若存在，返回第一步;若不存在，結束算法，得到一個經過治略的新的相容簇集。算法描述如下：

上文中經過三支治略，得到了一個新的相容簇集SC，為與原相容簇集區(qū)分，使用SC'來表示。下面根據基于相容關系的聚類和三支治略的方法。

該模型采取基于動態(tài)規(guī)劃的策略。令f（i，k）表示對第i個可行動對象在有限成本k下的最大效益，通過推導得出f（i，k）的一個完整公式，即公式（4）。

根據基于相容關系的三支聚類與三支治略的過程，可以設計出3WC-BC算法，如下：

輸入：D—關系度量;S—對象集;α、β、γ—閾值;Ca—給定成本。

輸出：B—最大收益;aij—行動步驟。

步驟1：根據相容關系確定POS域、BND域、NEG域中的元素。

步驟2：找到所有的DES。

步驟3：遍歷每個DES，求其成本與效益。

步驟4：根據步驟3得到的成本與效益構造效益表與行動表。

步驟5：根據效益表與行動表求得不同成本下的最大效益及其行動步驟。

步驟6：算法結束，返回結果。

3? ?實驗結果（Experimental result）

文中的所有實驗都是運行在windows 10 64bit上，采用i5 2.50GHz CPU和8GB RAM。實驗數據全部由UCI數據庫提供。在此使用其中一個克利夫蘭數據集[17]。需要設置三個實驗，實驗一對數據集進行聚類分析，保證“三分”的有效性;實驗二對治略前后相容簇中的數據對象轉移情況進行分析;實驗三對算法得到的策略行動步驟與隨機選取的策略行動步驟做比較，確保算法的性能。

3.1? ?聚類分析實驗

實驗一對數據集進行基于相容關系的三支聚類，對于心臟病診斷數據集來說，使用邏輯回歸[18，19]計算出對決策屬性影響最大的兩個可變屬性——BP和CP指標。作為橫縱坐標在坐標軸上進行聚類分析。在聚類分析時需要涉及對相容關系閾值的選取，此時使用余弦相似度，按照前文闡述的規(guī)則選取閾值。聚類結果如圖1所示。

由圖4可以看出，基于相容關系的聚類允許一個數據對象存在于多個相容集中，這點和傳統(tǒng)聚類有很大不同，同時每個相容簇又有自己獨有的數據對象，與模糊聚類有著明顯的不同。并且本文在一個相容簇中設置了POS域、BND域、NEG域，采取“分而治之”的思想對在不同域中的對象采取不同的治略策略。在之后提出DES，符合DES的數據對象作為Optional將擁有很多的可選策略，而對應于不同行動策略的行動成本顯然是不同的，因此使用之后提出的算法進行計算，求其最優(yōu)的行動方案。

3.2? ?治略有效性度量實驗

實驗二依照文中治略的方法對實驗一得到的聚類結果進行了治略，原數據對象經過治略中對數據對象進行移動的一系列行動，心臟病數據集中數據對象在不同域的轉移情況如圖2所示，圖中對POS域、BND域、NEG域，以及其他區(qū)域中的數據對象在給定成本為0、274、589時各域中的對象數量進行了表示，從圖中可以看出給定成本為0時聚類初始狀態(tài)下各個域中都有數據對象;給定成本為274時，BND域中的對象轉移的最多，體現了治略的有效性。

4? ?結論（Conclusion）

本文對基于相容關系的三支聚類治略的有效性進行了評估，通過策略的成本和效益分析，設計了三個算法模型對三支聚類的治略效果進行了評估。算法中使用分段函數進行策略行動成本與效益的檢索，避免因小數而出現檢索錯誤的情況。

對心臟病數據集的三個實驗結果表明，基于相容關系的三支聚類不同于傳統(tǒng)的聚類方法，增加了靈活性;通過三支治略有效地提高了相容簇的質量，并將數據對象從負域或邊界域轉移到了正域;在有限成本下求最大收益的算法具有理想的效果，相比于隨機選取行動，算法能夠更早的達到期望的目的。接下來的研究方向將研究屬性和策略行動成本之間的關系，可以考慮使用屬性的一部分來獲取相應的部分效益，同時需要的成本也相對較低。在實際問題中，某些屬性對結果的影響可能是決定性的。因此，需要對屬性進行更有效的加權處理，并使之通用性更強。同時，不同的策略間可能存在相關的隱藏約束，在研究中可以繼續(xù)考慮放寬本文關于策略行動模式的約束，加強行動策略的泛化能力。

參考文獻（References）

[1] Jiang C，Wu J，Li Z.Adaptive thresholds determination for saving cloud energy using three-way decisions[J].Cluster Computing，2018（1）：1-8.

[2] Yang X，Li T，Fujita H，et al.A unified model of sequential three-way decisions and multilevel incremental processing[J].Knowledge-Based Systems，2017.

[3] Yao Y.Three-Way Decisions and Cognitive Computing[J].Cognitive Computation，2016，8（4）：543-554.

[4] Hu B Q.Three-way decisions space and three-way decisions[M].Elsevier Science Inc，2014.

[5] 賈修一，商琳，周獻中，等.三支決策理論與應用[M].南京大學出版社，2012.

[6] 李金海，鄧碩.概念格與三支決策及其研究展望[J].西北大學學報：自然科學版，2017，47（3）：321-329.

[7] DengX，YaoY.Decision-theoretic three-way approximations of fuzzy sets[J].Information Sciences，2014（279）：702-715.

[8] 汪璐，賈修一，顧雁囡.三支決策貝葉斯網絡分類器[J].南京大學學報（自然科學），2016，52（5）：833-843.

[9] 劉盾，李天瑞，李華雄.粗糙集理論：基于三支決策視角[J].南京大學學報（自然科學），2013，49（5）：574-581.

[10] Gao C，Yao Y.Determining Thresholds in Three-Way Decisions with Chi-Square Statistic[C].International Joint Conference on Rough Sets.Springer，Cham，2016.

[11] Jing-Tao Y，Herbert J P.A game-theoretic perspective on rough set analysis[C].2008國際知識技術論壇，2008.

[12] Ra?，Zbigniew W，Tsay L S，et al.Tree-based algorithms for action rules discovery[J].Studies in Computational Intelligence，2009：153-163.

[13] 萬仁霞，王立新，劉振文，等.一種基于相容關系的聚類算法[J].計算機應用研究，2009，26（4）：1302-1304.

[14] 陳大力，沈巖濤，謝檳竹，等.基于余弦相似度模型的最佳教練遴選算法[J].東北大學學報（自然科學版），2014，35（12）：1697-1700.

[15] Wang D，Lu H，Bo C.Visual Tracking via Weighted Local Cosine Similarity[J].IEEE Transactions on Cybernetics，2017，45（9）：1838-1850.

[16] Zhang X，Miao D.Reduction target structure-based hierarchical attribute reduction for two-category decision-theoretic rough sets[J].Information Sciences，2014，277（2）：755-776.

[17] Gao C，Yao Y.Actionable Strategies in Three-way Decisions[J].Knowledge-Based Systems，2017：183-199.

[18] Kianifard F.Logistic Regression：A Self-Learning Text[J].Technometrics，1995，37（1）：116.

[19] 毛毅，陳穩(wěn)霖，郭寶龍，等.基于密度估計的邏輯回歸模型[J].自動化學報，2014，40（1）：62-72.