The “Cognitive Master Teacher” is a result of discussions with teachers, members of educational institutions, government bodies and other thought leaders in the United States who have helped us shape its the requirements. It is conceived as a cloud-based and mobile-accessible personal agent that is readily available for teachers to use at anytime and assist them with various issues related to day-to-day teaching activities as well as professional development.

Data quality is a perennial problem for many enterprise data assets. To improve data quality, businesses often employ rule based data standardization systems in which domain experts code rules for handling important and prevalent patterns. Finding these patterns is laborious and time consuming, particularly for noisy or highly specialized data sets. It is also subjective to the persons determining these patterns. In this paper we present a tool to automatically mine patterns that can help in improving the efficiency and effectiveness of these data standardization systems. The automatically extracted patterns are used by the domain and knowledge experts for rule writing. We use a greedy algorithm to extract patterns that result in a maximal coverage of data. We further group the extracted patterns such that each group represents patterns that capture similar domain knowledge. We propose a similarity measure that uses input pattern semantics to group these patterns. We demonstrate the effectiveness of our method for standardization tasks on three real world datasets.

This paper considers the problem of vehicular traffic density estimation, utilizing the information cues present in the cumulative acoustic signal acquired from a roadside-installed single microphone. This cumulative signal comprises several noise signals such as tire noise, engine noise, engine-idling noise, occasional honks, and air turbulence noise of multiple vehicles. The occurrence and mixture weightings of these noise signals are determined by the prevalent traffic density conditions on the road segment. For instance, under a free-flowing traffic condition, the vehicles typically move with medium to high speeds and thereby produce mainly tire noise and air turbulence noise and less engine-idling noise and honks. For slow-moving congested traffic, the cumulative signal will largely be dominated by engine-idling noise and honks; air turbulence and tire noises will be inconspicuous. Furthermore, these various noise signals have spectral content that are very different from each other and, hence, can be used to discriminate between the different traffic density states that lead to them. Therefore, in this work, we extract the short-term spectral envelope features of the cumulative acoustic signals and model their class-conditional probability distributions, conditioned on one of the three broad traffic density states, i.e., Jammed (0-10 km/h), Medium-Flow (10-40 km/h), and Free-Flow (40 km/h and above) traffic. While these states are coarse measures of the average traffic speed, they nevertheless can provide useful traffic density information in the often-chaotic and nonlane-driven traffic conditions of the developing geographies, where other techniques (magnetic loop detectors) are inapplicable. Based on these learned distributions, we use a Bayes' classifier to classify the acoustic signal segments spanning a duration of 5-30 s, which results in a high classification accuracy of ~95%. Using a discriminative classifier such as a support vector machine (SVM) results in further classification accuracy gains over the Bayes' classifier.

A skyline query returns a set of objects that are not dominated by other objects. An object is said to dominate another if it is closer to the query than the latter on all factors under consideration. In this paper, we consider the case where the similarity measures may be arbitrary and do not necessarily come from a metric space. We first explore middleware algorithms, analyze how skyline retrieval for non-metric spaces can be done on the middleware backend, and lay down a necessary and sufficient stopping condition for middleware-based skyline algorithms. We develop the Balanced Access Algorithm, which is provably more IO-friendly than the state-of-the-art algorithm for skyline query processing on middleware and show that BAA outperforms the latter by orders of magnitude. We also show that without prior knowledge about data distributions, it is unlikely to have a middleware algorithm that is more IO-friendly than BAA. In fact, we empirically show that BAA is very close to the absolute lower bound of IO costs for middleware algorithms. Further, we explore the non-middleware setting and devise an online algorithm for skyline retrieval which uses a recently proposed value space index over non-metric spaces (AL-Tree [10]). The AL-Tree based algorithm is able to prune subspaces and efficiently maintain candidate sets leading to better performance. We compare our algorithms to existing ones which can work with arbitrary similarity measures and show that our approaches are better in terms of computational and disk access costs leading to significantly better response times.

