【摘要】：概念格構(gòu)造問題起源于哲學(xué),如今已廣泛應(yīng)用于實際生產(chǎn)中,是對事物的共同本質(zhì)特點進行抽取,加以概括,形成概念,并最終建立起概念之間相互關(guān)系的格狀結(jié)構(gòu),即本文改進算法所要解決的問題。本文的研究目的是建立一個比目前的算法在時間和空間上實現(xiàn)雙重壓縮的概念格構(gòu)造算法。首先按照批處理型、漸進構(gòu)造型、并行構(gòu)造型和模糊構(gòu)造型對現(xiàn)階段的構(gòu)造算法進行了分類,并在每一類中挑選若干具有代表性的算法進行優(yōu)缺點的分析,最終選擇批處理型中的Chein算法作為本文改進算法的基礎(chǔ)。Chein算法具備不依賴于形式背景的優(yōu)勢,且新概念的生成過程和概念之間層次關(guān)系的構(gòu)造相互獨立。因此提出了劃分子形式背景的方式將新概念的生成過程根據(jù)交運算的左值進行子形式背景的劃分,正文中給出了證明。從而相互獨立的計算即可實現(xiàn)并行化。經(jīng)過大量實驗證明采用FP-Tree對概念進行存儲不僅可以實現(xiàn)更高比例的存儲空間壓縮,同時極大優(yōu)化了概念之間的交運算過程,效果明顯優(yōu)于其它算法所采用的位運算方式。本文另一個重要改進點是借助FP-Tree實現(xiàn)了冗余概念提早發(fā)現(xiàn)并直接刪除,從子形式背景劃分階段就避免了冗余概念的產(chǎn)生,從而解決冗余概念對空間的浪費,正文中給出了詳細證明。最后通過領(lǐng)域內(nèi)通用的標準UCI數(shù)據(jù)集與其它算法進行了多維度對比,驗證了改進算法的正確性和高性能的可行性,同時通過轉(zhuǎn)置數(shù)據(jù)說明了批處理型算法相比于漸進構(gòu)造型算法具備更好的實用性。正文也給出了實驗數(shù)據(jù),方便其它改進者進行算法類比。
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP301.6;TP311.5
【圖文】：

圖５．邋１對象數(shù)目對時間的影響逡逑數(shù)據(jù)轉(zhuǎn)置前后時間提升十分明顯

０邐１０００邐２０００邐３０００邐４０００邐５０００邐６０００邐７０００邐８０００邐９０００逡逑對象維度逡逑圖５．邋１對象數(shù)目對時間的影響逡逑數(shù)據(jù)轉(zhuǎn)置前后時間提升十分明顯。逡逑表５．２轉(zhuǎn)置后實驗對比逡逑對象數(shù)目逡逑１００邐２００邐５００邐１０００邐２０００邐５０００邐８１２４逡逑耗時逡逑Ｍｙ邋Ａｌｇｏｒｉｔｈｍ邐—１0邐１０邐２０邐４０邐６０邐１６５邐２１０￣逡逑ＩｎＣｌｏｓｅ２邐１０邐２０邐３０邐ＩＴ0邐２２０邐６５０邐９２０￣逡逑１０００逡逑９００邐少，＂逡逑８００逡逑７００逡逑＾邋６００邐Ｘ逡逑＾邐ｚ逡逑＾邋５００邐Ｚ逡逑＾邐１邋？邋Ｍｙ邋Ａｌｇｏｒｉｔｈｍ逡逑４００邐Ｚ逡逑■邋１邋ｌｎＣｌｏｓｅ２逡逑３００逡逑２００邋＾邋邐邐逡逑０邐１０００邋２０００邋３０００邋４０００邋５０００邋６０００

對象的交集，即ＦＰ－Ｔｒｅｅ中的公共前綴。而算法只需要計算非公共部分的節(jié)點之間的交逡逑運算，囡此計算量得到了極太的降低。算法的執(zhí)行效率也得到了極大的提升＾逡逑對于轉(zhuǎn)置后的數(shù)據(jù)，我們進行進一步的對比，將圖５．１與圖５．２繪制在同一張曲線逡逑圖中進行對比，如圖５．３所示。逡逑１０００逡逑９００逡逑８００逡逑７００逡逑＾邋６００逡逑—５００邐ｌｎＣｌｏｓｅ２逡逑宕４００邐轉(zhuǎn)置前逡逑３００邐轉(zhuǎn)置后逡逑２００逡逑二逡逑０邐１０００邐２０００邐３０００邐４０００邐５０００邐６０００邐７０００邐８０００邐９０００逡逑對象維度逡逑圖５．３轉(zhuǎn)置前后算ｔ去時間對比圖逡逑通過圖５．３對下述的兩個問題進行分析。首先，轉(zhuǎn)置對批處理算法的影響較大，因逡逑為Ｍｙ邋Ａｌｇｏｒｉｔｈｍ算法在建立ＦＰ－Ｔｒｅｅ時索引的選取決定了算法g＿多壓縮的計栜羹，由于逡逑Ｍｕｓｈｒｏｏｍ（８，１２４ｘ１２５）數(shù)據(jù)集的對象較多，屬性較少，因此表５．１中選擇屬性集作為逡逑ＦＰ－Ｔｒｅｅ的索引時數(shù)據(jù)的壓縮并不明顯，因此大量對象需要進行概念之間的交運算．ｓ雖逡逑然屬性的交運算在ＦＰ－Ｔｒｅｅ優(yōu)化下己經(jīng)只進行非公共部分屬性的交運算，但由于對象集逡逑基數(shù)較大，因此較高的計算量仍然無法被忽略。逡逑對比轉(zhuǎn)置前后的數(shù)據(jù)

【參考文獻】

相關(guān)期刊論文 前2條

1 崔芳婷;王黎明;張卓;;基于約束的模糊概念格構(gòu)造算法[J];計算機科學(xué);2015年08期

2 謝志鵬,劉宗田;概念格的快速漸進式構(gòu)造算法[J];計算機學(xué)報;2002年05期

相關(guān)碩士學(xué)位論文 前3條

1 楊建峰;多值概念格和區(qū)間值概念格構(gòu)造及屬性約簡[D];西北大學(xué);2012年

2 劉冬;區(qū)間值信息系統(tǒng)上概念格的屬性約簡方法[D];長安大學(xué);2012年

3 紀彤坤;概念格Chein算法的研究與改進[D];華南理工大學(xué);2012年

本文編號：2802236