概念三元格構(gòu)造算法研究.pdf

1、概念格理論是 Wille在1982年提出的一種數(shù)學理論，也被稱作形式概念分析（FCA）。概念格理論是一種可以從數(shù)據(jù)集中找出概念結(jié)構(gòu)的數(shù)據(jù)分析工具，它的層次結(jié)構(gòu)是信息表示的基礎(chǔ)，如今已經(jīng)被廣泛應(yīng)用在心理學、社會學、人類學、醫(yī)藥學、生物學、語言學、計算機科學、數(shù)學和工業(yè)工程等各大領(lǐng)域。概念格理論從提出到現(xiàn)在的30幾年，已經(jīng)發(fā)展得比較成熟。概念格理論一般用于處理二維數(shù)據(jù)，在處理三維數(shù)據(jù)的時候須把三元背景分解為三個二元背景，顯得很不直接。

2、>　　1995年，Wille在概念格理論的基礎(chǔ)上提出概念三元格理論。概念三元格理論也被稱作三元概念分析（TCA），它在概念格理論二維的基礎(chǔ)上多了一維，為直接處理三維數(shù)據(jù)提供了理論基礎(chǔ)。它可以直接對三維數(shù)據(jù)挖掘三元概念，進行分類，并使用這些概念構(gòu)造一種特殊的可視化三元結(jié)構(gòu)，顯示概念之間的關(guān)系和三個維度之間的關(guān)系。隨著近幾年來因特網(wǎng)上Folksonomy等三維數(shù)據(jù)的涌現(xiàn)，概念三元格理論成為了研究焦點。概念三元格理論在處理三維數(shù)據(jù)的時候，生成

3、的結(jié)構(gòu)要比概念格復雜得多。因此，概念三元格的構(gòu)造將更困難。和概念格類似，構(gòu)造概念三元格的一個關(guān)鍵步驟是計算三元概念。高效的算法可以快速生成概念，同時也是數(shù)據(jù)分析中至關(guān)重要的一步。不幸的是，概念三元格的構(gòu)造算法研究在國內(nèi)外仍處于初級階段。Wille在提出概念三元格理論的時候給出的構(gòu)造算法時間復雜度較高，在現(xiàn)實中很難推廣，目前其它可以使用的構(gòu)造算法又少之又少。
　　本文旨在設(shè)計時間復雜度較低的概念三元格構(gòu)造算法。首先，本文回顧了二元概

4、念格的三個構(gòu)造算法：按字典序生成概念的Nextclousre算法、采用正則測試的Cbo算法和在Cbo基礎(chǔ)上優(yōu)化了的Fcbo算法。其次，本文采用把三元背景(U, T, R, Y)轉(zhuǎn)換為一個二元背景（對象不變，屬性為三元屬性和三元條件間關(guān)系的二元背景(U, T× R, Y?)）的巧妙方法，并結(jié)合三個二元算法的思想，設(shè)計出了三個概念三元格的構(gòu)造算法：基于Nextclousre的Tri-Nextclousre算法，基于Cbo的Tri-Cbo算法