Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Iterative Algorithm
kmeans algorithm
kmeans clustering
Object Identification
Satisfiability
Vector Quantizer
Infra Red
K Means
Related Publications
(18)
Integrating constraints and metric learning in semisupervised clustering
SemiSupervised Clustering Using Genetic Algorithms
A probabilistic framework for semisupervised clustering
Clustering with Missing Values: No Imputation Required
Constrained Kmeans Clustering with Background Knowledge
Subscribe
Academic
Publications
Clustering with Constraints: Feasibility Issues and the kMeans Algorithm
Clustering with Constraints: Feasibility Issues and the kMeans Algorithm,Ian Davidson,S. S. Ravi
Edit
Clustering with Constraints: Feasibility Issues and the kMeans Algorithm
(
Citations: 73
)
BibTex

RIS

RefWorks
Download
Ian Davidson
,
S. S. Ravi
Recent work has looked at extending the kMeans al gorithm to incorporate background information in the form of instance level mustlink and cannotlink con straints. We introduce two ways of specifying additional background information in the form of and con straints that operate on all instances but which can be interpreted as conjunctions or disjunctions of instance level constraints and hence are easy to implement. We present complexity results for the feasibility of cluster ing under each type of constraint individually and sev eral types together. A key finding is that determining whether there is a feasible solution satisfying all con straints is, in general, NPcomplete. Thus, an
iterative algorithm
such as kMeans should not try to find a fea sible partitioning at each iteration. This motivates our derivation of a new version of the
kMeans algorithm
that minimizes the constrained vector quantization er ror but at each iteration does not attempt to satisfy all constraints. Using standard UCI datasets, we find that using constraints improves accuracy as others have reported, but we also show that our algorithm reduces the number of iterations until convergence. Finally, we illustrate these benefits and our new constraint types on a complex real world
object identification
problem using the infrared detector on an Aibo robot.
Conference:
SIAM International Conference on Data Mining  SDM
, 2005
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
dns2.icar.cnr.it
)
(
www.informatik.unitrier.de
)
Citation Context
(59)
...These methods are socalled semisupervised clustering [1, 2, 5, 6, 912, 14,
16
]...
...Both Davidson et al. [
16
] and Wagstaff [31] show that if queries are not selected properly, then the effectiveness and performance of learning may be reduced in active learning...
Songyu Chen
,
et al.
Using semisupervised clustering to improve regression test selection ...
...In this paper, a clustering problem with balancing constraints is studied [
26
] and a modified kmeans clustering algorithm is proposed in this paper...
Sun Yuepeng
,
et al.
A Modified kmeans Algorithm for Clustering Problem with Balancing Con...
...This approach can be recalled as clustering with constraints, following the ideas proposed in [
9
], [10]...
Nicola Barbieri
.
Regularized Gibbs Sampling for User Profiling with Soft Constraints
...Other related work focuses on constraint feasibility on a kmeanslike scheme [
11
], and on an agglomerative hierarchical clustering scheme [12]...
...We refer to [
11
,12] for studies on constraint feasibility for both partitioning and hierarchical clustering methods...
...Moreover, we know that the satisfaction of a set of cannotlink constraints for a given number of clusters is an NPcomplete task [
11
]...
Ruggero G. Pensa
,
et al.
Coclustering numerical data under userdefined constraints
...Clustering with instancelevel constraints has recently received a lot of attention (
Davidson and Basu 2005, 2006
), also under the label semisupervised clustering (Gunopulos et al. 2006)...
Carlos Ruiz
,
et al.
Densitybased semisupervised clustering
References
(20)
Clustering with instancelevel constraints
(
Citations: 164
)
Kiri Wagstaff
,
Claire Cardie
Conference:
International Conference on Machine Learning  ICML
, pp. 10971110, 2000
Constrained Kmeans Clustering with Background Knowledge
(
Citations: 413
)
Kiri Wagstaff
,
Claire Cardie
,
Seth Rogers
,
Stefan Schrödl
Conference:
International Conference on Machine Learning  ICML
, pp. 577584, 2001
From Instancelevel Constraints to SpaceLevel Constraints: Making the Most of Prior Knowledge in Data Clustering
(
Citations: 194
)
Dan Klein
,
Sepandar D. Kamvar
,
Christopher D. Manning
Conference:
International Conference on Machine Learning  ICML
, pp. 307314, 2002
A densitybased algorithm for discovering clusters in large spatial databases
(
Citations: 90
)
M. Ester
,
H. P Kriegel
,
J. Sander
,
X. Xu
Conference:
Knowledge Discovery and Data Mining  KDD
, 1996
A probabilistic framework for semisupervised clustering
(
Citations: 250
)
Sugato Basu
,
Mikhail Bilenko
,
Raymond J. Mooney
Conference:
Knowledge Discovery and Data Mining  KDD
, pp. 5968, 2004
Sort by:
Citations
(73)
Using semisupervised clustering to improve regression test selection techniques
Songyu Chen
,
Zhenyu Chen
,
Zhihong Zhao
,
Baowen Xu
,
Yang Feng
Conference:
International Conference on Software Testing, Verification, and Validation  ICST
, pp. 110, 2011
A Modified kmeans Algorithm for Clustering Problem with Balancing Constraints
Sun Yuepeng
,
Liu Min
,
Wu Cheng
Conference:
International Conference on Measuring Technology and Mechatronics Automation  ICMTMA
, 2011
Regularized Gibbs Sampling for User Profiling with Soft Constraints
Nicola Barbieri
Conference:
Advances in Social Network Analysis and Mining  ASONAM
, 2011
Coclustering numerical data under userdefined constraints
(
Citations: 2
)
Ruggero G. Pensa
,
JeanFrançois Boulicaut
,
Francesca Cordero
,
Maurizio Atzori
Journal:
Statistical Analysis and Data Mining
, vol. 3, no. 1, pp. 3855, 2010
Densitybased semisupervised clustering
(
Citations: 1
)
Carlos Ruiz
,
Myra Spiliopoulou
,
Ernestina Menasalvas Ruiz
Journal:
Data Mining and Knowledge Discovery  DATAMINE
, vol. 21, no. 3, pp. 345370, 2010