基于二進(jìn)制區(qū)分矩陣的離散化算法

侯利娟，史長瓊

長沙理工大學(xué)計算機(jī)與通信工程學(xué)院，長沙 410004

基于二進(jìn)制區(qū)分矩陣的離散化算法

侯利娟，史長瓊

長沙理工大學(xué)計算機(jī)與通信工程學(xué)院，長沙 410004

提出離散化中基本二進(jìn)制區(qū)分矩陣的定義及其簡化方法和基于簡化二進(jìn)制區(qū)分矩陣的離散化算法，把符號運(yùn)算轉(zhuǎn)變成二進(jìn)制運(yùn)算，有效地節(jié)約了存儲空間和運(yùn)算時間。從區(qū)分度和區(qū)分率兩個不同層次考察斷點(diǎn)的重要性，引導(dǎo)求解過程趨于最優(yōu)化，只采用新增加的斷點(diǎn)對應(yīng)位與矩陣的行相應(yīng)位進(jìn)行運(yùn)算，進(jìn)一步提高計算效率。實(shí)例分析表明算法是正確有效的。

粗糙集理論；離散化；二進(jìn)制區(qū)分矩陣；簡化二進(jìn)制區(qū)分矩陣

1 引言

數(shù)據(jù)離散化是粗糙集理論中的預(yù)處理問題之一，處理結(jié)果的好壞，直接影響到屬性約簡和值約簡，人們對基于粗糙集模型的離散化方法已經(jīng)取得了一些有價值的研究成果。Nguyen等人提出了粗糙集與布爾邏輯方法[1]，該方法具有完備性，即理論上可以找出所有可能組合的離散化斷點(diǎn)集，但是其算法復(fù)雜度是指數(shù)級的，無法在實(shí)際問題中應(yīng)用，離散化問題都是在此基礎(chǔ)上提出的啟發(fā)式算法。文獻(xiàn)[2]提出的貪心算法，是基于斷點(diǎn)對實(shí)例的可分性，屬于局部尋優(yōu)搜索算法，算法時間復(fù)雜度和空間復(fù)雜度較高，更適合小樣本數(shù)據(jù)集；文獻(xiàn)[3-4]提出的基于屬性重要性的算法，優(yōu)先選取重要性高的屬性上的斷點(diǎn)。用判別函數(shù)對候選斷點(diǎn)進(jìn)行篩選是一類較常用的離散化算法，文獻(xiàn)[5-8]給出了基于信息熵的離散化算法，該算法用信息熵作判斷標(biāo)準(zhǔn)，從候選斷點(diǎn)中選擇合適的斷點(diǎn)，然后刪除一些冗余的斷點(diǎn)來優(yōu)化離散結(jié)果；文獻(xiàn)[9]提出改進(jìn)粒子群優(yōu)化的離散算法；文獻(xiàn)[10]提出一種新的區(qū)間拆分方法；文獻(xiàn)[11]提出了連續(xù)屬性決策表信息系統(tǒng)的圖論形式和離散化的圖論方法；文獻(xiàn)[12]提出了一種基于密度分布函數(shù)聚類的連續(xù)屬性離散化算法。根據(jù)基于聚類思想的離散化算法是否考慮連續(xù)屬性的互補(bǔ)性和相關(guān)性；文獻(xiàn)[13]將算法分為整體屬性離散化算法和單個屬性離散化算法；文獻(xiàn)[14]提出一種基于超立方體聚類的連續(xù)屬性整體離散化算法；文獻(xiàn)[15]提出基于傳統(tǒng)區(qū)分矩陣的數(shù)據(jù)離散化算法，把所有候選斷點(diǎn)集中到區(qū)分矩陣中，以斷點(diǎn)核為起點(diǎn)，根據(jù)候選斷點(diǎn)在區(qū)分矩陣中出現(xiàn)的頻率作為啟發(fā)信息，逐次選擇最重要的斷點(diǎn)加入到斷點(diǎn)子集中。

