張?zhí)祺? 李英梅

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

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

中圖分類號：TP391? ? ?文獻(xiàn)標(biāo)識碼：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]，在已有的一系列相關(guān)理論中，三支決策可以形式化的表示為“trisecting-and-acting”這樣一個兩步走的活動[3-6]。目前在三支決策的研究領(lǐng)域中多數(shù)的研究集中于對三分法的研究[7-11]，對在不同區(qū)域采取適合的行動策略的研究相對較少。在本文中，將三支決策的思想與行動規(guī)則的策略結(jié)合起來[12]，建立一個三支決策行動策略的模型。

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

2? ?治略模型（Action model）

本文提出的治略模型分為三部分，一是在對數(shù)據(jù)集進(jìn)行基于相容關(guān)系的三支聚類，二是對聚類結(jié)果的三支治略，三是將治略后的聚類結(jié)果與原結(jié)果進(jìn)行對比。

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

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

三個域分別對應(yīng)上文所定義的正域結(jié)果對象所在的域，邊界域結(jié)果對象所在的域，負(fù)域結(jié)果對象所在的域。如果x與y兩個對象之間的相容度小于γ，則稱兩者之間存在相容關(guān)系。

根據(jù)三個域的特點(diǎn)可以構(gòu)造三個關(guān)于行動策略的子集——DES、UND、IND。分別代表渴望的行動策略，不渴望的行動策略，不產(chǎn)生效益的行動策略，

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

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

②構(gòu)造相容簇的BND域：從數(shù)據(jù)集中找出所有滿足與中心對象相容度大于、小于且決策屬性為1的數(shù)據(jù)對象，標(biāo)記選取的所有對象并進(jìn)行下一步。

③構(gòu)造相容簇的NEG域：從數(shù)據(jù)集中找出所有滿足與中心對象相容度大于、小于且決策屬性為2的數(shù)據(jù)對象，標(biāo)記選取的所有對象并進(jìn)行下一步。

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

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

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

②對邊界域中的數(shù)據(jù)對象進(jìn)行治略行動：根據(jù)已知的DES，將該相容簇邊界域中的所有數(shù)據(jù)對象使用行動轉(zhuǎn)移至正域。

③對負(fù)域中的數(shù)據(jù)對象進(jìn)行治略行動：根據(jù)已知的DES，將該相容簇負(fù)域中的所有數(shù)據(jù)對象使用行動轉(zhuǎn)移至正域。

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

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

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

根據(jù)基于相容關(guān)系的三支聚類與三支治略的過程，可以設(shè)計出3WC-BC算法，如下：

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

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

步驟1：根據(jù)相容關(guān)系確定POS域、BND域、NEG域中的元素。

步驟2：找到所有的DES。

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

步驟4：根據(jù)步驟3得到的成本與效益構(gòu)造效益表與行動表。

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

步驟6：算法結(jié)束，返回結(jié)果。

3? ?實(shí)驗(yàn)結(jié)果（Experimental result）

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

3.1? ?聚類分析實(shí)驗(yàn)

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

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

3.2? ?治略有效性度量實(shí)驗(yàn)

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

4? ?結(jié)論（Conclusion）

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

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

參考文獻(xiàn)（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，F(xiàn)ujita 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] 賈修一，商琳，周獻(xiàn)中，等.三支決策理論與應(yīng)用[M].南京大學(xué)出版社，2012.

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

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

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

[9] 劉盾，李天瑞，李華雄.粗糙集理論：基于三支決策視角[J].南京大學(xué)學(xué)報（自然科學(xué)），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國際知識技術(shù)論壇，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] 萬仁霞，王立新，劉振文，等.一種基于相容關(guān)系的聚類算法[J].計算機(jī)應(yīng)用研究，2009，26（4）：1302-1304.

[14] 陳大力，沈巖濤，謝檳竹，等.基于余弦相似度模型的最佳教練遴選算法[J].東北大學(xué)學(xué)報（自然科學(xué)版），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].自動化學(xué)報，2014，40（1）：62-72.