題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 基于缺值形式背景的概念格構(gòu)造算法研究
- 小類：
- 信息技術(shù)
- 簡介：
- 概念格是一個(gè)有效的形式化工具，針對(duì)傳統(tǒng)概念格處理不完備信息的局限性，給出了一個(gè)能夠處理形式背景缺值現(xiàn)象的概念格擴(kuò)展模型—近似概念格。并在此基礎(chǔ)上提出一個(gè)改進(jìn)的概念格增量構(gòu)造算法，算法通過引入哈希技術(shù)和最近父節(jié)點(diǎn)的增量計(jì)算方法，加速定位生成元和更新邊這兩個(gè)關(guān)鍵過程，有效的提高建格效率，采用隨機(jī)數(shù)據(jù)集設(shè)計(jì)了實(shí)驗(yàn)，充分驗(yàn)證了算法的有效性，尤其對(duì)數(shù)據(jù)規(guī)模和發(fā)生關(guān)系概率較大的數(shù)據(jù)集有更好的效果。
- 詳細(xì)介紹：
- 概念格是一個(gè)有效的形式化工具，針對(duì)傳統(tǒng)概念格處理不完備信息的局限性，給出了一個(gè)能夠處理形式背景缺值現(xiàn)象的概念格擴(kuò)展模型—近似概念格。并在此基礎(chǔ)上提出一個(gè)改進(jìn)的概念格增量構(gòu)造算法，算法通過引入哈希技術(shù)和最近父節(jié)點(diǎn)的增量計(jì)算方法，加速定位生成元和更新邊這兩個(gè)關(guān)鍵過程，有效的提高建格效率，采用隨機(jī)數(shù)據(jù)集設(shè)計(jì)了實(shí)驗(yàn)，充分驗(yàn)證了算法的有效性，尤其對(duì)數(shù)據(jù)規(guī)模和發(fā)生關(guān)系概率較大的數(shù)據(jù)集有更好的效果。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 針對(duì)經(jīng)典概念格不能處理不完備信息的問題，借鑒偏大近似的思想擴(kuò)展概念格，構(gòu)建了近似概念格，使其能夠描述不完備信息，拓展了概念格理論。并在此基礎(chǔ)上，給出了改進(jìn)的概念格增量構(gòu)造算法。通過分析影響概念格構(gòu)造過程中的關(guān)鍵因素，算法從加速定位生成元和更新邊這兩個(gè)關(guān)鍵過程改進(jìn)Godin算法，得到高效的概念增量格構(gòu)造算法。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 傳統(tǒng)的概念格不能直接描述不完備信息，并且缺乏適合大型數(shù)據(jù)庫的建格算法，作品首先擴(kuò)展了概念格模型，使其能夠處理不完備信息，并且將哈希表和最近父節(jié)點(diǎn)的增量計(jì)算方法引入建格過程，提高的建格效率，拓展了概念格的應(yīng)用范圍。
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 作品研究了缺值形式背景下的概念格構(gòu)造問題，改善了概念格在實(shí)際應(yīng)用中對(duì)缺值信息的表示和構(gòu)建效率低下的問題，為概念格研究提供理論和實(shí)踐依據(jù)。
學(xué)術(shù)論文摘要
- 概念格是一個(gè)有效的形式化工具，針對(duì)傳統(tǒng)概念格處理不完備信息的局限性，給出了一個(gè)能夠處理形式背景缺值現(xiàn)象的概念格擴(kuò)展模型—近似概念格。并在此基礎(chǔ)上提出一個(gè)改進(jìn)的概念格增量構(gòu)造算法，算法通過引入哈希技術(shù)和最近父節(jié)點(diǎn)的增量計(jì)算方法，加速定位生成元和更新邊這兩個(gè)關(guān)鍵過程，有效的提高建格效率，采用隨機(jī)數(shù)據(jù)集設(shè)計(jì)了實(shí)驗(yàn)，充分驗(yàn)證了算法的有效性，尤其對(duì)數(shù)據(jù)規(guī)模和發(fā)生關(guān)系概率較大的數(shù)據(jù)集有更好的效果。
獲獎(jiǎng)情況
- 無
鑒定結(jié)果
- 已通過鑒定
參考文獻(xiàn)
- [1] Wille R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]//Rival I. Orderd Sets. Dordrecht,Boston,1982:445-470 [2] Yadav B S. A Conceptual Model for User-centered Quality Information Retrievalon the World Wide Web[J].Journal of Intelligent Information Systems, 2010, 35(1): 91-121 [3] Tonella P. Formal Concept Analysis in Software Engineering[C].In: Proceedings of the 26th International Conference on Software Engineering. Washington DC: IEEE Computer Society, 2004:743-744 [4] Stumme G. Efficient Data Mining Based on Formal Concept Analysis[C]. In:Proceedings of the 13th International Conference on Database and Expert Systems Applications. London: Springer-Ver-lag, 2002: 534-546 [5] 強(qiáng)宇,劉宗田,吳強(qiáng)等.模糊概念格在知識(shí)發(fā)現(xiàn)中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2005,32(1):182-184 [6] Formica A. Ontology-based Concept Similarity in Formal Concept Analysis[J]. Information Sciences, 2006, 176(18): 2624-2641
同類課題研究水平概述
- 概念格也稱為形式概念分析，基本思想是根據(jù)二元關(guān)系來表達(dá)領(lǐng)域中的形式背景，從中提取概念層次結(jié)構(gòu)，即概念格，本質(zhì)上體現(xiàn)了內(nèi)涵(屬性集)和外延(擁有該屬性集的實(shí)體集)的統(tǒng)一。作為數(shù)據(jù)分析和知識(shí)處理的形式化工具，概念格已被廣泛用于信息檢索、軟件工程、知識(shí)發(fā)現(xiàn)、本體研究等領(lǐng)域。經(jīng)典的概念格基于完備的形式背景，而現(xiàn)實(shí)生活中，信息的非完備(對(duì)象的屬性值缺損)現(xiàn)象是廣泛存在的。一旦出現(xiàn)缺值，傳統(tǒng)的處理方法有刪除法、補(bǔ)全法和擴(kuò)展屬性法。然而，刪除法和補(bǔ)全法容易造成知識(shí)的缺失或增加，擴(kuò)展屬性法雖然能夠保留原有形式背景的信息，但同時(shí)增加了形式背景的規(guī)模。因此，研究基于不完備形式背景的概念格模型具有重要的意義。概念格構(gòu)造的過程實(shí)際上是概念聚類的過程，由于很多情況下需要處理大量的數(shù)據(jù)，因此，概念格構(gòu)造算法始終是形式概念分析在其應(yīng)用過程中首先要解決的一個(gè)基礎(chǔ)性問題。概念格的構(gòu)造算法主要分為兩類：批處理算法和漸進(jìn)式算法。批處理算法的思想是首先生成所有概念，然后根據(jù)它們之間的直接前驅(qū)-后繼關(guān)系生成邊，完成概念格的構(gòu)造，如Bordat算法、Chein算法、Ganter算法等；漸進(jìn)式算法是將當(dāng)前要插入的對(duì)象與格中所有的概念求交，根據(jù)交的不同結(jié)果進(jìn)行不同的操作。典型的漸進(jìn)式構(gòu)造算法有Godin算法等。批處理算法對(duì)形式背景稠密的情況下性能較好，但缺乏靈活性，增量算法能夠有效的在原概念格基礎(chǔ)上進(jìn)行動(dòng)態(tài)更新和維護(hù)。影響增量算法效率的關(guān)鍵是生成元的定位和新節(jié)點(diǎn)邊的更新。針對(duì)該問題一些學(xué)者提出了改進(jìn)的增量算法。沈夏炯等提出利用數(shù)據(jù)庫內(nèi)部技術(shù)來實(shí)現(xiàn)確定生成元的查找判斷過程。Capineto提出的算法通過找到新節(jié)點(diǎn)的最小上界和最大下界，刪除它們的邊，并將其連接到新概念。這些研究都不同程度上提高了建格效率。
