Data Mining_ Concepts and Techniques - Jiawei Han [311]
Gene expression
Gene expression matrices are popular in bioinformatics research and development. For example, an important task is to classify a new gene using the expression data of the gene and that of other genes in known classes. Symmetrically, we may classify a new sample (e.g., a new patient) using the expression data of the sample and that of samples in known classes (e.g., tumor and nontumor). Such tasks are invaluable in understanding the mechanisms of diseases and in clinical treatment.
As can be seen, many gene expression data mining problems are highly related to cluster analysis. However, a challenge here is that, instead of clustering in one dimension (e.g., gene or sample/condition), in many cases we need to cluster in two dimensions simultaneously (e.g., both gene and sample/condition). Moreover, unlike the clustering models we have discussed so far, a cluster in a gene expression data matrix is a submatrix and usually has the following characteristics:
■ Only a small set of genes participate in the cluster.
■ The cluster involves only a small subset of samples/conditions.
■ A gene may participate in multiple clusters, or may not participate in any cluster.
■ A sample/condition may be involved in multiple clusters, or may not be involved in any cluster.
To find clusters in gene-sample/condition matrices, we need new clustering techniques that meet the following requirements for biclustering:
■ A cluster of genes is defined using only a subset of samples/conditions.
■ A cluster of samples/conditions is defined using only a subset of genes.
■ The clusters are neither exclusive (e.g., where one gene can participate in multiple clusters) nor exhaustive (e.g., where a gene may not participate in any cluster).
Biclustering is useful not only in bioinformatics, but also in other applications as well. Consider recommender systems as an example.
Using biclustering for a recommender system
AllElectronics collects data from customers' evaluations of products and uses the data to recommend products to customers. The data can be modeled as a customer-product matrix, where each row represents a customer, and each column represents a product. Each element in the matrix represents a customer's evaluation of a product, which may be a score (e.g., like, like somewhat, not like) or purchase behavior (e.g., buy or not). Figure 11.4 illustrates the structure.
The customer-product matrix can be analyzed in two dimensions: the customer dimension and the product dimension. Treating each customer as an object and products as attributes, AllElectronics can find customer groups that have similar preferences or purchase patterns. Using products as objects and customers as attributes, AllElectronics can mine product groups that are similar in customer interest.
Moreover, AllElectronics can mine clusters in both customers and products simultaneously. Such a cluster contains a subset of customers and involves a subset of products. For example, AllElectronics is highly interested in finding a group of customers who all like the same group of products. Such a cluster is a submatrix in the customer-product matrix, where all elements have a high value. Using such a cluster, AllElectronics can make recommendations in two directions. First, the company can recommend products to new customers who are similar to the customers in the cluster. Second, the company can recommend to customers new products that are similar to those involved in the cluster.
Figure 11.4 Customer-product matrix.
As with biclusters in a gene expression data matrix, the biclusters in a customer-product matrix usually have the following characteristics:
■ Only a small set of customers participate in a cluster.
■ A cluster involves only a small subset of products.
■ A customer can participate in multiple clusters, or may not participate in any cluster.
■ A product may be involved in multiple clusters, or may not be involved in any cluster.
Biclustering can be applied to customer-product matrices to mine clusters satisfying these requirements.