【畢業(yè)學(xué)位論文】（Word原稿）二進制在集合運算與數(shù)據(jù)挖掘中的應(yīng)用研究-計算機應(yīng)用技術(shù)

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