weka.clusterers

Class Canopy

java.lang.Object

weka.clusterers.AbstractClusterer

weka.clusterers.RandomizableClusterer

weka.clusterers.Canopy

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Clusterer, NumberOfClustersRequestable, UpdateableClusterer, CapabilitiesHandler, CapabilitiesIgnorer, CommandlineRunnable, OptionHandler, Randomizable, RevisionHandler, TechnicalInformationHandler

public class Canopy
extends RandomizableClusterer
implements UpdateableClusterer, NumberOfClustersRequestable, OptionHandler, TechnicalInformationHandler

Cluster data using the capopy clustering algorithm, which requires just one pass over the data. Can run in eitherbatch or incremental mode. Results are generally not as good when running incrementally as the min/max for each numeric attribute is not known in advance. Has a heuristic (based on attribute std. deviations), that can be used in batch mode, for setting the T2 distance. The T2 distance determines how many canopies (clusters) are formed. When the user specifies a specific number (N) of clusters to generate, the algorithm will return the top N canopies (as determined by T2 density) when N < number of canopies (this applies to both batch and incremental learning); when N > number of canopies, the difference is made up by selecting training instances randomly (this can only be done when batch training). For more information see:

A. McCallum, K. Nigam, L.H. Ungar: Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching. In: Proceedings of the sixth ACM SIGKDD internation conference on knowledge discovery and data mining ACM-SIAM symposium on Discrete algorithms, 169-178, 2000.

BibTeX:

 @inproceedings{McCallum2000,
    author = {A. McCallum and K. Nigam and L.H. Ungar},
    booktitle = {Proceedings of the sixth ACM SIGKDD internation conference on knowledge discovery and data mining ACM-SIAM symposium on Discrete algorithms},
    pages = {169-178},
    title = {Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching},
    year = {2000}
 }
 

Valid options are:

 -N <num>
  Number of clusters.
  (default 2).

 -max-candidates <num>
  Maximum number of candidate canopies to retain in memory
  at any one time. T2 distance plus, data characteristics,
  will determine how many candidate canopies are formed before
  periodic and final pruning are performed, which might result
  in exceess memory consumption. This setting avoids large numbers
  of candidate canopies consuming memory. (default = 100)

 -periodic-pruning <num>
  How often to prune low density canopies. 
  (default = every 10,000 training instances)

 -min-density
  Minimum canopy density, below which a canopy will be pruned
  during periodic pruning. (default = 2 instances)

 -t2
  The T2 distance to use. Values < 0 indicate that
  a heuristic based on attribute std. deviation should be used to set this.
  Note that this heuristic can only be used when batch training
  (default = -1.0)

 -t1
  The T1 distance to use. A value < 0 is taken as a
  positive multiplier for T2. (default = -1.5)

 -M
  Don't replace missing values with mean/mode when running in batch mode.
 

 -S <num>
  Random number seed.
  (default 1)

 -output-debug-info
  If set, clusterer is run in debug mode and
  may output additional info to the console

 -do-not-check-capabilities
  If set, clusterer capabilities are not checked before clusterer is built
  (use with caution).

Version:

$Revision: 11012 $

Author:

Mark Hall (mhall{[at]}pentaho{[dot]}com)

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_T1
static double	DEFAULT_T2

Constructor Summary

Constructors

Constructor and Description
Canopy()

Method Summary

