[Home] DMelt member access. Java source code: jsat.clustering.hierarchical.NNChainHAC
/*
* Copyright (C) 2016 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.clustering.hierarchical;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import static jsat.clustering.ClustererBase.createClusterListFromAssignmentArray;
import jsat.clustering.KClusterer;
import jsat.clustering.KClustererBase;
import jsat.clustering.dissimilarity.LanceWilliamsDissimilarity;
import jsat.clustering.dissimilarity.WardsDissimilarity;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.math.OnLineStatistics;
import jsat.utils.FakeExecutor;
import jsat.utils.IndexTable;
import jsat.utils.IntDoubleMap;
import jsat.utils.IntDoubleMapArray;
import jsat.utils.IntList;
import jsat.utils.ListUtils;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;
/**
* This class implements Hierarchical Agglomerative Clustering via the Nearest
* Neighbor Chain approach. This runs in O(n2) time for any
* {@link LanceWilliamsDissimilarity Lance Williams} dissimilarity and uses O(n)
* memory.
* This implementation also supports multi-threaded execution.
*
* see:
*
* - Müllner, D. (2011). Modern hierarchical, agglomerative clustering
* algorithms. arXiv Preprint arXiv:1109.2378. Retrieved from
* here
* - Murtagh, F., & Contreras, P. (2011). Methods of Hierarchical Clustering.
* In Data Mining and Knowledge Discovery. Wiley-Interscience.
*
*
* @author Edward Raff
*/
public class NNChainHAC implements KClusterer
{
private LanceWilliamsDissimilarity distMeasure;
private DistanceMetric dm;
/**
* Stores the merge list, each merge is in a pair of 2 values. The final
* merge list should contain the last merged pairs at the front of the array
* (index 0, 1), and the first merges at the end of the array. The left
* value in each pair is the index of the data point that the clusters were
* merged under, while the right value is the index that was merged in and
* treated as no longer its own cluster.
*/
private int[] merges;
/**
* Creates a new NNChainHAC using the {@link WardsDissimilarity Ward} method.
*/
public NNChainHAC()
{
this(new WardsDissimilarity());
}
/**
* Creates a new NNChainHAC
* @param distMeasure the dissimilarity measure to use
*/
public NNChainHAC(LanceWilliamsDissimilarity distMeasure)
{
this(distMeasure, new EuclideanDistance());
}
/**
* Creates a new NNChain using the given dissimilarity measure and distance
* metric. The correctness guarantees may not hold for distances other than
* the {@link EuclideanDistance Euclidean} distance, which is the norm for
* Hierarchical Cluster.
*
* @param distMeasure the dissimilarity measure to use
* @param distance the distance metric to use
*/
public NNChainHAC(LanceWilliamsDissimilarity distMeasure, DistanceMetric distance)
{
this.distMeasure = distMeasure;
this.dm = distance;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
protected NNChainHAC(NNChainHAC toCopy)
{
this.distMeasure = toCopy.distMeasure.clone();
this.dm = toCopy.dm.clone();
if(toCopy.merges != null)
this.merges = Arrays.copyOf(toCopy.merges, toCopy.merges.length);
}
@Override
public NNChainHAC clone()
{
return new NNChainHAC(this);
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, 2, (int) Math.sqrt(dataSet.getSampleSize()), parallel, designations);
}
private double getDist(int a, int j, int[] size, List vecs, List cache, List
Ads help maintain this website.