Topic hierarchies are a popular method of summarizing the results obtained in response to a query in various search applications. However, topic hierarchies are rigid when they are pre-defined and somewhat unintuitive when they are dynamically generated by statistical techniques. In this paper, we propose an alternative approach to query disambiguation and result summarization by placing the results in set of contextual dimensions which can be viewed as facets. For the generic search scenario, we illustrate our approach by using three types of contextual dimensions, namely, concepts, features, and specializations. We use NLP techniques and a data mining algorithm to select distinct contexts.

Speed to market is critical to companies that are driven by sales in a competitive market. The earlier a potential customer can be approached in the decision making process of a purchase, the higher are the chances of converting that prospect into a customer. Traditional methods to identify sales leads such as company surveys and direct marketing are manual, expensive and not scalable. Over the past decade the World Wide Web has grown into an information-mesh, with most important facts being reported through Web sites. Several news papers, press releases, trade journals, business magazines and other related sources are on-line. These sources could be used to identify prospective buyers automatically. In this paper, we present a system called ETAP (Electronic Trigger Alert Program) that extracts trigger events from Web data that help in identifying prospective buyers. Trigger events are events of corporate relevance and indicative of the propensity of companies to purchase new products associated with these events. Examples of trigger events are change in management, revenue growth and mergers & acquisitions. The unstructured nature of information makes the extraction task of trigger events difficult. We pose the problem of trigger events extraction as a classification problem and develop methods for learning trigger event classifiers using existing classification methods. We present methods to automatically generate the training data required to learn the classifiers. We also propose a method of feature abstraction that uses named entity recognition to solve the problem of data sparsity. We score and rank the trigger events extracted from ETAP for easy browsing. Our experiments show the effectiveness of the method and thus establish the feasibility of automatic sales lead generation using the Web data.

Many practical applications require that distance measures to be asymmetric and context-sensitive. We introduce context-sensitive learnable asymmetric dissimilarity (CLAD) measures, which are defined to be a weighted sum of a fixed number of dissimilarity measures where the associated weights depend on the point from which the dissimilarity is measured. The parameters used in defining the measure capture the global relationships among the features. We provide an algorithm to learn the dissimilarity measure automatically from a set of user specified comparisons in the form "x is closer to y than to z" and study its performance. The experimental results show that the proposed algorithm outperforms other approaches due to the context sensitive nature of the CLAD measures.

We introduce a Bayesian model, BayesANIL, that is capable of estimating uncertainties associated with the labeling process. Given a labeled or partially labeled training corpus of text documents, the model estimates the joint distribution of training documents and class labels by using a generalization of the Expectation Maximization algorithm. The estimates can be used in standard classification models to reduce error rates. Since uncertainties in the labeling are taken into account, the model provides an elegant mechanism to deal with noisy labels. We provide an intuitive modification to the EM iterations by re-estimating the empirical. distribution in order to reinforce feature values in unlabeled data and to reduce the influence of noisily labeled examples. Considerable improvement in the classification accuracies of two popular classification algorithms on standard labeled data-sets with and without artificially introduced noise, as well as in the presence and absence of unlabeled data, indicates that this may be a promising method to reduce the burden of manual labeling.

We propose a method for hierarchical clustering based on the decision tree approach. As in the case of supervised decision tree, the unsupervised decision tree is interpretable in terms of rules, i.e., each leaf node represents a cluster, and the path from the root node to a leaf node represents a rule. The branching decision at each node of the tree is made based on the clustering tendency of the data available at the node. We present four different measures for selecting the most appropriate attribute to be used for splitting the data at every branching node (or decision node), and two different algorithms for splitting the data at each decision node. We provide a theoretical basis for the approach and demonstrate the capability of the unsupervised decision tree for segmenting various data sets. We also compare the performance of the unsupervised decision tree with that of the supervised one.

Data presented on commerce sites runs into thousands of pages, and is typically delivered from multiple back-end sources. This makes it difficult to identify incorrect, anomalous, or interesting data such as $9.99 air fares, missing links, drastic changes in prices and addition of new products or promotions. We describe a system that monitors Web sites automatically and generates various types of reports so that the content of the site can be monitored and the quality maintained. The solution designed and implemented by us consists of a site crawler that crawls dynamic pages, an information miner that learns to extract useful information from the pages based on examples provided by the user, and a reporter that can be configured by the user to answer specific queries. The tool can also be used for identifying price trends and new products or promotions at competitor sites. A pilot run of the tool has been successfully completed at the ibm.com site.