Modifier and Type	Method and Description
static Canopy	aggregateCanopies(java.util.List<Canopy> canopies, double aggregationT1, double aggregationT2, NormalizableDistance finalDistanceFunction, Filter missingValuesReplacer, int finalNumCanopies) Aggregate the canopies from a list of Canopy clusterers together into one final model.
long[]	assignCanopies(Instance inst) Uses T1 distance to assign canopies to the supplied instance.
void	buildClusterer(Instances data) Generates a clusterer.
void	cleanUp() Save memory
double[]	distributionForInstance(Instance instance) Predicts the cluster memberships for a given instance.
java.lang.String	dontReplaceMissingValuesTipText() Returns the tip text for this property.
double	getActualT1() Get the actual value of T1 (which may be different from the initial value if the heuristic is used)
double	getActualT2() Get the actual value of T2 (which may be different from the initial value if the heuristic is used)
Instances	getCanopies() Get the canopies (cluster centers).
Capabilities	getCapabilities() Returns default capabilities of the clusterer.
java.util.List<long[]>	getClusterCanopyAssignments() Get the canopies that each canopy (cluster center) is within T1 distance of
boolean	getDontReplaceMissingValues() Gets whether missing values are to be replaced.
int	getMaxNumCandidateCanopiesToHoldInMemory() Get the maximum number of candidate canopies to retain in memory during training.
double	getMinimumCanopyDensity() Get the minimum T2-based density below which a canopy will be pruned during periodic pruning.
int	getNumClusters() Get the number of clusters to generate
java.lang.String[]	getOptions() Gets the current settings of Canopy.
int	getPeriodicPruningRate() Get the how often to prune low density canopies during training
double	getT1() Get the T1 distance.
double	getT2() Get the T2 distance to use.
TechnicalInformation	getTechnicalInformation() Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.
java.lang.String	globalInfo() Returns a string describing this clusterer.
void	initializeDistanceFunction(Instances init) Initialize the distance function (i.e set min/max values for numeric attributes) with the supplied instances.
java.util.Enumeration<Option>	listOptions() Returns an enumeration describing the available options.
static void	main(java.lang.String[] args)
java.lang.String	maxNumCandidateCanopiesToHoldInMemory() Returns the tip text for this property.
java.lang.String	minimumCanopyDensityTipText() Returns the tip text for this property.
static boolean	nonEmptyCanopySetIntersection(long[] first, long[] second) Tests if two sets of canopies have a non-empty intersection
int	numberOfClusters() Returns the number of clusters.
java.lang.String	numClustersTipText() Returns the tip text for this property.
java.lang.String	periodicPruningRateTipText() Returns the tip text for this property.
static java.lang.String	printCanopyAssignments(Instances dataPoints, java.util.List<long[]> canopyAssignments) Print the supplied instances and their canopies
static java.lang.String	printSingleAssignment(long[] assignments)
void	setCanopies(Instances canopies) Set the canopies to use (replaces any learned by this clusterer already)
void	setClusterCanopyAssignments(java.util.List<long[]> clusterCanopies) Set the canopies that each canopy (cluster center) is within T1 distance of
void	setDontReplaceMissingValues(boolean r) Sets whether missing values are to be replaced.
void	setMaxNumCandidateCanopiesToHoldInMemory(int max) Set the maximum number of candidate canopies to retain in memory during training.
void	setMinimumCanopyDensity(double dens) Set the minimum T2-based density below which a canopy will be pruned during periodic pruning.
void	setMissingValuesReplacer(Filter missingReplacer) Set a ready-to-use missing values replacement filter
void	setNumClusters(int numClusters) Set the number of clusters to generate
void	setOptions(java.lang.String[] options) Parses a given list of options.
void	setPeriodicPruningRate(int p) Set the how often to prune low density canopies during training
void	setT1(double t1) Set the T1 distance.
void	setT2(double t2) Set the T2 distance to use.
java.lang.String	t1TipText() Tip text for this property
java.lang.String	t2TipText() Tip text for this property
java.lang.String	toString()
java.lang.String	toString(boolean header) Return a textual description of this clusterer
void	updateClusterer(Instance newInstance) Adds an instance to the clusterer.
void	updateFinished() Signals the end of the updating.

Methods inherited from class weka.clusterers.RandomizableClusterer

getSeed, seedTipText, setSeed

Methods inherited from class weka.clusterers.AbstractClusterer

clusterInstance, debugTipText, doNotCheckCapabilitiesTipText, forName, getDebug, getDoNotCheckCapabilities, getRevision, makeCopies, makeCopy, postExecution, preExecution, run, runClusterer, setDebug, setDoNotCheckCapabilities

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface weka.core.OptionHandler

makeCopy

Field Detail

DEFAULT_T2

public static final double DEFAULT_T2

See Also:

Constant Field Values

DEFAULT_T1

public static final double DEFAULT_T1

See Also:

Constant Field Values

Constructor Detail

Canopy

public Canopy()

Method Detail

globalInfo

public java.lang.String globalInfo()

Returns a string describing this clusterer.

Returns:

