[發(fā)明專利]基于Hadoop的粗糙集快速屬性約簡方法

有效

• 申請?zhí)枺?/td>: 201310224737.7
• 申請日: 2013-06-06
• 公開（公告）號(hào): CN103336791A
• 公開（公告）日: 2013-10-02
• 發(fā)明（設(shè)計(jì)）人: 蔣云良;楊建黨;劉勇;范婧;張雄濤
• 申請（專利權(quán)）人: 湖州師范學(xué)院
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京天奇智新知識(shí)產(chǎn)權(quán)代理有限公司 11340
• 代理人: 韓洪

1.基于Hadoop的粗糙集快速屬性約簡方法，其特征在于：包括以下步驟：

a)建立基于Hadoop的分布式平臺(tái)：建立HDFS分布式文件系統(tǒng)和MapReduce并行編程模型；所述HDFS分布式文件系統(tǒng)采用主從結(jié)構(gòu)體系，由一個(gè)管理者和多個(gè)工作者構(gòu)成，管理者管理文件系統(tǒng)的命名空間，維護(hù)文件系統(tǒng)樹及整棵樹內(nèi)所有的文件和目錄，工作者是文件系統(tǒng)的工作節(jié)點(diǎn)，根據(jù)需要存儲(chǔ)并檢索數(shù)據(jù)塊，并且定期向管理者發(fā)送“心跳”報(bào)告，如果管理者在指定的時(shí)間段內(nèi)沒有收到工作者的“心跳”報(bào)告，則管理者啟動(dòng)容錯(cuò)機(jī)制對其進(jìn)行處理；所述MapReduce并行編程模型將任務(wù)分成若干小任務(wù)去執(zhí)行，每個(gè)小任務(wù)對集群節(jié)點(diǎn)本地存儲(chǔ)的數(shù)據(jù)塊進(jìn)行處理；

b)生成候選集：采用搜索策略生成一組待評(píng)價(jià)特征子集作為候選集，最初的候選集是空集或者特征全集或者隨機(jī)產(chǎn)生的一組特征子集；

c)計(jì)算每個(gè)屬性的重要度：建立一個(gè)Mapper類和一個(gè)Reducer類，Mapper類讀入樣本數(shù)據(jù)，并將樣本集合按照已選的屬性集合為每個(gè)待評(píng)價(jià)的屬性分配對應(yīng)的樣本集合作為Reducer類的輸入，每個(gè)reducer只接受一個(gè)屬性的所有樣本子集，并在一個(gè)reducer之內(nèi)通過組合鍵數(shù)據(jù)進(jìn)行分區(qū)，Reducer任務(wù)的個(gè)數(shù)就是待評(píng)價(jià)的屬性個(gè)數(shù)，對應(yīng)的樣本集合將以不同的屬性編號(hào)輸入到對應(yīng)的Reducer任務(wù)中，多個(gè)Reducer任務(wù)并行執(zhí)行，采用相同的評(píng)價(jià)方法來評(píng)價(jià)每個(gè)屬性的重要度；

d)選擇重要度最大的屬性加入到候選集：將c)步驟中的輸出作為本步驟的輸入，與之前最大的重要度值進(jìn)行比較，如果當(dāng)前屬性的重要度值更高，則把當(dāng)前的屬性作為最好的特征子集添加到候選集中；

e)判斷是否滿足停止條件：采用特征產(chǎn)生過程和評(píng)價(jià)過程作為停止條件，特征產(chǎn)生過程的停止條件有兩種：一種是判斷是否已經(jīng)選擇了預(yù)先定義的特征個(gè)數(shù)，另一種是判斷是否已經(jīng)達(dá)到預(yù)先定義的迭代個(gè)數(shù)；評(píng)價(jià)過程的停止條件有兩種：一種是判斷是否添加或剔除了一個(gè)特征將產(chǎn)生一個(gè)更好的特征子集，另一種是判斷是否最優(yōu)特征子集已經(jīng)得到；

f)保存特征選擇的狀態(tài)：分別保存已選擇的特征集合和未選擇的特征集合，c)步驟中對未選擇的特征集合計(jì)算重要度，e)步驟中已選擇的特征集合和未選擇的特征集合進(jìn)行更新，最后將已選擇的特征集合和未選擇的特征集合作為結(jié)果輸出。

2.如權(quán)利要求1所述的基于Hadoop的粗糙集快速屬性約簡方法，其特征在于：所述b)步驟中搜索策略采用窮舉法，從空集開始，采用廣度優(yōu)先搜索策略，直到找到一個(gè)能夠完整預(yù)測分類的最小子集。

3.如權(quán)利要求1所述的基于Hadoop的粗糙集快速屬性約簡方法，其特征在于：所述b)步驟中搜索策略采用完全搜索算法，從特征全集開始，每次剔除一個(gè)特征。

4.如權(quán)利要求1所述的基于Hadoop的粗糙集快速屬性約簡方法，其特征在于：所述b)步驟中搜索策略采用啟發(fā)式搜索算法，從空集開始，每次放入一個(gè)能夠使選擇的特征子集覆蓋率更高的特征，直到“覆蓋率”到達(dá)一個(gè)設(shè)定的值，或者所有特征被窮舉完的時(shí)候，算法停止。