Package elki.clustering.kmeans
Class XMeans<V extends NumberVector,M extends MeanModel>
- java.lang.Object
-
- elki.clustering.kmeans.AbstractKMeans<V,M>
-
- elki.clustering.kmeans.XMeans<V,M>
-
- Type Parameters:
V
- Vector typeM
- Model type
- All Implemented Interfaces:
Algorithm
,ClusteringAlgorithm<Clustering<M>>
,KMeans<V,M>
- Direct Known Subclasses:
GMeans
@Title("X-means") @Reference(authors="D. Pelleg, A. Moore", title="X-means: Extending K-means with Efficient Estimation on the Number of Clusters", booktitle="Proc. 17th Int. Conf. on Machine Learning (ICML 2000)", url="http://www.pelleg.org/shared/hp/download/xmeans.ps", bibkey="DBLP:conf/icml/PellegM00") public class XMeans<V extends NumberVector,M extends MeanModel> extends AbstractKMeans<V,M>
X-means: Extending K-means with Efficient Estimation on the Number of Clusters.Note: this implementation does currently not use a k-d-tree for acceleration. Also note that kmax is not a hard threshold - the algorithm can return up to 2*kmax clusters!
Reference:
D. Pelleg, A. Moore
X-means: Extending K-means with Efficient Estimation on the Number of Clusters
Proc. 17th Int. Conf. on Machine Learning (ICML 2000)- Since:
- 0.7.0
- Author:
- Tibor Goldschwendt, Erich Schubert
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class elki.clustering.kmeans.AbstractKMeans
AbstractKMeans.Instance
-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field Description (package private) KMeansQualityMeasure<V>
informationCriterion
Information criterion to choose the better split.protected KMeans<V,M>
innerKMeans
Inner k-means algorithm.private int
k_max
Effective number of clusters, minimum and maximum.private int
k_min
Effective number of clusters, minimum and maximum.private static Logging
LOG
The logger for this class.(package private) RandomFactory
rnd
Random factory.(package private) Predefined
splitInitializer
Initializer for k-means.-
Fields inherited from class elki.clustering.kmeans.AbstractKMeans
distance, initializer, k, maxiter
-
Fields inherited from interface elki.clustering.kmeans.KMeans
DISTANCE_FUNCTION_ID, INIT_ID, K_ID, MAXITER_ID, SEED_ID, VARSTAT_ID
-
-
Constructor Summary
Constructors Constructor Description XMeans(NumberVectorDistance<? super V> distance, int k_min, int k_max, int maxiter, KMeans<V,M> innerKMeans, KMeansInitialization initializer, KMeansQualityMeasure<V> informationCriterion, RandomFactory random)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.protected Logging
getLogger()
Get the (STATIC) logger for this class.Clustering<M>
run(Relation<V> relation)
Run the algorithm on a database and relation.protected double[][]
splitCentroid(Cluster<? extends MeanModel> parentCluster, Relation<V> relation)
Split an existing centroid into two initial centers.protected java.util.List<Cluster<M>>
splitCluster(Cluster<M> parentCluster, Relation<V> relation)
Conditionally splits the clusters based on the information criterion.-
Methods inherited from class elki.clustering.kmeans.AbstractKMeans
getDistance, incrementalUpdateMean, initialMeans, means, minusEquals, nearestMeans, plusEquals, plusMinusEquals, setDistance, setInitializer, setK
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.clustering.ClusteringAlgorithm
autorun
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
innerKMeans
protected KMeans<V extends NumberVector,M extends MeanModel> innerKMeans
Inner k-means algorithm.
-
k_min
private int k_min
Effective number of clusters, minimum and maximum.
-
k_max
private int k_max
Effective number of clusters, minimum and maximum.
-
splitInitializer
Predefined splitInitializer
Initializer for k-means.
-
informationCriterion
KMeansQualityMeasure<V extends NumberVector> informationCriterion
Information criterion to choose the better split.
-
rnd
RandomFactory rnd
Random factory.
-
-
Constructor Detail
-
XMeans
public XMeans(NumberVectorDistance<? super V> distance, int k_min, int k_max, int maxiter, KMeans<V,M> innerKMeans, KMeansInitialization initializer, KMeansQualityMeasure<V> informationCriterion, RandomFactory random)
Constructor.- Parameters:
distance
- Distance functionk_min
- k_min parameter - minimum number of result clustersk_max
- k_max parameter - maximum number of result clustersmaxiter
- Maximum number of iterations each.innerKMeans
- K-Means variant to use inside.informationCriterion
- The information criterion used for the splitting steprandom
- Random factory
-
-
Method Detail
-
run
public Clustering<M> run(Relation<V> relation)
Run the algorithm on a database and relation.- Parameters:
relation
- Data relation- Returns:
- Clustering result.
-
splitCluster
protected java.util.List<Cluster<M>> splitCluster(Cluster<M> parentCluster, Relation<V> relation)
Conditionally splits the clusters based on the information criterion.- Parameters:
parentCluster
- Cluster to splitrelation
- Data relation- Returns:
- Parent cluster when split decreases clustering quality or child clusters when split improves clustering.
-
splitCentroid
protected double[][] splitCentroid(Cluster<? extends MeanModel> parentCluster, Relation<V> relation)
Split an existing centroid into two initial centers.- Parameters:
parentCluster
- Existing clusterrelation
- Data relation- Returns:
- List of new centroids
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Overrides:
getInputTypeRestriction
in classAbstractKMeans<V extends NumberVector,M extends MeanModel>
- Returns:
- Type restriction
-
getLogger
protected Logging getLogger()
Description copied from class:AbstractKMeans
Get the (STATIC) logger for this class.- Specified by:
getLogger
in classAbstractKMeans<V extends NumberVector,M extends MeanModel>
- Returns:
- the static logger
-
-