最小斷點(diǎn)集的計算問題是一個NP問題[1]，論域規(guī)模的增加和屬性值的組合爆炸對各種算法的效率影響很大。文獻(xiàn)[15]用斷點(diǎn)集合表示矩陣元素，消耗了大量的存儲空間，且所生成的區(qū)分矩陣在求解時，需要大量的符號邏輯運(yùn)算。本文提出了基本二進(jìn)制區(qū)分矩陣的定義及其簡化方法和在簡化二進(jìn)制區(qū)分矩陣基礎(chǔ)上的離散化算法，和文獻(xiàn)[15]相比可以有效地減少矩陣的存儲空間，在矩陣運(yùn)算上，采用二進(jìn)制的與運(yùn)算代替符號運(yùn)算，可以有效地節(jié)約運(yùn)算時間。

2 離散化問題的描述

3 基本二進(jìn)制區(qū)分矩陣

3.1 基本二進(jìn)制區(qū)分矩陣的定義

文獻(xiàn)[15]中傳統(tǒng)區(qū)分矩陣的元素是斷點(diǎn)的集合，消耗了大量的存儲空間，可以把它轉(zhuǎn)換成基本二進(jìn)制區(qū)分矩陣，用二進(jìn)制元素代替符號集合，節(jié)約存儲空間，基本二進(jìn)制區(qū)分矩陣的定義如下：

定義1基本二進(jìn)制區(qū)分矩陣BM構(gòu)造如下：

3.2 基本二進(jìn)制區(qū)分矩陣的分析

基本二進(jìn)制區(qū)分矩陣有下面四種主要的形式：

（1）如果某一列中所有的元素都為1，則這列所對應(yīng)的斷點(diǎn)能區(qū)分由所有斷點(diǎn)區(qū)分的所有實(shí)例對，這個斷點(diǎn)是決策表的一個最小斷點(diǎn)集，這種情況非常少見。

（2）如果某一列中所有的元素都為0，則這列所對應(yīng)的斷點(diǎn)不能區(qū)分任何一個實(shí)例對，因此，它是不必要的。

（3）如果某一行中元素1的個數(shù)為1，則元素1所對應(yīng)的斷點(diǎn)是能區(qū)分這個實(shí)例對的唯一斷點(diǎn)，因此，它是必要的，把這樣的斷點(diǎn)稱為斷點(diǎn)核。

（4）某一列中元素1所占的比例越大，相應(yīng)斷點(diǎn)能區(qū)分的實(shí)例對個數(shù)就越多，斷點(diǎn)的重要程度就越大。

4 簡化二進(jìn)制區(qū)分矩陣SBM

基本的二進(jìn)制區(qū)分矩陣將傳統(tǒng)區(qū)分矩陣中的元素用二進(jìn)制整數(shù)表示，其所占存儲空間比用符號表示的矩陣要少，另外，在由區(qū)分矩陣計算最小斷點(diǎn)集時，將符號邏輯運(yùn)算轉(zhuǎn)換成了位邏輯運(yùn)算，從而提高了效率。

但基本二進(jìn)制區(qū)分矩陣中還存在著大量的重復(fù)信息，仍占用比較大的存儲空間，根據(jù)符號邏輯運(yùn)算中的吸收律，設(shè)計了一個算法用于形成簡化的二進(jìn)制區(qū)分矩陣，簡化算法如下：

5 基于簡化二進(jìn)制區(qū)分矩陣的離散化算法

5.1 最小斷點(diǎn)集的二進(jìn)制表示

5.2 算法的核心思想

假設(shè)SBM(i，j)m是簡化二進(jìn)制區(qū)分矩陣的第m行，相應(yīng)的實(shí)例對為(xi，xj)，CBmin中值為1的位和SBM(i，j)m中的相應(yīng)位與運(yùn)算的結(jié)果如果全為0，則(xi，xj)將不能被Cmin區(qū)分。基于這種思想，設(shè)計一種直觀的算法，首先，選擇一個CBmin，然后將CBmin中值為1的位與SBM的每一行相應(yīng)位進(jìn)行與運(yùn)算，如果所有行運(yùn)算結(jié)果的每一位都為0，則重新選擇CBmin，否則保留CBmin中的值為1的位，重復(fù)這個過程直到遍歷了所有的行，最終所得的CBmin就是一個最小斷點(diǎn)集的二進(jìn)制表示。

