Labelled clustering and its applications

Abstract

Clustering is a process of grouping a collection of objects. Clustering approaches can be broadly categorized into conventional and knowledge-based approaches. In a conventional approach, objects are typically represented as points in an n-dimensional space, and the essential ingredients of a clustering algorithm such as similarity measure and/or objective function to be optimized are implicitly represented. On the other hand, in knowledge-based approaches, the objects are typically described using linguistic concepts such as round, shape, color, red, etc., and the background knowledge contains goals of clustering, cluster validation criteria, etc. A well-known example of knowledge-based clustering is Michalski’s conceptual clustering. Here, the object descriptions are logical expressions of the form: [color=red] [shape=round] [size=medium] It is to be observed that the above logical expression is a conjunction of three primitive concepts: [color=red], [shape=round], and [size=medium]. The conceptual clustering algorithm operates on these descriptions, using the background knowledge, to generate clusters and their descriptions that optimize a lexical evaluation function. A second example of knowledge-based clustering is Shekar, Murty, and Krishna’s functional clustering. Even in this case, objects are described using linguistic concepts. However, the background knowledge now contains the knowledge regarding functionalities of various objects. More specifically, the knowledge contains information regarding various sub-concepts that are essential to realize a super-concept. For example, the concepts cutting, lathering, and mirroring are essential concepts to realize the concept shaving. Given a collection of objects described using the concepts such as cutting, the functional clustering algorithm generates clusters with the highest-level concepts (based on the knowledge) that can be realized as cluster descriptions. Clustering algorithms (both conventional and knowledge-based) described in the literature operate on unlabelled objects. More specifically, objects are described using the properties of the objects rather than the concepts that label them. For example, a cricket ball might be described as [color=red] [size=medium] [shape=round]. The clustering algorithm proposed in this thesis, on the other hand, operates on the labels of objects such as cricket-ball. The approach is based on the following fundamental observation: Humans tend to use the most appropriate general description to describe a collection of objects. For example, when we take a walk within a campus, we talk about cycles and scooters. On the other hand, while we stride along a main road, we worry about sound and air pollution caused by vehicles. Observe how the description has been generalized from cycles and scooters to vehicles. Similarly, if we watch from a balcony of our house, we see crows and sparrows, whereas we go for bird watching to a bird sanctuary. The proposed Deductive Clustering Approach (DCA), a knowledge-based clustering approach, operates on labelled objects to generate clusters and their descriptions. The approach utilizes the knowledge represented in the form of a hierarchy (more specifically, a rooted directed acyclic graph). Cluster descriptions generated by the DCA are the most plausible generalizations given the knowledge and a collection of input objects. Typically, the object labels correspond to the leaf nodes of the hierarchy. We have used logic as a framework for representing knowledge as well as to describe the clustering approach. We have proposed a modified first-order logic that characterizes the clustering approach. The proposed logic is a non-monotonic logic and has both proof theory and model theory. A formula denoting a cluster description along with the associated objects is a logical consequence of the proposed theory and hence the name deductive clustering. We have also described an algorithm to realize the DCA and implemented the same in the context of reviews drawn from ACM Computing Reviews. The source of domain knowledge is the Full Computing Reviews Classification Scheme. The DCA, here, can be viewed as a proof-theoretic approach to clustering. We have also investigated a model-theoretic approach to clustering. Here again, we use first-order logic as a framework to characterize clustering. We have defined the notion of maximal models to describe clusters. More specifically, we partition a collection of well-formed formulas, describing the proper axioms (that include domain knowledge as well as input objects), into three blocks: The maximal models are defined with respect to the set and each such maximal model defines a cluster. We remark that Ac constrains the number and nature of the generated clusters. We have proposed an algorithm to achieve this sort of clustering and investigated the same in the context of library books. The source of domain knowledge is the Dewey Decimal Classification Scheme. We have pointed out that labelled clustering tends to identify the most plausible general label of a collection of objects. Thus, labelled clustering can be viewed as an act of data abstraction. As a consequence, it finds applications in modeling databases. We have proposed labelled clustering as a framework to provide an extended semantic data model for databases. Such an extended semantic data model can facilitate not only answering structure-dependent queries such as “How good is a library with respect to the artificial intelligence area?” but also the comparison of databases. Specifically, we begin with a common hierarchy for a collection of databases and we cluster each database using a labelled clustering approach such as DCA with respect to this common hierarchy. We achieve the qualitative comparison of databases by comparing the respective cluster structures. We have implemented the proposed scheme in the context of library book databases. Another interesting application of labelled clustering is in the context of belief revision. The problem of belief revision is to keep a database of beliefs consistent (in other words, there should not be any contradiction in the collection of beliefs) and is an active field of research within artificial intelligence. We have proposed the object-centered belief revision, in which the belief revision can be restricted to a small number of related clusters of beliefs. Specifically, we have proposed an axiomatic approach to model belief revision. In order to represent knowledge that includes default knowledge syntactically as well as semantically using logic, we have used two implication operators: • the conventional material implication operator of first-order logic for ISA relationships, and • > (a logical operator introduced to deal with default relationships). The problem of multiple inheritance with exceptions is handled by defining non-monotonic transitive closures and using the same in defining the non-monotonic inference rule (in lieu of modus ponens of first-order logic). The proposed logical system is a 3-tier system that deals with contexts and reasons consistently with the most recent beliefs. In order to achieve reasoning with the most recent beliefs, we represent input beliefs in a reified form that accounts for contextual as well as temporal information. The proposed belief revision model has been employed to model the beliefs about patients of a physician in allopathy and Ayurveda contexts. Finally, we have provided pointers to further work along the following lines: 1. Extending the DCA to handle default knowledge. This is very useful in achieving inductive question-answering. 2. Providing a framework for learning default knowledge. 3. Providing a formalization of the maximal model. 4. Extending the 3-tier logical system to model human decision-making.