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 relations are generated among conceptual clusters for constructing the concept 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.
Conceptual clustering [
Formal Concept Analysis (FCA) [
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. Moreover, 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 [
In this paper, we propose a new technique that incorporates fuzzy logic into
FCA as Fuzzy Formal Concept Analysis (FFCA), in which uncertainty
information is directly represented by a real number of membership value in the range
of [
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 generating a concept hierarchy of research areas. Section 8 evaluates the performance of the proposed approach. Finally, Section 9 concludes the paper. 2
Conceptual clustering techniques can be used to construct a concept hierarchy
from data. Traditional conceptual clustering techniques such as COBWEB [
Fuzzy Concept Lattice
Conceptual Clusters
Concept Hierarchy Database containing Uncertainty Information
Fuzzy Formal Concept Analysis
Fuzzy Conceptual
Clustering
Hierarchical
Relation Generation
Definition 1. A fuzzy formal context is a triple K = (G, M, I = ϕ(G × M ))
where G is a set of objects, M is a set of attributes, and I is a fuzzy set on
domain G × M . Each relation (g, m) ∈ I has a membership value μ (g, m) in
[
A fuzzy formal context can also be represented as a cross-table as shown in Table 1(a). The context has three objects representing three documents, namely D1, D2 and D3. In addition, it also has three attributes, ”Data Mining” (D), ”Clustering” (C) and ”Fuzzy Logic” (F) representing three research topics. The relationship between an object and an attribute is represented by a membership value between 0 and 1.
A confidence threshold T can be set to eliminate relations that have low membership values. Table 1(b) shows the cross-table of the fuzzy formal context given in Table 1(a) with T = 0.5.
Generally, we can consider the attributes of a formal concept as the
description of the concept. Thus, the relationships between the object and the
concept should be the intersection of the relationships between the objects and
the attributes of the concept. Since each relationship between the object and
an attribute is represented as a membership value in fuzzy formal context, then
the intersection of these membership values should be the minimum of these
membership values, according to fuzzy theory [
Definition 2. Given a fuzzy formal context K=(G, M , I) and a confidence threshold T , we define A∗ = {m ∈ M |∀g ∈ A: μ (g, m) ≥ T } for A ⊆ G and B∗ = {g ∈ G|∀m ∈ B: μ (g,m) ≥ T } for B ⊆ M . A fuzzy formal concept (or fuzzy concept) of a fuzzy formal context (G, M , I) with a confidence threshold T is a pair (Af =ϕ(A), B) where A ⊆ G, B ⊆ M , A∗ = B and B∗ = A. Each object g ∈ ϕ(A) has a membership μ g defined as μ g = min μ (g, m)
m∈B where μ (g, m) is the membership value between object g and attribute m, which is defined in I. Note that if B= {} then μ g = 1 for every g.
Definition 3. Let (A1, B1) and (A2, B2) be two fuzzy concepts of a fuzzy formal context (G, M , I). (ϕ(A1), B1) is the subconcept of (ϕ(A2), B2), denoted as (ϕ(A1), B1) ≤ (ϕ(A2), B2), if and only if ϕ(A1) ⊆ ϕ(A2)(⇔ B2 ⊆ B1). Equivalently, (A2, B2) is the superconcept of (A1, B1). ≤ Definition 4. A fuzzy concept lattice of a fuzzy formal context K with a confidence threshold T is a set F (K) of all fuzzy concepts of K with the partial order with the confidence threshold T .
Definition 5. The similarity of a fuzzy formal concept K1= (ϕ(A1), B1) and its subconcept K2 = (ϕ(A2), B2) is defined as E(K1, K2) = ||ϕϕ((AA11))∪∩ϕϕ((AA22))|| , where ∩ and ∪ refer intersection and union operators on fuzzy sets, respectively.
Figure 2 gives the traditional concept lattice generated from Table 1(a), in which crisp values “Yes” and “No” are used instead of membership values. Figure 3 gives the fuzzy concept lattice generated from the fuzzy formal context given in Table 1(b). As shown from the gfiures, the fuzzy concept lattice can provide additional information, such as membership values of objects in each fuzzy formal concept and similarities of fuzzy formal concepts, that are important for the construction of concept hierarchy. {} {D1, D2,D3} {} As in traditional concept lattice, the fuzzy concept lattice generated using FFCA is sometimes quite complicated due to the large number of fuzzy formal concepts generated. Since the formal concepts are generated mathematically, objects that have small differences in terms of attribute values are classiefid into distinct formal concepts. At a higher level, such objects should belong to the same concept when they are interpreted by human.
Based on this observation, we propose to cluster formal concepts into conceptual clusters using fuzzy conceptual clustering, which have the following properties: – Each conceptual cluster is a sublattice extracted from the fuzzy concept lattice. – A formal concept must belong to at least one conceptual cluster, but it can also belong to more than one conceptual cluster. This property is derived from the characteristic of concepts that an object can belong to more than one concept. For example, a scientific document can belong to more than one research area.
Conceptual clusters are generated based on the premise that if a formal concept A belongs to a conceptual cluster R, then its subconcept Balso belongs to R if B is similar to A. We can use a similarity confidence threshold Ts to determine whether two concepts are similar or not.
Definition 6. A conceptual cluster of a concept lattice K with a similarity confidence threshold Ts is a sublattice SK of K which has the following properties: 1. SK has a supremum concept CS that is not similar to any of its superconcepts. 2. Any concept C6=CS in SK must have at least one superconcept C0 ∈ SK such that E(C, C0) > Ts.
Figures 4 and 5 show the conceptual clusters that are generated from the fuzzy concept lattice given in Figure 3 with the similarity condfience thresholds Ts = 0.4 and Ts = 0.5 respectively.
Algorithm: Conceptual Cluster Generation Input: Starting concept CS of concept lattice F (K) and a similarity threshold TS Output: A set of generated conceptual clusters SC Process: 1: SC ← {} 2: F 0(K) ← An empty concept lattice 3: Add CS to F 0(K) 4: for each subconcept C0 of CSin F (K) do 5: F 0(C0) ← Conceptual Cluster Generation(C0, F (K), TS) 6: if E(CS, C0) = ||CCSS∩∪CC00|| < TS then 7: SC ← SC ∪{ F 0(C0)} 8: else 9: Insert F 0(C0) to F 0(K) with sup(F 0(K)) as a subconcept of CS 10: endif 11: endfor 12: SC ← SC ∪{F 0(K)}
As discussed in Section 5, fuzzy conceptual clustering generates a set of
conceptual clusters SC . To construct a concept hierarchy from the conceptual clusters,
we need to find the hierarchy relations from the clusters. We first define a concept
hierarchy [
Definition 7. A concept hierarchy is a poset (partially ordered set) (H,∠) where H is a finite set of concepts, and ∠ is a partial order on H.
Hence, to construct a concept hierarchy satisfying Definition 7, we must construct hierarchical relations among conceptual clusters as a partial order on SC .
C1.
Definition 8. Let C1 and C2be two conceptual clusters corresponding to two sublattices L1 and L2of a fuzzy concept lattice F (K). Let the fuzzy formal concept Ibe the supremum of L1, or I= sup(L1). C1is the subconcept of C2, denoted as C1 ∠ C2, if Iis the subconcept of any concept C0 ∈ L2, , or I ≤ C0 where ≤ is the partial order defined on F (K). Equivalently, C2is the superconcept of
From the FCA theory, a fuzzy concept lattice F (K) is a complete lattice. That is, any fuzzy concept CF on F (K)must have at least one superconcept unless CF = sup(F (K)). Therefore, the denfiition of superconcept and subconcept relations on conceptual clusters, which is given in Definition 8, assures that each conceptual cluster has at least one superconcept, unless it corresponds to the root node of the concept hierarchy generated. However, we must prove that the ∠ relation given in Definition 8 is a partial order.
Corollary 1. Let C1 and C2be two conceptual clusters corresponding to two sublattices L1 and L2of a fuzzy concept lattice F (K). Let the fuzzy formal concepts I1 and I2 be the supremums of L1and L2 respectively. If C1∠C2then I1 ≤ I2 where ≤ is the partial order defined on F (K).
Proof. Since C1∠C2, then ∃C0 ∈ L2 such that I1 ≤ C0. Since I2 = sup (L2), therefore C0 ≤ I2. Since ≤ is a partial order, then I1 ≤ I2.
From Corollary 1, we realize that the ∠ relation of conceptual clusters is equivalent to the ≤ relation of the supremums of the corresponding sublattices. Since ≤ relation is the partial order, the ∠ relation is a partial order. Therefore, the concept hierarchy generated using the superconcept and subconcept relations given in Definition 8 satisfies the requirements of a concept hierarchy given in Definition 7.
Figure 8 illustrates the hierarchical relations constructed from the conceptual clusters given in Figure 7. In Figure 7, the formal concept C4, which is the supremum of the corresponding sublattice of the conceptual cluster CK 3, is a subconcept of C1, which is a formal concept in the corresponding sublattice of the conceptual cluster CK 1. Therefore, CK 3 is a subconcept of CK 1.Similarly, hierarchical relations for other conceptual clusters are also generated to form the concept hierarchy that is shown in Figure 8. Each concept in the concept hierarchy is represented by a set of its attributes. The supremum and infimum of the lattice is considered as “Anything” and “Nothing” concepts, respectively.
CK1
We have applied the proposed approach to generate a concept hierarchy of
research areas from a citation database. The citation database is created from a set
of 1400 scientific documents on the research area “Information Retrieval”
published in 1987-1997 downloaded from Institute for Scientific Information (ISI)
[
The construction of fuzzy formal context is performed as follows. For each document, we have extracted the 10 most frequent citation keywords. We then construct a fuzzy formal context Kf = (G,M ,I), with G as the set of documents and M as the set of keywords. The membership value of a document D on a citation keyword CK in Kf is computed as μ (D, CK ) = n1 n2 where n1is the number of documents that cited D and contained CK and n2 is the number of documents that cited D.
From the constructed fuzzy formal context, FFCA is used to generate the fuzzy concept lattice. Next, the Fuzzy Concept Clustering is applied to the fuzzy concept lattice to generate a set of conceptual clusters. Each cluster generated is considered as a research area in the main research theme “Information Retrieval”. Each concept is represented by a set of keywords generated from documents belonging to the corresponding conceptual cluster. Then, Hierarchical Relation Generation is performed to construct a concept hierarchy of the research areas. The concept hierarchy reflects the taxonomy of research areas in the research theme “Information Retrieval”, in which a research area can be a super-area or sub-area of other research areas.
The concept hierarchy can also be converted into ontology for sharing and reuse with other systems. Figure 9 depicts a part of the generated concept hierarchy of research areas with the similarity threshold T = 0.7. For simplification, we only use the keyword that has the highest membership value to label the research area. However, users can browse more detail information of each research area as illustrated in Figure 9. 8
The performance of the concept hierarchy can be measured in order to evaluate
the performance of the proposed fuzzy FCA-based approach for conceptual
clustering. To do this, we use the relaxation error (RE) [
Evaluation Using Relaxation Error To evaluate the goodness of the clusters generated, we measure the relaxation error, which implies dissimilarities of items in a cluster based on attributes’ values. The relaxation error RE of a cluster C is defined as
n n RE(C) = X X X P (xi)P (xj )da(xi, xj )
a∈A i=1 j=1 where A is the set of attributes of items in C, P (xi) is the probability of item xi occurring in C and da(xi,xj ) is the distance of xi and xj on attribute a. In our application, da(xi,xj ) = |m(i,a) – m(j,a)| where m(i,a) and m(j,a) are the membership values of objects xi and xj on attribute a respectively. The cluster goodness G of cluster C is defined as
G(C) = 1 - RE (C)
As discussed in Section 7, we extract citation keywords of documents as their attributes. Since these attributes are used as descriptors for the generated clusters, we vary the number of keywords extracted to observe the effect of the keywords on cluster goodness. Besides, since COBWEB is considered as one of the most popular techniques for conceptual clustering, we also apply COBWEB to the citation database for performance comparison purposes. To use COBWEB, the membership values of keywords are replaced by appropriate nominal values. If the membership value is greater than 0.5, it is set as “Yes”, otherwise it is set as “No”.
Figure 10 shows the performance evaluation results on cluster goodness using FFCA and COBWEB while the number of extracted keywords is varied from 2 to 10. As shown in Figure 10, FFCA has achieved better cluster goodness than COBWEB. In addition, the experimental results have also shown that good cluster goodness is obtained when the number of extracted keywords is small. It is expected because smaller number of keywords used will cause smaller differences in objects in terms of keywords’ membership values. Therefore, the relaxation error will be smaller. However, as we will see later in Section 8.2, smaller number of extracted keywords will cause poor retrieval performance.
1 ss 0.8 edn 0.6 goo 0.4 r tse 0.2 u lC 0
N=2 N=4 N=6 N=8 N=10
Fuzzy FCA COBWEB The Average Uninterpolated Precision (AUP) is denfied as the sum of the precision value at each point (or node) in a hierarchical structure where a relevant item appears, divided by the total number of relevant items. For evaluating AUP, we have manually classiefid the downloaded documents into classes based on their research themes. For each class, we extract 5 most frequent keywords from the documents in the class. Then, we use these keywords as inputs to form retrieval queries and evaluate the retrieval performance using AUP. This is carried out as follows. For each document, we will generate a set of document keywords. There are two ways to generate document keywords. The first way is to use the set of keywords, known as attribute keywords, from each conceptual cluster as the document keywords. The second way is to use the keywords from each document as the document keywords. Then, we vectorize the document keywords and the input query, and calculate the vectors’ distance for measuring the retrieval performance.
Fig. 12. Performance evaluation on
AUP.
We refer the precision and AUP measured using the first way (i.e. using attribute keywords) to as Hierarchical Precision (P (H)) and Hierarchical Average Uninterpolated Precision (AUP(H)), as each concept inherits attribute keywords from its superconcepts. Whereas the precision and AUP measured using the second way (i.e. using keywords from documents) is referred to as Unconnected Precision (P (U )) and Unconnected Average Uninterpolated Precision (AUP(U)).
Figures 11 and 12 give the performance results for P (H)and P (U )and AUP(H) and AUP(U) using different numbers of extracted keywords N . From Figure 11, we found that when N gets larger, the performance on P (H), P (U ), AUP(H) and AUP(U) gets better. When N is larger than 5, the values of P (H) and P (U ) are considered as good performance (around 0.9 and 0.8 respectively). It has shown that the number of keywords extracted for conceptual clustering has affected the retrieval performance. In addition, the performance results on P (H) and AUP(H) are generally better than that of P (U ) and AUP(U) respectively. It implies that the attribute keywords generated for conceptual clusters are more appropriate concepts for representing the concept hierarchical structure. 9
In this paper, we have proposed a fuzzy FCA-based approach for conceptual clustering for automatic generation of concept hierarchy from uncertainty information. The proposed approach consists of the following steps: Fuzzy Formal Concept Analysis, Fuzzy Conceptual Clustering and Hierarchical Relation Generation. In addition, we have also discussed an application that applies the proposed approach to generate a concept hierarchy of research areas from an experimental citation database. The performance evaluation of the proposed approach has also been presented based on the evaluation of the concept hierarchy generated from the citation database.