亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于粗糙集方法的決策樹多值偏向理論分析

        2014-12-02 14:14:50
        關(guān)鍵詞:偏向粗糙集信息熵

        (浙江工業(yè)大學(xué)信息工程學(xué)院,浙江 杭州310023)

        0 引 言

        決策樹方法是最受歡迎的數(shù)據(jù)挖掘技術(shù)之一,主要用于分類和預(yù)測(cè)。學(xué)者提出了著名的ID3 決策樹分類方法[1]。然而實(shí)驗(yàn)表明ID3算法在構(gòu)造決策樹時(shí)有多值偏向的問(wèn)題,以往大多數(shù)的學(xué)者都是通過(guò)實(shí)驗(yàn)研究多值偏向問(wèn)題[2-5]。有學(xué)者首次提出一種理論分析多值偏向問(wèn)題的方法[6]。然而文獻(xiàn)[6]在分析多值偏向問(wèn)題時(shí),理論的嚴(yán)密性及邏輯性不強(qiáng),缺少實(shí)例驗(yàn)證。本文在文獻(xiàn)[6]基礎(chǔ)上,針對(duì)其不足,基于粗糙集理論引入屬性重要度概念,從理論上分析了屬性多值對(duì)信息熵的影響和屬性多值對(duì)其他屬性的重要性程度的影響兩個(gè)問(wèn)題。最后通過(guò)實(shí)驗(yàn)表明理論分析方法的正確性與可行性。

        1 ID3算法及粗糙集理論

        1.1 ID3算法

        算法的主要思想[7]:已知數(shù)據(jù)樣本集S,樣本個(gè)數(shù)s,樣本所屬類別集合為C,設(shè)共有m個(gè){c1,c2,…,cm-1,cm},把S 分為m個(gè)樣本子集為S={S1,S2,…,Sm-1,Sm},樣本集Si中樣本的個(gè)數(shù)為si。樣本集的信息熵表示為:

        設(shè)樣本集集合S 中某個(gè)屬性為A,A 有n個(gè)不同的屬性值{a1,a2,…,an-1,an}?;贏的屬性值把S劃分為n個(gè)樣本子集:S={S1,S2,…,Sn-1,Sn},sij表示為Sj(j=1,2,…,n)中屬于類ci(i=1,2,…,m)的個(gè)數(shù),pij表示為樣本子集Sj中樣本屬于有類ci的概率:

        子集Sj的信息熵為:

        根據(jù)屬性A 劃分后的樣本集合的信息熵為:

        信息增益:

        選擇屬性對(duì)結(jié)點(diǎn)進(jìn)行劃分的標(biāo)準(zhǔn)就是選取信息增益最大的屬性。

        1.2 粗糙集理論及屬性重要度

        定義1 在信息表S中,對(duì)于屬性集I?A,可構(gòu)成對(duì)應(yīng)的二元等價(jià)關(guān)系:

        式中,f(x)表示對(duì)象x 在屬性I 上的屬性值,稱為由I 構(gòu)成的不可分辨關(guān)系。

        定義2 設(shè)X?U,A為屬性集合,X的A的下近似的定義:

        式中,U/IND(A)表示對(duì)象集合關(guān)于屬性集合A的等價(jià)類集合。表示一定屬于X的對(duì)象集合。X的A的上近似的定義為:

        定義3 在信息表中,存在屬性集P,Q?A,定義Q的P 正域表示為:

        定義4 在信息表中,存在屬性集R?C,定義D 依賴于R的程度為:

        定義5 存在屬性集R?C 及屬性r∈R,定義屬性重要性度為:

        式中,Card(POSR(D))表示集合的基數(shù),屬性重要度表示屬性r 在條件屬性集R 中對(duì)樣本分類的重要性程度。其中D為決策屬性。

        2 多值偏向及屬性重要度分析

        設(shè)A是樣本集的某個(gè)屬性,具有n個(gè)屬性{A1,A2,…,An-1,An},該屬性把樣本集合S劃分為S ={S1,S2,…,Sn-1,Sn}。現(xiàn)在把屬性值為An的樣本隨機(jī)的分拆為屬性值分別為A'n,A'n+1的樣本子集,與A1,A2,…,An-1構(gòu)成新的屬性A',A'有n+1個(gè)屬性值:{A1,A2,…,An-1,A'n,An},A'把樣本集S劃分為S={S1,S2,…,Sn-1,S'n,Sn+1}。

        2.1 算法多值偏向理論分析

        思路:比較分裂前后屬性A的信息熵大小及重要度,即Gain(S/A')和Gain(S/A)的大小及與I(A)的大小。

        1)由粗糙集理論可知:

        2)為方便計(jì)算,用p(ci/Aj)=pij,即表示屬性值等于Aj時(shí)樣本集屬于C =ci的概率。用p(Aj)表示屬性值為Aj時(shí)樣本子集的權(quán)值。比較Gain(S/A')與Gain(S/A)的大小。

        對(duì)上式等式兩邊同除以p(An),得:

        由式(12)、(15)得:I(A')=I(A) Gain(S/A')≥Gain(S/A),證明完畢。

        2.2 屬性多值對(duì)其它屬性重要度的影響

        假設(shè)屬性集為{A,B,C},拆分屬性A的一個(gè)屬性值,然后計(jì)算屬性C的重要性程度。

        式(17)、(18)中,Xn=X'n∪Xn+1。

        式中,Xi屬于U/IND(A),Yj屬于U/IND(B)。

        式中,Xi屬于U/IND(A'),Yj屬于U/IND(B)。

        式(19)、(20)中,Zi=Z'i(i=1,…,(n-1)m),Znm=Z'(n-1)m∪Z'(n-1)m+1∪…∪Z'(n+1)m。{A,B,C}及{A',B,C}中C的重要度分別為I(C,{ABC},D)其中,Card(POSABC(D))=Card(POSA'BC(D)),所以只需決策樹要比較Card(POSAB(D))與Card(POSA'B(D))的大小。

        比較式(21)、(22),得到Card(POSAB(D))≤Card(POSA'B(D)),最終得到I(C,{ABC},D)≥I'(C,{A'BC},D)。證明了屬性集合中的某屬性的增加屬性降低其他屬性的屬性重要性程度。

        3 實(shí)例

        以下實(shí)例是判斷氣候各個(gè)因素是否適合外出旅游,如表1所示。

        設(shè)U為全體樣本,Q=scsamyg,P={a1,a2,a3,a4}為條件屬性集集合。

        這里只計(jì)算屬性a1熵與a4的重要性屬性,拆分a5=rain的屬性值,形成新的屬性a'1,計(jì)算a1分裂前后a1的信息增益,得Gain(U/a1)=0.246,Gain(U/a1')=0.298。計(jì)算a1分裂前后的屬性a4重要度為:I(a4)=0.286,I(a4)' =0.143。實(shí)驗(yàn)結(jié)果驗(yàn)證了理論分析的正確性。

        表1 氣候因素表

        4 結(jié)束語(yǔ)

        本文從理論的角度分析了決策樹ID3算法的多值偏向問(wèn)題?;诖植诩碚?,引入屬性重要度,證明了屬性在增加屬性值的時(shí)候,屬性信息熵增加,但是該屬性的屬性重要度沒(méi)有增加。本文最后還分析了屬性增加屬性值對(duì)其他屬性重要度的影響。本文的不足之處是沒(méi)有提出克服決策樹ID3 多值偏向的方法,下一步工作重點(diǎn)是修正決策樹ID3算法的多值偏向問(wèn)題。

        [1]Quinlan J R.Induction of Decision Tree[J].Machine Learning,1986,(1):81-106.

        [2]劉小虎,李生.決策樹的優(yōu)化算法[J].軟件學(xué)報(bào),1998,9(10):797-800.

        [3]胡學(xué)鋼,張冬艷.基于粗糙集的混合變量決策樹構(gòu)造算法研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,30(3):257-260.

        [4]朱顥東.ID3算法的改進(jìn)和簡(jiǎn)化[J].上海交通大學(xué)學(xué)報(bào),2010,44(7):883-886.

        [5]張琳,陳燕,李桃迎,等.決策樹分類算法研究[J].計(jì)算機(jī)工程,2011,37(13):66-67.

        [6]韓松來(lái),張輝,周華平.決策樹算法中多值偏向問(wèn)題的理論分析[C].北京:中國(guó)金屬學(xué)會(huì),2005:133-140.

        [7]Ding Baoshi,Zheng Yongqing,Zhang Shaoyu.A New Decision Tree Algorithm Based on Rough Set Theory[C].Wuhan:Asia-Pacific Conference on Information Processing,2009:326-329.

        猜你喜歡
        偏向粗糙集信息熵
        基于信息熵可信度的測(cè)試點(diǎn)選擇方法研究
        8~12歲兒童抑郁與認(rèn)知重評(píng)的關(guān)系:悲傷面孔注意偏向的中介作用*
        基于Pawlak粗糙集模型的集合運(yùn)算關(guān)系
        “偏向”不是好導(dǎo)向
        考核偏向:錯(cuò)把經(jīng)過(guò)當(dāng)結(jié)果
        基于信息熵的實(shí)驗(yàn)教學(xué)量化研究
        一種基于信息熵的雷達(dá)動(dòng)態(tài)自適應(yīng)選擇跟蹤方法
        多粒化粗糙集性質(zhì)的幾個(gè)充分條件
        雙論域粗糙集在故障診斷中的應(yīng)用
        基于信息熵的IITFN多屬性決策方法
        久久99精品久久只有精品| 欧美色欧美亚洲另类二区不卡| 国产伦精品一区二区三区四区| 日本岛国视频在线观看一区二区| 国产亚洲精品色婷婷97久久久| 国产精品久久久国产盗摄| 日韩毛片基地一区二区三区| 性无码国产一区在线观看| 亚洲视频在线观看第一页| 曰本女人与公拘交酡| 亚洲精品自产拍在线观看| 永久免费毛片在线播放| 亚洲中文字幕精品久久a| 真实国产精品vr专区| av大片在线无码免费| 91精品国产综合久久青草| 久久精品国产亚洲av久按摩| 日本一本之道高清不卡免费| 国产精品第一二三区久久蜜芽| 久久精品中文字幕亚洲| 99精品国产一区二区三区| 中文字幕丰满伦子无码| 亚州精品无码久久aV字幕| 白白色青青草视频免费观看| 激情综合婷婷色五月蜜桃 | 亚洲欧洲无码一区二区三区| 激情 一区二区| 三级国产高清在线观看| 国产精品www夜色视频| 亚洲男人精品| 日本一二三区在线视频观看| 亚洲va中文字幕无码一二三区 | 中文字幕人妻伦伦| 男女边吃奶边做边爱视频| 日韩美女av二区三区四区| 亚洲色图视频在线免费看| 久久露脸国产精品| 在线亚洲AV不卡一区二区| 午夜视频一区二区三区播放| 欧美乱人伦人妻中文字幕| 亚洲AV毛片无码成人区httP|