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

        ?

        基于選擇度的分類規(guī)則學習算法

        2014-12-02 01:11:50何田中周忠眉黃再祥
        計算機工程 2014年8期
        關鍵詞:剪枝信息熵度量

        何田中,周忠眉,黃再祥

        (閩南師范大學計算機科學與工程系,福建 漳州 363000)

        1 概述

        分類技術一直是數(shù)據挖掘技術中研究的熱點之一,近年來提出了各種不同的分類技術,如:將近似求導引入分類[1],使用最近鄰進行分類[2]等。為了提高不平衡數(shù)據集分類準確率,文獻[3]使用KNN技術,文獻[4]提出基于Boosting 技術。規(guī)則式分類一直是分類技術的重要方法之一,近年來也提出了許多規(guī)則式分類技術,如:基于DE/QDE 算法技術[5],具有多標準分類技術[6],分層模糊化規(guī)則分類技術[7],進化的規(guī)則式系統(tǒng)[8]等。規(guī)則式分類具有分類速度快特點,因此規(guī)則式分類技術也得到了較為廣泛的應用,如:肺癌評估[9],預測蛋白質相互作用類型[10]等。規(guī)則式分類技術抽取一條新規(guī)則時,使用某種度量獲取“最好”屬性值添加到當前規(guī)則中。如ID3、C4.5[11]算法分別使用信息熵及信息增益來選擇“最好”屬性,信息熵及信息增益都是單一度量,使用它們度量屬性時存在很多度量值相等的“最好”屬性,導致上述算法很難選擇出真正的“最好”屬性。FOIL[12]算法使用FOIL 增益來度量,F(xiàn)OIL增益是支持數(shù)與相關度的乘積。當支持數(shù)較大時,相關度幾乎不起任何作用,使用FOIL 增益也不能選擇出“最好”的屬性值。

        規(guī)則式分類技術抽取一條新規(guī)則時,不斷選擇出“好”屬性值添加到規(guī)則中,直到該規(guī)則置信度100%為止,然后抽取下一條規(guī)則。這種學習方法容易導致過度學習,規(guī)則的支持度小、質量不高,并且使規(guī)則抽取更為耗時。如在ID3 算法中,當節(jié)點包含的實例為同一類時,分枝結束;此時的規(guī)則置信度為100%。FOIL 算法不斷地選擇“好”屬性值添加到當前規(guī)則中,直到該規(guī)則不包含負實例為止,規(guī)則的置信度也是100%。

        為了解決上述問題,本文提出了基于選擇度的分類規(guī)則學習算法LRSM,該算法具有以下特點:

        (1)使用一個新的屬性值度量方法——屬性值的選擇度,屬性值的選擇度是屬性值的信息熵、類的支持度及偏離度的綜合。由于選擇度是3 種度量的綜合,用它度量屬性值時,度量值相等“最好”屬性值的數(shù)量將大大減少。另外,選擇度包含偏離度,偏離度能夠衡量屬性值偏向某一類屬性值的程度。因此,選擇度不但能度量屬性值的好壞,而且還能夠反映出其偏向某一類屬性值的程度。

        (2)LRSM 算法使用基于負實例數(shù)進行剪枝(NIP),即當規(guī)則覆蓋的負實例數(shù)小于特定值時,LRSM 算法結束該規(guī)則抽取,進行下一條規(guī)則抽取過程;這種方法克服了FOIL 等零負實例的學習方法帶來的過度擬合的問題,提高規(guī)則的支持度及質量,分類準確率得到較大的提高,同時也大大減少抽取規(guī)則時間。

        2 屬性值的選擇度

        設T 為元組集合,其屬性為A1,A2,…,Am及類屬性C={c1,c2,…,ck},每一元組{a1,a2,…,am,c}稱謂實例,其中,ai是屬性Ai;c 是類屬性C 的值。實例{a1,a2,…,am,cp}稱為正實例,而實例{a1,a2,…,am,cq},其中,q≠p 則稱謂負實例。

        定義1 屬性值ai的信息熵:

        其中,pj=mj/mai,m為包含屬性值的實例數(shù),mj為包含屬性值ai,且類值為cj的實例數(shù)。

        屬性值的信息熵能夠度量出屬性值所包含信息量大小,但不能夠反映出該信息量更偏向哪個類屬性值。數(shù)據集D 如表1 所示。

        表1 數(shù)據集D

        屬性值(A,1)的信息熵E((A,1))=0.918 3,其包含的實例如表2 所示。

        表2 屬性值(A,1)包含的實例

        從表2 可以看出,屬性值(A,1)包含的實例中,屬于類(C,1)的實例數(shù)比類(C,0)要少;但無法從信息熵看出屬性值(A,1)更偏向類(C,0)。為了克服信息熵的這種缺點,本文提出了屬性值的偏向熵。

        定義2 屬性值ai對類cj的偏向熵:

        其中,m為包含屬性值ai的實例數(shù);mcj為包含屬性值ai,且類值為cj的實例數(shù)。

        按照定義2 屬性值(A,1)對類(C,0)及類(C,1)的偏向熵分別為:

        可以看出,屬性值(A,1)更偏向于類(C,0)與實際情況一致。

        定義3 屬性值ai對類cj的偏離度:

        其中,k 為類值個數(shù);mc為包含屬性值ai,且類值為c的實例數(shù);Mc為類值為c 的實例數(shù)。

        定義4 屬性值ai對類cj的選擇度:

        從定義4 可以看出,選擇度是偏向熵與偏離度的綜合,而偏向熵綜合了熵與類的支持度,即選擇度是熵、類支持度及偏離度3 種度量的綜合;屬性值度量值相同的機會較少,更易選擇出“好”屬性值,實驗結果表明,使用選擇度來度量屬性值具有更高的準確率。

        3 基于選擇度的分類規(guī)則學習算法LRSM

        LRSM 算法具有以下特點:(1)使用選擇度來度量屬性值,具有相同度量值的“最好”屬性值的數(shù)量大大減少,能更好地選擇出“好”屬性值;(2)LRSM算法使用基于負實例數(shù)進行剪枝,因此抽取的規(guī)則的置信度小于100%,從而避免了過度學習,提高規(guī)則的支持度。對于訓練集的每一個類屬性值,LRSM算法依次把屬于該類的所有實例作為正實例集,屬于其他類的實例作為負實例集,然后抽取屬于正實例集類的規(guī)則。抽取正實例集類規(guī)則時,LRSM 算法不斷使用選擇度來選擇“最好”屬性值添加到當前規(guī)則中,當該規(guī)則覆蓋的負實例數(shù)小于給域值時,規(guī)則抽取結束,刪除該規(guī)則覆蓋的正實例,再進行下一條規(guī)則抽取。因此,LRSM 算法具有較高準確率,且規(guī)則提取耗時更少的優(yōu)點。

        LRSM 算法具體描述如下:

        輸入 數(shù)據集D

        輸出 一組規(guī)則集RS

        (1)對數(shù)據集D 中的每一類標c 值循環(huán)。

        (2)將D 分成正實例集PS 及負實例集NS,其中,PS 為類標值為c 實例,其余的組成NS。

        (3)抽取規(guī)則rs=mineRule(PS,NS),并添加到RS 中。

        mineRule(PS,NS)過程描述如下:

        1)規(guī)則集rs←Φ;

        2)正實例數(shù)n←|PS|;

        3)max_rule_length←屬性個數(shù);

        4)WHILE n >0

        5) NS'←NS,PS'←PS;

        6) 規(guī)則r←Φ;

        7) 當前負實例數(shù)m←|NS'|;

        8) 最小負實例數(shù)δ←m×α

        9) WHILE(m >δ AND 規(guī)則r 長度<max_rule_length)

        10) 根據PS' 及NS 計算所有屬性值的選擇度,并返回選擇度最大的屬性值av;

        11) 將av 添加到規(guī)則r 中;

        12) 從PS'、NS'移除不滿足規(guī)則r 的實例;

        13)m←|NS'|

        14) END

        15) 規(guī)則r 添加到規(guī)則集rs 中;

        16) 從PS'移除滿足規(guī)則r 的實例;

        17) n←|PS'|

        18)END

        19)返回規(guī)則集rs

        LRSM 使用選擇度選擇“好”的屬性值;由于選擇度是3 種度量綜合,因此屬性值具有相同度量值機會大大減少,更容易選擇“好”的屬性值;另外,當負實例數(shù)小于最小負實例數(shù)δ,規(guī)則提取提前結束,因此規(guī)則抽取耗時更少,支持度更高。

        以下通過一個例子說明LRSM 主要思想:數(shù)據集如表3 所示,以正實例為類屬性值(C,1),負實例數(shù)域值為δ=2 為例進行說明。

        表3 數(shù)據集

        此時,正實例集為:PS={X1,X2,X3,X7},負實例集為:NS={X4,X5,X6,X8}。

        提取第一條規(guī)則,PS'=PS,NS'=NS;空規(guī)則為:null→(c,1)。

        計算屬性值的偏向信息熵、偏離度及選擇度如表4 所示。

        表4 屬性值的偏離度、偏向熵及選擇度

        由表4 可知,屬性值(A1,1)選擇度最大,將(A1,1)添加到規(guī)則中得:(A1,1)→(C,1)。

        從PS'、NS'中刪除滿足規(guī)則前件的正、負實例得:PS'={X3,X7},負實例集為:NS'={X8}。

        從PS 中刪除滿足規(guī)則的實例,此時,正實例集為:PS={X1,X2},負實例集為:NS={X4,X5,X6,X8}。由于正實例數(shù)不為零,繼續(xù)下一條規(guī)則抽取,過程同上,正類(C,1)的規(guī)則集為:(A1,1)→(C,1),(A3,2)→(C,1)。

        4 分類規(guī)則學習算法LRSM 的測試

        在進行測試之前,先計算出所有規(guī)則強度RS。測試每一實例時,如果該實例匹配的規(guī)則集的類屬性值相同,且該實例的類屬性值與規(guī)則集類屬性值一致,測試正確;若匹配的規(guī)則集類屬性值不同,將這些規(guī)則集按類屬性值分組,計算規(guī)則集R 的平均強度ARS(R),如果該實例的類屬性值與最高平均強度的規(guī)則集類屬性值一致,測試正確。

        計算規(guī)則強度定義如下:

        其中,nc為滿足規(guī)則實例數(shù);l(r)為規(guī)則r 的拉普拉斯值[13]。

        規(guī)則集R 的平均強度定義如下:

        其中,n 為規(guī)則集R 中規(guī)則數(shù)。

        5 實驗結果與分析

        所有的實驗都是PC 機上進行,其中,CPU 為3.1 GHz、內存4 GB、操作系統(tǒng)為Windows XP;實驗數(shù)據來源于UCI 機器學習庫。為了驗證選擇度及LRSM 算法的準確性及耗時,分別設計以下3 組與FOIL 對照的實驗。

        在第1 組實驗中,用實驗測試本文中屬性值的度量選擇度有效性。在FOIL 算法中,分別使用FOIL 增益及選擇度來選擇“好”屬性,表5 實驗結果表明,選擇度度量平均準確率比FOIL 增益高,尤其在數(shù)據集lymph、monks 和breast 有較大的提高。

        表5 FOIL 增益及選擇度的準確率對比

        在第2 組實驗中,為驗證基于負實例數(shù)提前剪枝(NIP)的有效性,在FOIL 算法中使用基于NIP 剪枝與不使用NIP 剪枝,表6 結果表明,使用提前剪枝能使規(guī)則的支持度更高,規(guī)則質量更好。因此,基于負實例數(shù)提前剪枝能較大地提高分類準確率。

        表6 使用NIP 剪枝與不剪枝的準確率對比

        在第3 組實驗中,用實驗測試LRSM 算法的準確率及效率,使用LRSM 算法與FOIL 算法進行實驗,由于LRSM 算法使用提前剪枝且使用選擇度度量,表7 實驗結果表明,與FOIL 算法相比,LRSM 算法訓練耗時減少近一個數(shù)量級,而平均準確率提高了近3 個百分點。

        表7 FOIL 算法與LRSM 算法的準確率及耗時對比

        從上述3 組實驗可以得出如下結論:

        (1)三度量結合的選擇度比兩度量結合FOIL增益,更易選擇出“好”屬性值,分類準確率更高;

        (2)使用基于負實例數(shù)提前剪枝(NIP)不但能提高分類準確率,而且能大大縮短提取規(guī)則的時間。

        6 結束語

        通常屬性值的度量采用單度量如信息增益,或2 種度量結合如FOIL 增益。不管是單度量還是2 種度量結合,仍然會存在若干不同屬性值的度量值相同,從而較難選擇出“好”的屬性值。本文提出一種三度量結合的度量選擇度,使用選擇度度量屬性值時,不同屬性值具有相同的度量值大大減少,因此更容易地找出“好”屬性值。此外,本文提出基于選擇度的規(guī)則學習算法LRSM。在LRSM 算法中,使用選擇度,及基于負實例數(shù)提前剪枝。用基于負實例數(shù)提前剪枝方法能提取到的規(guī)則支持度更高、質量更好且耗時更少。實驗結果表明,LRSM 算法減少了訓練時間,且提高了分類準確率。

        [1]劉建偉,李雙成,羅雄麟.基于非近似求導過程的加更新和乘更新分類算法[J].計算機學報,2013,36(2):327-340.

        [2]鐘 智,朱曼龍,張 晨,等.最近鄰分類方法的研究[J].計算機科學與探索,2011,5(5):467-473.

        [3]王超學,潘正茂,馬春森,等.改進型加權KNN 算法的不平衡數(shù)據集分類[J].計算機工程,2012,38(20):160-163.

        [4]李秋潔,茅耀斌,王執(zhí)銓.基于Boosting 的不平衡數(shù)據分類算法研究[J].計算機科學,2011,38 (12):224-228.

        [5]Su Haijun,Yang Yupu,Zhao Liang.Classification Rule Discovery with DE/QDE Algorithm[J].Expert Systems with Applications,2010,37(2):1216-1222.

        [6]Rezaei J,Dowlatshahi S.A Rule-based Multi-criteria Approach to Inventory Classification[J].International Journal of Production Research,2010,48 (23):7107-7126.

        [7]Fernández A,del Jesus M J,Herrera F.Hierarchical Fuzzy Rule Based Classification Systems with Genetic Rule Selection for Imbalanced Data-sets[J].International Journal of Approximate Reasoning,2009,50 (3):561-577.

        [8]Orriols-Puig A,Bernadó-Mansilla E.Evolutionary Rulebased Systems for Imbalanced Data Sets [J].Soft Computing,2009,13(3):213-225.

        [9]Anthony N N,Michael J L.Symbolic Rule-based Classification of Lung Cancer Stages from Free-text Pathology Reports[J].Journal of the American Medical Informatics Association,2010,17(4):440-445.

        [10]Sung H P,José A R.Prediction ofProtein-protein Interaction Types Using Association Rule Based Classification[J].BMC Bioinformatics,2009,10(1):36.

        [11]Quinlan J R.C4.5:Programs for Machine Learning[M].Vol.1.San Francisco,USA:Morgan Kaufmann,1993.

        [12]Quinlan J R,Cameron-Jones R M.FOIL:A Midterm Report[C]//Proc.of ECML'93.Vienna,Austria:Springer,1993:3-20.

        [13]Yin Xiaoxin,Han Jiawei.CPAR:Classification Based on Predictive Association Rules[C]//Proc.of SDM'03.San Francisco,USA:Society for Industrial & Applied Mathematics,2003.

        猜你喜歡
        剪枝信息熵度量
        有趣的度量
        人到晚年宜“剪枝”
        基于信息熵可信度的測試點選擇方法研究
        模糊度量空間的強嵌入
        基于YOLOv4-Tiny模型剪枝算法
        迷向表示分為6個不可約直和的旗流形上不變愛因斯坦度量
        基于信息熵的實驗教學量化研究
        電子測試(2017年12期)2017-12-18 06:35:48
        一種基于信息熵的雷達動態(tài)自適應選擇跟蹤方法
        雷達學報(2017年6期)2017-03-26 07:52:58
        剪枝
        天津詩人(2017年2期)2017-03-16 03:09:39
        地質異常的奇異性度量與隱伏源致礦異常識別
        亚洲av天堂在线免费观看| 亚洲av无码av在线播放| 中字亚洲国产精品一区二区| 国语自产啪在线观看对白| 音影先锋中文字幕在线| 久久青青草原亚洲av无码麻豆| 婷婷四房播播| 日本精品极品视频在线| 国产精品成人av大片| 天堂网www资源在线| 特级毛片a级毛片在线播放www| 麻豆精品国产精华液好用吗| 国产精品香蕉在线观看| baoyu网址国产最新| 久久久亚洲免费视频网| 射精专区一区二区朝鲜| 四虎影院在线观看| 亚洲国产一区久久yourpan| 日韩精品乱码中文字幕| 亚洲国产av玩弄放荡人妇| 91av精品视频| 国产黑色丝袜在线观看网站91| 亚洲高清在线天堂精品| 成人三级a视频在线观看| 亚洲AV综合A∨一区二区 | 国产天堂av手机在线| 国产剧情一区二区三区在线| 人人妻人人澡人人爽人人精品97| 国产成人啪精品| 日本小视频一区二区三区| 国产成人精品免费视频大全软件| 国产精品兄妹在线观看麻豆| 国产无码夜夜一区二区| 日本女优中文字幕四季视频网站| 婷婷亚洲岛国热超碰中文字幕 | 男人无码视频在线观看| av中文字幕在线资源网| 国产av在线观看久久| 久久久精品人妻一区二区三区| 动漫av纯肉无码av在线播放| 中文字幕av熟女中文av|