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

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

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

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

本文編號(hào)：2802236