a description of the evaluator suitable for displaying in the explorer/experimenter gui

getTechnicalInformation

public TechnicalInformation getTechnicalInformation()

Description copied from interface: TechnicalInformationHandler

Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.

Specified by:

getTechnicalInformation in interface TechnicalInformationHandler

Returns:

the technical information about this class

getCapabilities

public Capabilities getCapabilities()

Returns default capabilities of the clusterer.

Specified by:

getCapabilities in interface Clusterer

Specified by:

getCapabilities in interface CapabilitiesHandler

Overrides:

getCapabilities in class AbstractClusterer

Returns:

the capabilities of this clusterer

See Also:

Capabilities

listOptions

public java.util.Enumeration<Option> listOptions()

Returns an enumeration describing the available options.

Specified by:

listOptions in interface OptionHandler

Overrides:

listOptions in class RandomizableClusterer

Returns:

an enumeration of all the available options.

setOptions

public void setOptions(java.lang.String[] options)
                throws java.lang.Exception

Parses a given list of options.

Valid options are:

 -N <num>
  Number of clusters.
  (default 2).

 -max-candidates <num>
  Maximum number of candidate canopies to retain in memory
  at any one time. T2 distance plus, data characteristics,
  will determine how many candidate canopies are formed before
  periodic and final pruning are performed, which might result
  in exceess memory consumption. This setting avoids large numbers
  of candidate canopies consuming memory. (default = 100)

 -periodic-pruning <num>
  How often to prune low density canopies. 
  (default = every 10,000 training instances)

 -min-density
  Minimum canopy density, below which a canopy will be pruned
  during periodic pruning. (default = 2 instances)

 -t2
  The T2 distance to use. Values < 0 indicate that
  a heuristic based on attribute std. deviation should be used to set this.
  Note that this heuristic can only be used when batch training
  (default = -1.0)

 -t1
  The T1 distance to use. A value < 0 is taken as a
  positive multiplier for T2. (default = -1.5)

 -M
  Don't replace missing values with mean/mode when running in batch mode.
 

 -S <num>
  Random number seed.
  (default 1)

 -output-debug-info
  If set, clusterer is run in debug mode and
  may output additional info to the console

 -do-not-check-capabilities
  If set, clusterer capabilities are not checked before clusterer is built
  (use with caution).

Specified by:

setOptions in interface OptionHandler

Overrides:

setOptions in class RandomizableClusterer

Parameters:

options - the list of options as an array of strings throws Exception if an option is not supported

Throws:

java.lang.Exception - if an option is not supported

getOptions

public java.lang.String[] getOptions()

Gets the current settings of Canopy.

Specified by:

getOptions in interface OptionHandler

Overrides:

getOptions in class RandomizableClusterer

Returns:

an array of strings suitable for passing to setOptions()

nonEmptyCanopySetIntersection

public static boolean nonEmptyCanopySetIntersection(long[] first,
                                                    long[] second)
                                             throws java.lang.Exception

Tests if two sets of canopies have a non-empty intersection

Parameters:

first - the first canopy set

second - the second canopy set

Returns:

true if the intersection is non-empty

Throws:

java.lang.Exception - if a problem occurs

assignCanopies

public long[] assignCanopies(Instance inst)
                      throws java.lang.Exception

Uses T1 distance to assign canopies to the supplied instance. If the instance does not fall within T1 distance of any canopies then the instance has the closest canopy assigned to it.

Parameters:

inst - the instance to find covering canopies for

Returns:

a set of canopies that contain this instance according to T1 distance

Throws:

java.lang.Exception - if a problem occurs

updateClusterer

public void updateClusterer(Instance newInstance)
                     throws java.lang.Exception

Description copied from interface: UpdateableClusterer

Adds an instance to the clusterer.

Specified by:

updateClusterer in interface UpdateableClusterer

Parameters:

newInstance - the instance to be added

Throws:

java.lang.Exception - if something goes wrong

distributionForInstance

public double[] distributionForInstance(Instance instance)
                                 throws java.lang.Exception

Description copied from class: AbstractClusterer

Predicts the cluster memberships for a given instance. Either this or clusterInstance() needs to be implemented by subclasses.

Specified by:

distributionForInstance in interface Clusterer

