摘  要： 基于模糊粗糙集模型構(gòu)建模糊等價(jià)關(guān)系是混合數(shù)據(jù)分析的有效方法之一。針對屬性類別多樣性的混合型信息系統(tǒng)，提出一種帶權(quán)的對象間相似性度量方法，該方法建立每類屬性對應(yīng)的相似性度量函數(shù)，再通過歸并確立帶權(quán)的模糊相似矩陣。在轉(zhuǎn)化為模糊等價(jià)關(guān)系的基礎(chǔ)上，采用加入蘊(yùn)含專家領(lǐng)域知識及用戶需求的約簡算法。通過數(shù)據(jù)庫中幾個(gè)數(shù)據(jù)集樣本對屬性約簡后的數(shù)目、精度進(jìn)行對比，驗(yàn)證了方法的有效性和可行性。

　　關(guān)鍵詞： 模糊粗糙集模型；模糊等價(jià)關(guān)系；混合數(shù)據(jù)；模糊相似矩陣；約簡

0 引言

　　粗糙集理論是一種以精確的數(shù)學(xué)形式處理不確定信息的數(shù)學(xué)工具，屬性約簡在保持分類能力不變的前提下獲得最小特征子集，是粗糙集理論的核心應(yīng)用之一。經(jīng)典粗糙集理論[1-3]通常是處理只包含符號型屬性的數(shù)據(jù)模型，而實(shí)際的信息系統(tǒng)中屬性和決策的值域是多樣性的，有符號型屬性，也有連續(xù)數(shù)值型屬性，即混合分類數(shù)據(jù)。對于混合數(shù)據(jù)的處理大體可分為兩類：一類是離散化方法[4]，將數(shù)值型屬性轉(zhuǎn)化為符號型屬性的數(shù)據(jù)形式，即在數(shù)值屬性值域中選擇合適的分割點(diǎn)，劃分成若干由字符標(biāo)記的不同區(qū)域，從而將不同類別屬性轉(zhuǎn)化為統(tǒng)一的數(shù)據(jù)形式再進(jìn)行約簡。如何選擇分割點(diǎn)引出了離散化方法的系統(tǒng)分析比較[5]，討論的關(guān)鍵在于分割點(diǎn)數(shù)量和位置的設(shè)計(jì)，缺點(diǎn)在于產(chǎn)生了量化誤差，丟失了同種符號表示的區(qū)域內(nèi)不同屬性值間的序信息。另一類是對不可分辨關(guān)系進(jìn)行拓展的混合型方法。Hall提出了利用信息熵計(jì)算符號變量相關(guān)性的特征選擇方法[6]，Zhou和Qian提出了采用定性信息分解復(fù)雜問題的決策樹構(gòu)造方法[7]，以及之后提出的混合數(shù)據(jù)特征選擇的方法[8]，缺點(diǎn)都是將符號型屬性和數(shù)值型屬性割裂開分析，丟失了分類能力較強(qiáng)的數(shù)值屬性信息。Kwak和Choi、Peng等人陸續(xù)采用Parzen窗方法計(jì)算數(shù)值型樣本概率密度來進(jìn)行特征選擇[9]，取得了一定進(jìn)展。Zadeh提出了模糊集理論[10]，認(rèn)為模糊信息粒化在知識發(fā)現(xiàn)過程中極其重要，模糊粗糙集和粗糙模糊集概念的提出，融合了模糊?；痛植诒平鼉煞N不確定方法[11-15]，使得約簡結(jié)果能更清晰地體現(xiàn)信息系統(tǒng)的分類能力。Hu采用信息熵的概念度量信息系統(tǒng)的分類能力，在混合數(shù)據(jù)的處理過程中，得到的對象間相似矩陣數(shù)值單一，且整合符號型和數(shù)值型屬性的過程中丟失很多分類信息[16]。遺傳算法應(yīng)用于混合數(shù)據(jù)約簡的方法，由于本身算法的特點(diǎn)導(dǎo)致計(jì)算量大、耗時(shí)長[17-18]。

　　本文重點(diǎn)研究在模糊粗糙集模型框架下如何定義混合數(shù)據(jù)間帶權(quán)的相似性度量方法及模糊等價(jià)關(guān)系，通過定義不同類別屬性對應(yīng)的相似性度量函數(shù)，以及帶權(quán)的模糊相似矩陣，最終確定模糊等價(jià)關(guān)系；之后通過加入領(lǐng)域?qū)＜业慕?jīng)驗(yàn)知識和系統(tǒng)客戶的需求偏好對數(shù)據(jù)進(jìn)行約簡，將約簡后的屬性數(shù)目、精度與其他方法的數(shù)據(jù)進(jìn)行對比，以驗(yàn)證方法的有效性和可行性。

