二進制在集合運算與 數據挖掘中的應用研究 李天志 二 0 0 六年 六 月 碩士學位 論 文 李天志 碩 士 二制 在 集 合運算與數據挖掘中的應用研究 2006 分類號 密級 碩士學位論文 二進制在集合運算與 數據挖掘中的應用研究 李 天 志 學科專業(yè) 計算機應用技術 指導教師 梁家榮 教授 論文答辯日期 2006 年 6 月 日 學位授予日期 答辯委員會主席 論文評閱人 i 二進制在集合運算與數據挖掘中的應用研究 摘 要 集合論的提出及發(fā)展大大促進了計算機應用技術的創(chuàng)新，尤其，近些年來迅速發(fā)展起來的 理論，對于處理不確定、不精確、模糊信息提供了良好的解決方法，加快了人工智能技術的發(fā)展。但是，集合運算計算機實現技術的落后嚴重阻礙了集合的進一步應用。二進制與集合存在著密切的內在聯系，二進制位運算是計算機中處理速度最 快的運算，而且二進制數據運用方便，變化靈活。 本文將二進制引入到集合運算中，并不斷加深研究。首先，探討了集合運算的基本概念，通過分析二進制與集合之間的內在聯系，將二進制位運算引入到集合基本運算中，并給出了各種基本運算的具體實現算法。接著，通過對粗糙集理論的研究，闡明了粗糙集理論是一種尤為適用于不確定、不完備系統(tǒng)的數據挖掘的數學工具，其中，重點探討了屬性約簡以及數據挖掘的相關內容。在此基礎上，提出了基于二進制的粗糙集運算理論，將二進制位運算運用到粗糙集的基本運算、屬性求核中，并且提出了相關的一些定理。 然后， 通過分析知識表以及決策表求核過程，找到新的求核方法，提出新的定理及規(guī)則，并將求核運算轉化為二進制數據的比較運算，進一步提高了求核效率。最后，通過分析二進制與關聯規(guī)則項集的關系，提出了基于二進制的關聯規(guī)則挖掘算法，并分析比較了相對于傳統(tǒng)算法的優(yōu)勢。 關鍵詞：集合論；粗糙集；二進制；屬性約簡；核；知識表；決策表；關聯規(guī)則；數據挖掘 of is of a or of of s an is as to is a of is is us of of is a of or on on on is is to by of of to of It is is is 西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 目 錄 第一章 緒 論 . 1 . 1 . 1 文的主要工作 . 2 文的組織結構 . 3 第二章 基于二進制的集合運算研究 . 5 . 5 合基本定義 . 5 . 6 . 6 于二進制的集合運算 . 7 二進 制求集合的冪集 . 7 二進制求集合的交集 . 9 二進制求集合的并集 . 9 二進制求集合的補集 . 10 二進制求集合的相對補 . 10 斷一個集合是否是另一個集合的子集 . 10 . 11 第三章 粗糙集理論概述 . 12 糙集理論的基本概念 . 12 性約簡 . 15 性約簡 . 15 約簡與規(guī)則提取 . 17 糙集的理論研究 . 18 . 18 . 18 . 19 章小結 . 20 第四章 基于二進制的粗糙集基本運算研究 . 21 進制與粗糙集的內在聯系 . 21 于二進制的粗糙集基本運算 . 21 糙集的上近似集 . 22 糙集的下近似集 . 22 . 23 合的基數 . 24 糙集運算舉例 . 24 . 24 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 第五章 基于位運算的屬性核約簡 . 26 . 26 . 27 . 27 . 30 . 30 例分析 . 30 . 31 第六章 基于二進制的知識表求核算法 . 32 . 32 . 33 . 35 . 35 第七章 基于二進制的決策表求核算法 . 36 . 36 . 37 . 40 . 40 第八章 基于二進制的關聯規(guī)則挖掘算法 . 42 . 42 . 43 . 43 . 43 . 44 . 45 . 46 第九章 總結 . 48 作小結 . 48 在的問題 . 48 一步的工作 . 49 參考文獻 . 50 致 謝 . 55 攻讀碩士學位期間完成的學術論文 . 56 攻讀碩士學位期間參加的科研項目 . 57 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 1 第一章 緒 論 內外研究現狀 集合論在計算機科學、人工智能領域、邏輯學及語言學等方面的理論研究成果已經很多，但在理論研究中人們主要是利用傳統(tǒng)數學方式對集合進行描述，對于集合的計算機實現算法研究很少， 主要局限文 5提到的一些方法，這些方法由于自身操作的復雜性導致集合運算的效率很低。 二進制位運算是計算機中最基本的運算，具有易于實現，運算速度快等特點，被廣泛應用與計算機的各個領域中，如密碼學 10，遺傳算法 11，可變矩陣約簡 12，編碼 13，其主要思想是利用二進制的位操作來實現各種技術。隨著人們對二進制認識的不斷加深，其應用領域也在不斷擴大，運用技巧方法也不斷被改進更新。在求集合冪集、組合方面有學者曾嘗試使用二進制來實現 15，但是由于所用技巧方法不當，時間復雜度仍然很高。 隨著數據挖掘技術和粗集理論的不斷發(fā)展，人們將二者有效結合了起來，即出現了對基于粗集理論的數據挖掘技術的研究?；诖旨碚摰臄祿诰蛩枷胧牵簩祿熘械膶傩苑譃闂l件屬性和決策屬性，對數據庫中的元組根據各個屬性不同的屬性值分成相應的子集，然后根據條件屬性劃分的子集和決策屬性劃分的子集之間的上下近似關系生成決策規(guī)則。將以粗集為代表的集合論方法應用到數據挖掘 (域已經取得了一定的成果 16一些學者曾嘗試將二進制融于數據挖掘中 30并且取得了良好的效果。 因此，將二進制應用于集合以及粗糙集運 算中，完成數據挖掘，無論在理論上還是應用上都有待深入研究和發(fā)展，這為本課題的研究提供了契機。 文的選題背景及意義 集合論是在 19 世紀 70 年代由德國數學家康托（ G. 無窮序列和分析的有關課題的理論研究中創(chuàng)立的 1，康托對具有任意特性的無窮集合進行了深入的探討，提出了關于基數、序數、超窮數和良序集等理論，奠定了集合論的深厚基礎，以后逐步發(fā)展形成一門獨立學科，一般稱此時期的集合理論為經典集合論。經典集合論是以二值邏輯為基礎的，從集合和特征函數定義看 , 某個事物只能屬于或不屬于某集合 , 不 可能有第三種可能，這就是經典集合的二值性。但是隨著集合論的發(fā)展，以及它與數學哲學密廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 2 切聯系所作的討論，出現了許多似是而非、自相矛盾的悖論，如著名的羅素（ B A W 論，有力的沖擊了或者說動搖了集合論的發(fā)展，由此，激發(fā)許多數學家、哲學家為克服這些矛盾而建立了各種公理化集合論體系。出于解決處理一些問題的需要， 20 世紀 60 年代 出了 理論 2， 20 世紀 80 提出了 理論 3，這兩種理論不同于經典集合理論，它們是一種新的模糊集合理論，自 問世以來，一直受到學術界的重視和青睞，并取得了喜人成果。 經典集合論曾為半個多世紀的計算機技術大發(fā)展立下不朽的功勛 ，并且當前仍然廣泛應用于各種計算機領域。但是，人腦是這個世界上最復雜、智能最高的系統(tǒng)。它的精妙之處就在于能夠處理信息的不確定性、不精確性、不完全性、模糊性、隨機性和非單調性，從而得到正確或滿意的結論，為人們作出決策提供強有力的支持。在現實世界中，人們對某個事物或事件進行判斷、推理、預測、決策時，所面對的信息常常是不精確、不完全或模糊的，這就要求我們在計算機中模擬人的智能行為時，計算機能夠處理這類信息。 理論作為經典集合論的擴展，是一種新的處理模糊和不確定知識的軟計算工具，它把那些無法確認的個體都歸屬于邊界線區(qū)域，而這種邊界線區(qū)域被定義為上近似集和下近似集之差集。由于上近似集和下近似集都可以通過等價關系給出確定的數學公式描述，所以含糊元素數目可以被計算出來，即在真假二值之間的含糊程度可以計算。粗糙集自問世以來，無論是在理論還是應用上都是一種新的、最重要的并且發(fā)展非常迅速的一門研究領域，它在理論上的深遠意義和應用中的巨大潛力正吸引著世界各國許多專家學者的注意，尤其在人工智能的各個研究領域中發(fā) 展尤其顯著 4。 給定一個集合，對其進行計算機運算并不是一件容易事，傳統(tǒng)的操作主要是將集合元素存入數組或者字符串中，通過字符串的查找、比較、插入等操作完成集合的各種運算，傳統(tǒng)的這些操作算法空間、時間復雜度都很高，有的還牽扯到數據的移動，因此，運算速度慢、效率低，大大制約了集合論在現實中的應用。如何快速有效的利用計算機對集合以及粗糙集運算進行處理，一直是學術界關心的課題。本課題將通過討論二進制與集合之間的內在聯系，提出基于二進制的集合運算理論，充分發(fā)揮二進制數據在計算機中運算速度快、節(jié)約空間的優(yōu)勢，并對二 進制在數據挖掘中的應用進行探索，以提高數據挖掘效率。因此，基于二進制的集合運算及在數據挖掘中的應用研究是一項很有學術價值和實際意義的工作。 文的主要工作 本文 從二進制在經典集合計算中的應用研究入手，將二進制與集合聯系在一起，進而將二進制應用到粗糙集運算中 ，并對其在 數據挖掘中的應用進行了探討 。論文 主要完成了以下幾個方面的工作： 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 3 1、研究了經典集合運算與二進制位運算的關系， 指出了傳統(tǒng)經典集合運算計算機實現方法的缺點，實現了二進制與集合基本運算的結合，并給出了相關算法。 2、研究了粗糙集的基本理論和方 法，討論了粗糙集基本運算與集合的聯系，重點研究了二進制位運算在粗糙集基本運算中以及屬性核約簡中的應用，并結合實例分析了基于二進制位運算的粗糙集運算的優(yōu)點，得出了有意義的結論。 3、通過分析屬性約簡過程，得出相關定理， 提出了基于二進制的知識表核約簡以及基于二進制的決策表核約簡思想，將求核過程轉化為數值的比較，并通過理論分析和實例說明了算法的有效性。 4、通過分析二進制與關聯規(guī)則項集的關系，提出了基于二進制的關聯規(guī)則挖掘算法，并分析比較了相對于傳統(tǒng)算法的優(yōu)勢。 文的組織結構 本文針對傳統(tǒng)集合運算計算機 算法運算效率低的問題，將二進制引入到集合以及數據挖掘中，圍繞二進制在集合以及粗糙集運算中的應用，逐步展開全面而深入的研究。本文各章節(jié)的安排如下： 第一章 緒論 介紹了論文的選題背景，闡述了論文選題的意義，并對本課題的國內外研究現狀進行了介紹。 第二章 基于二進制的集合運算研究 首先介紹了集合的基本概念，然后分析比較二進制與集合之間的內在聯系，最后，通過二進制位運算實現了集合的各種基本運算，并且對相關算法給出了 C 語言源代碼。 第三章 粗糙集理論概述 本章首先介紹粗糙集理論的基本概念，然后分析了該理論的研究 狀況，最后對粗糙集理論在數據挖掘中的應用進行了研究。 第四章 基于二進制的粗糙集基本運算研究 本章在第二章基于二進制的集合運算研究的基礎上，通過討論二進制與粗糙集之間的內在聯系，提出了 基于二進制的粗糙集運算理論。借助位操作對粗糙集進行運算，充分發(fā)揮其 運算速度快、節(jié)約空間的優(yōu)勢，并且 給出了相關算法的 第五章 基于位運算的屬性核約簡 本章是二進制位運算在粗糙集中的進一步應用，通過將二進制位運算運用到知識表屬性的核約簡中，提高求核效率。 第六章 基于二進制的知識表求核算法 本章首先分析知識表求核過程 ，得出了一個重要分類定理，然后，將二進制引入求廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 4 核算法中，利用此定理將屬性核的求 解變?yōu)閿抵档谋容^問題，充分利用了二進制數據處理靈活，運算速度快的優(yōu)勢，可以將時間復雜度降到 O(|U|*|R|)。 第七章 基于二進制的決策表求核算法 本章首先分析了決策表求核過程，提出了相關定理和規(guī)則，在此基礎上，將二進制運用到求核算法中，將決策表屬性核的求解變?yōu)閿抵档牟檎摇⒈容^問題，從而將算法時間復雜度大大降低。 第八章 基于二進制的關聯規(guī)則挖掘算法 本章通過分析二進制與關聯規(guī)則項集的關系，將二進制引入到關聯規(guī)則挖掘過程中，減少 了事務子集的求解次數，從而減少了時間復雜度，提高了挖掘效率。 第九章 總結 對論文工作進行了總結，對后續(xù)研究進行了展望。 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 5 第二章 基于二進制的集合運算研究 集合論是在十九世紀末由德國數學家康托創(chuàng)立的，以后逐步發(fā)展形成一門獨立學科， 由于廣泛的使用了數理邏輯的工具，集合論逐漸成為數理邏輯的一個分支，并從 60年代以來獲得迅速的發(fā)展 ，現已滲透到數學的許多分支中，并在計算機的人工智能等領域得到了廣泛應用，如粗糙集，模糊集等數據挖掘方法中都大量使用了集合的各種運算。但是，目前關于集合運算計算機實現算法的 相關研究文獻不多，而傳統(tǒng)的對集合操作主要是利用字符串匹配、查詢等來實現 5，效率低，而且對空間要求很高，大大制約了集合理論向實際應用的轉化，如何快速有效的利用計算機對集合運算進行處理一直是學術界關心的課題。 本章首先介紹了集合的基本概念，然后分析比較二進制與集合之間的內在聯系，最后，通過二進制位運算實現了集合的各種基本運算，并且對相關算法給出了 C 語言源代碼。 合的概念 合基本定義 定義 合是一些確定的對象的全體，對象稱為元素，若 a 是集合 A 的元素，則記為 a A。 定義 含 任何元素的集合叫做空集，記做 或。 定義 A,B 為集合，若任意 一定有 ，則稱 A 是 B 的子集，也稱 包含，或 B 包含 A，記為 。 定義 A,B 為集合，若 且 ，則稱 A 與 B 相等，記為 A=B。 定義 ，但是 ，則稱 A 是 B 的真子集，記為 。 定義 集：由 A 的所有子集組成的集合稱為 A 的冪集，記為 P（ A）或 定義 數：集合 A 中元素的個數稱為 A 的基數，記為 |A|。 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 6 合的基本運算 定義 集：集合 A 與 B 的交集 A B=x|x A 并且 x B。 定義 集：集合 A 與 B 的并集 A B= x|x A 或 x B。 定義 , B 是分離的，若 A B= 定義 對補：集合 A 對 B 的相對補 x|x A 并且 x B 。 定義 集：集合 A 的補集為全集 E 與 A 的差，記為 A。 定義 稱差：集合 A 與 B 的對稱差 A B=（ （ 合與二進制的關系 二進制自問世以來，在計算機的研究和應用領域起著重要的作用，它的值域只有“ 0”，“ 1”兩個值，但是通過對這兩個值的有效組合和簡單運算，卻能表達出客觀真實世界的千變萬化，下面通過分析二進制和集合之間強大的內在聯系，說明二進制在集合運算中的巨大作用。 若集合 A 具有 n 個元素，則 A 的所有 子集 (冪集 )的個數 | P(A)|= 例如， A a,b,c,則 A 的冪集為 ,a,b,a,b,c,a,c,b,c,a,b,c， A 的冪集的基數為 32 8 。 長度為 n 的二進制位所能表達的數據個數為 例如長度為 3 的二進制位，所能生成的數據為 000,001,010,011,100,101,110,111，共 32 8 個數據。 通過比較發(fā)現，長度為 n 的二進制位所能表達的數據個數和具有相同元素個數的集合的所有子集 (冪集 )的數目相同，由此可以猜想二進制和集合之間應該具有某些聯系 ,現在做以下規(guī)定： 規(guī)定 于集合 I=0,1,2, ,n,，規(guī)定個 進制 數 P=。 與之對應，其中二進制數的第 0 位 對 應集合的第 0 個元素 0 ，第 1 位 對 應第 1 個元素 1 ，第 k 個元素 。 例 定一個 3 位的二進制數，用此二進制數的第 0 位代表上面所提到的集合 A的 a 元素，第 1 位代表集合 A 的 b 元素，第 2 位代表集合 A 的 c 元素，然后比較集合 下表所示： 序號 子集 二進制數 0 000 表 西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 7 1 a 001 2 b 010 3 a,b 011 4 c 100 5 a,c 101 6 b,c 110 7 a,b,c 111 通過比較發(fā)現，如果我們按照上表中的對應關系對子集進行編號，則集合第 i 個子集和二進制所產生的第 i 個數據之間存在著非常微妙的對照關系：如果在子集中某個元素存在，則此子集對應的二進制 數中該元素所對應的二進制位為 1，否則為 0。例如 ,子集 a,b,因為 a 對應二進制第 0 位， b 對應二進制第 1 位， c 對應二進制的第三位，而 以，其對應的二進制數為 011。 定義 集的下標：集合 A 的子集所對應的二進制數的十進制數值稱為此子集的下標。 有了集合與二進制之間的這種內在聯系，以后在對集合操作時，我們沒有必要對子集中的實際元素進行處理，只要知道子集的下標，就可以很容易的利用位運算來實現對集合進行各種操作的目的。 于二進制的集合運算 二進制求集合的冪集 已知集合 A，求 A 的冪集。 由于集合子集中的元素與子集下標中二進制位的“ 1”相對應，因此求子集中元素的運算可以轉化為尋找子集下標二進制位中“ 1”所在位置的運算，此運算可以利用移位操作來實現。例如，求 101所對應的 們可以通過 3次移位，每次先將當前的數值與數值 1相與，如果結果等于 1，則本次第 0位上的值為 1，否則為 0，由移位的次數可以知道當前第 0位的 1在原數據中的位置，從而找到對應的實際元素。運算如下： 第 0次與： 101&001 1 ， 位，而且本次 相與的結果為 1，所以 101右移一位，現在的數值為 010 第 1次與： 010&001=0， 位，而且本次相與的結果為 0，所廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 8 以 010右移一位，現在的數值為 001 第 1次與： 001&001=1， 位，而且本次相與的結果為 1，所以 001右移一位，現在的數值為 000。 計算完畢。求出 101 對應的 a,c。 求子集元素的 /* 中子集下標 b 所對應的子集中的所有元素 */ ,b ) f,j 0; /*; n); b0) b&1)0 ) if(f=0) f=1; %c,Aj); ,%c ,Aj); b=b1; j=j+1; ); 若求 只要從子集下標 0 次求各對應子集的元素即可，本算法可用一個循環(huán)完成，代碼如下： ,n) /n= 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 9 i; i=0; i|i u; 糙集的下近似集 由粗糙集的 下 近似集公式 R X= Y U/R|Y X可知， R X 是 R 的所有等價類中包含于 X 的等價類的并。集合的包含關系可由其子集 下標 的或運算判斷得到，即 AB 當且僅當 A B=B。求下近似集的具體算法如下： ， ， M) 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 23 /返回值為下近似集對應的 子集 下標 i; u; ; ; i=0;=t; ; 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 24 合的基數 在計算 近似精確度 R（ X）以及其它很多運算時，需要計算集合的基數，即元素個數。由集合對應的子集下標可以非常容易的計算其基數，即子集下標二進制表示中“ 1”的個數，該值可以利用移位運算來得 到。具體算法如下： ; ) )0) /當前值的最后一位為 1 ; 1; 關于粗糙集中其它運算的算法，可仿照上述算法給出，限于篇幅不再敘述。 糙集運算舉例 例 例 X=按照前面的算法計算可得 : X=(10100111001)2=1337 R X=， X， M)=1467 R X=， X， M)=312 )=1467155 )=204780 R（ X） =|84 。 由此 ,可以看出，基于二進制的粗糙集基本運算方便，快捷。 章小結 本章在第二章研究的基礎上，通過討論 二進制與粗糙集之間的內在聯系，提出了基于二進制的粗糙集運算理論。借助位運算操作，給出了幾種基于二進制的粗糙集基本廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 25 運算算法，其 算法的時間復雜度主要與等價類的個數有關。由于算法中沒有了等價類元素的比較且主要是位運算，所以，與傳統(tǒng)的算法相比，其運算速度更快，效率更高。 本章提出的思想，也可以用于計算決策屬性的支持度、依賴度等，為屬性約簡以及擴展粗糙集的應用提供了理論基礎。該算 法思想可以應用在數據挖掘的分類、決策分析中。 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 26 第五章 基于位運算的屬性核約簡 粗糙集理論的核心內容之一就是知識約簡，國內外很多專家對之進行了研究 43眾所周知，求粗糙集的最小知識約簡是一個 識約簡方面的算法已經很多，如基于屬性重要性、基于差別矩陣等，其中，很多算法都需要預先求出知識表中的屬性核作為計算的初始條件，但是，到目前為止，還沒有一個公認的、高效的求核算法。 本章是二進制位運算在粗糙集中的進一步應用，通過將二進制位運算運用到知識表屬性的核約簡中，提高求核效率。 本章二 進制與粗糙集的關系同第四章所述。 法基本思想 本算法主要是通過屬性去除后，檢測分類數目的變化來確定屬性是否為必要的，下面給出算法所用到的一個定理。 定理 為某一等價關系簇，如果 ，且 r 為 R 必要的，則 U/ -r)所產生的分類數小于 U/ )產生的分類數。 證明：對 U/R 的任意等價類 x)，若 y x)，則 有 f(x,a)=f(y,a)，而R-r R，所以 y x-r), x) x-r) |U/R| |U/(R-r)| 又因為 r 為 R 必要的 |U/R| |U/(R-r)| 故 |U/R|0) /第 i 位元素還沒有歸類 (); /將當前等價類查找成功標志置 0 (*將第 i 位元素歸入 */ (*表將要檢測的下一元素對應位 */ 出：核屬性集 知識庫的屬性值二進制化； 據二進制化的元素屬性值，求 屬性 (R)； U/) 的每個分類中選取一個元素形成新的集合 i=1 R| 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應用研究 35 /|R|為知識庫中屬性的個數 將 ； 遍歷 是否有相同值的出現，有，則將 核算法復雜度分析 本算法中， 解 U/ )，需要遍歷知識庫中所有 元素，值相同的元素劃分到同一類 ，這部分的時間復雜度與所使用的分類存儲方式有關，可 以使用動態(tài)鏈表，或者靜態(tài)鏈表，如果使用方法得當，可以將時間復雜度控制在 O(|U|)；對于 產生的分類數目有關。所以本算法的總的時間復雜度可以控制在 O(|U|*|R|)，而傳統(tǒng)的求核算法中的時間復雜度為 O(|R|U|2)。 束語 知識約簡是粗糙集理論中的核心內容之一，而求核運算又是知識約簡的基礎，求核算法的效率對于知識約簡至關重要。本章提出了一個粗糙集分類定理，在這個定理基礎上， 通過將屬性值二進制化 ，給出了 基于二進制的知識表求核算法，充分利用了二進制數據處理 方便，變換靈活的優(yōu)勢。本 算法中主要運用的是數值的比較，與傳統(tǒng)算法 61,62相比，其運算速度更快，效率更高。 廣西大學碩士學位論文 二進制在集合運算與數據挖掘中的應