Bipartite graph partitioning and data clustering.
Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.
INTRODUCTION
analysis is an important tool for exploratory data
mining applications arising from many diverse disciplines.
Informally, cluster analysis seeks to partition a given data
set into compact clusters so that data objects within a cluster
are more similar than those in distinct clusters. The literature
on cluster analysis is enormous including contributions
from many research communities. (see [6, 9] for recent surveys
of some classical approaches.) Many traditional clustering
algorithms are based on the assumption that the given
dataset consists of covariate information (or attributes) for
each individual data object, and cluster analysis can be cast
as a problem of grouping a set of n-dimensional vectors each
representing a data object in the dataset. A familiar example
is document clustering using the vector space model
[1]. Here each document is represented by an n-dimensional
vector, and each coordinate of the vector corresponds to a
term in a vocabulary of size n. This formulation leads to
the so-called term-document matrix for the representation
of the collection of documents, where a ij is the
so-called term frequency, i.e., the number of times term i
occurs in document j. In this vector space model terms and
documents are treated asymmetrically with terms considered
as the covariates or attributes of documents. It is also
possible to treat both terms and documents as first-class
citizens in a symmetric fashion, and consider a ij as the frequency
of co-occurrence of term i and document j as is done,
for example, in probabilistic latent semantic indexing [12]. 1
In this paper, we follow this basic principle and propose a
new approach to model terms and documents as vertices
in a bipartite graph with edges of the graph indicating the
co-occurrence of terms and documents. In addition we can
optionally use edge weights to indicate the frequency of this
co-occurrence. Cluster analysis for document collections in
this context is based on a very intuitive notion: documents
are grouped by topics, on one hand documents in a topic
tend to more heavily use the same subset of terms which
form a term cluster, and on the other hand a topic usually
is characterized by a subset of terms and those documents
heavily using those terms tend to be about that particular
topic. It is this interplay of terms and documents which
gives rise to what we call bi-clustering by which terms and
documents are simultaneously grouped into semantically co-
Our clustering algorithm computes an approximate global
optimal solution while probabilistic latent semantic indexing
relies on the EM algorithm and therefore might be prone to
local minima even with the help of some annealing process.
herent clusters.
Within our bipartite graph model, the clustering problem
can be solved by constructing vertex graph partitions.
Many criteria have been proposed for measuring the quality
of graph partitions of undirected graphs [4, 14]. In this pa-
per, we show how to adapt those criteria for bipartite graph
partitioning and therefore solve the bi-clustering problem.
A great variety of objective functions have been proposed
for cluster analysis without efficient algorithms for finding
the (approximate) optimal solutions. We will show that our
bipartite graph formulation naturally leads to partial SVD
problems for the underlying edge weight matrix which admit
efficient global optimal solutions. The rest of the paper
is organized as follows: in section 2, we propose a new criterion
for bipartite graph partitioning which tends to produce
balanced clusters. In section 3, we show that our criterion
leads to an optimization problem that can be approximately
solved by computing a partial SVD of the weight matrix of
the bipartite graph. In section 4, we make connection of
our approximate solution to correspondence analysis used
in multivariate data analysis. In section 5, we briefly discuss
how to deal with clusters with overlaps. In section 6,
we describe experimental results on bi-clustering a dataset
of newsgroup articles. We conclude the paper in section 7
and give pointers to future research.
2.
We denote a graph by G(V; E), where V is the vertex
set and E is the edge set of the graph. A graph G(V; E) is
bipartite with two vertex classes X and Y if
and each edge in E has one endpoint in X and
one endpoint in Y . We consider weighted bipartite graph
denotes the
weight of the edge between vertex i and j. We let
if there is no edge between vertices i and j. In the context
of document clustering, X represents the set of terms and
Y represents the set of documents, and w ij can be used to
denote the number of times term i occurs in document j. A
vertex partition of G(X;Y; W ) denoted by \Pi(A; B) is defined
by a partition of the vertex sets X and Y , respectively:
, where for a set S, S c denotes its
compliment. By convention, we pair A with B, and A c with
. We say that a pair of vertices x 2 X and y 2 Y is
matched with respect to a partition \Pi(A; B) if there is an
edge between x and y, and either x 2 A and y 2 B or
. For any two subsets of vertices
and T ae Y , define
i.e., W (S; T ) is the sum of the weights of edges with one
endpoint in S and one endpoint in T . The quantity W (S; T )
can be considered as measuring the association between the
vertex sets S and T . In the context of cluster analysis edge
weight measures the similarity between data objects. To
partition data objects into clusters, we seek a partition of
such that the association
unmatched vertices is as small as possible. One possibility
is to consider for a partition \Pi(A; B) the following quantity
(1)
Intuitively, choosing \Pi(A; B) to minimize cut(A; B) will give
rise to a partition that minimizes the sum of all the edge
weights between unmatched vertices. In the context of document
clustering, we try to find two document clusters B
and B c which have few terms in common, and the documents
in B mostly use terms in A and those in B c use terms
in A c . Unfortunately, choosing a partition based entirely
on cut(A; B) tends to produce unbalanced clusters, i.e., the
sizes of A and/or B or their compliments tend to be small.
Inspired by the work in [4, 5, 14], we propose the following
normalized variant of the edge cut in (1)
The intuition behind this criterion is that not only we want
a partition with small edge cut, but we also want the two
subgraphs formed between the matched vertices to be as
dense as possible. This latter requirement is partially satisfied
by introducing the normalizing denominators in the
above equation. 2 Our bi-clustering problem is now equivalent
to the following optimization problem
min
i.e., finding partitions of the vertex sets X and Y to minimize
the normalized cut of the bipartite graph G(X;Y; W ).
3. APPROXIMATESOLUTIONSUSING SINGULAR
VECTORS
Given a bipartite graph G(X;Y; W ) and the associated
partition \Pi(A; B). Let us reorder the vertices of X and Y
so that vertices in A and B are ordered before vertices in A c
respectively. The weight matrix W can be written
in a block format
i.e., the rows of W11 correspond to the vertices in the vertex
set A and the columns of W11 correspond to those in
B. Therefore G(A;B;W11 ) denotes the weighted bipartite
graph corresponding to the vertex sets A and B. For any
i.e., s(H) is the sum of all the elements of H. It is easy to
see from the definition of Ncut,
2 A more natural criterion seems to be
However, it can be shown that it will leads to an SVD problem
with the same set of left and right singular vectors.
In order to make connections to SVD problems, we first
consider the case when W is symmetric. 3 It is easy to see
that with W symmetric (denoting Ncut(A; A) by Ncut(A)),
we have
Let e be the vector with all its elements equal to 1. Let D be
the diagonal matrix such that W
be the vector with
ae
It is easy to verify that
Then
and
Notice that (D \Gamma W scalar s, we have
(se
To cast (4) in the form of a Rayleigh quotient, we need to
find s such that
(se
it follows from the above equation
that is easy to see
that y T
Thus
min A
ae y T (D \Gamma W )y
oe
where
If we drop the constraints y let the
elements of y take arbitrary continuous values, then the optimal
y can be approximated by the following relaxed continuous
minimization problem,
min
ae y T (D \Gamma W )y
oe
Notice that it follows from W
D \Gamma1=2 WD \Gamma1=2 (D 1=2
3 A different proof for the symmetric case was first derived
in [14]. However, our derivation is simpler and more transparent
and leads naturally to the SVD problems for the
rectangular case.
and therefore D 1=2 e is an eigenvector of D \Gamma1=2 WD \Gamma1=2 corresponding
to the eigenvalue 1. It is easy to show that all the
eigenvalues of D \Gamma1=2 WD \Gamma1=2 have absolute value at most
1 (See the Appendix). Thus the optimal y in (5) can be
computed as
y, where -
y is the second largest eigenvector
of D \Gamma1=2 WD \Gamma1=2 .
Now we return to the rectangular case for the weight matrix
W , and let DX and DY be diagonal matrices such that
e: (6)
Consider a partition \Pi(A; B), and define
ae
ae
Let W have the block form as in (2), and consider the augmented
22
If we interchange the second and third block rows and columns
of the above matrix, we obtain6 6 4
22 07 7 5 j
W22
and the normalized cut can be written as
a form that resembles the symmetric case (3). Define
Then we have
v. It is also easy to
see that
Therefore,
min
x6=0;y 6=0
ae 2x T Wy
oe
In [11], the Laplacian of -
W is used for partitioning a rectangular
matrix in the context of designing load-balanced
matrix-vector multiplication algorithms for parallel compu-
tation. However, the eigenvalue problem of the Laplacian of
W does not lead to a simpler singular value problem.
Ignoring the discrete constraints on the elements of x and
y, we have the following continuous maximization problem,
x6=0;y 6=0
ae 2x T Wy
oe
Without the constraints x T the above
problem is equivalent to computing the largest singular triplet
of D \Gamma1=2
Y (see the Appendix). From (6), we have
Y (D 1=2
(D \Gamma1=2
and similarly to the symmetric case, it is easy to show
that all the singular values of D \Gamma1=2
Y are at most 1.
Therefore, an optimal pair fx; yg for (8) can be computed
as
x and
y, where -
x and - y are the second
largest left and right singular vectors of D \Gamma1=2
Y ,
respectively (see the Appendix). With the above discus-
sion, we can now summerize our basic approach for bipartite
graph clustering incorporating a recursive procedure.
Algorithm. Spectral Recursive Embedding (SRE)
Given a weighted bipartite graph E) with
its edge weight matrix W :
1. Compute DX and DY and form the scaled weight
Y .
2. Compute the second largest left and right singular
vectors of -
x and - y.
3. Find cut points cx and cy for
x and
y, respectively.
4. Form partitions
vertex set Y .
5. Recursively partition the sub-graphs G(A;B) and
necessary.
Two basic strategies can be used for selecting the cut
points cx and cy . The simplest strategy is to set
and cy = 0. Another more computing-intensive approach
is to base the selection on Ncut: Check N equally spaced
splitting points of x and y, respectively, find the cut points
cx and cy with the smallest Ncut [14].
Computational complexity. The major computational
cost of SRE is Step 2 for computing the left and right singular
vectors which can be obtained either by power method
or more robustly by Lanczos bidiagonalization process [8,
Chapter 9]. Lanczos method is an iterative process for computing
partial SVDs in which each iterative step involves
the computation of two matrix-vector multiplications -
and -
vectors u and v. The computational cost
of these is roughly proportional to nnz( -
W ), the number of
nonzero elements of -
W . The total computational cost of
SRE is O(c sre k svd nnz( -
sre the the level of recursion
and k svd is the number of Lanczos iteration steps.
In general, k svd depends on the singular value gaps of -
W .
Also notice that nnz( -
is the average
number of terms per document and n is the total number
of document. Therefore, the total cost of SRE is in general
linear in the number of documents to be clustered.
4. CONNECTIONSTOCORRESPONDENCE
ANALYSIS
In its basic form correspondence analysis is applied to
an m-by-n two-way table of counts W [2, 10, 16]. Let
the sum of all the elements of W , DX and DY
be diagonal matrices defined in section 3. Correspondence
analysis seeks to compute the largest singular triplets of the
(DX (i; i)=w)(DY (j; j)=w)
The matrix Z can be considered as the correlation matrix
of two group indicator matrices for the original W [16]. We
now show that the SVD of Z is closely related to the SVD
of -
Y . In fact, in section 3, we showed
that D 1=2
Y e are the left and right singular vectors
of -
W corresponding to the singular value one, and it is also
easy to show that all the singular values of -
W are at most
1. Therefore, the rest of the singular values and singular
vectors of -
W can be found by computing the SVD of the
following rank-one modification of -
Y
Y k2
which has (i;
and is a constant multiple of the (i; j) element of Z. There-
fore, normalized-cut based cluster analysis and correspondence
analysis arrive at the same SVD problems even though
they start with completely different principles. It is worth-while
to explore more deeply the interplay between these two
different points of views and approaches, for example, using
the statistical analysis of correspondence analysis to provide
better strategy for selecting cut points and estimating the
number of clusters.
5. PARTITIONS WITH OVERLAPS
So far in our discussion, we have only looked at hard clus-
tering, i.e., a data object belongs to one and only one cluster.
In many situations, especially when there are much overlap
among the clusters, it is more advantageous to allow data
objects to belong to different clusters. For example, in document
clustering, certain groups of words can be shared by
two clusters. Is it possible to model this overlap using our
bipartite graph model and also find efficient approximate
solutions? The answer seems to be yes, but our results at
this point are rather preliminary and we will only illustrate
the possibilities. Our basic idea is that when computing
B), we should disregard the contributions of the
set of vertices that is in the overlap. More specifically, let
A and
B, where OX denotes the

Figure

1: Sparsity patterns of a test matrix before
clustering (left) and after clustering (right)
overlap between the vertex subsets A[OX and -
A[OX , and
OY the overlap between B [ OY and -
However, we can make Ncut(A; B; -
smaller simply by
putting more vertices in the overlap. Therefore, we need
to balance these two competing quantities: the size of the
overlap and the modified normalized cut
by minimizing
where ff is a regularization parameter. How to find an efficient
method for computing the (approximate) optimal solution
to the above minimization problem still needs to be
investigated. We close this section by presenting an illustrative
example showing that in some situations, the singular
vectors already automatically separating the overlap sets
while giving the coordinates for carrying out clustering.
Example 1. We construct a sparse m-by-n rectangular
matrix
so that W11 and W22 are relatively denser than W12 and
W21 . We also add some dense rows and columns to the matrix
W to represent row and column overlaps. The left panel
of

Figure

1 shows the sparsity pattern of -
W , a matrix obtained
by randomly permuting the rows and columns of W .
We then compute the second largest left and right singular
vectors of D \Gamma1=2
WD \Gamma1=2
Y , say x and y, then sort the rows
and columns of -
W according to the values of the entries in
Y y, respectively. The sparsity pattern of
this permuted -
W is shown on the right panel of Figure 1. As
can be seen that the singular vectors not only do the job of
clustering but at the same time also concentrate the dense
rows and columns at the boundary of the two clusters.
6. EXPERIMENTS
In this section we present our experimental results on clustering
a dataset of newsgroup articles submitted to 20 news-
groups. 5 This dataset contains about 20,000 articles (email
messages) evenly divided among the 20 newsgroups. We list
the names of the newsgroups together with the associated
group labels (the labels will be used in the sequel to identify
the newsgroups).
NG2: comp.graphics
NG3: comp.os.ms-windows.misc
NG4: comp.sys.ibm.pc.hardware
NG5:comp.sys.mac.hardware
NG7:misc.forsale
NG8: rec.autos
NG9:rec.motorcycles
NG10: rec.sport.baseball
NG11:rec.sport.hockey
NG12: sci.crypt
NG13:sci.electronics
NG14: sci.med
NG15:sci.space
soc.religion.christian
NG17:talk.politics.guns
NG18: talk.politics.mideast
NG20: talk.religion.misc
We used the bow toolkit to construct the term-document
matrix for this dataset, specifically we use the tokenization
option so that the UseNet headers are stripped, and we also
applied stemming [13]. Some of the newsgroups have large
overlaps, for example, the five newsgroups comp.* about
computers. In fact several articles are posted to multiple
newsgroups. Before we apply clustering algorithms to
the dataset, several preprocessing steps need to be consid-
ered. Two standard steps are weighting and feature selec-
tion. For weighting, we considered a variant of tf.idf weighting
scheme, tf log 2 (n=df); where tf is the term frequency
and df is the document frequency and several other variations
listed in [1]. For feature selection, we looked at three
approaches 1) deleting terms that occur less than certain
number of times in the dataset; 2) deleting terms that occur
in less than certain number of documents in the dataset;
selecting terms according to mutual information of terms
and documents defined as
x
where y represents a term and x a document [15]. In general
we found out that the traditional tf.idf based weighting
schemes do not improve performance for SRE. One possible
explanation comes from the connection with correspondence
analysis, the raw frequencies are samples of co-occurrence
probabilities, and the pre- and post-multiplication by D \Gamma1=2
and D \Gamma1=2
Y in D \Gamma1=2
Y automatically taking
into account of weighting. We did, however, found out that
trimming the raw frequencies can sometimes improve performance
for SRE, especially for the anomalous cases where
some words can occur in certain documents an unusual number
of times, skewing the clustering process.
5 The newsgroup dataset together with the bow
toolkit for processing it can be downloaded from
http://www.cs.cmu.edu/afs/cs/project/theo-11/www/
naive-bayes.html.

Table

1: Comparison of spectral embedding (SRE), PDDP, and K-means (NG1/NG2)
Mixture SRE PDDP K-means
50/100 90:57 \Sigma 3:11% 86:11 \Sigma 3:94% (86; 5;

Table

2: Comparison of spectral embedding (SRE), PDDP, and K-means (NG10/NG11)
Mixture SRE PDDP K-means
For the purpose of comparison, we consider two other clustering
methods: 1) K-means method [9]; 2) Principal direction
divisive partion (PDDP) method [3]. K-means method
is a widely used cluster analysis tool. The variant we used
employs the Euclidean distance when comparing the dissimilarity
between two documents. When applying K-means,
we normalize the length of each document so that it has
Euclidean length one. In essence, we use the cosine of the
angle between two document vectors when measuring their
similarity. We have also tried K-means without document
length normalization, the results are far worse and therefore
we will not report the corresponding results. Since K-means
method is an iterative method, we need to specify a stopping
criterion. For the variant we used, we compare the centroids
between two consecutive iterations, and stop when the difference
is smaller than a pre-defined tolerance.
PDDP is another clustering method that utilizes singular
vectors. It is based on the idea of principal component
analysis and has been shown to outperform several standard
clustering methods such as hierarchical agglomerative algorithm
[3]. First each document is considered as a multivariate
data point. The set of document is normalized to have
unit Euclidean length and then centered, i,e., let W be the
term-document matrix, and w be the average of the columns
of W . Compute the largest singular value triplet fu; oe; vg of
split the set of documents based on their
values of the simple scheme is to let
those with positive v i go into one cluster and those with
nonnegative v i inot another cluster. Then the whole process
is repeated on the term-document matrices of the two
clusters, respectively. Although both our clustering method
SRE and PDDP make use of the singular vectors of some
versions of the term-document matrices, they are derived
from fundamentally different principles. PDDP is a feature-based
clustering method, projecting all the data points to
the one-dimensional subspace spanned by the first principal
axis; SRE is a similarity-based clustering method, two co-occurring
variables (terms and documents in the context of
document clustering) are simultaneously clustered. Unlike
SRE, PDDP does not have a well-defined objective function
for minimization. It only partitions the columns of the term-document
matrices while SRE partitions both of its rows and
columns. This will have significant impact on the computational
costs. PDDP, however, has an advantage that it can
be applied to dataset with both positive and negative values
while SRE can only be applied to datasets with nonnegative
data values.
Example 2. In this example, we examine binary clustering
with uneven clusters. We consider three pairs of news-
groups: newsgroups 1 and 2 are well-separated, 10 and 11
are less well-separated and have a lot of overlap.
We used document frequency as the feature selection criterion
and delete words that occur in less than 5 documents
in each datasets we used. For both K-means and PDDP we
apply tf.idf weighting together with document length normalization
so that each document vector will have Euclidean
norm one. For SRE we trim the raw frequency so that the
maximum is 10. For each newsgroup pair, we select four
types of mixture of articles from each newsgroup: x=y indicates
that x articles are from the first group and y articles
are from the second group. The results are listed in Table 1
for groups 1 and 2, Table 2 for groups 10 and 11 and Table 3
for groups We list the means and standard deviations
for 100 random samples. For PDDP and K-means we
also include a triplet of numbers which indicates how many
of the 100 samples SRE performs better (the first number),
the same (the second number) and worse (the third num-
ber) than the corresponding methods (PDDP or K-means).
We should emphasize that K-means method can only find
local minimum, and the results depend on initial values and
stopping criteria. This is also reflected by the large standard
deviations associated with K-means method. From the three
tests we can conclude that both SRE and PDDP outperform
K-means method. The performance of SRE and PDDP are
similar in balanced mixtures, but SRE is superior to PDDP
in skewed mixtures.
Example 3. In this example, we consider an easy multi-cluster
case, we examine five newsgroups 2; 9; 10; 15;
was also considered in [15]. We sample 100 articles from each
newsgroups, we use mutual information for feature selection.
We use minimum normalized cut as cut point for each level
of the recursion. For one sample, Table 4 gives the confusion
matrix. The accuracy for this sample is 88:2%. We also
tested two other samples with accuracy 85:4% and 81:2%
which compare favorably with those obtained for three samples
with accuracy 59%, 58% and 53% reported in [15]. In
the following we also listed the top few words for each clusters
computed by mutual information.

Table

3: Comparison of spectral embedding (SRE), PDDP, and K-means (NG18/NG19)
Mixture SRE PDDP K-means

Table

4: Confusion matrix for newsgroups f2; 9; 10; 15; 18g
mideast graphics space baseball motorcycles
cluster
cluster
cluster
cluster
cluster
armenian israel arab palestinian peopl jew isra
iran muslim kill turkis war greek iraqi adl call
2:
imag file bit green gif mail graphic colour
group version comput jpeg blue xv ftp ac uk list
3:
univers space nasa theori system mission henri
moon cost sky launch orbit shuttl physic work
clutch year game gant player team hirschbeck
basebal won hi lost ball defens base run win
5:
bike dog lock ride don wave drive black
articl write apr motorcycl ca turn dod insur
7. CONCLUSIONS AND FUTURE WORK
In this paper, we formulate a class of clustering problems
as bipartite graph partitioning problems, and we show
that efficient optimal solutions can be found by computing
the partial singular value decomposition of some scaled
edge weight matrices. However, we have also shown that
there still remain many challenging problems. One area that
needs further investigation is the selection of cut points and
number of clusters using multiple left and right singular vec-
tors, and the possibility of adding local refinements to improve
clustering quality. 6 Another area is to find efficient
algorithms for handling overlapping clusters. Finally, the
treatment of missing data under our bipartite graph model
especially when we apply our spectral clustering methods to
the problem of data analysis of recommender systems also
deserves further investigation.
8.

ACKNOWLEDGMENTS

6 It will be difficult to use local refinement for PDDP because
it does not have a global objective function for minimization.
The work of Hongyuan Zha and Xiaofeng He was supported
in part by NSF grant CCR-9901986. The work of
Xiaofeng He, Chris Ding and Horst Simon was supported
in part by Department of Energy through an LBL LDRD
fund.
9.



--R

Finding Out About: A Cognitive Perspective on Search Engine Technology and the WWW.
Correspondence analysis handbook.
Principal Direction Divisive Partitioning.
Spectral Graph Theory.
An improved spectral bisection algorithm and its application to dynamic load balancing.
Analysis.
Algebraic connectivity of graphs.
Matrix computations
Second Edition
Correspondence analysis in practice.
Partitioning sparse rectangular and structurally nonsymmetric matrices for parallel computation.
Probabilistic Latent Semantic Indexing.
A toolkit for statistical language modeling
Normalized cuts and image segmentation.

Modern Applied Statistics with S-plus
--TR
An improved spectral bisection algorithm and its application to dynamic load balancing
Matrix computations (3rd ed.)
Probabilistic latent semantic indexing
Document clustering using word clusters via the information bottleneck method
Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing
Finding out about
Principal Direction Divisive Partitioning
Normalized Cuts and Image Segmentation

--CTR
Bhushan Mandhani , Sachindra Joshi , Krishna Kummamuru, A matrix density based algorithm to hierarchically co-cluster documents and words, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
Hongyuan Zha , Xiang Ji, Correlating multilingual documents via bipartite graph modeling, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland
Wei Xu , Yihong Gong, Document clustering by concept factorization, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
S. H. Srinivasan, Features for unsupervised document classification, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002
Long , Zhongfei (Mark) Zhang , Xiaoyun W , Philip S. Yu, Spectral clustering for multi-type relational data, Proceedings of the 23rd international conference on Machine learning, p.585-592, June 25-29, 2006, Pittsburgh, Pennsylvania
Long , Xiaoyun Wu , Zhongfei (Mark) Zhang , Philip S. Yu, Unsupervised learning on k-partite graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Chris Ding , Tao Li, Adaptive dimension reduction using discriminant analysis and K-means clustering, Proceedings of the 24th international conference on Machine learning, p.521-528, June 20-24, 2007, Corvalis, Oregon
Hua Yan , Keke Chen , Ling Liu, Efficiently clustering transactional data with weighted coverage density, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Zheng-Yu Niu , Dong-Hong Ji , Chew-Lim Tan, Document clustering based on cluster validation, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Bin Gao , Tie-Yan Liu , Guang Feng , Tao Qin , Qian-Sheng Cheng , Wei-Ying Ma, Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1263-1273, September 2005
Bin Gao , Tie-Yan Liu , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Gne Erkan, Language model-based document clustering using random walks, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.479-486, June 04-09, 2006, New York, New York
Zheng-Yu Niu , Dong-Hong Ji , Chew Lim Tan, Using cluster validation criterion to identify optimal feature subset and cluster number for document clustering, Information Processing and Management: an International Journal, v.43 n.3, p.730-739, May, 2007
Long , Zhongfei (Mark) Zhang , Xiaoyun Wu , Philip S. Yu, Relational clustering by symmetric convex coding, Proceedings of the 24th international conference on Machine learning, p.569-576, June 20-24, 2007, Corvalis, Oregon
Navaratnasothie Selvakkumaran , George Karypis, Multi.Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization, Proceedings of the IEEE/ACM international conference on Computer-aided design, p.726, November 09-13,
Bin Gao , Tie-Yan Liu , Tao Qin , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Web image clustering by consistent utilization of visual features and surrounding texts, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Chris Ding , Tao Li , Wei Peng , Haesun Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Han , Lee Giles , Hongyuan Zha , Cheng Li , Kostas Tsioutsiouliklis, Two supervised learning approaches for name disambiguation in author citations, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA
Ying Zhao , George Karypis , Usama Fayyad, Hierarchical Clustering Algorithms for Document Datasets, Data Mining and Knowledge Discovery, v.10 n.2, p.141-168, March     2005
Ying Zhao , George Karypis, Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, v.55 n.3, p.311-331, June 2004
Han , Hongyuan Zha , C. Lee Giles, Name disambiguation in author citations using a K-way spectral clustering method, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA
singular value decomposition;graph partitioning;correspondence analysis;document clustering;spectral relaxation;bipartite graph