1 模糊等價(jià)關(guān)系及其度量

　　針對符號型變量的處理，可以利用粗糙集在等價(jià)關(guān)系的基礎(chǔ)上建立對象間關(guān)系。但對于數(shù)值型變量，等價(jià)關(guān)系不足以清晰地刻畫對象間關(guān)系，需要借助模糊等價(jià)關(guān)系的概念。

　　給定信息系統(tǒng)S=（U，A），論域U={x1，x2，…，xn}，屬性集合A=C∪D是條件屬性和決策屬性的集合，且C∩D=。本文討論的混合信息系統(tǒng)的屬性集合既有條件屬性，也有數(shù)值屬性。

　　定義1：給定一個(gè)矩陣A=（aij）n×n，若對i，j=1，2，…，n，滿足：（1）自反性：aii=1；（2）對稱性：aij=aji；（3）模糊性：aij∈[0，1]；（4）傳遞性：aij≥∨k（aik∧akj），則稱矩陣A為模糊等價(jià)矩陣。

　　在以下論述中，用M（R）=（rij）n×n來表示二元關(guān)系R的關(guān)系矩陣，其中R滿足模糊等價(jià)關(guān)系。

　　定義4[16]：給定模糊信息系統(tǒng)<U，A，V，f>，A=C∪d，若H（d|B-a）=H（d|B），則屬性a是冗余的，若H（d|B-a）>H（d|B），則B是獨(dú)立的。若滿足：（1）H（d|B）=H（d|A）；（2）∨a∈B∶H（d|B-a）<H（d|B），則稱B是A的屬性約簡。

　　下節(jié)將利用上述度量，構(gòu)造混合數(shù)據(jù)間的模糊等價(jià)關(guān)系，依據(jù)屬性重要性的度量進(jìn)行約簡。

2 模糊等價(jià)矩陣的構(gòu)造及算法描述

　　基于模糊等價(jià)關(guān)系的數(shù)據(jù)構(gòu)造是混合數(shù)據(jù)分析的重要模型，利用矩陣形式刻畫具有不同屬性類別的樣本間關(guān)系。針對符號型屬性，Hu[16]根據(jù)屬性取值是否相等計(jì)算樣本間的相似度貢獻(xiàn)，屬性間取其交集得結(jié)果，由此矩陣中只見兩個(gè)單一數(shù)值，不能具體地刻畫樣本間的區(qū)分信息，且需針對每個(gè)屬性做重復(fù)計(jì)算；刻畫不同類別屬性間的關(guān)系依然采用取其交集的簡便算法，在各種屬性類別取值豐富多樣的信息空間，這種關(guān)系構(gòu)造方法丟失大量的非冗余的有效信息。本節(jié)將對混合數(shù)據(jù)中各個(gè)類別屬性分別重新進(jìn)行構(gòu)造，提出一種帶權(quán)的對象間相似性度量方法，并且使其最終轉(zhuǎn)化為一個(gè)模糊等價(jià)關(guān)系，在加入量化知識的基礎(chǔ)上進(jìn)行約簡。

　　2.1 模糊相似關(guān)系的構(gòu)造

　　給定一個(gè)包含n個(gè)樣本的決策系統(tǒng)<U，A，D>，其中A=A1∪A2，A1定義為符號型屬性的集合，A2定義為數(shù)值型屬性的集合，U={x1，x2，…，xn}，，。本節(jié)將描述樣本的屬性分類處理，分別定義與之對應(yīng)的唯一函數(shù)。

　　符號型屬性的取值是離散的、非有序的，若兩個(gè)樣本的條件屬性取值完全相同，則其決策是一致的。因此，不同樣本間的區(qū)分能力由取值不同的屬性來體現(xiàn)，在此引入一個(gè)關(guān)系矩陣來體現(xiàn)符號型屬性集對樣本間的貢獻(xiàn)度。

　　數(shù)值型屬性的取值是連續(xù)的、有序的，當(dāng)兩個(gè)樣本除屬性a之外的其余條件屬性相同時(shí)，針對屬性a，若樣本x比樣本y占優(yōu)，則x的決策至少不比y差。因此，不同樣本間的區(qū)分能力由決策不一致的程度（即樣本x比樣本y占優(yōu)的程度）來體現(xiàn)。同樣定義數(shù)值型屬性集對樣本間的貢獻(xiàn)度：

