Quantum clustering

Quantum clustering (QC), is a data clustering algorithm accomplished by substituting each point in a given dataset with a Gaussian. The width of the Gaussian is a sigma value, a hyper-parameter which can be manually defined and manipulated to suit the application. Gradient descent is then used to "move" the points to their local minima. These local minima then define the cluster centers. QC has not been evaluated against traditional modern clustering algorithms, aside from Jaccard scoring. QC has thus far failed to produce separations with enough variance to exploit at big data scale.

Not to be confused with Quantum Computing.

Approximate quantum clustering

Approximate quantum clustering (AQC) attempts to tame some of the computational complexity of QC by reducing the allowed number of Gaussians in a given region. If a pixel is a physical point in a rendering which represents the smallest addressable element (pix, for pictures, el for element), then a voxel is a three-dimensional version of the pixel (vox for volume, el for element). These voxels, while uniform in the space they represent, do not have to be homogenous in their contents. Once the volume of the voxel has been established, AQC limits the allowed number of Gaussians to a maximum of one per voxel. When compared to the quadratic limitations of QC, AQC has the benefit of limiting the computational complexity to O(n * p), where n represents the number of Gaussians, and p represents the number of data points.

Limiting behavior

Traditional approaches to QC tend toward quadratic O(n^2), while solutions in deep learning are necessarily linearly limited due to scale and complexity: O(n).

With the possible exception of exponent distance-based quantum clustering algorithms, many QC solutions still required data preprocessing (primarily, cleaning to resolve noise, artifacting, column gapping and interchange). This preprocessing step, even when successful, would introduce inherent data bias by corrupting the full richness of the data set.

Dynamic quantum clustering

Developed by David Horn and Marvin Weinstein in 2009, Dynamic Quantum Clustering (DQC) approaches the complexity problem from a different heading than AQC. Using a mathematical shortcut to simplify the gradient descent, it also features the ability of nearby points in adjacent local minima to "tunnel" and resolve to a single cluster. A tunneling hyper-parameter determines whether or not a data point "tunnels" based on the width of the Gaussian.

References
    1. Brooke, J; Bitko, D.; Rosenbaum, T. F; Aeppli, G. (1999) Quantum Annealing of a Disordered Magnet
    2. Farhi, E.; Goldstone, J.; Gutmann, S.; Sipser, M. (2000) Quantum Computation by Adiabatic Evolution
    3. Kaminsky, W. M.; Lloyd, S.; Orlando, T. P. (2004) Scalable Superconducting Architecture for Adiabatic Quantum Computation
    4. Yao, Z.; Peng, W.; Gao-yun, C.; Dong-Dong, C.; Rui, Ding; Yan, Z (2008) Quantum Clustering Algorithm based on Exponent Measuring Distance
    5. Horn, D.; Gottlieb, A. (2002) Algorithm for data clustering in pattern recognition problems based on quantum mechanics
    6. Weinstein, M.; Horn, D. (2009) Dynamic quantum clustering: a method for visual exploration of structures in data
    7. Scott, T.C., Therani, M., Wang X.M. (2017) Data Clustering with Quantum Mechanics, Mathematics, vol. 5, No. 5, p.1-17.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.