Clustering algorithms typically operate on a feature vector representation of the data and find clusters that are compact with respect to an assumed (dis)similarity measure between the data points in feature space. This makes the type of clusters identified highly dependent on the assumed similarity measure. Building on recent work in this area, we formally define a class of spatially varying dissimilarity measures and propose algorithms to learn the dissimilarity measure automatically from the data. The idea is to identify clusters that are compact with respect to the unknown spatially varying dissimilarity measure. Our experiments show that the proposed algorithms are more stable and achieve better accuracy on various textual data sets when compared with similar algorithms proposed in the literature.

Organizing Web search results into a hierarchy of topics and sub-topics facilitates browsing the collection and locating results of interest. In this paper, we propose a new hierarchical monothetic clustering algorithm to build a topic hierarchy for a collection of search results retrieved in response to a query. At every level of the hierarchy, the new algorithm progressively identifies topics in a way that maximizes the coverage while maintaining distinctiveness of the topics. We refer the proposed algorithm to as DisCover. Evaluating the quality of a topic hierarchy is a non-trivial task, the ultimate test being user judgment. We use several objective measures such as coverage and reach time for an empirical comparison of the proposed algorithm with two other monothetic clustering algorithms to demonstrate its superiority. Even though our algorithm is slightly more computationally intensive than one of the algorithms, it generates better hierarchies. Our user studies also show that the proposed algorithm is superior to the other algorithms as a summarizing and browsing tool.

A typical content-based image retrieval (CBIR) system would need to handle the vagueness in the user queries as well as the inherent uncertainty in image representation, similarity measure, and relevance feedback. We discuss how fuzzy set theory can be effectively used for this purpose and describe an image retrieval system called FIRST (fuzzy image retrieval system) which incorporates many of these ideas. FIRST can handle exemplar-based, graphical-sketch-based, as well as linguistic queries involving region labels, attributes, and spatial relations. FIRST uses fuzzy attributed relational graphs (FARGs) to represent images, where each node in the graph represents an image region and each edge represents a relation between two regions. The given query is converted to a FARG, and a low-complexity fuzzy graph matching algorithm is used to compare the query graph with the FARGs in the database. The use of an indexing scheme based on a leader clustering algorithm avoids an exhaustive search of the FARG database. We quantify the retrieval performance of the system in terms of several standard measures.

Conventional clustering algorithms such as K-means and SAHN (also known as AHC) have been well studied and used in the information retrieval community for clustering text documents. More recently, efforts have been made to cluster documents and words simultaneously. The FCCM algorithm due to Oh et al. is a fuzzy clustering algorithm that maximizes the co-occurrence of categorical attributes (keywords) and the individual patterns (documents) in clusters. However, this algorithm poses certain problems when the number of documents or the number of words is very large. In this paper, we modify the FCCM algorithm so that it can be used to cluster large text corpora. Our experiments show that the modified algorithm is scalable and produces meaningful clusters. We also show the relation between FCCM and the Spherical K-Means (SKM) algorithm and introduce the Spherical Fuzzy c-Means (SFCM) algorithm.

Structural information (such as layout and look-and-feel) has been extensively used in the literatuce for extraction of interesting or relevant data, efficient storage, and query optimization. Traditionally, tree models (such as DOM trees) have been used to represent structural information, especially in the case of HTML and XML documents. However, computation of structural similarity between documents based on the tree model is computationally expensive. In this paper, we propose an alternative scheme for representing the structural information of documents based on the paths contained in the corresponding tree model. Since the model includes partial information about parents, children and siblings, it allows us to define a new family of meaningful (and at the same time computationally simple) structural similarity measures. Our experimental results based on the SIGMOD XML data set as well as HTML document collections from ibm.com, dell.com, and amazon.com show that the representation is powerful enough to produce good clusters of structurally similar pages.