Overrides:

distributionForInstance in class AbstractClusterer

Parameters:

instance - the instance to be assigned a cluster.

Returns:

an array containing the estimated membership probabilities of the test instance in each cluster (this should sum to at most 1)

Throws:

java.lang.Exception - if distribution could not be computed successfully

updateFinished

public void updateFinished()

Description copied from interface: UpdateableClusterer

Signals the end of the updating.

Specified by:

updateFinished in interface UpdateableClusterer

initializeDistanceFunction

public void initializeDistanceFunction(Instances init)
                                throws java.lang.Exception

Initialize the distance function (i.e set min/max values for numeric attributes) with the supplied instances.

Parameters:

init - the instances to initialize with

Throws:

java.lang.Exception - if a problem occurs

buildClusterer

public void buildClusterer(Instances data)
                    throws java.lang.Exception

Description copied from class: AbstractClusterer

Generates a clusterer. Has to initialize all fields of the clusterer that are not being set via options.

Specified by:

buildClusterer in interface Clusterer

Specified by:

buildClusterer in class AbstractClusterer

Parameters:

data - set of instances serving as training data

Throws:

java.lang.Exception - if the clusterer has not been generated successfully

numberOfClusters

public int numberOfClusters()
                     throws java.lang.Exception

Description copied from class: AbstractClusterer

Returns the number of clusters.

Specified by:

numberOfClusters in interface Clusterer

Specified by:

numberOfClusters in class AbstractClusterer

Returns:

the number of clusters generated for a training dataset.

Throws:

java.lang.Exception - if number of clusters could not be returned successfully

setMissingValuesReplacer

public void setMissingValuesReplacer(Filter missingReplacer)

Set a ready-to-use missing values replacement filter

Parameters:

missingReplacer - the missing values replacement filter to use

getCanopies

public Instances getCanopies()

Get the canopies (cluster centers).

Returns:

the canopies

setCanopies

public void setCanopies(Instances canopies)

Set the canopies to use (replaces any learned by this clusterer already)

Parameters:

canopies - the canopies to use

getClusterCanopyAssignments

public java.util.List<long[]> getClusterCanopyAssignments()

Get the canopies that each canopy (cluster center) is within T1 distance of

Returns:

a list of canopies for each cluster center

setClusterCanopyAssignments

public void setClusterCanopyAssignments(java.util.List<long[]> clusterCanopies)

Set the canopies that each canopy (cluster center) is within T1 distance of

Parameters:

clusterCanopies - the list canopies for each cluster center

getActualT2

public double getActualT2()

Get the actual value of T2 (which may be different from the initial value if the heuristic is used)

Returns:

the actual value of T2

getActualT1

public double getActualT1()

Get the actual value of T1 (which may be different from the initial value if the heuristic is used)

Returns:

the actual value of T1

t1TipText

public java.lang.String t1TipText()

Tip text for this property

Returns:

the tip text for this property

setT1

public void setT1(double t1)

Set the T1 distance. Values < 0 are taken as a positive multiplier for the T2 distance - e.g. T1_actual = Math.abs(t1) * t2;

Parameters:

t1 - the T1 distance to use

getT1

public double getT1()

Get the T1 distance. Values < 0 are taken as a positive multiplier for the T2 distance - e.g. T1_actual = Math.abs(t1) * t2;

Returns:

the T1 distance to use

t2TipText

public java.lang.String t2TipText()

Tip text for this property

Returns:

the tip text for this property

setT2

public void setT2(double t2)

Set the T2 distance to use. Values < 0 indicate that a heuristic based on attribute standard deviation should be used to set this (note that the heuristic is only applicable when batch training).

Parameters:

t2 - the T2 distance to use

getT2

public double getT2()

Get the T2 distance to use. Values < 0 indicate that a heuristic based on attribute standard deviation should be used to set this (note that the heuristic is only applicable when batch training).

Returns:

the T2 distance to use

numClustersTipText

public java.lang.String numClustersTipText()

Returns the tip text for this property.

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setNumClusters

public void setNumClusters(int numClusters)
                    throws java.lang.Exception

Description copied from interface: NumberOfClustersRequestable

Set the number of clusters to generate

Specified by:

