Oracle Data Mining Concepts 10g Release 1 (10.1) Part Number B1069801 


View PDF 
This chapter describes descriptive models, that is, the unsupervised learning functions. These functions do not predict a target value, but focus more on the intrinsic structure, relations, interconnectedness, etc. of the data. The Oracle Data Mining interfaces support the following descriptive models and associated algorithms:
Function  Algorithm 

Clustering (Section 4.1) 
Enhanced kmeans (Section 4.1.1) 
Orthogonal Clustering (OCluster) Java interface only (Section 4.1.2)  
Association (Section 4.2) 
Apriori Algorithm (Section 4.2.4) 
Feature Extraction (Section 4.3) 
NonNegative Matrix Factorization (Section 4.3.1) 
Clustering is a technique useful for exploring data. It is particularly useful where there are many cases and no obvious natural groupings. Here, clustering data mining algorithms can be used to find whatever natural groupings may exist.
Clustering analysis identifies clusters embedded in the data. A cluster is a collection of data objects that are similar in some sense to one another. A good clustering method produces highquality clusters to ensure that the intercluster similarity is low and the intracluster similarity is high; in other words, members of a cluster are more like each other than they are like members of a different cluster.
Clustering can also serve as a useful datapreprocessing step to identify homogeneous groups on which to build predictive models. Clustering models are different from predictive models in that the outcome of the process is not guided by a known result, that is, there is no target attribute. Predictive models predict values for a target attribute, and an error rate between the target and predicted values can be calculated to guide model building. Clustering models, on the other hand, uncover natural groupings (clusters) in the data. The model can then be used to assign groupings labels (cluster IDs) to data points.
In ODM a cluster is characterized by its centroid, attribute histograms, and place in the clustering model hierarchical tree. ODM performs hierarchical clustering using an enhanced version of the kmeans algorithm and OCluster, an Oracle proprietary algorithm. The clusters discovered by these algorithms are then used to create rules that capture the main characteristics of the data assigned to each cluster. The rules represent the hyperboxes (bounding boxes) that envelop the data in the clusters discovered by the clustering algorithm. The antecedent of each rule describes the clustering bounding box. The consequent encodes the cluster ID for the cluster described by the rule. For example, for a data set with two attributes: AGE and HEIGHT, the following rule represents most of the data assigned to cluster 10:
The clusters are also used to generate a Bayesian probability model which is used during scoring for assigning data points to clusters.
The two clustering algorithms supported by ODM interfaces are
The kmeans algorithm is a distancebased clustering algorithm that partitions the data into a predetermined number of clusters (provided there are enough distinct cases). The kmeans algorithm works only with numerical attributes. Distancebased algorithms rely on a distance metric (function) to measure the similarity between data points. The distance metric is either Euclidean, Cosine, or Fast Cosine distance. (Cosine and Fast Cosine are supported in the DBMS_DATA_MINING version of kmeans only.) Data points are assigned to the nearest cluster according to the distance metric used.
Note: DBMS_DATA_MINING and the Java interface use different versions of the enhanced kmeans algorithm. The two implementations may give different results. 
ODM implements an enhanced version of the kmeans algorithm with the following features:
This incremental approach to kmeans avoids the need for building multiple kmeans models and provides clustering results that are consistently superior to the traditional kmeans.
The kMeans Clustering algorithm implementation in DBMS_DATA_MINING is a modified and enhanced version of the implementing in the Java interface. There is no upper limit on the number of attributes and target cardinality for this implementation of kMeans. The DBMS_DATA_MINING implementation will be the ODM implementation of the kMeans Clustering algorithm in future ODM releases. Table 41 summarizes the differences between the two implementations.
The choice between balanced and unbalanced approaches in the Java interface is controlled by the system parameter CL_ALG_SETTING_TREE_GROWTH in the ODM_CONFIGURATION table. The balanced approach is faster than the unbalanced approach, while the unbalanced approach generates models with smaller overall distortion.
In the Java interface, the kmeans algorithm works with numerical data only. As a result, if you need to cluster data with categorical attributes, you must explode the categorical attribute into multiple binary columns (one per unique value of the categorical attribute) before using kmeans. If you bin the data manually, you must bin the new binary columns after you have exploded them.
The DBMS_DATA_MINING supports both categorical and numerical data.
The kmeans algorithms work best with a moderate number of attributes (at most 100); however, there is no upper limit on the number of attributes and target cardinality for the DBMS_DATA_MINING implementation of kMeans.
Because traditional kmeans requires multiple passes through the data, it can be impractical for large data tables that don't fit in memory. In this case multiple expensive database scans would be required. ODM's enhanced kmeans requires at most one database scan. For data tables that don't fit in memory, the enhanced kmeans algorithm employs a smart summarization approach that creates a summary of the data table that can be stored in memory. This approach allows the enhanced kmeans algorithm to handle data tables of any size. The summarization scheme can be seen as a smart sampling approach that first identifies the main partitions in the data and then generates summary points for each partition in proportion to their share of the total data. Each summary point has a weight that accounts for the proportion of the data it represents.
The clusters discovered by enhanced kmeans are used to generate a Bayesian probability model that is then used during scoring (model apply) for assigning data points to clusters. The traditional kmeans algorithm can be interpreted as a mixture model where the mixture components are spherical multivariate normal distributions with the same variance for all components. A mixture model is a type of density model that includes several component functions (usually Gaussian) that are combined to provide a multimodal density.
In the mixture model created from the clusters discovered by enhanced kmeans, on the other hand, the mixture components are a product of independent normal distribution with potentially different variances. Because of this greater flexibility, the probability model created by enhanced kmeans provides a better description of the underlying data than the underlying model of traditional kmeans.
The OCluster algorithm supports Orthogonal Partitioning Clustering; OCluster creates a hierarchical gridbased clustering model, that is, it creates axisparallel (orthogonal) partitions in the input attribute space. The algorithm operates recursively. The resulting hierarchical structure represents an irregular grid that tessellates the attribute space into clusters. The resulting clusters define dense areas in the attribute space. The clusters are described by intervals along the attribute axes and the corresponding centroids and histograms. A parameter called sensitivity defines a baseline density level. Only areas with peak density above this baseline level can be identified as clusters.
To compare, the kmeans algorithm tesselates the space even when natural clusters may not exist. For example, if there is a region of uniform density, kMeans tesselates it into n clusters (specified by the user). On the other hand, OCluster separates areas of high density by placing cutting planes through areas of low density. OCluster needs multimodal histograms (peaks and valleys). If an area has projections with uniform or monotonically changing density, OCluster does not partition it.
OCluster does not necessarily use all the data when it builds a model. It reads the data in batches (the default batch size is 50000). It will only read another batch if it believes, based on some statistical tests, that there may still exist clusters that it has not uncovered.
Because OCluster may stop the model build before it reads all of the data, it is highly recommended that you randomize the data.
OCluster bins the data internally, thus providing automatic data discretization. However, if manual binning is used, the bin values must be represented by contiguous integer numbers starting at 1.
Binary attributes should be declared as categorical. OCluster distinguishes between continuous and discrete numerical attributes. The two types of attributes undergo different binning procedures in order to capture the characteristics of the underlying distributions. For example, a discrete numerical attribute such as age should be declared of data type INTEGER. On the other hand, continuous numerical attributes such as height measured in feet should be declared of data type NUMBER.
The clusters discovered by OCluster are used to generate a Bayesian probability model that is then used during scoring (model apply) for assigning data points to clusters. The generated probability model is a mixture model where the mixture components are represented by a product of independent normal distributions for numerical attributes and multinomial distributions for categorical attributes.
The main characteristics of the enhanced kmeans and OCluster algorithms are summarized in Table 42, below.
The Association model is often associated with "market basket analysis", which is used to discover relationships or correlations in a set of items. It is widely used in data analysis for direct marketing, catalog design, and other business decisionmaking processes. A typical association rule of this kind asserts the likelihood that, for example, "70% of the people who buy spaghetti, wine, and sauce also buy garlic bread."
Association models capture the cooccurrence of items or events in large volumes of customer transaction data. Because of progress in barcode technology, it is now possible for retail organizations to collect and store massive amounts of sales data, referred to as "basket data." Association models were initially defined on basket data, even though they are applicable in several other applications. Finding all such rules is valuable for crossmarketing and mailorder promotions, but there are other applications as well: catalog design, addon sales, store layout, customer segmentation, web page personalization, and target marketing.
Traditionally, association models are used to discover business trends by analyzing customer transactions. However, they can also be used effectively to predict Web page accesses for personalization. For example, assume that after mining the Web access log, Company X discovered an association rule "A and B implies C," with 80% confidence, where A, B, and C are Web page accesses. If a user has visited pages A and B, there is an 80% chance that he/she will visit page C in the same session. Page C may or may not have a direct link from A or B. This information can be used to create a dynamic link to page C from pages A or B so that the user can "clickthrough" to page C directly. This kind of information is particularly valuable for a Web server supporting an ecommerce site to link the different product pages dynamically, based on the customer interaction.
There are several properties of association models that can be calculated. ODM provides two:
These statistical measures can be used to rank the rules and hence the predictions.
ODM supports the Apriori algorithm for association models.
The Apriori algorithm works by iteratively enumerating item sets of increasing lengths subject to the minimum support threshold. Since association rule mining is defined this way and the stateoftheart algorithms work by iterative enumeration, association rules algorithms don't handle the following cases efficiently:
By definition, association rule mining discovers frequent patterns with frequency above the minimum support threshold. Therefore, in order to find associations involving rare events, the algorithm must run with very low minimum support values. However, doing so could potentially explode the number of enumerated item sets, especially in cases with large number of items. That could increase the execution time significantly.
Therefore, association rule mining is not recommended for finding associations involving "rare" events in problem domains with large number of items.
However, there are ways to restrict the item set enumeration to a smaller set if the "rare" events of interest are known. One could also use association rules to perform "partial classification" of the rare events. Those enhancements to association rules are not supported in this release.
Another option is to use classification models in such problem domains.
Since association rule algorithms work by iterative enumeration, they work best for sparse data sets, that is, data sets where each record contains only a small fraction of the total number of possible items (if the total number of items is very large). Algorithm performance degrades exponentially with increasing number of frequent items per record. Therefore, to get good runtime performance, one of the following conditions should hold:
The last condition holds for higher minimum support values.
Typical data sets in many bioinformatics applications are dense with large number of attributes. In order to use association rules effectively for such problems, careful planning is required. One option is to start with a high minimum support threshold and repeat it for lower values until desirable results are obtained. Another option is to recode some of the uninteresting attribute values to NULL, if such recoding makes the data set sparse.
Association models are designed to use sparse data. Sparse data is data for which only a small fraction of the attributes are nonzero or nonnull in any given row. Examples of sparse data include market basket and text mining data. For example, a market basket problem, there might be 1,000 products in the company's catalog, and the average size of a basket (the collection of items that a customer purchases in a typical transaction) is 20 products. In this example, a transaction/case/record has on average 20 out of 1000 attributes that are not null. This implies that the fraction of nonzero attributes on the table (or the density) is 20/1000, or 2%. This density is typical for market basket and text processing problems. Data that has a significantly higher density can require extremely large amounts of Temp space to build associations. For more information about sparse data, see Section 2.2.6.
Association models treat NULL values an indication of sparse data. The algorithm doesn't handle missing values. If the data is not sparse and the NULL values are indeed missing at random, it is necessary to perform missing data imputation (that is, "treat" the missing values) and substitute the NULL values for a nonnull value.
The association rule mining problem can be decomposed into two subproblems:
The number of frequent itemsets is governed by the minimum support parameters. The number of rules generated is governed by the number of frequent itemsets and the confidence parameter. If the confidence parameter is set too high, there may be frequent itemsets in the association model but no rules.
ODM uses an SQLbased implementation of the Apriori algorithm. The candidate generation and support counting steps are implemented using SQL queries. We do not use any specialized inmemory data structures. The SQL queries are finetuned to run efficiently in the database server by using various hints.
ODM Feature Extraction creates a new set of features by decomposing the original data. Feature extraction lets you describe the data with a number of features far smaller than the number of original dimensions (attributes). A feature is a combination of attributes in the data that is of special interest and captures important characteristics of the data.
Some applications of feature extraction are latent semantic analysis, data compression, data decomposition and projection, and pattern recognition. Feature extraction can also be used to enhance the speed and effectiveness of supervised learning.
For example, feature extraction can be used to extract the themes of a document collection, where documents are represented by a set of key words and their frequencies. Each theme (feature) is represented by a combination of keywords. The documents in the collection can then be expressed in terms of the discovered themes.
Nonnegative Matrix Factorization (NMF) is described in the paper " Learning the Parts of Objects by NonNegative Matrix Factorization" by D. D. Lee and H. S. Seung in Nature (401, pages 7887910, 1999). Nonnegative Matrix Factorization is a feature extraction algorithm that decomposes multivariate data by creating a userdefined number of features, which results in a reduced representation of the original data. NMF decomposes a data matrix V into the product of two lower rank matrices W and H so that V is approximately equal to WH. NMF uses an iterative procedure to modify the initial values of W and H so that the product approaches V. The procedure terminates when the approximation error converges or the specified number of iterations is reached. Each feature is a linear combination of the original attribute set; the coefficients of these linear combinations are nonnegative. During model apply, an NMF model maps the original data into the new set of attributes (features) discovered by the model.
There is no upper limit on the number of attributes and target cardinality for NMF.
Text mining involves extracting information from unstructured data. Further, typical text data is highdimensional and sparse. Unsupervised algorithms like Principal Components Analysis (PCA), Singular Value Decomposition (SVD), and NMF involve factorizing the documentterm matrix based on different constraints. One widely used approach for text mining is latent semantic analysis. NMF focuses on reducing dimensionality. By comparing the vectors for two adjoining segments of text in a highdimensional semantic space, NMF provides a characterization of the degree of semantic relatedness between the segments. NMF is less complex than PCA and can be applied to sparse data. NMFbased latent semantic analysis is an attractive alternative to SVD approaches due to the additive nonnegative nature of the solution and the reduced computational complexity and resource requirements.