kneeliverse.clustering

  1# coding: utf-8
  2
  3'''
  4The following module provides a 1D version 
  5of hierarchical clustering, optimized for 
  6linear complexity due to the use of a 
  7single dimension.
  8'''
  9
 10__author__ = 'Mário Antunes'
 11__version__ = '1.0'
 12__email__ = 'mario.antunes@ua.pt'
 13__status__ = 'Development'
 14__license__ = 'MIT'
 15__copyright__ = '''
 16Copyright (c) 2021-2023 Stony Brook University
 17Copyright (c) 2021-2023 The Research Foundation of SUNY
 18'''
 19
 20
 21import math
 22import numpy as np
 23
 24
 25def single_linkage(points: np.ndarray, t: float = 0.01) -> np.ndarray:
 26    """
 27    Computes the 1D clustering of the input points.
 28
 29    Efficient implementation that uses a single pass to compute the clusters.
 30    Computes the single linkage clustering based only on the x axis:
 31    $$
 32        D(C_1, C_2) = \\min_{c_1  \\in C_1, c_2 \\in C_2} d(c_1, c_2)
 33    $$
 34
 35    Args:
 36        points (np.ndarray): numpy array with the points (x, y)
 37        t (float): the threshold for merging (in percentage, default 0.01)
 38
 39    Returns:
 40        np.ndarray: the clusters ids
 41    """
 42    clusters = []
 43    cluster_index = 0
 44    length = points[-1, 0] - points[0, 0]
 45
 46    # First Point is a cluster
 47    clusters.append(cluster_index)
 48
 49    for i in range(1, len(points)):
 50        distance = math.fabs(points[i][0]-points[i-1][0])/length
 51        if distance >= t:
 52            cluster_index += 1
 53        clusters.append(cluster_index)
 54
 55    return np.array(clusters)
 56
 57
 58def complete_linkage(points: np.ndarray, t: float = 0.01) -> np.ndarray:
 59    """
 60    Computes the 1D clustering of the input points.
 61
 62    Efficient implementation that uses a single pass to compute the clusters.
 63    Computes the complete linkage clustering based only on the x axis:
 64    $$
 65        D(C_1, C_2) = \\max_{c_1  \\in C_1, c_2 \\in C_2} d(c_1, c_2)
 66    $$
 67
 68    Args:
 69        points (np.ndarray): numpy array with the points (x, y)
 70        t (float): the threshold for merging (in percentage, default 0.01)
 71
 72    Returns:
 73        np.ndarray: the clusters ids
 74    """
 75    clusters = []
 76    cluster_index = 0
 77    length = points[-1, 0] - points[0, 0]
 78
 79    # First Point is a cluster
 80    clusters.append(cluster_index)
 81    cluster_point_idx = 0
 82
 83    for i in range(1, len(points)):
 84        distance = math.fabs(points[i][0]-points[cluster_point_idx][0])/length
 85        if distance >= t:
 86            cluster_index += 1
 87            cluster_point_idx = i
 88        clusters.append(cluster_index)
 89
 90    return np.array(clusters)
 91
 92
 93def centroid_linkage(points: np.ndarray, t: float = 0.01) -> np.ndarray:
 94    """
 95    Computes the 1D clustering of the input points.
 96
 97    Efficient implementation that uses a single pass to compute the clusters.
 98    Computes the centroid linkage clustering based only on the x axis:
 99    $$
100        D(C_1, C_2) = ||c_1 - c_2 ||
101    $$
102
103    Args:
104        points (np.ndarray): numpy array with the points (x, y)
105        t (float): the threshold for merging (in percentage, default 0.01)
106
107    Returns:
108        np.ndarray: the clusters ids
109    """
110    clusters = []
111    cluster_index = 0
112    length = points[-1, 0] - points[0, 0]
113
114    # First Point is a cluster
115    clusters.append(cluster_index)
116    cluster_center = points[0, 0]
117    cluster_size = 1
118
119    for i in range(1, len(points)):
120        distance = math.fabs(points[i][0] - cluster_center)/length
121        if distance < t:
122            clusters.append(cluster_index)
123            # Update center
124            cluster_center = (cluster_size/(cluster_size+1)) * \
125            cluster_center + (1/(cluster_size+1)) * points[i][0]
126            cluster_size += 1
127        else:
128            cluster_index += 1
129            clusters.append(cluster_index)
130            cluster_center = points[i, 0]
131            cluster_size = 1
132
133    return np.array(clusters)
134
135
136def average_linkage(points: np.ndarray, t: float = 0.01) -> np.ndarray:
137    """
138    Computes the 1D clustering of the input points.
139
140    Efficient implementation that uses a single pass to compute the clusters.
141    Computes the average linkage clustering based only on the x axis:
142    $$
143        D(C_1, C_2) = \\frac{1}{|C_1|}\\sum_{c_1 \\in C_1}d(c_1, C_2)
144    $$
145
146    Args:
147        points (np.ndarray): numpy array with the points (x, y)
148        t (float): the threshold for merging (in percentage, default 0.01)
149
150    Returns:
151        np.ndarray: the clusters ids
152    """
153    clusters = []
154    cluster_index = 0
155    length = points[-1, 0] - points[0, 0]
156
157    # First Point is a cluster
158    clusters.append(cluster_index)
159    idx = 0
160
161    for i in range(1, len(points)):
162        cluster_points = points[idx:i, 0]
163        distances = np.abs(cluster_points - points[i][0])
164        distance = np.sum(distances)/(len(cluster_points)*length)
165        if distance >= t:
166            cluster_index += 1
167            idx = i
168        clusters.append(cluster_index)
169
170    return np.array(clusters)