setNumClusters in interface NumberOfClustersRequestable

Parameters:

numClusters - the number of clusters to generate

Throws:

java.lang.Exception - if the requested number of clusters in inapropriate

getNumClusters

public int getNumClusters()

Get the number of clusters to generate

Returns:

the number of clusters to generate

periodicPruningRateTipText

public java.lang.String periodicPruningRateTipText()

Returns the tip text for this property.

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setPeriodicPruningRate

public void setPeriodicPruningRate(int p)

Set the how often to prune low density canopies during training

Parameters:

p - how often (every p instances) to prune low density canopies

getPeriodicPruningRate

public int getPeriodicPruningRate()

Get the how often to prune low density canopies during training

Returns:

how often (every p instances) to prune low density canopies

minimumCanopyDensityTipText

public java.lang.String minimumCanopyDensityTipText()

Returns the tip text for this property.

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setMinimumCanopyDensity

public void setMinimumCanopyDensity(double dens)

Set the minimum T2-based density below which a canopy will be pruned during periodic pruning.

Parameters:

dens - the minimum canopy density

getMinimumCanopyDensity

public double getMinimumCanopyDensity()

Get the minimum T2-based density below which a canopy will be pruned during periodic pruning.

Returns:

the minimum canopy density

maxNumCandidateCanopiesToHoldInMemory

public java.lang.String maxNumCandidateCanopiesToHoldInMemory()

Returns the tip text for this property.

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setMaxNumCandidateCanopiesToHoldInMemory

public void setMaxNumCandidateCanopiesToHoldInMemory(int max)

Set the maximum number of candidate canopies to retain in memory during training. T2 distance and data characteristics determine how many candidate canopies are formed before periodic and final pruning are performed. There may not be enough memory available if T2 is set too low.

Parameters:

max - the maximum number of candidate canopies to retain in memory during training

getMaxNumCandidateCanopiesToHoldInMemory

public int getMaxNumCandidateCanopiesToHoldInMemory()

Get the maximum number of candidate canopies to retain in memory during training. T2 distance and data characteristics determine how many candidate canopies are formed before periodic and final pruning are performed. There may not be enough memory available if T2 is set too low.

Returns:

the maximum number of candidate canopies to retain in memory during training

dontReplaceMissingValuesTipText

public java.lang.String dontReplaceMissingValuesTipText()

Returns the tip text for this property.

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setDontReplaceMissingValues

public void setDontReplaceMissingValues(boolean r)

Sets whether missing values are to be replaced.

Parameters:

r - true if missing values are to be replaced

getDontReplaceMissingValues

public boolean getDontReplaceMissingValues()

Gets whether missing values are to be replaced.

Returns:

true if missing values are to be replaced

printSingleAssignment

public static java.lang.String printSingleAssignment(long[] assignments)

printCanopyAssignments

public static java.lang.String printCanopyAssignments(Instances dataPoints,
                                                      java.util.List<long[]> canopyAssignments)

Print the supplied instances and their canopies

Parameters:

dataPoints - the instances to print

canopyAssignments - the canopy assignments, one assignment array for each instance

Returns:

a string containing the printed assignments

toString

public java.lang.String toString(boolean header)

Return a textual description of this clusterer

Parameters:

header - true if the header should be printed

Returns:

a string describing the result of the clustering

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

cleanUp

public void cleanUp()

Save memory

aggregateCanopies

public static Canopy aggregateCanopies(java.util.List<Canopy> canopies,
                                       double aggregationT1,
                                       double aggregationT2,
                                       NormalizableDistance finalDistanceFunction,
                                       Filter missingValuesReplacer,
                                       int finalNumCanopies)

Aggregate the canopies from a list of Canopy clusterers together into one final model.

Parameters:

canopies - the list of Canopy clusterers to aggregate

aggregationT1 - the T1 distance to use for the aggregated classifier

aggregationT2 - the T2 distance to use when aggregating canopies

finalDistanceFunction - the distance function to use with the final Canopy clusterer

missingValuesReplacer - the missing value replacement filter to use with the final clusterer (can be null for no missing value replacement)

finalNumCanopies - the final number of canopies

Returns:

a Canopy clusterer that aggregates all the canopies

main

public static void main(java.lang.String[] args)