　　s（xi，xj）表示對象xi比xj在屬性a上偏好、占優(yōu)的程度，若xi比xj占優(yōu)，則s（xi，xj）>0.5。若xj比xi占優(yōu)，則s（xi，xj）<0.5。當(dāng)s（xi，xj）=1時(shí)，說明xi比xj絕對占優(yōu)。矩陣是s（xi，xj）轉(zhuǎn)化后的對象間模糊相似關(guān)系，表示對象xi和xj間的相似性度量。

　　以上是針對一個(gè)數(shù)值屬性進(jìn)行的對象間模糊相似處理，對于多個(gè)屬性，采用交運(yùn)算來歸并不同屬性間的模糊關(guān)系。假設(shè)屬性a和屬性b分別計(jì)算其偏好關(guān)系為wij和zij，則對象xi與xj對屬性{a}∪量化的偏好關(guān)系為min（wij，zij）。

　　以上論述中提出了帶權(quán)的對象間相似性度量方法，實(shí)現(xiàn)了混合數(shù)據(jù)間的模糊相似關(guān)系構(gòu)造，但模糊等價(jià)關(guān)系是計(jì)算信息熵的前提，因此，最后還需將模糊相似矩陣轉(zhuǎn)化為模糊等價(jià)矩陣。

　　2.2 模糊等價(jià)關(guān)系的構(gòu)造算法及約簡算法

　　本節(jié)采用Lee Hauan-Shih給出的關(guān)于模糊相似矩陣傳遞閉包問題的優(yōu)化算法來進(jìn)行轉(zhuǎn)化[19]，使其滿足模糊等價(jià)關(guān)系的充要條件傳遞性，具體算法如下：

　　算法：設(shè)模糊相似矩陣為R=（rij）n×n，模糊等價(jià)矩陣為R*=（r*ij）n×n

　　輸入：R=（rij）n×n

　　輸出：R的傳遞閉包R*

　?。?）令r*ii=1（1≤i≤n）；

　?。?）集合U={rij|j>i}中的元素是從大到小排序的序列；

　?。?）

　?、偃鬜*中元素不存在r*ii=，結(jié)束算法；否則轉(zhuǎn)步驟②。

　?、趯τ赨中的最大元素ri′j′，若r*i′j′=，令I(lǐng)={j|r*i′j≠}，J={i|r*ij′≠}，置r*ij=r*ji=ri′j′（i∈I，j∈J），U=U-{ri′′j}；否則，轉(zhuǎn)步驟①。

　　下面將采用基于屬性重要性的約簡算法進(jìn)行約簡，算法中設(shè)置一個(gè)信息表T用來存儲所有屬性值，其中屬性元素按照領(lǐng)域?qū)＜业慕?jīng)驗(yàn)值和用戶的需求偏好多寡來排序。

　　算法如下：

　　輸入：決策系統(tǒng)S=<U，A，V，f>，A=C∪d，信息表T；

　　輸入：S的屬性約簡RED。

　?。?）令RED=；

　?。?）令T中元素從大到小進(jìn)行排序；

　?。?）

　?、龠x擇T中第一個(gè)屬性ai，計(jì)算H（d|ai∪RED）以及SIGi（ai，ai∪RED，d）=H（d|RED）-H（d|ai∪RED）

　?、谌鬝IGi>0，則ai∪RED→RED，T-ai→T，返回

　　步驟①；否則算法結(jié)束。

3 實(shí)驗(yàn)分析

　　本節(jié)在MATLAB實(shí)驗(yàn)環(huán)境下選擇UCI數(shù)據(jù)庫中的數(shù)據(jù)集，驗(yàn)證混合數(shù)據(jù)的模糊等價(jià)關(guān)系構(gòu)造約簡方法的有效性，表1列出了數(shù)據(jù)集的基本信息。可以看出其中數(shù)據(jù)集WPBC包含一類屬性，其他數(shù)據(jù)集包含兩類屬性。

　　表2和表3分別列出了本文方法下的數(shù)據(jù)集約簡結(jié)果以及約簡后屬性數(shù)目的統(tǒng)計(jì)。