算法的關(guān)鍵就是如何選擇CBmin，即選擇哪些斷點(diǎn)。為了衡量每個斷點(diǎn)的重要性，給出了兩個定義——斷點(diǎn)的區(qū)分度和區(qū)分率，用它們來衡量斷點(diǎn)的重要性，從而引導(dǎo)斷點(diǎn)的選取。

根據(jù)這兩個定義，選擇斷點(diǎn)時，可以優(yōu)先選擇重要性大的斷點(diǎn)，避免盲目選擇。

5.3 算法步驟

6 實(shí)例分析

表1 未離散化的決策表

表2 表1的基本二進(jìn)制區(qū)分矩陣BM

根據(jù)二進(jìn)制區(qū)分矩陣的簡化方法可以得到表1的簡化二進(jìn)制區(qū)分矩陣如表3，和基本的二進(jìn)制區(qū)分矩陣相比，矩陣元素進(jìn)一步減少。

表3 表1的簡化二進(jìn)制區(qū)分矩陣

7 算法分析與比較

文獻(xiàn)[15]用斷點(diǎn)集合表示矩陣元素，由于矩陣是對稱矩陣，只需要存儲下三角矩陣即可，假設(shè)決策表有n個實(shí)例，所有條件屬性共有m個候選斷點(diǎn)，則文獻(xiàn)[15]的步驟2中存儲斷點(diǎn)信息所需要的最大存儲空間為n× (n-1)×m×2k比特（k為一整數(shù)，具體的值和開發(fā)平臺有關(guān)，如C語言中k為8）。用本文中提出的基本二進(jìn)制區(qū)分矩陣存儲斷點(diǎn)信息，最大需要存儲空間為n×(n-1)×m比特，若用簡化的二進(jìn)制區(qū)分矩陣存儲，存儲空間將會進(jìn)一步減少，但簡化的二進(jìn)制區(qū)分矩陣的規(guī)模和決策表的數(shù)據(jù)相關(guān)，最壞情況下需要的存儲空間為n×(n-1)×m比特，是文獻(xiàn)[15]的1/（2k），節(jié)約了較多的存儲空間。

文獻(xiàn)[15]主要的時間開銷是步驟5中計算頻率最高的斷點(diǎn)，其基本操作是字符串的比較，每得到一個頻率最高的斷點(diǎn)最壞需要進(jìn)行n×(n-1)×m×β次字符串的比較（0＜β≤1，當(dāng)決策表不存在斷點(diǎn)核時β=1）。本文5.3節(jié)中步驟5遍歷簡化二進(jìn)制區(qū)分矩陣得到一個頻率最高的斷點(diǎn)需要的二進(jìn)制與運(yùn)算的次數(shù)最壞的情況為n×(n-1)×β次，節(jié)約了較多的運(yùn)算時間。

8 結(jié)束語

本文提出離散化中基本二進(jìn)制區(qū)分矩陣的定義及其簡化方法和基于簡化二進(jìn)制區(qū)分矩陣的離散化算法，用二進(jìn)制形式矩陣來代替?zhèn)鹘y(tǒng)矩陣表示對象之間的不可區(qū)分關(guān)系，把符號運(yùn)算轉(zhuǎn)變成二進(jìn)制運(yùn)算，有效地節(jié)約了存儲空間和運(yùn)算時間。通過對二進(jìn)制區(qū)分矩陣的特點(diǎn)進(jìn)行分析，定義了區(qū)分度和區(qū)分率兩個概念，從不同層次考察斷點(diǎn)的重要性，引導(dǎo)離散化過程趨于最優(yōu)化。在矩陣的行和斷點(diǎn)的二進(jìn)制位與運(yùn)算時，采用新增的斷點(diǎn)對應(yīng)的位和矩陣中行的相應(yīng)位進(jìn)行與運(yùn)算，進(jìn)一步節(jié)約運(yùn)算時間，對大數(shù)據(jù)量的決策表的離散化具有重要的意義。下一步的工作可以用并行程序設(shè)計的方法設(shè)計在簡化二進(jìn)制矩陣過程中涉及到的兩個二進(jìn)制串的與運(yùn)算。

