Package elki.clustering.svm
Class SupportVectorClustering
- java.lang.Object
-
- elki.clustering.svm.SupportVectorClustering
-
- All Implemented Interfaces:
Algorithm
,ClusteringAlgorithm<Clustering<? extends Model>>
@Reference(authors="A. Ben-Hur, D. Horn, H. T. Siegelmann, V. Vapnik",title="A Support Vector Method for Clustering",booktitle="Neural Information Processing Systems",url="https://proceedings.neurips.cc/paper/2000/hash/14cfdb59b5bda1fc245aadae15b1984a-Abstract.html",bibkey="DBLP:conf/nips/Ben-HurHSV00") @Reference(authors="A. Ben-Hur, H. T. Siegelmann, D. Horn, V. Vapnik",title="A Support Vector Clustering Method",booktitle="International Conference on Pattern Recognition (ICPR)",url="https://doi.org/10.1109/ICPR.2000.906177",bibkey="DBLP:conf/icpr/Ben-HurSHV00") @Reference(authors="A. Ben-Hur, D. Horn, H. T. Siegelmann, V. Vapnik",title="Support Vector Clustering",booktitle="Journal of Machine Learning Research",url="http://jmlr.org/papers/v2/horn01a.html",bibkey="DBLP:journals/jmlr/Ben-HurHSV01") public class SupportVectorClustering extends java.lang.Object implements ClusteringAlgorithm<Clustering<? extends Model>>
Support Vector Clustering works on SVDD, which tries to find the smallest sphere enclosing all objects in kernel space. SupportVectorClustering then checks if the line between two data points stay inside the sphere in kernel space. Clusters are those points connected by enclosed lines.References:
A. Ben-Hur, D. Horn, H. T. Siegelmann, V. Vapnik
A Support Vector Method for Clustering
Neural Information Processing SystemsA. Ben-Hur, H. T. Siegelmann, D. Horn, V. Vapnik
A Support Vector Clustering Method
International Conference on Pattern Recognition (ICPR)A. Ben-Hur, D. Horn, H. T. Siegelmann, V. Vapnik
Support Vector Clustering
Journal of Machine Learning Research 2 (2001)- Since:
- 0.8.0
- Author:
- Robert Gehde
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field Description (package private) double
C
C parameter.(package private) PrimitiveSimilarity<? super NumberVector>
kernel
Kernel function.private static Logging
LOG
Class logger.(package private) int
lsz
Sample size for line check.
-
Constructor Summary
Constructors Constructor Description SupportVectorClustering(PrimitiveSimilarity<? super NumberVector> kernel, double C)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private boolean
accept(NumberVector cur, RegressionModel model, double fixed, ArrayDBIDs ids, SimilarityQuery<NumberVector> sim, double r_square)
evaluate if a point cur is inside the sphere in kernel space.private double
calcfixedpart(RegressionModel model, ArrayDBIDs ids, SimilarityQuery<NumberVector> sim)
calculate fixed part of model evaluationprivate boolean
checkConnectivity(Relation<NumberVector> relation, double[] start, DBIDRef destRef, RegressionModel model, double fixed, ArrayDBIDs ids, SimilarityQuery<NumberVector> sim, double r_squared)
Checks if the connecting line between start and dest lies inside the kernel space sphere.private java.util.ArrayList<ArrayModifiableDBIDs>
collectClusters(StaticDBIDs sids, UnionFind uf)
TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.Clustering<Model>
run(Relation<NumberVector> relation)
perform clustering-
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
Class logger.
-
kernel
PrimitiveSimilarity<? super NumberVector> kernel
Kernel function.
-
C
double C
C parameter.
-
lsz
int lsz
Sample size for line check. (lsz-1 are between the points, last is on point)
-
-
Constructor Detail
-
SupportVectorClustering
public SupportVectorClustering(PrimitiveSimilarity<? super NumberVector> kernel, double C)
Constructor.- Parameters:
kernel
- kernel to useC
- C parameter
-
-
Method Detail
-
run
public Clustering<Model> run(Relation<NumberVector> relation)
perform clustering- Parameters:
relation
- relation to cluster- Returns:
- clustering
-
checkConnectivity
private boolean checkConnectivity(Relation<NumberVector> relation, double[] start, DBIDRef destRef, RegressionModel model, double fixed, ArrayDBIDs ids, SimilarityQuery<NumberVector> sim, double r_squared)
Checks if the connecting line between start and dest lies inside the kernel space sphere.- Parameters:
relation
- databasestart
- start vector as arraydestRef
- dest vector as DBIDRefmodel
- model containing spherefixed
- fixed part of evaluationids
- ArrayDBIDs used to train modelsim
- Similarity Query used to train modelr_squared
- squared radius of trained model- Returns:
- true if connected, false if not
-
accept
private boolean accept(NumberVector cur, RegressionModel model, double fixed, ArrayDBIDs ids, SimilarityQuery<NumberVector> sim, double r_square)
evaluate if a point cur is inside the sphere in kernel space.- Parameters:
cur
- point to evaluatemodel
- Model to check the point infixed
- fixed part of calculationids
- IDs used for accesssim
- kernel similarity queryr_square
- squared radius- Returns:
- true iff point is inside sphere
-
calcfixedpart
private double calcfixedpart(RegressionModel model, ArrayDBIDs ids, SimilarityQuery<NumberVector> sim)
calculate fixed part of model evaluation- Parameters:
model
- model to calculate the fixed part forids
- IDs for accesssim
- kernel similarity query- Returns:
- fixed part of evaluation
-
collectClusters
private java.util.ArrayList<ArrayModifiableDBIDs> collectClusters(StaticDBIDs sids, UnionFind uf)
-
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
- Returns:
- Type restriction
-
-