概念格理论是Wille在1982年提出的一种数学理论,也被称作形式概念分析(FCA)。概念格理论是一种可以从数据集中找出概念结构的数据分析工具,它的层次结构是信息表示的基础,如今已经被广泛应用在心理学、社会学、人类学、医药学、生物学、语言学、计算机科学、数学和工业工程等各大领域。概念格理论从提出到现在的30几年,已经发展得比较成熟。概念格理论一般用于处理二维数据,在处理三维数据的时候须把三元背景分解为三个二元背景,显得很不直接。1995年,Wille在概念格理论的基础上提出概念三元格理论。概念三元格理论也被称作三元概念分析(TCA),它在概念格理论二维的基础上多了一维,为直接处理三维数据提供了理论基础。它可以直接对三维数据挖掘三元概念,进行分类,并使用这些概念构造一种特殊的可视化三元结构,显示概念之间的关系和三个维度之间的关系。随着近几年来因特网上Folksonomy等三维数据的涌现,概念三元格理论成为了研究焦点。概念三元格理论在处理三维数据的时候,生成的结构要比概念格复杂得多。因此,概念三元格的构造将更困难。和概念格类似,构造概念三元格的一个关键步骤是计算三元概念。高效的算法可以快速生成概念,同时也是数据分析中至关重要的一步。不幸的是,概念三元格的构造算法研究在国内外仍处于初级阶段。Wille在提出概念三元格理论的时候给出的构造算法时间复杂度较高,在现实中很难推广,目前其它可以使用的构造算法又少之又少。本文旨在设计时间复杂度较低的概念三元格构造算法。首先,本文回顾了二元概念格的三个构造算法:按字典序生成概念的Nextclousre算法、采用正则测试的Cbo算法和在Cbo基础上优化了的Fcbo算法。其次,本文采用把三元背景(U,T,R,Y)转换为一个二元背景(对象不变,属性为三元属性和三元条件间关系的二元背景(U,T×R,Y?))的巧妙方法,并结合三个二元算法的思想,设计出了三个概念三元格的构造算法:基于Nextclousre的Tri-Nextclousre算法,基于Cbo的Tri-Cbo算法和基于Fcbo的Tri-Fcbo算法。最后,本文实现了这三个算法,从对象、属性、条件、背景密度方面测试了它们对算法性能的影响,并使用Tri-Nextclousre算法挖掘Bibsonomy网站上的数据展示了概念三元格理论在Folksonomy上的应用。