Data Mining: An Overview from a Database Perspective <s> Clustering analysis <s> Conceptual clustering is an important way to sununarize data in an understandable manner. However, the recency of the conceptual clustering paradigm has allowed little exploration of conceptual clustering as a means of improving performance. This paper presents COBWEB, a conceptual clustering system that organizes data to maximize inference abilities. It does this by capturing attribute inter-correlations at classification tree nodes and generating inferences as a by-product of classification. Results from the domains of soybean and thyroid disease diagnosis support the success of this approach. <s> BIB001 </s> Data Mining: An Overview from a Database Perspective <s> Clustering analysis <s> The authors' perspective of database mining as the confluence of machine learning techniques and the performance emphasis of database technology is presented. Three classes of database mining problems involving classification, associations, and sequences are described. It is argued that these problems can be uniformly viewed as requiring discovery of rules embedded in massive amounts of data. A model and some basic operations for the process of rule discovery are described. It is shown how the database mining problems considered map to this model, and how they can be solved by using the basic operations proposed. An example is given of an algorithm for classification obtained by combining the basic rule discovery operations. This algorithm is efficient in discovering classification rules and has accuracy comparable to ID3, one of the best current classifiers. > <s> BIB002
The process of grouping physical or abstract objects into classes of similar objects is called clustering or unsupervised classi cation. Clustering analysis helps construct meaningful partitioning of a large set of objects based on a \divide and conquer" methodology which decomposes a large scale system into smaller components to simplify design and implementation. As a data mining task, data clustering identi es clusters, or densely populated regions, according to some distance measurement, in a large, multidimensional data set. Given a large set of multidimensional data points, the data space is usually not uniformly occupied by the data points. Data clustering identi es the sparse and the crowded places, and hence discovers the overall distribution patterns of the data set. Data clustering has been studied in statistics   , machine learning 31, 32], spatial database 11], and data mining     areas with di erent emphases. As a branch of statistics, clustering analysis has been studied extensively for many years, mainly focused on distance-based clustering analysis. Systems based on statistical classi cation methods, such as AutoClass 18] which uses a Bayesian classi cation method, have been used in clustering in real world databases with reported success. The distance-based approaches assume that all the data points are given in advance and can be scanned frequently. They are global or semi-global methods at the granularity of data points. That is, for each clustering decision, they inspect all data points or all currently existing clusters equally no matter how close or far away they are, and they use global measurements, which require scanning all data points or all currently existing clusters. Hence they do not have linear scalability with stable clustering quality. In machine learning, clustering analysis often refers to unsupervised learning, since which classes an object belongs to are not prespeci ed, or conceptual clustering, because the distance measurement may not be based on geometric distance, but be based on that a group of objects represents a certain conceptual class. One needs to de ne a measure of similarity between the objects and then apply it to determine classes. Classes are de ned as collections of objects whose intraclass similarity is high and interclass similarity is low. The method of clustering analysis in conceptual clustering is mainly based on probability analysis. Such approaches, represented by BIB001  , make the assumption that probability distributions on separate attributes are statistically independent of each other. This assumption is, however, not always true since correlation between attributes often exists. Moreover, the probability distribution representation of clusters makes it very expensive to update and store the clusters. This is especially so when the attributes have a large number of values since their time and space complexities depend not only on the number of attributes, but also on the number of values for each attribute. Furthermore, the probability-based tree (such as 31]) that is built to identify clusters is not height-balanced for skewed input data, which may cause the time and space complexity to degrade dramatically. Clustering analysis in large databases has been studied recently in the database community. The PAM algorithm 48] nds k clusters in n objects by rst nding a representative object for each cluster. Such a representative, which is the most centrally located point in a cluster, is called a medoid. After selecting k medoids, the algorithm repeatedly tries to make a better choice of medoids by analyzing all possible pairs of objects such that one object is a medoid and the other is not. The measure of clustering quality is calculated for each such combination. The best choice of points in one iteration is chosen as the medoids for the next iteration. The cost of a single iteration is O(k(n ? k)  ). It is therefore computationally ine cient for large values of n and k. The CLARA algorithm 48] accomplishes the same task whereas it utilizes the technique of sampling. Only a small portion of the real data is chosen as a representative of the data and medoids are chosen from this sample using PAM. The idea is that if the sample is selected in a fairly random manner, then it correctly represents the whole data set, and the representative objects (medoids) chosen will therefore be similar to those chosen from the whole data set. CLARA draws multiple samples and outputs the best clustering out of these samples. As expected, CLARA can deal with larger data sets than PAM. However, since CLARA searches for the best k medoids among the selected sample of the data set, it cannot nd the best clustering if any sampled medoid is not among the best k medoids. The CLARANS algorithm 62] tries to integrate PAM and CLARA by searching only the subset of the data set but not con ning itself to any sample at any given time. While CLARA has a xed sample at every stage of the search, CLARANS draws a sample with some randomness in each step of the search. The clustering process can be presented as searching a graph where every node is a potential solution, i.e., a set of k medoids. The clustering obtained after replacing a single medoid is called the neighbor of the current clustering. If a better neighbor is found, CLARANS moves to the neighbor's node and the process is started again, otherwise the current clustering produces a local optimum. If the local optimum is found, CLARANS starts with new randomly selected nodes in search for a new local optimum. CLARANS has been experimentally shown to be more e ective than both PAM and CLARA. The computational complexity of every iteration in CLARANS is basically linearly proportional to the number of objects   . It should be mentioned that CLARANS can be used to nd the most natural number of clusters k nat . A heuristic is adopted in 62] to determine k nat , which uses silhouette coe cients BIB002 , introduced by Kaufman and Rousseeuw 48] . CLARANS also enables the detection of outliers, e.g., points that do not belong to any cluster. Based upon CLARANS, two spatial data mining algorithms were developed in a fashion similar to the attribute-oriented induction algorithms developed for spatial data mining 56, 37]: spatial dominant approach, SD(CLARANS) and non-spatial dominant approach, NSD(CLARANS). Both algorithms assume that the user speci es the type of the rule to be mined and relevant data through a learning request in a similar way as DBMiner 40] . Experiments show that the method can be used to cluster reasonably large data sets, such as houses in the Vancouver area, and the CLARAN algorithm outperforms PAM and CLARA.