一種面向混合數(shù)據(jù)的模糊等價關(guān)系構(gòu)造約簡*

宋婷

（太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原030024）

一種面向混合數(shù)據(jù)的模糊等價關(guān)系構(gòu)造約簡*

宋婷

（太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原030024）

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

模糊粗糙集模型；模糊等價關(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)為模糊信息?；谥R發(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ì)算量大、耗時長[17-18]。

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

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

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

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

定義1：給定一個矩陣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為模糊等價矩陣。

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

定義2[16]：R是U上的模糊等價關(guān)系，定義R的信息量的模糊等價類。

定義3[16]：給定兩個模糊等價關(guān)系B和E，對應(yīng)的模糊等價類為[xi]B和[xi]E，則B和E的聯(lián)合熵定義為：

條件熵定義為：

定義4[16]：給定模糊信息系統(tǒng)＜U，A，V，f＞，A=C∪d，B?C，若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ù)間的模糊等價關(guān)系，依據(jù)屬性重要性的度量進(jìn)行約簡。

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

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

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

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

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

定義對象xi和xj間的相似性度量當(dāng)不存在能區(qū)分對象xi和xj的屬性時，=1；當(dāng)對象xi和 xj的分類完全不一致時，=0。

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

其中k是一個常數(shù)，且k＞0。

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時，說明xi比xj絕對占優(yōu)。矩陣r2ij是s（xi，xj）轉(zhuǎn)化后的對象間模糊相似關(guān)系，表示對象xi和xj間的相似性度量。

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

在屬性分類處理之后，引入模糊相似矩陣R=（rij）n×n度量對象間的相似性程度：表示對象xi和 xj在屬性集Ak上的相似性度量，其中α1和α2分別體現(xiàn)符號型屬性和數(shù)值型屬性在系統(tǒng)中的權(quán)重比例。

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

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

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

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

輸入：R=（rij）n×n

輸出：R的傳遞閉包R*

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

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

（3）

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

②對于U中的最大元素ri′j′，若?，令I(lǐng)={j≠?}，（i∈I，j∈J），U=U-{ri′′j}；否則，轉(zhuǎn)步驟①。

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

算法如下：

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

輸入：S的屬性約簡RED。

（1）令RED=?；

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

（3）

①選擇T中第一個屬性ai，計(jì)算H（d|ai∪RED）以及SIGi（ai，ai∪RED，d）=H（d|RED）-H（d|ai∪RED）

②若SIGi＞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ù)的模糊等價關(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ù)據(jù)集都進(jìn)行了有效的約簡。表4是采用支持向量機(jī)對本文結(jié)果與其他幾種方法[16]的約簡數(shù)據(jù)進(jìn)行精度對比。實(shí)驗(yàn)結(jié)果顯示本文方法下約簡后的屬性精度平均值較高。由此可以看出本文提出的基于模糊等價關(guān)系構(gòu)造的混合數(shù)據(jù)約簡有效地達(dá)到了約簡的目的，并且得到較優(yōu)的約簡結(jié)果。

表1 數(shù)據(jù)集基本信息

表2 五個數(shù)據(jù)集的約簡結(jié)果

表3 約簡后屬性數(shù)目對比

表4 基于SVM的約簡結(jié)果屬性精度比較（%）

4 結(jié)束語

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

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

[2]張清華，王國胤，肖雨.粗糙集的近似集[J].軟件學(xué)報，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é)報，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é)報，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é)報，2012，35（7）：1522-1538.

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

Hybrid data reduction based on fuzzy equivalence relations construction

Song Ting
（Computer Science and Technology Institute，Taiyuan University of Science and Technology，Taiyuan 030024，China）

Constructing the fuzzy equivalence relation based on fuzzy-rough set model is one of the effective methods for hybrid data analysis.A weighted similarity measurement between objects for hybrid information system that attributes diversity is proposed. The method creates similarity measurement function corresponding to each class of attribute and then establish fuzzy similar matrix by merging.Reduction algorithm that contains knowledge of filed experts and needs of user is on the basis of transforming into fuzzy equivalence relation.The validity and feasibility of the proposed method are verified by comparing the number and precision of attributes reducted of sample data sets from UCI database.

fuzzy-rough set model；fuzzy equivalence relation；hybrid data；fuzzy similar matrix；reduction

TP3

A

1674-7720（2015）09-0022-04

2015-03-05）

宋婷（1984-），女，碩士研究生，助教，主要研究方向：數(shù)據(jù)挖掘。

太原科技大學(xué)青年基金（20123005）