Package elki.clustering.dbscan
Class LSDBC<O extends NumberVector>
- java.lang.Object
-
- elki.clustering.dbscan.LSDBC<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Algorithm
,ClusteringAlgorithm<Clustering<Model>>
@Title("LSDBC: Locally Scaled Density Based Clustering") @Reference(authors="E. Bi\u00e7ici, D. Yuret", title="Locally Scaled Density Based Clustering", booktitle="Adaptive and Natural Computing Algorithms", url="https://doi.org/10.1007/978-3-540-71618-1_82", bibkey="DBLP:conf/icannga/BiciciY07") @Priority(100) public class LSDBC<O extends NumberVector> extends java.lang.Object implements ClusteringAlgorithm<Clustering<Model>>
Locally Scaled Density Based Clustering.This is a variant of DBSCAN which starts with the most dense point first, then expands clusters until density has dropped below a threshold.
Reference:
E. Biçici, D. Yuret
Locally Scaled Density Based Clustering
Adaptive and Natural Computing Algorithms- Since:
- 0.7.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
LSDBC.Par<O extends NumberVector>
Parameterization class-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field Description protected double
alpha
Alpha parameter.protected Distance<? super O>
distance
Distance function used.protected int
kplus
Number of neighbors (+ query point)private static Logging
LOG
Class logger.protected static int
NOISE
Constants used internally.protected static int
UNPROCESSED
Constants used internally.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected int
expandCluster(int clusterid, WritableIntegerDataStore clusterids, KNNSearcher<DBIDRef> knnq, DBIDs neighbors, double maxkdist, FiniteProgress progress)
Set-based expand cluster implementation.private void
fillDensities(KNNSearcher<DBIDRef> knnq, DBIDs ids, WritableDoubleDataStore dens)
Collect all densities into an array for sorting.TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.private boolean
isLocalMaximum(double kdist, DBIDs neighbors, WritableDoubleDataStore kdists)
Test if a point is a local density maximum.Clustering<Model>
run(Relation<O> relation)
Run the LSDBC algorithm-
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.
-
kplus
protected int kplus
Number of neighbors (+ query point)
-
alpha
protected double alpha
Alpha parameter.
-
distance
protected Distance<? super O extends NumberVector> distance
Distance function used.
-
UNPROCESSED
protected static int UNPROCESSED
Constants used internally.
-
NOISE
protected static int NOISE
Constants used internally.
-
-
Method Detail
-
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
-
run
public Clustering<Model> run(Relation<O> relation)
Run the LSDBC algorithm- Parameters:
relation
- Data relation- Returns:
- Clustering result
-
isLocalMaximum
private boolean isLocalMaximum(double kdist, DBIDs neighbors, WritableDoubleDataStore kdists)
Test if a point is a local density maximum.- Parameters:
kdist
- k-distance of currentneighbors
- Neighbor pointskdists
- kNN distances- Returns:
true
when the point is a local maximum
-
expandCluster
protected int expandCluster(int clusterid, WritableIntegerDataStore clusterids, KNNSearcher<DBIDRef> knnq, DBIDs neighbors, double maxkdist, FiniteProgress progress)
Set-based expand cluster implementation.- Parameters:
clusterid
- ID of the current cluster.clusterids
- Current object to cluster mapping.knnq
- kNNQueryneighbors
- Neighbors acquired by initial getNeighbors call.maxkdist
- Maximum k-distanceprogress
- Progress logging- Returns:
- cluster size
-
fillDensities
private void fillDensities(KNNSearcher<DBIDRef> knnq, DBIDs ids, WritableDoubleDataStore dens)
Collect all densities into an array for sorting.- Parameters:
knnq
- kNN queryids
- DBIDs to processdens
- Density storage
-
-