題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 一種基于集合運(yùn)算的分類規(guī)則處理方法
- 小類：
- 信息技術(shù)
- 簡介：
- 分類規(guī)則是數(shù)據(jù)挖掘主要任務(wù)之一，消除分類規(guī)則集中的冗余規(guī)則，提高分類效率是一項(xiàng)重要的研究內(nèi)容。本文通過分析分類規(guī)則與訓(xùn)練集之間的映射關(guān)系，采用集合的相關(guān)運(yùn)算尋找特征規(guī)則及相應(yīng)特征集，從而消除分類規(guī)則集中存在的冗余，并在此基礎(chǔ)上提出了基于集合運(yùn)算的分類規(guī)則處理算法（PASO）。最后，以恒星光譜數(shù)據(jù)為背景，實(shí)驗(yàn)驗(yàn)證了該方法的正確性和可行性。
- 詳細(xì)介紹：
- 一種基于集合運(yùn)算的分類規(guī)則處理方法 摘要 分類規(guī)則是數(shù)據(jù)挖掘主要任務(wù)之一，消除分類規(guī)則集中的冗余規(guī)則，提高分類效率是一項(xiàng)重要的研究內(nèi)容。本文通過分析分類規(guī)則與訓(xùn)練集之間的映射關(guān)系，采用集合的相關(guān)運(yùn)算尋找特征規(guī)則及相應(yīng)特征集，從而消除分類規(guī)則集中存在的冗余，并在此基礎(chǔ)上提出了基于集合運(yùn)算的分類規(guī)則處理算法（PASO）。最后，以恒星光譜數(shù)據(jù)為背景，實(shí)驗(yàn)驗(yàn)證了該方法的正確性和可行性。 關(guān)鍵字 數(shù)據(jù)挖掘；分類規(guī)則；集合；恒星光譜數(shù)據(jù) A Processing Method of Classification Rule based on Set Operation Abstract: Classification is one of the main tasks in the fields of data mining, and to eliminate the redundant rules in classification rule set is one of study focuses. In this paper, a processing algorithm of classification rule based on set operation is presented by analyzing the mapping relationship between rules and training data，and using set operations to get characteristic rule and its characteristic set，so that the redundant rules may be discovered and eliminated. In the end, experimental results validate its correctness and efficiency by using star spectra data as the decision system. Keywords: DM (Data Mining); Classification Rule; Set; Star Spectra Data 1引言 分類是用來抽取能夠描述重要數(shù)據(jù)集合的模型，用于預(yù)測未知數(shù)據(jù)對象的離散類別，是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中的重要研究內(nèi)容之一，在市場營銷、金融投資、天文、地理的數(shù)據(jù)分析與決策等領(lǐng)域有著廣泛應(yīng)用[1]。 近年來國內(nèi)、外學(xué)者在該領(lǐng)域做了大量研究，如何提高分類效率及分類質(zhì)量是一個(gè)重要研究目標(biāo)。采用分類規(guī)則獲取方法的不同，分類質(zhì)量及效率各有優(yōu)劣。如概念格[2]，通過格結(jié)點(diǎn)間的關(guān)系獲取的分類規(guī)則，具有精確性、分類質(zhì)量高的特點(diǎn)，但是知識集容量較大；決策樹分類方法[1，3], 采用貪心算法思想，自頂向下遞歸的方式造決策樹，起源于概念學(xué)習(xí)系統(tǒng)，其獲取的規(guī)則具有可理解性強(qiáng)的特征；貝葉斯分類法[1,4]是一種統(tǒng)計(jì)學(xué)分類方法，用于大型數(shù)據(jù)庫中具有較高分類質(zhì)量；此外，較常用的獲取分類規(guī)則的方法還有粗糙集理論、模糊集、蟻群算法等[5-7]。在通過上述方法獲取的分類規(guī)則集中，往往存在功能完全相同或a規(guī)則的功能是b規(guī)則功能子集的冗余現(xiàn)象，以及規(guī)則前件完全相同，但規(guī)則后件不同的沖突現(xiàn)象，導(dǎo)致在分類和預(yù)測過程中出現(xiàn)錯(cuò)誤判斷、效率低下等問題。消除這類問題的方法分為兩大類：直接處理和后處理[8]。直接處理指的是在分類規(guī)則生成的過程中進(jìn)行剪枝操作，即規(guī)則提取和規(guī)則剪枝同時(shí)進(jìn)行，也即對原提取方法的改進(jìn)，對分類的研究主要集中在分類質(zhì)量。算法C4.5[9]中，Quinlan提出在生成規(guī)則的過程中，通過對規(guī)則的剪枝來消除冗余，并且Liu B [8]等在構(gòu)造CBA分類器的過程中也采用這種技術(shù)來消除冗余；在一些關(guān)聯(lián)規(guī)則的剪枝中也采用了這種方法，例如Calders等，在生成頻繁項(xiàng)目集的過程中進(jìn)行了剪枝操作[11]；后處理在已獲取分類規(guī)則集后進(jìn)行的，如Thabtah.F[12]在文中對挖掘出來的分類規(guī)則集進(jìn)行剪枝，根據(jù)分類規(guī)則之間的關(guān)系，對規(guī)則集進(jìn)行約簡，消除規(guī)則集內(nèi)存在的冗余； Bruha，F(xiàn)amili[13]提出的規(guī)則過濾方法，Huawen Liu等[8]采用閉集的方法對關(guān)聯(lián)、分類規(guī)則進(jìn)行約簡，都是典型的規(guī)則后處理例子。 實(shí)際上，分類規(guī)則集與訓(xùn)練集之間存在一種映射（規(guī)則與記錄間的適應(yīng)關(guān)系）關(guān)系，本文在對這種映射關(guān)系進(jìn)行分析的基礎(chǔ)上，通過該映射，利用分類規(guī)則集將訓(xùn)練集劃分為訓(xùn)練子集群，并利用子集群中各集合間的各種運(yùn)算特征，描述并消除分類規(guī)則集中的冗余規(guī)則。在分類規(guī)則集后處理過程中，由于充分考慮了訓(xùn)練集數(shù)據(jù)的特征，可有效地提高分類效率。采用恒星光譜數(shù)據(jù)，實(shí)驗(yàn)驗(yàn)證該方法正確可行，從而為提高分類效率提供了一條有效途徑。 2分類規(guī)則問題描述 分類是數(shù)據(jù)挖掘的一項(xiàng)重要任務(wù)，參照文獻(xiàn)[1]，首先給出分類問題的相關(guān)定義： 定義1 設(shè)三元組T=(O,R,K)，其中O={x1,x2,… xn}表示數(shù)據(jù)集，R={r1,r2,…rn}表示規(guī)則集，K?O×R是一個(gè)在O和R之間的二元關(guān)系，K={<x,r>|M(x,r)=1?x?O?r?R}，M(x,r)=1表示規(guī)則r能對數(shù)據(jù)x進(jìn)行分類，否則M(x,r)=0，稱該三元組T為分類背景。 在T中，二元關(guān)系K中的元素均為二元序偶，其第一元素與第二元素之間是一種數(shù)據(jù)記錄與規(guī)則的映射關(guān)系。 定義2 設(shè)三元組 T=(O,R,K)是一個(gè)分類背景，在R?O上，算子f(r)={x|<x,r>?K, x?O,r?R}，是O中適應(yīng)規(guī)則r的所有記錄集，在O?R上，算子g(x)={r|<x,r>?K, x?O,r?R }，是R中記錄x適應(yīng)的所有規(guī)則集。 一條分類規(guī)則r能對多條數(shù)據(jù)進(jìn)行分類，而能對一條數(shù)據(jù)x分類的規(guī)則也可能有多條。 定義3 設(shè)三元組 T=(O,R,K)是一個(gè)分類背景，P(O)={s|s?O}為O的冪集，P(R)={s| s?R}是R的冪集，在P(R)?P(O)上，f(Y)={x |"r?Y,(x,r)?K，x?O，Y?P(R) }，表示規(guī)則集Y中所有規(guī)則都適應(yīng)的記錄集；在P(O)?P(R)上g(X)={r|"x?X,(x,r)?K，r?R，X?P(O) }，表示記錄集X所有記錄都適應(yīng)的規(guī)則集。 當(dāng)|Y|=1時(shí)，f(Y)就表示能被規(guī)則Y分類的數(shù)據(jù)的集合，當(dāng)|Y|>1時(shí)，即Y={r1,r2,…rm}，則f(Y)=f(r1)∩f(r2)∩…∩f(rm)；對于一條分類規(guī)則r?R，規(guī)則的支持度為supp(r)=|f(r)|，其含義為能被規(guī)則r分類的數(shù)據(jù)的個(gè)數(shù)。而集合Y的支持度supp(Y)=|f(Y)|，含義為能被集合Y中所有規(guī)則分類的數(shù)據(jù)的個(gè)數(shù)。 定義4對于T=(O,R,K)，規(guī)則r1,r2?R，若f(r2)?f(r1)，稱規(guī)則r1覆蓋規(guī)則r2，記為r1 ? r2特殊地，若f(r1)=f(r2)，稱r1與r2等價(jià)，記為r1 = r2。 規(guī)則r1覆蓋規(guī)則r2，即對于任意的一條數(shù)據(jù)x，如果有(x,r2)?K，則必有(x,r1)?K，但是反之并不一定成立，且必有supp(r1)≥supp(r2)。兩條規(guī)則r1和r2等價(jià)，如果一條數(shù)據(jù)能被規(guī)則r1進(jìn)行分類，(x,r1)?K，那么必有(x,r2)?K，反之也一樣成立，且必有supp(r1)=supp(r2)。 易見，對任意兩條規(guī)則r1、r2，若r1 ? r2或 r1 = r2，所有能被r2分類的記錄均可被r1分類，r2是冗余的。 定義5 任意Y?R，且Y中所有規(guī)則的決策屬性相同，如果在Y中存在一個(gè)規(guī)則r，對于"r′?Y都有f(r′)?f(r)，且規(guī)則r的條件屬性不多于規(guī)則r′的條件屬性，稱規(guī)則集Y為規(guī)則r的特征集，規(guī)則r稱為Y的特征規(guī)則。 定理1：設(shè)Y是規(guī)則r的特征集，且|Y|>1，則規(guī)則集Y是可約簡的，并且特征規(guī)則r與特征集Y的分類能力是等價(jià)的。 證明：由定義5中易得，"r′?Y, f(r′)?f(r)，則f(Y) ?f(r)；又r?Y，故f(Y) =f(r)，證畢。 3分類規(guī)則處理算法 3.1算法思想 通過各種工具獲取的分類規(guī)則集中，存在大量的冗余規(guī)則，由上節(jié)定理1，首先在分類規(guī)則集中尋找特征規(guī)則及相應(yīng)的特征集，然后保留特征規(guī)則，刪除特征集中其余冗余規(guī)則，從而達(dá)到約簡分類規(guī)則集的目的。 在尋找特征規(guī)則及相應(yīng)特征集的過程中，首先對每條規(guī)則r，求解f(r)；將所有規(guī)則按其決策屬性值（類屬性）進(jìn)行分組，并按規(guī)則前件容量（條件屬性個(gè)數(shù)）進(jìn)行升序排列，在尋找特征規(guī)則時(shí)，優(yōu)先考慮條件屬性個(gè)數(shù)較少的規(guī)則；選擇某類小組為當(dāng)前組，依次選擇每條規(guī)則為假想特征規(guī)則，為其尋找特征集，并刪除特征集中規(guī)則；如此反復(fù)，直至所有類小組全部過濾結(jié)束。 3.2算法描述 ALGORITHM: PASO(a Processing Algorithm based on Set Operation) INPUT：分類規(guī)則集R，訓(xùn)練數(shù)據(jù)集O OUTPUT：約簡分類規(guī)則集R′ BEGIN 1.for(i=0;i<|O|;i++) 2. for(j=0;j<|R|;j++) 3. if(R[j]能對O[i]進(jìn)行分類) 4. {將O[i]寫入R[j]的分類記錄集} 5.對規(guī)則集按類屬性分組，并按條件屬性個(gè)數(shù)進(jìn)行升序排列 6.for(k=0;k<|R|;k++) 7． 初始化特征集Y=?，將R[j]并入Y 8. for(m=k+1;m<|R|;m++) 9. if((R[j]覆蓋R[m]) 10. 將R[m]并入Y中 11. if (|Y|>1) delete all rules in Y from R END. 算法的功能是分三步實(shí)現(xiàn)的，首先用規(guī)則集內(nèi)的各個(gè)規(guī)則掃描數(shù)據(jù)庫的各條數(shù)據(jù)，計(jì)算f(r)的過程，設(shè)規(guī)則集內(nèi)有i條規(guī)則，數(shù)據(jù)集內(nèi)有j條數(shù)據(jù)，則其時(shí)間消耗為O(i*j)；其次是對規(guī)則集內(nèi)的規(guī)則進(jìn)行分組排序的過程，主要時(shí)間消耗為O(j*j)；最后，特征規(guī)則及相應(yīng)特征集的發(fā)現(xiàn)并消除冗余規(guī)則，消耗的時(shí)間為O(j*j)。因此，該影響該算法的主要因素為規(guī)則數(shù)及訓(xùn)練集記錄數(shù)，時(shí)間復(fù)雜度可表示為O（j*j+ i*j）。 4實(shí)驗(yàn)分析 在Pentium(R)D-3.0G CPU，512M 內(nèi)存，Windows XP操作系統(tǒng)，DBMS為ORACLE9i，用Visual C++實(shí)現(xiàn)了概念格和包含集的挖掘及處理算法。選用由國家天文臺(tái)提供的SDSS恒星光譜數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集，并經(jīng)過以下預(yù)處理后構(gòu)成該實(shí)驗(yàn)中的數(shù)據(jù)集：1)選定間隔為20 ?的200個(gè)波長3810，3830，…7790 ?，依據(jù)流量、峰寬和形狀，將每個(gè)波長離散化為十三種值；2)恒星的任意類型溫度等間隔離散化為三種值，七類恒星溫度離散化為二十一種值；3)根據(jù)恒星的光度、化學(xué)分度、微湍流、其它參數(shù)等間隔離散化為三種值。為了驗(yàn)證算法的正確性和有效性，對由概念格提取的分類規(guī)則集進(jìn)行處理，處理前后對比結(jié)果如表1所示。 表1 分類規(guī)則集處理前后對比表 Table 1 the Compared Table of Classification Rule Sets 記錄數(shù) 規(guī)則處理前 規(guī)則處理后 規(guī)則數(shù) 正確率 錯(cuò)誤率 平均使用規(guī)則數(shù) 規(guī)則數(shù) 正確率 錯(cuò)誤率 平均使用規(guī)則數(shù) 1000 1933 98.8% 1.2% 766.7 263 98.8% 1.2% 41.9 2000 4103 84.1% 15.8% 2503.3 486 84.1% 15.8% 89.7 3000 6105 81.9% 17.4% 3498.5 817 81.9% 17.4% 113.6 4000 7810 93.1% 6.7% 3578.9 1165 93.1% 6.7% 215.3 表1的實(shí)驗(yàn)結(jié)果可以看出：1）處理后規(guī)則數(shù)大幅減少，即減小了目標(biāo)分類器的大??；這是因?yàn)樵鹊囊?guī)則集中存在著大量的冗余規(guī)則，這大大增加了分類器內(nèi)規(guī)則的數(shù)量，所以當(dāng)對冗余規(guī)則進(jìn)行處理之后，分類器的大小明顯減?。?）在對分類規(guī)則結(jié)果進(jìn)行測試過程中，避免了處理前對冗余規(guī)則的匹配，因此降低了平均使用規(guī)則數(shù)，從而有效地提高了分類效率；3）因?yàn)楸惶幚淼囊?guī)則都為包含或者是等價(jià)規(guī)則，所以在處理后規(guī)則集的分類質(zhì)量并沒有改變。 5小結(jié) 分類是數(shù)據(jù)挖掘的主要任務(wù)之一，針對獲取的分類規(guī)則中存在的冗余，通過采用集合的相關(guān)運(yùn)算，尋找特征規(guī)則及相應(yīng)特征集，從而消除冗余。該方法在對分類規(guī)則集進(jìn)行后處理過程中，充分考慮到訓(xùn)練集的數(shù)據(jù)特征，有效地約簡了分類規(guī)則集，有效地提高了分類效率。 參考文獻(xiàn) [1]J Han, M. Kambr. Data Mining Concepts and Techniques. Morgan Kaufmann Publishers. 2000 [2]張繼福，馬洋.一種基于約束概念格的恒星光譜數(shù)據(jù)自動(dòng)分類方法[J], 光譜學(xué)與光譜分析， 2010,30 (2): 559-562 [3] Quinlan J R. Introduction of decision trees [ J ]. Machine Learning, 1986，1 (1): 84 - 100. [4] Rudy Sicard, Thierry Artières, Eric Petit. Learning iteratively a classifier with the Bayesian Model Averaging Principle[J], Pattern Recognition,2008,41(3):930-938 [5] HUANGLONG-JUN, ZHOU CA I-YING, HUANGMING-HE, et al.A new method for constructing decision tree based on rough set theory[J ]. Journal of Nanchang Institute of Technology, 2006, 25 (2) : 122 -125 [6]李潔，鄧一鳴，沈士團(tuán).基于模糊區(qū)域分布的分類規(guī)則提取及推理算法[J]，計(jì)算機(jī)學(xué)報(bào)，2008，31（6）：934-941 [7]吳正龍，王儒敬等. 基于蟻群算法的分類規(guī)則挖掘算法[J]，計(jì)算機(jī)工程與應(yīng)用，2004，40（20）：30-33 [8] Huawen Liu, Jigui Sun, HuijieZhang. Post-processing of associative classification rules using closed sets [ J ]. Expert Systems with Applications, 2008, 36 (3): 6659-6667 [9] Quinlan J R. C4. 5: Programs for Machine Learning [M]. SanMateo, Calif. :Morgan Kaufmann, 1993: 17 - 42. [10] Liu B,Hsu W,Ma Y.Pruning and summarizing the discovered association.In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,1999,p.125-134 [11] Calders,T,Rigotti,C,Boulicaut,J.F.A survey on condensed representations for frequent sets.Lecture Notes in Computer Science,2006,3848：64-80 [12]Thabtah,F.Rule Pruning in Associative Classification Mining.Proceedings of the IBIMA conference,2005,101-107 [13]Bruha,I,&Famili,A.Post processing in machine learning and data mining.ACM SIGKDD Explorations Newsletter,2000,p.110–114
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 采用集合的相關(guān)運(yùn)算尋找特征規(guī)則及相應(yīng)特征集，從而消除分類規(guī)則集中存在的冗余，提高分類效率
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 提出了基于集合運(yùn)算的分類規(guī)則處理算法（PASO）
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 為提高分類效率提供了一條有效途徑。
學(xué)術(shù)論文摘要
- 通過分析分類規(guī)則與訓(xùn)練集之間的映射關(guān)系，采用集合的相關(guān)運(yùn)算尋找特征規(guī)則及相應(yīng)特征集，從而消除分類規(guī)則集中存在的冗余，并在此基礎(chǔ)上提出了基于集合運(yùn)算的分類規(guī)則處理算法（PASO）。最后，以恒星光譜數(shù)據(jù)為背景，實(shí)驗(yàn)驗(yàn)證了該方法的正確性和可行性。
獲獎(jiǎng)情況
- 已投稿
鑒定結(jié)果
- 無
參考文獻(xiàn)
- 數(shù)據(jù)挖掘；分類規(guī)則；集合；恒星光譜數(shù)據(jù)
同類課題研究水平概述
- 分類是用來抽取能夠描述重要數(shù)據(jù)集合的模型，用于預(yù)測未知數(shù)據(jù)對象的離散類別，是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中的重要研究內(nèi)容之一，在市場營銷、金融投資、天文、地理的數(shù)據(jù)分析與決策等領(lǐng)域有著廣泛應(yīng)用。 近年來國內(nèi)、外學(xué)者在該領(lǐng)域做了大量研究，如何提高分類效率及分類質(zhì)量是一個(gè)重要研究目標(biāo)。采用分類規(guī)則獲取方法的不同，分類質(zhì)量及效率各有優(yōu)劣。如概念格，通過格結(jié)點(diǎn)間的關(guān)系獲取的分類規(guī)則，具有精確性、分類質(zhì)量高的特點(diǎn)，但是知識集容量較大；決策樹分類方法, 采用貪心算法思想，自頂向下遞歸的方式造決策樹，起源于概念學(xué)習(xí)系統(tǒng)，其獲取的規(guī)則具有可理解性強(qiáng)的特征；貝葉斯分類法是一種統(tǒng)計(jì)學(xué)分類方法，用于大型數(shù)據(jù)庫中具有較高分類質(zhì)量；此外，較常用的獲取分類規(guī)則的方法還有粗糙集理論、模糊集、蟻群算法等。在通過上述方法獲取的分類規(guī)則集中，往往存在功能完全相同或a規(guī)則的功能是b規(guī)則功能子集的冗余現(xiàn)象，以及規(guī)則前件完全相同，但規(guī)則后件不同的沖突現(xiàn)象，導(dǎo)致在分類和預(yù)測過程中出現(xiàn)錯(cuò)誤判斷、效率低下等問題。消除這類問題的方法分為兩大類：直接處理和后處理。直接處理指的是在分類規(guī)則生成的過程中進(jìn)行剪枝操作，即規(guī)則提取和規(guī)則剪枝同時(shí)進(jìn)行，也即對原提取方法的改進(jìn)，對分類的研究主要集中在分類質(zhì)量。算法C4.5中，Quinlan提出在生成規(guī)則的過程中，通過對規(guī)則的剪枝來消除冗余，并且Liu B 等在構(gòu)造CBA分類器的過程中也采用這種技術(shù)來消除冗余；在一些關(guān)聯(lián)規(guī)則的剪枝中也采用了這種方法，例如Calders等，在生成頻繁項(xiàng)目集的過程中進(jìn)行了剪枝操作；后處理在已獲取分類規(guī)則集后進(jìn)行的，如Thabtah.F在文中對挖掘出來的分類規(guī)則集進(jìn)行剪枝，根據(jù)分類規(guī)則之間的關(guān)系，對規(guī)則集進(jìn)行約簡，消除規(guī)則集內(nèi)存在的冗余； Bruha，F(xiàn)amili提出的規(guī)則過濾方法，Huawen Liu等采用閉集的方法對關(guān)聯(lián)、分類規(guī)則進(jìn)行約簡，都是典型的規(guī)則后處理例子。 實(shí)際上，分類規(guī)則集與訓(xùn)練集之間存在一種映射（規(guī)則與記錄間的適應(yīng)關(guān)系）關(guān)系，本文在對這種映射關(guān)系進(jìn)行分析的基礎(chǔ)上，通過該映射，利用分類規(guī)則集將訓(xùn)練集劃分為訓(xùn)練子集群，并利用子集群中各集合間的各種運(yùn)算特征，描述并消除分類規(guī)則集中的冗余規(guī)則。在分類規(guī)則集后處理過程中，由于充分考慮了訓(xùn)練集數(shù)據(jù)的特征，可有效地提高分類效率。 實(shí)驗(yàn)驗(yàn)證該方法正確可行，從而為提高分類效率提供了一條有效途徑 。
