94 lines
5.3 KiB
C++
94 lines
5.3 KiB
C++
#include <limits>
|
|
#include <vector>
|
|
#include <set>
|
|
#include <map>
|
|
#include <algorithm>
|
|
#include "../Utils/bitSet.hpp"
|
|
#include <list>
|
|
#include "undirectedGraph.hpp"
|
|
#include "outlierScore.hpp"
|
|
#include "cluster.hpp"
|
|
#include "hdbscanConstraint.hpp"
|
|
|
|
namespace hdbscanStar {
|
|
class hdbscanAlgorithm {
|
|
public:
|
|
/// <summary>
|
|
/// Calculates the core distances for each point in the data set, given some value for k.
|
|
/// </summary>
|
|
/// <param name="distances">A vector of vectors where index [i][j] indicates the jth attribute
|
|
/// of data point i</param> <param name="k">Each point's core distance will be it's distance to
|
|
/// the kth nearest neighbor</param> <returns> An array of core distances</returns>
|
|
static std::vector<double> calculateCoreDistances(std::vector<std::vector<double>> distances,
|
|
int k);
|
|
|
|
static undirectedGraph constructMst(std::vector<std::vector<double>> distances,
|
|
std::vector<double> coreDistances, bool selfEdges);
|
|
|
|
/// <summary>
|
|
/// Propagates constraint satisfaction, stability, and lowest child death level from each child
|
|
/// cluster to each parent cluster in the tree. This method must be called before calling
|
|
/// findProminentClusters() or calculateOutlierScores().
|
|
/// </summary>
|
|
/// <param name="clusters">A list of Clusters forming a cluster tree</param>
|
|
/// <returns>true if there are any clusters with infinite stability, false otherwise</returns>
|
|
|
|
static void computeHierarchyAndClusterTree(undirectedGraph* mst, int minClusterSize,
|
|
std::vector<hdbscanConstraint> constraints,
|
|
std::vector<std::vector<int>>& hierarchy,
|
|
std::vector<double>& pointNoiseLevels,
|
|
std::vector<int>& pointLastClusters,
|
|
std::vector<cluster*>& clusters);
|
|
|
|
static std::vector<int> findProminentClusters(std::vector<cluster*>& clusters,
|
|
std::vector<std::vector<int>>& hierarchy,
|
|
int numPoints);
|
|
|
|
static std::vector<double> findMembershipScore(std::vector<int> clusterids,
|
|
std::vector<double> coreDistances);
|
|
|
|
static bool propagateTree(std::vector<cluster*>& sclusters);
|
|
|
|
/// <summary>
|
|
/// Produces the outlier score for each point in the data set, and returns a sorted list of
|
|
/// outlier scores. propagateTree() must be called before calling this method.
|
|
/// </summary>
|
|
/// <param name="clusters">A list of Clusters forming a cluster tree which has already been
|
|
/// propagated</param> <param name="pointNoiseLevels">A double[] with the levels at which each
|
|
/// point became noise</param> <param name="pointLastClusters">An int[] with the last label each
|
|
/// point had before becoming noise</param> <param name="coreDistances">An array of core
|
|
/// distances for each data point</param> <returns>An List of OutlierScores, sorted in
|
|
/// descending order</returns>
|
|
static std::vector<outlierScore> calculateOutlierScores(std::vector<cluster*>& clusters,
|
|
std::vector<double>& pointNoiseLevels,
|
|
std::vector<int>& pointLastClusters,
|
|
std::vector<double> coreDistances);
|
|
|
|
/// <summary>
|
|
/// Removes the set of points from their parent Cluster, and creates a new Cluster, provided the
|
|
/// clusterId is not 0 (noise).
|
|
/// </summary>
|
|
/// <param name="points">The set of points to be in the new Cluster</param>
|
|
/// <param name="clusterLabels">An array of cluster labels, which will be modified</param>
|
|
/// <param name="parentCluster">The parent Cluster of the new Cluster being created</param>
|
|
/// <param name="clusterLabel">The label of the new Cluster </param>
|
|
/// <param name="edgeWeight">The edge weight at which to remove the points from their previous
|
|
/// Cluster</param> <returns>The new Cluster, or null if the clusterId was 0</returns>
|
|
static cluster* createNewCluster(std::set<int>& points, std::vector<int>& clusterLabels,
|
|
cluster* parentCluster, int clusterLabel, double edgeWeight);
|
|
|
|
/// <summary>
|
|
/// Calculates the number of constraints satisfied by the new clusters and virtual children of
|
|
/// the parents of the new clusters.
|
|
/// </summary>
|
|
/// <param name="newClusterLabels">Labels of new clusters</param>
|
|
/// <param name="clusters">An List of clusters</param>
|
|
/// <param name="constraints">An List of constraints</param>
|
|
/// <param name="clusterLabels">An array of current cluster labels for points</param>
|
|
static void calculateNumConstraintsSatisfied(std::set<int>& newClusterLabels,
|
|
std::vector<cluster*>& clusters,
|
|
std::vector<hdbscanConstraint>& constraints,
|
|
std::vector<int>& clusterLabels);
|
|
};
|
|
|
|
} // namespace hdbscanStar
|