A Fuzzy FCA-based Approach to Conceptual
Clustering for Automatic Generation of Concept
Hierarchy on Uncertainty Data
Thanh Tho Quan1 , Siu Cheung Hui1 , and Tru Hoang Cao2
1
School of Computer Engineering, Nanyang Technological University, Singapore
{PA0218164B, asschui}@ntu.edu.sg
2
Faculty of Information Technology, Hochiminh City University of Technology,
Vietnam
tru@dit.hcmut.edu.vn
Abstract. This paper proposes a new fuzzy FCA-based approach to
conceptual clustering for automatic generation of concept hierarchy on
uncertainty data. The proposed approach first incorporates fuzzy logic
into Formal Concept Analysis (FCA) to form a fuzzy concept lattice.
Next, a fuzzy conceptual clustering technique is proposed to cluster the
fuzzy concept lattice into conceptual clusters. Then, hierarchical rela-
tions are generated among conceptual clusters for constructing the con-
cept hierarchy. In this paper, we also apply the proposed approach to
generate a concept hierarchy of research areas from a citation database.
The performance of the proposed approach is also discussed in the paper.
Keywords: Formal Concept Analysis, Fuzzy Logic, Conceptual Clustering, Con-
cept Hierarchy
1 Introduction
Conceptual clustering [3] is an advanced data mining technique that clusters data
into clusters associated with conceptual representations, or conceptual clusters.
Concept hierarchy can then be constructed from the conceptual clusters. How-
ever, traditional conceptual clustering techniques can only work on specific data
types such as nominal and numeric. In addition, the concept hierarchy is mostly
in a tree-like structure which is unable to support the representation of multiple
inheritance.
Formal Concept Analysis (FCA) [4] is a data analysis technique based on
the ordered lattice theory. It defines formal contexts to represent relationships
between objects and attributes in a domain and interprets the corresponding
concept lattice. The concept lattice is more informative than traditional tree-
like conceptual structures as it can also support multiple inheritance. This makes
FCA a very suitable technique for conceptual clustering. Several FCA-based
c V. Snášel, R. Bělohlávek (Eds.): CLA 2004, pp. 1–12, ISBN 80-248-0597-9.
VŠB – Technical University of Ostrava, Dept. of Computer Science, 2004.
, 2 Thanh Tho Quan, Siu Cheung Hui, Tru Hoang Cao
conceptual clustering systems such as TOSCANA [15] and INCOSHAM [6] have
been developed.
However, there are many situations in which uncertainty information also
occurs. For example, keywords extracted from scientific documents can be used
to infer the corresponding research areas, however, it is inappropriate to treat all
keywords equally as some keywords may be more significant than others. More-
over, it is sometimes difficult to judge whether a document belongs totally to a
research area or not. Traditional FCA-based conceptual clustering approaches
are hardly able to represent such vague information. To tackle this problem,
we propose a fuzzy FCA-based approach to conceptual clustering for automatic
generation of concept hierarchy on uncertainty data.
Pollandt [13], and Huynh and Nakamori [7] proposed the L-Fuzzy context
as an attempt to combine fuzzy logic with FCA. The L-Fuzzy context uses
linguistic variables, which are linguistic terms associated with fuzzy sets, to
represent uncertainty in the context. However, human interpretation is required
to define the linguistic variables. Moreover, the fuzzy concept lattice generated
from the L-fuzzy context usually causes a combinatorial explosion of concepts
as compared to the traditional concept lattice.
In this paper, we propose a new technique that incorporates fuzzy logic into
FCA as Fuzzy Formal Concept Analysis (FFCA), in which uncertainty informa-
tion is directly represented by a real number of membership value in the range
of [0,1]. As such, linguistic variables are no longer needed. In comparison with
the fuzzy concept lattice generated from the L-fuzzy context, the fuzzy concept
lattice generated using FFCA will be simpler in terms of the number of for-
mal concepts, and it also supports a formal mechanism for calculating concept
similarities. Therefore, the proposed FFCA’s fuzzy concept lattice is a suitable
representation for conceptual clustering.
The rest of the paper is organized as follows. Section 2 discusses the related
work on conceptual clustering. Section 3 presents the proposed approach. Section
4 discuses the Fuzzy Formal Concept Analysis. Fuzzy Conceptual Clustering is
presented in Section 5. Section 6 discusses the Hierarchical Relation Generation
process. Section 7 applies the proposed approach to a citation database for gener-
ating a concept hierarchy of research areas. Section 8 evaluates the performance
of the proposed approach. Finally, Section 9 concludes the paper.
2 Conceptual Clustering
Conceptual clustering techniques can be used to construct a concept hierarchy
from data. Traditional conceptual clustering techniques such as COBWEB [3]
and AutoClass [1] are based on taxonomy clustering techniques and use statisti-
cal models as conceptual representations of clusters. However, these techniques
are only applicable to specific types of data. CLASSIT [5] and ECOBWEB [14]
were proposed to improve on COBWEB to deal with numeric attributes of data.
SBAC [10] was introduced as a conceptual clustering technique that can handle
mixed numeric and nominal data. However, as conceptual hierarchies generated
