Motivation and Technology Background
With the rapid progress in data acquisition, sensing, and
storage technologies, the size of available datasets is increasing
at a rapid rate. Given this overwhelming amount of data, data
mining, which transforms raw datasets into useful higherlevel
knowledge, becomes a must in analyzing and understanding the
information. The raw dataset is consists of objects that are
usually represented as a vector of numeric values in multidimensional
space. Higherlevel of knowledge can be extracted by discovering
groups (clusters) of similar objects from the raw dataset.
And, traditional clustering methods, which consider all of
the dimensions (attributes) for measuring similarity between
objects, have taken a leading role in data mining. However,
there are several weaknesses for dealing with high dimensional
data with traditional clustering frameworks. This is caused
by inherent characteristics of high dimensional raw data,
which are the increasing irrelevance of some dimensions, and
the tendency to be nearly equidistant between objects as the
number of dimensions in the dataset increases. For example,
in Figure1, same objects that don’t show strong correlation
in left side graph can have correlation in right side graph.
Feature selection methods have been used for discovering relevant
dimensions from high dimensional space, and clusters on them,
however the feature selection methods have a critical limit
that uncovers relations between objects in multiple, overlapping
subdimensional spaces.
Figure 1. Full dimension vs. Subspace
Subspace clustering algorithms are suggested to overcome inherent
problems in fulldimensional clustering frameworks and feature
selection methods. The main purpose of subspace clustering
algorithms is to find meaningful groups of objects in multiple
subdimensions that may be overlapped, because clusters may
be embedded in lower dimensional subspaces. In addition, different
sets of dimensions may be relevant for different sets of objects,
and an object can have multiple characteristics in different
subspaces.
There are two main streams of previous approaches in subspace
clustering. Topdown algorithms (e.g., PROCLUS, FINDIT, etc)
find fulldimensional clusters first, and then refine them
to find subspace clusters. Bottomup strategies (e.g., CLIQUE,
MAFIA, etc.) start from finding low dimensional dense regions,
and then use them to make relevant subspace clusters. However,
both of them have a major weakness on scalability of dimensions.
For example, the number of dimensions (m) for gene expression
data usually varies from 20 to 100, and the number of dimensions
of feature vectors for documents is well over 100,000. When
m is equal to 50, the number of possible subspaces is 250
– 1. It is computationally expensive to search all subspaces
to identify clusters. To cope with this problem, bottomup
type of algorithms first identify clusters in low dimensional
spaces, and use them to find clusters in higher dimensional
spaces based on the a priori algorithm. However, this approach
is not scalable with the number of dimensions in general.
This motivates the necessity of a subspace clustering algorithm
that is scalable with the number of dimensions. To this end,
we develop a novel subspace clustering algorithm that utilizes
domain transformation from objects to objectobject relations.
Current efforts and capabilities
Our efforts on data mining are mainly focused on gene expression
analysis [1, 2]. This is because there can be valuable hidden
highlevel knowledge in gene expression datasets that consist
of the expression levels of thousands of genes under hundreds
of conditions. The other reason that we use gene expression
data is that most genes are expected to be strongly correlated
under certain subconditions (e.g. Figure1), and these genes
have similar biological functions. In addition to gene expression
analysis, we also focus our research on word subspace clustering.
Figure 2. Overview of SCLUDOT
Our current capabilities on data mining include the following:

Identifying coherent patterns on subsets of gene expression
datasets [1]: We propose a novel Subspace clustering algorithm,
referred to as SCLUDOT (Subspace CLUstering based on DOmain
Transformation), for identifying coherent subpatterns of
gene expression datasets. The overview of our proposed subspace
clustering algorithm is shown on Figure2. By performing
discretization (step1 in Figre2) to gene expression profiles,
each gene can be expressed as a sequence of symbols instead
of a sequence of numeric values.
As gene pairs may be similar in certain conditions and not in other conditions, the maximum
number of same symbols in gene pairs would be less than
or equal to total number of conditions, even though all
genes have same length of sequence of symbols (total number
of conditions). Now, the similarity between two genes is
transformed as a sequence of symbols that represents the
maximal subspace cluster for the gene pair (step2 in Figure2).
This domain transformation (from genes into genegene relations)
allows us to make the number of possible subspace clusters
dependent on the number of genes (objects) instead of number
of conditions (dimensions).
Based on the symbolized genes,
we present an efficient subspace clustering algorithm that
is linearly scalable to the number of dimensions. In addition,
the running time can be drastically reduced by utilizing
inverted indexing and pruning noninteresting subspaces.
Experimental results so far indicate that the proposed method
efficiently identifies coexpressed gene subspace clusters
for a yeast cell cycle dataset. However, SCLUDOT is not
limited to gene expression mining, but applicable to subspace
clustering in general for highdimensional massive datasets.

