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

侯利娟，史長瓊

長沙理工大學計算機與通信工程學院，長沙 410004

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

侯利娟，史長瓊

長沙理工大學計算機與通信工程學院，長沙 410004

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

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

1 引言

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

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

2 離散化問題的描述

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

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

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

定義1基本二進制區(qū)分矩陣BM構造如下：

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

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

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

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

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

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

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

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

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

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

5.1 最小斷點集的二進制表示

5.2 算法的核心思想

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

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

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

5.3 算法步驟

6 實例分析

表1 未離散化的決策表

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

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

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

7 算法分析與比較

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

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

8 結束語

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

[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].計算機科學，2000，27（12）：89-94.

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

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

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

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

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

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

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

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

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

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

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

[15]秦川，黃歡.基于區(qū)分矩陣的數(shù)據(jù)離散化算法[J].計算機工程與應用，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—），女，講師，研究領域為粗糙集理論與應用，數(shù)據(jù)挖掘等；史長瓊（1968—），女，副教授，研究領域為計算機網絡，數(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