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

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

　　1、方法原理

　　1.1　粗集基本理論

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

　　1.2　MIE-RS的理論基礎(chǔ)

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

　　2.1　算法設(shè)計(jì)

　　MIE-RS算法:輸入:非一致的例子集U,分類正確標(biāo)準(zhǔn)α.輸出:滿足α的簡化的分類規(guī)則集.(1)用戶選擇待挖掘的條件屬性集C和決策屬性集D.(2)計(jì)算U關(guān)于C和D的等價(jià)類C*和D*.對U中每個(gè)決策類Yk∈D*,修改使CαYk中的每個(gè)例子的決策類別都是第k類.經(jīng)此操作后有些決策類集合Yk發(fā)生了改變.(3)計(jì)算每個(gè)決策類Yk的核屬性集Core〔k〕.(3.1)計(jì)算每個(gè)決策類Yk關(guān)于條件屬性集C的下近似集合CYk中的元素個(gè)數(shù)LANum(C,k);(3.2) Core〔k〕= ;(3.3) for each a∈C do{計(jì)算每個(gè)決策類Yk關(guān)于C-{a}的下近似集合中的元素個(gè)數(shù)LANum(C-{a},k);if (LANum(C-{a},k)! =LANum(C,k))　　Core〔k〕=Core〔k〕+{a};}(4)對每個(gè)決策類Yk,計(jì)算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)計(jì)算LANum(P,k);(4.6)while(LANum(P,k)! =LANum(C,k)){　　for each a∈Candidates do　　　　計(jì)算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};　　　計(jì)算LANum(P,k);　　　if (LANum(P,k)! =LANum(C,k))　　　　P=P+{a};　　}(4.8) for each E∈PYkdo　　生成Yk的決策規(guī)則;}

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

　　在上述算法中,求等價(jià)類(進(jìn)而求下近似集合)是個(gè)最基本的操作,提高該操作的效率是個(gè)關(guān)鍵問題.容易看出,直接求某屬性集的等價(jià)類的時(shí)間復(fù)雜度為O(n2).若采用本文的Hash表方法求等價(jià)類,可將時(shí)間復(fù)雜度降為O(n).另外,本文提出的方法,不需要具體求出各個(gè)等價(jià)類集合,而是直接求出各個(gè)下近似集合中的元素個(gè)數(shù),從而避免了頻繁進(jìn)行集合的交運(yùn)算,提高了效率.首先對例子集U進(jìn)行預(yù)處理.設(shè)用戶選擇了條件屬性集C和決策屬性集D.將用戶選擇的每個(gè)屬性j的各值轉(zhuǎn)換為從0開始的整數(shù),生成轉(zhuǎn)換表T.屬性j的不同值的個(gè)數(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表中的每個(gè)存儲(chǔ)單元初始化為0.對表T中每個(gè)記錄r,用a(i)表示記錄r第i個(gè)屬性的值,構(gòu)造如下兩個(gè)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表,我們采用如下方法求每個(gè)決策類Yk關(guān)于某屬性集C的下近似集合CYk中的元素個(gè)數(shù)LANum(C,k).(1)掃描一遍轉(zhuǎn)換表T,對每個(gè)記錄r,按照計(jì)算出的Hash地址H1(r)和H2(r),把相應(yīng)的兩個(gè)存儲(chǔ)單元的值各加上1.掃描完成后,T關(guān)于屬性集C的任一等價(jià)類(設(shè)記錄r為其任一代表元)中元素的個(gè)數(shù)就存放在Hash表E的相應(yīng)位置(H1(r))中;同理,表T關(guān)于屬性集C∪D的任一等價(jià)類(設(shè)記錄r為其任一代表元)中元素的個(gè)數(shù)就存放在Hash表EandY的相應(yīng)位置(H2(r))中.(2)再一次掃描表T,對每個(gè)記錄r,設(shè)其類別為第k類,計(jì)算Hash地址H1(r)和H2(r),取出相應(yīng)存儲(chǔ)單元的值進(jìn)行比較,若E〔H1(r)〕=EandY〔H2(r)〕,說明記錄r屬于CYk,則LANum(C,k)=www.51lunwen.com/database/ LANum(C,k)+1.容易看出,計(jì)算LANum(C,k)只需掃描表T兩遍,設(shè) T =n,則時(shí)間復(fù)雜度為O(n).

　　2.3算法分析

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

　　3、結(jié)語

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

　　參考文獻(xiàn)：

　　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.