　　分析表3，與其他三種方法（原始數(shù)據(jù)下的約簡、離散化方法下的約簡、模糊熵方法下的約簡）[16]支撐的數(shù)據(jù)相比，本文方法在信息量保持不變的前提下剔除了更多的冗余屬性；同時(shí)，針對包含一類或兩類屬性的數(shù)據(jù)集都進(jìn)行了有效的約簡。表4是采用支持向量機(jī)對本文結(jié)果與其他幾種方法[16]的約簡數(shù)據(jù)進(jìn)行精度對比。實(shí)驗(yàn)結(jié)果顯示本文方法下約簡后的屬性精度平均值較高。由此可以看出本文提出的基于模糊等價(jià)關(guān)系構(gòu)造的混合數(shù)據(jù)約簡有效地達(dá)到了約簡的目的，并且得到較優(yōu)的約簡結(jié)果。

4 結(jié)束語

　　模糊粗糙集和粗糙模糊集概念的提出，融合了模糊粒化和粗糙逼近兩種不確定性方法，基于模糊粗糙集模型構(gòu)建模糊等價(jià)關(guān)系是混合數(shù)據(jù)分析的有效方法之一。針對混合型信息系統(tǒng)，本文分別提出各類數(shù)據(jù)的對象間度量以及總體度量方法，建立帶權(quán)的對象間相似性度量方法，在轉(zhuǎn)化為模糊等價(jià)關(guān)系的基礎(chǔ)上，采用了加入領(lǐng)域?qū)＜业慕?jīng)驗(yàn)知識和系統(tǒng)客戶需求的約簡算法。通過實(shí)驗(yàn)數(shù)據(jù)分析驗(yàn)證了方法的有效性和可行性。

　　參考文獻(xiàn)

　　[1] PAWLAK Z. Rough sets-theoretical aspects of reasoning about data[M]. Dordrecht： Kluwer Academic， 1991.

　　[2] 張清華，王國胤，肖雨.粗糙集的近似集[J].軟件學(xué)報(bào)，2012，23（7）：1745-1759.

　　[3] 石夢婷，劉文奇，余高鋒，等.變精度軟粗糙集[J].計(jì)算機(jī)工程與應(yīng)用，2014（1）：101-104.

　　[4] CATLETT J. On changing continuous attributes into ordered discrete attributes[C]. European working session on learning， 1991：164-178.

　　[5] LIU H， HUSSIANM F， TAN C L， et al. Discretization： an enabling technique[J]. Data Mining and Knowledge Discovery， 2002，6（4）：393-423.

　　[6] HALL M A. Correlation-based feature selection for discrete and numeric class machine learning[C]. In Proc 17th ICML， 2000：359-366.

　　[7] ZHOU Z H， QIAN C Z. Hybrid decision tree[J]. Knowledge Based Systems， 2002，15（8）：515-528.

　　[8] TANG W. Y， MAO K. Z. Feature selection algorithm for mixed data with both nominal and continuous features[J]. Pattern Recognition Letters， 2007，28（5）：563-571.

　　[9] KWAK N， CHOI C H. Input feature selection by mutual information based on parzen window[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002，24（12）： 1667-1671.

　　[10] ZADEH L. Toward a generalized theory of uncertainty-an outline[J]. Information Science， 2005，172：1-40.

　　[11] DUBOIS D， PRADE H.  Rough fuzzy sets and fuzzy rough sets[J]. International Journal of General Systems， 1990，17（2-3）：191-209.

　　[12] 范成禮，邢清華，鄒志剛，等.基于直覺模糊粗糙集相似度的多屬性決策方法[J].計(jì)算機(jī)工程與應(yīng)用，2014（7）：121-124.

　　[13] 丁世飛，朱紅，許新征，等.基于熵的模糊信息測度研究[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（4）：796-801.

　　[14] Pan Zhenghua， Zhang Lijuan. A new fuzzy set with three kinds of negations and applications to decision making in financial investment[J]. Journal of Haman and Ecological Risk Assessment， 2011，17（4）：795-780.

　　[15] 潘正華.模糊知識的三種否定及其集合基礎(chǔ)[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（7）：1421-1428.

　　[16] Hu Qinghua， Yu Daren， Xie Zongxia. Information-preserving hybrid data reduction based on fuzzy-rough techniques[J]. Pattern Recognition Letters， 2006，27（5）：414-423.

　　[17] HASHMI K， ALHOSBAN A， MALIK Z， et al. WebNeg： a genetic algorithm based approach for service negotiation[C]. In： Foster I， et al.， eds. Proc. of the ICWS 2011， Los Alamitos： IEEE CS， 2011：105-112.

　　[18] 梁亞瀾，聶長海.覆蓋表生成的遺傳算法配置參數(shù)優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（7）：1522-1538.

　　[19] LEE H S. An optimal algorithm for computing the max-min transitive closure of a fuzzy similarity matrix[J]. Fuzzy Sets and Systems， 2011，123（1），129-136.