SCLUDOTbased metadata management: To strengthen our
work in terms of generality, we plan to apply SCLUDOT to
word subspace clustering. In order to retrieve rich semantic
information from the overwhelming amount of unstructured
data, metadata (e.g., ontologies) can be employed. Since
manually building and maintaining such metadata is nearly
impossible, an automated dynamic metadata management technique
will play an important role.
We proposed a novel algorithm
called WebSim (Webbased term Similarity metric) [4,5],
whose feature extraction and similarity model is based on
a conventional Web search engine.
There are two main benefits
of utilizing a Web search engine. First, we can obtain the
freshest content for each term that represents the uptodate
knowledge on the term. Second, in comparison with the approaches
that use the certain amount of crawled Web documents as
a corpus, our method is less sensitive to the problem of
data sparseness because we access as much content as possible
using a search engine.
A new approach that combines WebSim
with SCLUDOT gives a promising dynamic metadata management
model. Even though WebSim provides more reliable metrics
for relationships between terms or concepts, it is still
suffering from dealing with ambiguity of terms.
Because SCLUDOT finds clusters in multiple, overlapped subspaces
in the manner of being scalable to the number of dimensions,
it has the capability to extract multiple relations between
terms or concepts under different subsets of features in
very high dimensional feature vector space extracted by
WebSim. And, these subspace clusters reveal hidden term
relationships that cannot be found by fulldimensional term
similarity metrics.
At the core of our current research efforts, SCLUDOT plays
a key role. An efficient subspace clustering algorithm promises
huge benefits on diverse problem domains, and SCLUDOT may
be a stepping stone to the successful subspace clustering
framework.
Possible problem domains of subspace clustering
Although all the high dimensional data can be considered as
input data of subspace clustering, datasets in certain problem
domains have recently received scientific attention:

Gene expression analysis: Since gene expression datasets
consist of measurements across various conditions (or time
points), they are characterized by high dimensional, huge
size volume, and noisy data. It is well known that genes
can manifest a coherent pattern under subsets of experimental
conditions, and these patterns are closely related with
certain functionality of genes. Therefore, It is essential
to identify such local patterns in gene expression datasets,
which is a key to revealing biologically meaningful clusters.

Ecommerce: With the fast growing online market, finding
user groups who show similar interests in products is more
important than any other era in history. Also, users can
be identified by diverse characteristics, and current technologies
allow substantial user information to be gathered. However,
it is difficult to analyze the user information data because
of its high dimensionality and the heterogeneity of users’
interests. A subspace clustering with the ability of finding
locally correlated patterns is a promising method for recommendation
systems and target marketing in ecommerce.
? Besides gene expression analysis and ecommerce, there
are several problem domains that are suitable for subspace
clustering. For example, creating a hierarchy of data sources
in an information integration system and organizing unstructured
web search results are possible problem domains where subspace
clustering can be utilized.
Research Plan
Regarding our subspace clustering algorithm (SCLUDOT), we
plan to investigate the following:

Improving discritization step: Discritization on each
condition is the first step in SCLUDOT, and plays a key
role in improving the quality of subspace clusters. Currently,
we utilize a kmeans algorithm for this step, but it limits
number of possible symbols in each condition (dimension)
to a predefined fixed number. But, there can be different
characteristics (e.g. density distribution of values, predetermined
importance, etc.) of each condition: this means the algorithm
should have an ability to freely determine the number of
symbols in each dimension. So, we plan to apply different
known algorithms for this step, and conduct experiments
to find the most efficient method.

Finding concrete subspace clusters: There are still more
issues visavis SCLUDOT – how we can systematically
determine the bound of number of objects in a subspace cluster,
and what is relevant minimum number of dimensions that provides
meaningful clusters? Currently, a probabilistic model is
used to determine the minimum number of objects in a cluster.
And, the minimum number of dimensions is determined experimentally.
These two issues strongly affect the average running time
and quality of result, because the threshold for the minimum
number of objects in a cluster is related with the pruning
step and total number of obtained subspace clusters, and
the minimum number of dimensions determines the size of
search space. We plan to investigate these issues in diverse
ways.

Extending SCLUDOT to patternbased subspace clustering:
Our current subspace clustering algorithm utilizes value
similarity for finding subspace clusters, but there is high
possibility to extent it to patternbased clustering. Patternbased
clustering is performed by pattern similarity, and it has
been widely studied for the purpose of dealing with timeseries
data. By adding numeric orders of symbols as another factor
for the clustering, we can achieve patternbased subspace
clustering.

Efficient analysis for the result: In order to interpret
obtained clusters, external knowledge needs to be involved.
It depends on problem domain, because available external
knowledge will be different domain by domain. For gene expression
analysis, we plan to explore the methodology to quantify
the relationship between subspace clusters and known biological
knowledge by utilizing a Gene Ontology.

Comprehensive evaluation of the proposed algorithm on
different datasets: For the purpose of qualitatively testing
SCLUDOT, we plan to conduct more comprehensive experiments
on diverse datasets as well as compare our approach with
other competitive algorithms.
Besides improving our subspace clustering algorithm itself,
we plan to extend our research to apply SCLUDOT to other application
domains. SCLUDOT is a generalpurpose subspace clustering
algorithm, therefore it may be suitable for ecommerce and
association rule mining by combining SCUDOT with a classification
method. So, we plan to investigate whether SCLUDOT is suitable
to domains such as association rule mining, and recommendation
systems.