[1]Nguyen H S，Skowron A.Quantization of real values attributes，rough set and Boolean reasoning approaches[C]// Proc of the 2nd Joint Annual Conference on Information Science.Wrightsville Beach：[s.n.]，1995：34-37.

[2]Nguyen S H，Nguyen H S.Some efficient algorithms for rough set methods[C]//Proc of Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems，1996.

[3]侯利娟，王國胤.粗糙集理論中的離散化問題[J].計算機(jī)科學(xué)，2000，27（12）：89-94.

[4]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2001.

[5]謝宏，程浩忠，牛東曉.基于信息熵的粗糙集連續(xù)屬性離散化算法[J].計算機(jī)學(xué)報，2005，28（9）：1570-1574.

[6]白根柱，裴志利.基于粗糙集理論和信息熵的屬性離散化方法[J].計算機(jī)應(yīng)用研究，2008，25（6）：1701-1703.

[7]高建國，崔業(yè)勤.基于信息熵理論的連續(xù)屬性離散化方法[J].微電子學(xué)與計算機(jī)，2011，28（7）：187-189.

[8]岳海亮，閆德勤.一種基于信息論的決策表連續(xù)屬性離散化算法[J].計算機(jī)科學(xué)，2010，37（4）：231-233.

[9]汪凌，胡培.基于改進(jìn)粒子群優(yōu)化的粗糙集連續(xù)屬性離散化[J].計算機(jī)工程與應(yīng)用，2010，46（15）：115-117.

[10]李慧，閆德勤.一種基于粗糙集理論的連續(xù)屬性離散化新算法[J].計算機(jī)應(yīng)用研究，2010，27（1）：77-78.

[11]盧鵬，王錫淮.連續(xù)屬性決策表離散化的圖論方法[J].計算機(jī)工程與應(yīng)用，2012，48（6）：13-16.

[12]李興生，李德毅.一種基于密度分布函數(shù)聚類的屬性離散化方法[J].系統(tǒng)仿真學(xué)報，2003，15（6）：804-806.

[13]苗奪謙.Routgh Set理論中連續(xù)屬性的離散化方法[J].自動化學(xué)報，2001，27（3）：296-302.

[14]于金龍，李曉紅，孫立新.連續(xù)屬性的整體離散化[J].哈爾濱工業(yè)大學(xué)學(xué)報，2000，32（3）：48-53.

[15]秦川，黃歡.基于區(qū)分矩陣的數(shù)據(jù)離散化算法[J].計算機(jī)工程與應(yīng)用，2008，44（35）：148-150.

HOU Lijuan,SHI Changqiong

School of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha 410004,China

This paper puts forward the definition of the basic binary discernibility matrix and it’s simplify method in discretization.Discretization algorithm based on simplify binary discernibility matrix is proposed.It changes symbolic computation into binary operation,can save the storage space and computing time efficiently.Cut significance is investigated at two different levels,which can lead the solution to optimization.Only using the new adding cut’s corresponding bit operate with the rows of the matrix corresponding bit,can reduce computing time further.Analysis of the example shows that the algorithm is correct and efficient.

rough set theory;discretization;binary discernibility matrix;simplify binary discernibility matrix

A

TP18

10.3778/j.issn.1002-8331.1212-0373

HOU Lijuan,SHI Changqiong.Discretization algorithm based on binary discernibility matrix.Computer Engineering and Applications,2014,50（21）：214-217.

湖南省教育廳資助科研項目（No.09C083）。

侯利娟（1973—），女，講師，研究領(lǐng)域?yàn)榇植诩碚撆c應(yīng)用，數(shù)據(jù)挖掘等；史長瓊（1968—），女，副教授，研究領(lǐng)域?yàn)橛嬎銠C(jī)網(wǎng)絡(luò)，數(shù)據(jù)挖掘等。E-mail：hlj1215@163.com

2013-01-04

2013-03-06

1002-8331（2014）21-0214-04

CNKI出版日期：2013-03-21，http://www.cnki.net/kcms/detail/11.2127.TP.20130321.0939.006.html