概念三元格構造算法研究.pdf

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

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

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

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