Finding the right set of target customers for a given product is an important problem in business-to-consumer (B2C) e-commerce. We propose an approach to solve this problem based on product attributes. Our approach is based on the assumption that the interest of a customer in a product depends on the customer's interest towards its attributes. We use a collection of membership estimators to compute the degree to which a customer might be interested in a product. Each estimator is based on a particular product attribute, and takes into consideration purchase information about other products that are similar to the given one from the point of view of the attribute. Thus, each estimator generates a membership value for each customer in the target customer set based on a specific attribute. We then use these memberships and other customer information to predict the target customers. Our experimental results show a significant improvement in prediction accuracy when the proposed approach is used.

% & ' )( * + , -( .(/ 10 % 2 3 4 ( 5 '6 7 8 9 : ; 2 < = > ( ?

We present a technique for simultaneously mining Web navigation patterns and maximally frequent context-sensitive itemsets (URL associations) from the historic user access data stored in Web server logs. A new hierarchical clustering technique that exploits the symbiosis between clusters in feature space and genetic biological niches in nature, called Hierarchical Unsupervised Niche Clustering (H-UNC) is presented. We use H-UNC as part of a complete system of knowledge discovery in Web usage data. Our approach does not necessitate fixing the number of clusters in advance, is insensitive to initialization, can handle noisy data, general non-differentiable similarity measures, and automatically provides profiles at multiple resolution levels. Our experiments show that our algorithm is not only capable of extracting meaningful user profiles on real Web sites, but also discovers associations between distinct URL pages on a site, with no additional cost. Unlike content based association methods, our approach discovers associations between different Web pages based only on the user access patterns and not on the page content. Also, unlike traditional context-blind association discovery methods, H-UNC discovers context-sensitive associations which are only meaningful within a limited context/user profile.

Clustering techniques find a collection of subsets of a data set such that the collection satisfies a criterion that is dependent on a relation defined on the data set. The underlying relation is traditionally assumed to be symmetric. However, there exist many practical scenarios where the underlying relation is asymmetric. One example of an asymmetric relation in text analysis is the inclusion relation, i.e., the inclusion of the meaning of a block of text in the meaning of another block. In this paper, we consider the general problem of clustering of asymmetrically related data and propose an algorithm to cluster such data. To demonstrate its usefulness, we consider two applications in text mining: (1) summarization of short documents, and (2) generation of a concept hierarchy from a set of documents. Our experiments show that the performance of the proposed algorithm is superior to that of more traditional algorithms.

This paper introduces generalised disjunctive association rules such as "People who buy bread also buy butter jam", and "People who buy either raincoats or umbrellas also buy flashlights". A generalised disjunctive association rule allows the disjunction of conjuncts, "People who buy jackets also buy bow ties or neckties and tiepins". Such rules capture contextual inter-relationships among items.Given a context (antecedent), there may be a large number of generalised disjunctive association rules that satisfy the minsupp and minconf constraints. It is computationally expensive to find all such rules. We present algorithm thrifty traverse which borrows concepts such as subsumption from propositional logic to mine a subset of such rules in a computationally feasible way. We experimented with our algorithm on US census data as well as transaction data from a grocery superstore to demonstrate its computational feasibility, utility and scalability.

Traditional hand-written word recognition approaches use character recognition algorithms in the first stage that return confidences in each character under consideration for each segment in the hand-written word. These confidences are used in the second stage to compute a match score between the segmented hand-written word and a given character string. We explore an alternative approach where we view the first stage as a membership assignment process, rather than a character recognition process. The memberships are assigned based on the notion of typicality, and are not relative as in the case of a probabilistic framework. To generate the membership values, we use a robust clustering algorithm that can determine the number of prototypes required to model each character class in a robust and parsimonious manner. Each prototype represents a subclass of the character class. Our experimental results show that when used in conjunction with the proposed approach to word recognition, the memberships generated in this manner produce word recognition results that compare favorably with those of other methods.

This paper presents new algorithms-fuzzy c-medoids (FCMdd) and robust fuzzy c-medoids (RFCMdd)-for fuzzy clustering of relational data. The objective functions are based on selecting c representative objects (medoids) from the data set in such a way that the total fuzzy dissimilarity within each cluster is minimized. A comparison of FCMdd with the well-known relational fuzzy c-means algorithm (RFCM) shows that FCMdd is more efficient. We present several applications of these algorithms to Web mining, including Web document clustering, snippet clustering, and Web access log analysis.

Graphs are very powerful and widely used representational tools in computer applications. We present a relaxation approach to (sub)graph matching based on a fuzzy assignment matrix. The algorithm has a computational complexity of O(n/sup 2/m/sup 2/) where n and m are the number of nodes in the two graphs being matched, and can perform both exact and inexact matching. To illustrate the performance of the algorithm, we summarize the results obtained for more than 12 000 pairs of graphs of varying types (weighted graphs, attributed graphs, and noisy graphs). We also compare our results with those obtained using the graduated assignment algorithm.

We present a new unsupervised robust clustering algorithm that can successfully find dense areas (clusters) in feature space and determine their number. The clustering problem is converted to a multimodal function optimization problem within the context of genetic niching. The niche peaks, which constitute the final cluster centers, are identified based on deterministic crowding (DC). The problem of crossover interactions in DC is eliminated by restricting the mating to members of the same niche only. Finally, the correct number of niche peaks or cluster centers is extracted from the final population. Genetic optimization makes our approach much less prone to suboptimal solutions than other objective function based approaches, and frees it from the necessity of an analytical derivation of the prototypes. As a result, our approach can handle a vast array of general subjective, even non-metric dissimilarities, and is thus useful in many applications such as Web and data mining. Additionally, the use of robust weights makes it less sensitive to the presence of noise than most traditional unsupervised clustering techniques.

Clustering algorithms such as the K-means algorithm and the fuzzy C-means algorithm are based on the minimization of the trace of the (fuzzy) within-fluster scatter matrix. In this paper, we explore the use of determinant (volume) criteria for clustering. We derive an algorithm called the minimum scatter volume (MSV) algorithm, that minimizes the scatter volume, and another algorithm called the minimum cluster volume (MCV) that minimizes the sum of the volumes of the individual clusters. The behavior of MSV is shown to be similar to that of K-means, whereas MCV is more versatile.

This paper addresses three major issues associated with conventional partitional clustering, namely, sensitivity to initialization, difficulty in determining the number of clusters, and sensitivity to noise and outliers. The proposed robust competitive agglomeration (RCA) algorithm starts with a large number of clusters to reduce the sensitivity to initialization, and determines the actual number of clusters by a process of competitive agglomeration. Noise immunity is achieved by incorporating concepts from robust statistics into the algorithm. RCA assigns two different sets of weights for each data point: the first set of constrained weights represents degrees of sharing, and is used to create a competitive environment and to generate a fuzzy partition of the data set. The second set corresponds to robust weights, and is used to obtain robust estimates of the cluster prototypes. By choosing an appropriate distance measure in the objective function, RCA can be used to find an unknown number of clusters of various shapes in noisy data sets, as well as to fit an unknown number of parametric models simultaneously. Several examples, such as clustering/mixture decomposition, line/plane fitting, segmentation of range images, and estimation of motion parameters of multiple objects, are shown.

This correspondence points out several published errors in replicates of the well-known iris data, which was collected by Anderson (1935) but first published by Fisher (1936).

In this letter, we show that the Gustafson-Kessel (G-K) algorithm (1979) and the original adaptive fuzzy clustering (AFC) algorithm can be thought of as special cases of a more general algorithm. Our analysis shows that the G-K algorithm is better suited for ellipsoidal clusters of equal volume, whereas the original AFC algorithm is better suited for linear clusters. We also discuss a new variation of these algorithms, which can be used to improve the results of the G-K and AFC algorithms in some cases.

Computer vision applications often involve measuring properties of objects in images. Typically, thresholding or segmentation techniques are used to obtain crisp object boundaries before object properties are computed. In this correspondence, we explore the possibility of using fuzzy definitions for measuring object properties without having to make crisp decisions about object boundaries prematurely. We present theorems which indicate that the use of fuzzy definitions to measure properties in intensity-based image analysis almost always gives accurate results. We also present experimental evidence and reasoning which show that fuzzy definitions are not always useful in feature-based methods.

Clustering methods need to be robust if they are to be useful in practice. In this paper, we analyze several popular robust clustering methods and show that they have much in common. We also establish a connection between fuzzy set theory and robust statistics, and point out the similarities between robust clustering methods and statistical methods such as the weighted least-squares technique, the M estimator, the minimum volume ellipsoid algorithm, cooperative robust estimation, minimization of probability of randomness, and the epsilon contamination model. By gleaning the common principles upon which the methods proposed in the literature are based, we arrive at a unified view of robust clustering methods. We define several general concepts that are useful in robust clustering, state the robust clustering problem in terms of the defined concepts, and propose generic algorithms and guidelines for clustering noisy data. We also discuss why the generalized Hough transform is a suboptimal solution to the robust clustering problem.

In this paper, we propose a robust approach to image enhancement based on fuzzy logic that addresses the seemingly conflicting goals of image enhancement: (i) removing impulse noise, (ii) smoothing out nonimpulse noise, and (iii) enhancing (or preserving) edges and certain other salient structures. We derive three different filters for each of the above three tasks using the weighted (or fuzzy) least squares (LS) method, and define the criteria for selecting each of the three filters. The criteria are based on the local context, and they constitute the antecedent clauses of the fuzzy rules. The overall result of the fuzzy rule-based system is the combination of the results of the individual filters, where each result contributes to the degree that the corresponding antecedent clause is satisfied. This approach gives us a powerful and flexible image enhancement paradigm. Results of the proposed method on several types of images are compared with those of other standard techniques.

We present a new clustering algorithm that addresses two major issues associated with conventional partitional clustering: the difficulty in determining the number of clusters, and the sensitivity to noise and outliers. The proposed algorithm determines the number of clusters by a process of competitive agglomeration. Noise immunity is achieved by integrating concepts from robust statistics into the algorithm. The proposed approach can incorporate different distance measures in the objective function to find an unknown number of clusters of various types including lines, planes and surfaces.

In this paper, we introduce a shell-clustering algorithm for ellipsoidal clusters based on the so-called "radial distance" which can be easily extended to superquadric clusters. We compare our algorithm with other algorithms in the literature that are based on the algebraic distance, the approximate distance, the normalized radial distance, and the exact distance. We evaluate the performance of each algorithm on two-dimensional data sets containing "scattered" ellipses, partial ellipses, outliers, and ellipses of disparate sizes, and summarize the relative strengths and weaknesses of each algorithm.

Recently, the possibilistic C-means algorithm (PCM) was proposed to address the drawbacks associated with the constrained memberships used in algorithms such as the fuzzy C-means (FCM). In this issue, Barni et al. (1996) report a difficulty they faced while applying the PCM, and note that it exhibits an undesirable tendency to converge to coincidental clusters. The purpose of this paper is not just to address the issues raised by Barni et al., but to go further and analytically examines the underlying principles of the PCM and the possibilistic approach, in general. We analyze the data sets used by Barni et al. and interpret the results reported by them in the light of our findings.

Using fuzzy set theory, we develop a fuzzy rule-based system to perform some of the most common tasks of image enhancement: removing impulsive noise; smoothing nonimpulsive noise; and enhancing edges. Three different filters for each task and the selection criteria based on local information are derived. The selection criteria constitute the antecedent clauses of the fuzzy rules, and the corresponding filters constitute the consequent clauses of the fuzzy rules. The overall result of the fuzzy rule-based system is computed as the combination of the results of the individual filters, where each result contributes to the degree that the corresponding antecedent clause is satisfied. This approach gives us a powerful and flexible image enhancement paradigm. We present results on several types of images such as retinal and chromosome images.>

We propose a fuzzy rule-based approach to image enhancement to address its seemingly conflicting goals: (a) removing impulse noise, (b) smoothing out nonimpulse noise, and (c) enhancing edges or certain other salient features. Three different filters for each task are derived using the weighted least mean squared method. Criteria for selecting each filter are defined. The criteria are based on the local context as well as the particular situation. They constitute the antecedent clauses of the fuzzy rules, and the corresponding filters constitute the consequent clauses of the fuzzy rules. The overall result of the fuzzy rule-based system is computed as the combination of the results of the individual filters, where each result contributes to the degree that the corresponding antecedent clause is satisfied. This approach gives us a powerful and flexible image enhancement paradigm. Experimental results are presented.

Traditionally, prototype-based fuzzy clustering algorithms such as the Fuzzy C Means (FCM) algorithm have been used to find "compact" or "filled" clusters. Recently, there have been attempts to generalize such algorithms to the case of hollow or "shell-like" clusters, i.e., clusters that lie in subspaces of feature space. The shell clustering approach provides a powerful means to solve the hitherto unsolved problem of simultaneously fitting multiple curves/surfaces to unsegmented, scattered and sparse data. In this paper, we present several fuzzy and possibilistic algorithms to detect linear and quadric shell clusters. We also introduce generalizations of these algorithms in which the prototypes represent sets of higher-order polynomial functions. The suggested algorithms provide a good trade-off between computational complexity and performance, since the objective function used in these algorithms is the sum of squared distances, and the clustering is sensitive to noise and outliers. We show that by using a possibilistic approach to clustering, one can make the proposed algorithms robust.>

Shell clustering algorithms are ideally suited for computer vision tasks such as boundary detection and surface approximation, particularly when the boundaries have jagged or scattered edges and when the range data is sparse. This is because shell clustering is insensitive to local aberrations, it can be performed directly in image space, and unlike traditional approaches it does assume dense data and does not use additional features such as curvatures and surface normals. The shell clustering algorithms introduced in Part I of this paper assume that the number of clusters is known, however, which is not the case in many boundary detection and surface approximation applications. This problem can be overcome by considering cluster validity. We introduce a validity measure called surface density which is explicitly meant for the type of applications considered in this paper, we show through theoretical derivations that surface density is relatively invariant to size and partiality (incompleteness) of the clusters. We describe unsupervised clustering algorithms that use the surface density measure and other measures to determine the optimum number of shell clusters automatically, and illustrate the application of the proposed algorithms to boundary detection in the case of intensity images and to surface approximation in the case of range images.>

Evidence Aggregation Networks based on multiplicative fuzzy hybrid operators were introduced by Krishnapuram and Lee. They have been used for image segmentation, pattern recognition, and general multicriteria decision making. One of the drawbacks to these networks is that the training is complex and quite time consuming. In this article, we modify these aggregation networks to implement additive fuzzy hybrid connectives. We study the theoretical properties of two classes of such aggregation operators, one where the union and intersection components are based on multiplication, and the other where these components are derived from Yager connectives. These new networks have similar excellent properties such as backpropagation training and node interpretability for decision making under uncertainty as do their multiplicative precursors. They also have the advantage that training is easier since the derivatives of the additive hybrid operators are not as complex in form. the appropriate training algorithms are derived, and several examples given to illustrate the properties of the networks. © 1994 John Wiley & Sons, Inc.

In image analysis, there have been few effective procedures that deal with a wide class of imagery acquired by different sensors under different environmental conditions. The success of a given classification algorithm is dependent upon pattern familiarity, background, and the image acquisition process. Thus, with the inaccuracies in the acquisition process, as well as incomplete or incorrect knowledge about the pattern classes, one cannot place complete confidence in the classifier outcome. There has been increasing success in making decisions under such uncertain conditions by using a rule-based approach with effective uncertainty management, which involves identifying the causes of uncertainty and developing mathematical models for the same. These are incorporated into the rule structure so that the result would be a set of choices or decisions, with a set of associated certainty values or confidences. This paper proposes a "unified" methodology to combine the uncertainties associated with evidence for a given proposition, which is then systematically propagated down the decision tree. The relative importance of propositions as well as the rules themselves have also been considered. Finally, the methodology has been applied to an ATR problem and the results, when compared to some existing methods, show the overall effectiveness of this approach.>

The clustering problem is cast in the framework of possibility theory. The approach differs from the existing clustering methods in that the resulting partition of the data can be interpreted as a possibilistic partition, and the membership values can be interpreted as degrees of possibility of the points belonging to the classes, i.e., the compatibilities of the points with the class prototypes. An appropriate objective function whose minimum will characterize a good possibilistic partition of the data is constructed, and the membership and prototype update equations are derived from necessary conditions for minimization of the criterion function. The advantages of the resulting family of possibilistic algorithms are illustrated by several examples.>

Properties of objects and spatial relations between objects play an important role in rule-based approaches for high-level vision. The partial presence or absence of such properties and relationships can supply both positive and negative evidence for region labeling hypotheses. Similarly, fuzzy labeling of a region can generate new hypotheses pertaining to the properties of the region, its relation to the neighboring regions, and, finally, hypotheses pertaining to the labels of the neighboring regions. A unified methodology that can be used to characterize both properties and spatial relationships of object regions in a digital image is presented. The methods proposed for computing the properties and relations of image regions can be used to arrive at more meaningful decisions about the contents of the scene.>

The use of recurrent neural networks for skeletonization and thinning of binary images is investigated. The networks are trained to learn a deletion rule and they iteratively delete object pixels until only the skeleton remains. Recurrent neural network architectures that implement a variety of thinning algorithms, such as the Rosenfeld-Kak algorithm and the Wang-Zhang (WZ) algorithm, are presented. A modified WZ algorithm which produces skeletons that are intuitively more pleasing is introduced.

Two morphological methods for edge detection in range images are proposed. The first method uses the opening and closing residues of structuring elements in orthogonal directions to detect roof and crease edges, and is essentially a morphological implementation of residue analysis techniques. The more general second method is based on a morphological version of the first derivative operator. This method utilizes dilation and erosion residues of structuring elements at different scales to reliably extract step edges along with roof edges and crease edges, and to classify each pixel as belonging to eight possible structure types: positive roof, negative roof, positive crease, negative crease, top of step, base of step, ramp, and constant surface. This method may be thought of as a morphological multiscale method.>

Fuzzy logic has been applied in many engineering disciplines. The problem of fuzzy logic inference is investigated as a question of aggregation of evidence. A fixed network architecture employing general fuzzy unions and intersections is proposed as a mechanism to implement fuzzy logic inference. It is shown that these networks possess desirable theoretical properties. Networks based on parameterized families of operators (such as Yager's union and intersection) have extra predictable properties and admit a training algorithm which produces sharper inference results than were earlier obtained. Simulation studies corroborate the theoretical properties.

The fuzzy c spherical shells (FCSS) algorithm is specially designed to search for clusters that can be described by circular arcs or, generally, by shells of hyperspheres. A new approach to the FCSS algorithm is presented. This algorithm is computationally and implementationally simpler than other clustering algorithms that have been suggested for this purpose. An unsupervised algorithm which automatically finds the optimum number of clusters is not known. It uses a cluster validity measure to identify good clusters, merges all compatible clusters, and eliminates spurious clusters to achieve the final results. Experimental results on several data sets are presented.

A fuzzy adaptive distance dynamic clusters (FADDC) algorithm, which is specially designed to search for clusters that lie in subspaces (such as lines, and (hyper)planes) is presented. One major drawback of all clustering algorithms is that the number of clusters has to be known a priori. A novel compatible cluster merging (CCM) technique, which finds the optimum number of clusters in an efficient way, is proposed. Such subspace clustering techniques may be used for character recognition and to obtain straight-line descriptions of an edge image. They may also be used to obtain planar approximations of 3-D (range) data. The effectiveness of the proposed algorithms in several such situations is demonstrated with real data.>

A variety of belief maintenance schemes for image analysis have been suggested and used to date. In the recent past, several researchers have suggested the use of the Dempster-Shafer theory of evidence for representation of belief. This approach appears to be particularly suited for knowledge-based image analysis systems because of its intuitively convincing ways of representing beliefs, support, plausibility, ignorance, dubiety, and a host of other measures that can be used for the purpose of decision making. It also provides a very attractive technique to combine these measures obtained from disparate knowledge sources. In this article, we show how the Dempster-Shafer theoretic concepts of refinement and coarsening can be used to aggregate and propagate evidence in a multi-resolution image analysis system based on a hierarchical knowledge base.

A technique for determining the distortion parameters (location and orientation) of general three-dimensional objects from a single range image view is introduced. The technique is based on an extension of the straight-line Hough transform to three-dimensional space. It is very efficient and robust, since the dimensionality of the feature space is low and since it uses range images directly (with no preprocessing such as segmentation and edge or gradient detection). Because the feature space separates the translation and rotation effects, a hierarchical algorithm to detect object rotation and translation is possible. The new Hough space can also be used as a feature space for discriminating among three-dimensional objects.>