10.39. Compute K Means

Group (Subgroup)

DREAM3D Review (Clustering)

Description

Warning: The randomness in this filter is not currently consistent between operating systems even if the same seed is used. Specifically between Unix and Windows. This does not affect the results, but the IDs will not correspond. For example if the Cluster Identifier at index one on Linux is 1 it could be 2 on Windows, the overarching clusters will be the same, but their IDs will be different.

This Filter applies the k means algorithm to an Attribute Array. K means is a clustering algorithm that assigns each point (each tuple) of the Attribute Array to a cluster Id. A cluster is a group of data points that are more similar to each other than to points in other groups. The user must specify the number of clusters (a dimensionless count, k) in which to partition the array.

Each cluster is summarized by its centroid, which is the arithmetic mean (the average position) of all the points assigned to that cluster. A k means partitioning is a Voronoi tessellation: every point is assigned to the cluster whose centroid is closest to it, so the data space is carved into regions where each region contains all the points nearer to one centroid than to any other. An optimal solution to the k means problem is one in which each point is associated with the cluster that has the closest mean. This partitioning minimizes the within-cluster variance, that is, the sum over all clusters of the squared distances from each point to its cluster centroid; minimizing it makes the points within each cluster as tightly grouped as possible. The user may select from several distance metrics: Euclidean, Squared Euclidean, Manhattan, Cosine, Pearson, and Squared Pearson.

Distance Metric

The Distance Metric parameter determines how distances between data points are measured when assigning points to clusters:

• Euclidean [0]: Standard straight-line distance between two points in the data space.

• Squared Euclidean [1]: The square of the Euclidean distance. Avoids a square root computation and gives extra weight to larger differences.

• Manhattan [2]: Sum of the absolute differences along each dimension (also known as L1 or city-block distance).

• Cosine [3]: One minus the cosine similarity between two points. Measures the angle between vectors, making it invariant to magnitude.

• Pearson [4]: One minus the Pearson correlation coefficient. Measures the linear correlation between two points, normalized by their standard deviations.

• Squared Pearson [5]: The square of the Pearson distance metric.

Optimal solutions to the k means partitioning problem are computationally difficult; this Filter used Lloyd’s algorithm to approximate the solution. Lloyd’s algorithm is an iterative algorithm that proceeds as follows:

1. Choose k points at random to serve as the initial cluster “means”

2. Until convergence, repeat the following steps:

• Associate each point with the closest mean, where “closest” is determined by the selected distance metric

• Recompute the means based on the new tessellation

Convergence is defined as when the computed means change very little (precisely, when the differences are within machine epsilon). Since Lloyd’s algorithm is iterative, it only serves as an approximation, and may result in different classifications on each execution with the same input data. The user may opt to use a mask to ignore certain points; where the mask is false, the points will be placed in cluster 0.

Note: In SIMPLNX there is no explicit positional subtyping for Attribute Matrix, so the next section should be treated as a high-level understanding of what is being created. Naming the Attribute Matrix to include the type listed on the respective line in the ‘Attribute Matrix Created’ column is encouraged to help with readability and comprehension.

A clustering algorithm can be considered a kind of segmentation; this implementation of k means does not rely on the Geometry on which the data lie, only on the arrangement of the values within the array itself (the topology of the space that the array forms). Therefore, this Filter has the effect of creating either Features or Ensembles depending on the kind of array passed to it for clustering. If an Element array (e.g., voxel-level Cell data) is passed to the Filter, then Features are created (in the previous example, a Cell Feature Attribute Matrix will be created). If a Feature array is passed to the Filter, then an Ensemble Attribute Matrix is created. The following table shows what type of Attribute Matrix is created based on what sort of array is used for clustering:

Attribute Matrix Source	Attribute Matrix Created
Generic	Generic
Vertex	Vertex Feature
Edge	Edge Feature
Face	Face Feature
Cell	Cell Feature
Vertex Feature	Vertex Ensemble
Edge Feature	Edge Ensemble
Face Feature	Face Ensemble
Cell Feature	Cell Ensemble
Vertex Ensemble	Vertex Ensemble
Edge Ensemble	Edge Ensemble
Face Ensemble	Face Ensemble
Cell Ensemble	Cell Ensemble

The filter creates a cluster Ids array (one dimensionless integer cluster label per input point) alongside the input array, and stores the final cluster means (one mean vector per cluster, in the units of the input array) within the created Attribute Matrix.

Related Filters

• Compute K Medoids uses representative data points (medoids) instead of means as the cluster centers.

• DBSCAN is a density-based clustering algorithm that does not require the number of clusters to be specified in advance.

• Silhouette evaluates the quality of a clustering produced by this filter.

Required Input Sources

• Clustered Attribute Array – any Attribute Array (cell-level, feature-level, or generic) whose tuples are to be partitioned into clusters. This is typically an output of an earlier computation or import step.

Random Number Seed Parameters

Parameter Name	Parameter Type	Parameter Notes	Description
Use Seed for Random Generation	Bool		When true the user will be able to put in a seed for random generation
Seed Value	Scalar Value	UInt64	The seed fed into the random generator
Stored Seed Value Array Name	DataObjectName		Name of array holding the seed value

Input Parameter(s)

Parameter Name	Parameter Type	Parameter Notes	Description
Number of Clusters	Scalar Value	UInt64	This will be the tuple size for Cluster Attribute Matrix and the values within
Distance Metric	Choices		Distance Metric type to be used for calculations

Optional Data Mask

Parameter Name	Parameter Type	Parameter Notes	Description
Use Mask Array	Bool		Specifies whether or not to use a mask array
Cell Mask Array	Array Selection	Allowed Types: uint8, boolean	DataPath to the boolean or uint8 mask array. Values that are true will mark that cell/point as usable.

Input Data Objects

Parameter Name	Parameter Type	Parameter Notes	Description
Attribute Array to Cluster	Array Selection	Allowed Types: int8, uint8, int16, uint16, int32, uint32, int64, uint64, float32, float64	The array to cluster from

Output Data Object(s)

Parameter Name	Parameter Type	Parameter Notes	Description
Cluster Ids Array Name	DataObjectName		name of the ids array to be created in Attribute Array to Cluster’s parent group
Cluster Attribute Matrix	DataGroupCreation		name and path of Attribute Matrix to hold Cluster Data
Cluster Means Array Name	DataObjectName		name of the Means array to be created in Cluster Attribute Matrix

References

[1] Least squares quantization in PCM, S.P. Lloyd, IEEE Transactions on Information Theory, vol. 28 (2), pp. 129-137, 1982.

Example Pipelines

License & Copyright

Please see the description file distributed with this Plugin

DREAM3D-NX Help

If you need help, need to file a bug report or want to request a new feature, please head over to the DREAM3DNX-Issues GitHub site where the community of DREAM3D-NX users can help answer your questions.