數(shù)據(jù)挖掘一般是指從大量的數(shù)據(jù)中通過算法搜索隱藏于其中信息的過程。數(shù)據(jù)挖掘通常與計算機科學有關，并通過統(tǒng)計、在線分析處理、情報檢索、機器學習、專家系統(tǒng)(依靠過去的經(jīng)驗法則)和模式識別等諸多方法來實現(xiàn)上述目標。以下是學習啦小編今天為大家精心準備的計算機職稱相關論文：粗集數(shù)據(jù)挖掘之MIE-RS實施。內(nèi)容僅供閱讀與參考!

　　粗集數(shù)據(jù)挖掘之MIE-RS實施全文如下：

　　1、方法原理

　　1.1　粗集基本理論

　　信息系統(tǒng)定義為,其中U是有限的例子集合.C是條件屬性集合,D是決策屬性集合,V是C和D的值域.函數(shù)f:U(C∪D→V,定義每個例子的屬性值.定義屬性集R C∪D上的等價關系為:R～={(xi,xj)∈U×U: a∈R,f(xi,a)=f(xj,a)}.R~的等價類的集合記作R*,它是U上的一個劃分.設Y U,Y關于R的下近似集合RY定義為:RY=∪{E∈R*: E Y}.即下近似集合包含所有根據(jù)R的信息能準確劃分到Y(jié)的例子.定義集合X關于集合Y的分類正確程度c(X,Y)為:c(X,Y)= X∩Y / X .其中 表示集合中元素的個數(shù).給定分類正確標準α,Y U ,根據(jù)粗集擴展模型,定義Y關于R的α-下近似RαY為:RαY=∪{E∈R*: c(E,Y) α},即Y的α-下近似包含所有能以不小于α的正確率劃分到Y(jié)中的等價類集合.

　　1.2　MIE-RS的理論基礎

　　令Yk U表示U中某一決策類(概念),k表示其決策類別是第k類.定義1:決策類Yk U的核定義為:Core〔k〕={a: CYk ≠ C-{a}Yk },即核Core〔k〕中屬性對決策類Yk而言是不可缺少的,否則會導致Yk中某些原可正確分類的例子現(xiàn)在不能被正確分類.定義2:屬性集P C是決策類Yk的一個覆蓋,當且僅當 PYk = CYk ,并且對 P’ P, P’Yk ( CYk .這說明若P是決策類Yk的一個覆蓋,則P具有與C同樣的區(qū)分決策類Yk的能力.因此可用P代替C來產(chǎn)生Yk的分類規(guī)則,這時規(guī)則的條件部分具有最小描述長度.按如下原則生成決策類Yk的分類規(guī)則:令E表示P*中的等價類,Des(E)表示對等價類E的描述,即等價類E對應的各條件屬性的特定取值;Des(Yk)表示對決策類Yk的描述,即第k類對應的各決策屬性的特定取值.則對每個E∈PYk建立如下的決策規(guī)則:r: Des(E)→Des(Yk)對于不一致例子集,給定分類正確標準α,令CαYk中的每個例子的決策類別都是第k類,即把CαYk中那些原來決策類別不是第k類的例子改為第k類,形成新的該決策類(第k類)的集合Y’k Yk,此時CαYk=CY’k(.再按上述方法求Y’k的覆蓋P,對每個E∈PY’k建立如下的決策規(guī)則:r’: Des(E)→Des(Yk)定理1:規(guī)則r’的可信度大于等于α.證明: E∈P Y’k,因為P Y’k=C Y’k,P C,所以PY’k中的等價類E是C Y’k中的一個或多個等價類Ei的并集,記作,E=YiEi,Ei∈C Y’k.又因為CαYk=CαY’k,即Ei∈CαYk,則有: Ei∩Yk ≥α Ei (1)　規(guī)則r’的可信度:cf= E∩Yk / E = (YiEi)∩Yk / YiEi = YiEiI Yk / YiEi =∑i Ei∩Yk /∑i Ei 由(1)式,cf ∑iα Ei /∑i Ei =α.得證.

　　2、MIE-RS的設計與實現(xiàn)

　　2.1　算法設計

　　MIE-RS算法:輸入:非一致的例子集U,分類正確標準α.輸出:滿足α的簡化的分類規(guī)則集.(1)用戶選擇待挖掘的條件屬性集C和決策屬性集D.(2)計算U關于C和D的等價類C*和D*.對U中每個決策類Yk∈D*,修改使CαYk中的每個例子的決策類別都是第k類.經(jīng)此操作后有些決策類集合Yk發(fā)生了改變.(3)計算每個決策類Yk的核屬性集Core〔k〕.(3.1)計算每個決策類Yk關于條件屬性集C的下近似集合CYk中的元素個數(shù)LANum(C,k);(3.2) Core〔k〕= ;(3.3) for each a∈C do{計算每個決策類Yk關于C-{a}的下近似集合中的元素個數(shù)LANum(C-{a},k);if (LANum(C-{a},k)! =LANum(C,k))　　Core〔k〕=Core〔k〕+{a};}(4)對每個決策類Yk,計算Yk的覆蓋,生成Yk的分類規(guī)則.(4.1) for each Ykdo {(4.2)用戶選擇感興趣的屬性集合Interest;(4.3) Candidates =C-Core〔k〕-Interest;(4.4) P =Core〔k〕+Interest;(4.5)計算LANum(P,k);(4.6)while(LANum(P,k)! =LANum(C,k)){　　for each a∈Candidates do　　　　計算LANum(P+{a},k);　　選取屬性b,使LANum(P+,k)值最大;　　P=P+;　　Candidates=Candidates-;}(4.7) for each a∈P do　　if(a不在Core〔k〕+Interest中)　　{　　　P=P-{a};　　　計算LANum(P,k);　　　if (LANum(P,k)! =LANum(C,k))　　　　P=P+{a};　　}(4.8) for each E∈PYkdo　　生成Yk的決策規(guī)則;}

　　2.2　用Hash表實現(xiàn)算法

　　在上述算法中,求等價類(進而求下近似集合)是個最基本的操作,提高該操作的效率是個關鍵問題.容易看出,直接求某屬性集的等價類的時間復雜度為O(n2).若采用本文的Hash表方法求等價類,可將時間復雜度降為O(n).另外,本文提出的方法,不需要具體求出各個等價類集合,而是直接求出各個下近似集合中的元素個數(shù),從而避免了頻繁進行集合的交運算,提高了效率.首先對例子集U進行預處理.設用戶選擇了條件屬性集C和決策屬性集D.將用戶選擇的每個屬性j的各值轉(zhuǎn)換為從0開始的整數(shù),生成轉(zhuǎn)換表T.屬性j的不同值的個數(shù)cnt〔j〕等于轉(zhuǎn)換后該屬性具有的最大整數(shù)值加1.j=1,2,..., C + D .如3.4節(jié)例子所示.任給條件屬性集C和決策屬性集D,建立并初始化Hash表E及EandY.E的大小為cnt〔1〕*cnt〔2〕*...*cnt〔 C 〕.EandY大小為cnt〔1〕*cnt〔2〕*...*cnt〔 C 〕*cnt〔 C +1〕*...*cnt〔 C + D 〕.Hash表中的每個存儲單元初始化為0.對表T中每個記錄r,用a(i)表示記錄r第i個屬性的值,構(gòu)造如下兩個Hash函數(shù):H1(r)=(((a(1)*cnt〔1〕+a(2))*cnt〔2〕+a(3))*cnt〔3〕+...)*cnt〔 C -1〕+a( C )H2(r)=(( H1(r)*cnt〔 C 〕+a( C +1))*cnt〔 C +1〕+...)*cnt〔 C + D -1〕+a( C + D )

　　利用Hash表,我們采用如下方法求每個決策類Yk關于某屬性集C的下近似集合CYk中的元素個數(shù)LANum(C,k).(1)掃描一遍轉(zhuǎn)換表T,對每個記錄r,按照計算出的Hash地址H1(r)和H2(r),把相應的兩個存儲單元的值各加上1.掃描完成后,T關于屬性集C的任一等價類(設記錄r為其任一代表元)中元素的個數(shù)就存放在Hash表E的相應位置(H1(r))中;同理,表T關于屬性集C∪D的任一等價類(設記錄r為其任一代表元)中元素的個數(shù)就存放在Hash表EandY的相應位置(H2(r))中.(2)再一次掃描表T,對每個記錄r,設其類別為第k類,計算Hash地址H1(r)和H2(r),取出相應存儲單元的值進行比較,若E〔H1(r)〕=EandY〔H2(r)〕,說明記錄r屬于CYk,則LANum(C,k)=www.51lunwen.com/database/ LANum(C,k)+1.容易看出,計算LANum(C,k)只需掃描表T兩遍,設 T =n,則時間復雜度為O(n).

　　2.3算法分析

　　令 U =n , C + D =m1+m2=m,決策類別個數(shù)為d.對MIE-RS算法采用Hash方法實現(xiàn),各步驟的時間復雜性分析如下:首先,對每個屬性進行預處理所需時間為O(m*n(n-1)/2)=O(mn2).其中n(n-1)/2=0+1+...+(n-1)為查找比較次數(shù).步驟(2)是對不一致例子的處理過程.有了Hash表E和EandY,對表中每條記錄r,設其屬于第k類,若EandY〔H2(r)〕≠E〔H1(r)〕且EandY〔H2(r)〕/E〔H1(r)〕≥α,則記錄r所在的關于C的等價類〔r〕C∈CαYk,根據(jù)2.2節(jié),對表中任一記錄r’,若H1(r’)=H1(r),但EandY〔H2(r’)〕/E〔H1(r’)〕<α,則在表T中將記錄r’的決策類別改為第k類.此步驟在最壞情況下的時間復雜度不超過O(n2).對步驟(3),由3.2節(jié)的分析可知,(3.1)的復雜度為O(n),(3.3)的復雜度為O(m1n)

　　3、結(jié)語

　　對于基于粗集的數(shù)據(jù)挖掘算法,目前也有一些研究〔3,4〕.本文提出了一個新的從不一致例子中挖掘規(guī)則的粗集方法MIE-RS.MIE-RS的特點在于:一是有效地統(tǒng)一處理了一致和不一致的例子,生成滿足給定可信度的可能性規(guī)則;二是將求所有例子的覆蓋化為求各個決策類的覆蓋,使挖掘出的規(guī)則更簡單;三是巧妙構(gòu)造了Hash函數(shù)來實現(xiàn)算法,大大降低了算法的時間復雜度.我們在自行研制開發(fā)的數(shù)據(jù)挖掘服務器中實現(xiàn)了MIE-RS,并用多個實際數(shù)據(jù)集進行了測試,效果良好,挖掘出來的規(guī)則簡單、實用.

　　參考文獻：

　　1 Z. Pawlak. Rough sets. Int. J〔J〕.Computer and InformationScience, 1982,Vol 11,No5,341～356.

　　2 W. Ziarko. Variable precision rough set model〔J〕. Journal ofComputer and System Sciences. 1993.46,39～59.

　　3 Chien-Chung Chan, Jerzy W. www.51lunwen.com/database/ Grzymala-Busse. On the lowerboundaries in learning rules from examples〔A〕. In IncompleteInformation. Rough Set Analysis ,Chapter 2, 1998, 58～74.

　　4 Xiaohua Hu. Knowledge discovery in databases: an attribute-oriented rough set approach〔D〕. Ph. D Thesis, in ComputerScience, University of Regina, Canada. June,1995.