3 @brief Collection of center initializers for algorithm that uses initial centers, for example, for K-Means or X-Means. 4 @details Implementation based on paper @cite article::kmeans++::1. 6 @authors Andrei Novikov, Aleksey Kukushkin (pyclustering@yandex.ru) 8 @copyright GNU Public License 10 @see pyclustering.cluster.kmeans 11 @see puclustering.cluster.xmeans 13 @cond GNU_PUBLIC_LICENSE 14 PyClustering is free software: you can redistribute it and/or modify 15 it under the terms of the GNU General Public License as published by 16 the Free Software Foundation, either version 3 of the License, or 17 (at your option) any later version. 19 PyClustering is distributed in the hope that it will be useful, 20 but WITHOUT ANY WARRANTY; without even the implied warranty of 21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 22 GNU General Public License for more details. 24 You should have received a copy of the GNU General Public License 25 along with this program. If not, see <http://www.gnu.org/licenses/>. 38 @brief Random center initializer is for generation specified amount of random of centers for specified data. 44 @brief Creates instance of random center initializer. 46 @param[in] data (list): List of points where each point is represented by list of coordinates. 47 @param[in] amount_centers (unit): Amount of centers that should be initialized. 56 raise ValueError(
"Amount of cluster centers should be at least 1.")
59 raise ValueError(
"Amount of cluster centers '%d' should be less than data size." % self.
__amount)
64 @brief Generates random centers in line with input parameters. 66 @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'return_index'). 68 <b>Keyword Args:</b><br> 69 - return_index (bool): If True then returns indexes of points from input data instead of points itself. 71 @return (list) List of initialized initial centers. 72 If argument 'return_index' is False then returns list of points. 73 If argument 'return_index' is True then returns list of indexes. 76 return_index = kwargs.get(
'return_index',
False)
79 return list(range(len(self.
__data)))
85 def __create_center(self, return_index):
87 @brief Generates and returns random center. 89 @param[in] return_index (bool): If True then returns index of point from input data instead of point itself. 92 random_index_point = random.randint(0, len(self.
__data[0]))
99 return random_index_point
100 return self.
__data[random_index_point]
106 @brief K-Means++ is an algorithm for choosing the initial centers for algorithms like K-Means or X-Means. 107 @details K-Means++ algorithm guarantees an approximation ratio O(log k). Clustering results are depends on 108 initial centers in case of K-Means algorithm and even in case of X-Means. This method is used to find 109 out optimal initial centers. 111 Algorithm can be divided into three steps. The first center is chosen from input data randomly with 112 uniform distribution at the first step. At the second, probability to being center is calculated for each point: 113 \f[p_{i}=\frac{D(x_{i})}{\sum_{j=0}^{N}D(x_{j})}\f] 114 where \f$D(x_{i})\f$ is a distance from point \f$i\f$ to the closest center. Using this probabilities next center 115 is chosen. The last step is repeated until required amount of centers is initialized. 117 Pyclustering implementation of the algorithm provides feature to consider several candidates on the second 122 amount_candidates = 3; 123 initializer = kmeans_plusplus_initializer(sample, amount_centers, amount_candidates); 126 If the farthest points should be used as centers then special constant 'FARTHEST_CENTER_CANDIDATE' should be used 127 for that purpose, for example: 130 amount_candidates = kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE; 131 initializer = kmeans_plusplus_initializer(sample, amount_centers, amount_candidates); 134 There is an example of initial centers that were calculated by the K-Means++ method: 136 @image html kmeans_plusplus_initializer_results.png 138 Code example where initial centers are prepared for K-Means algorithm: 140 from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer 141 from pyclustering.cluster.kmeans import kmeans 142 from pyclustering.cluster import cluster_visualizer 143 from pyclustering.utils import read_sample 144 from pyclustering.samples.definitions import SIMPLE_SAMPLES 146 # Read data 'SampleSimple3' from Simple Sample collection. 147 sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3) 149 # Calculate initial centers using K-Means++ method. 150 centers = kmeans_plusplus_initializer(sample, 4, kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE).initialize() 152 # Display initial centers. 153 visualizer = cluster_visualizer() 154 visualizer.append_cluster(sample) 155 visualizer.append_cluster(centers, marker='*', markersize=10) 158 # Perform cluster analysis using K-Means algorithm with initial centers. 159 kmeans_instance = kmeans(sample, centers) 161 # Run clustering process and obtain result. 162 kmeans_instance.process() 163 clusters = kmeans_instance.get_clusters() 170 FARTHEST_CENTER_CANDIDATE =
"farthest" 173 def __init__(self, data, amount_centers, amount_candidates=None):
175 @brief Creates K-Means++ center initializer instance. 177 @param[in] data (array_like): List of points where each point is represented by list of coordinates. 178 @param[in] amount_centers (uint): Amount of centers that should be initialized. 179 @param[in] amount_candidates (uint): Amount of candidates that is considered as a center, if the farthest points 180 (with the highest probability) should be considered as centers then special constant should be used 181 'FARTHEST_CENTER_CANDIDATE'. 183 @see FARTHEST_CENTER_CANDIDATE 187 self.
__data = numpy.array(data)
191 if amount_candidates
is None:
203 def __check_parameters(self):
205 @brief Checks input parameters of the algorithm and if something wrong then corresponding exception is thrown. 209 raise ValueError(
"Amount of cluster centers '" + str(self.
__amount) +
"' should be at least 1 and " 210 "should be less or equal to amount of points in data.")
212 if self.
__candidates != kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE:
214 raise ValueError(
"Amount of center candidates '" + str(self.
__candidates) +
"' should be at least 1 " 215 "and should be less or equal to amount of points in data.")
218 raise ValueError(
"Data is empty.")
221 def __calculate_shortest_distances(self, data, centers):
223 @brief Calculates distance from each data point to nearest center. 225 @param[in] data (numpy.array): Array of points for that initialization is performed. 226 @param[in] centers (numpy.array): Array of indexes that represents centers. 228 @return (numpy.array) List of distances to closest center for each data point. 232 dataset_differences = numpy.zeros((len(centers), len(data)))
233 for index_center
in range(len(centers)):
234 center = data[centers[index_center]]
236 dataset_differences[index_center] = numpy.sum(numpy.square(data - center), axis=1).T
238 with warnings.catch_warnings():
239 numpy.warnings.filterwarnings(
'ignore',
r'All-NaN (slice|axis) encountered')
240 shortest_distances = numpy.nanmin(dataset_differences, axis=0)
242 return shortest_distances
245 def __get_next_center(self, centers):
247 @brief Calculates the next center for the data. 249 @param[in] centers (array_like): Current initialized centers represented by indexes. 251 @return (array_like) Next initialized center.<br> 252 (uint) Index of next initialized center if return_index is True. 258 if self.
__candidates == kmeans_plusplus_initializer.FARTHEST_CENTER_CANDIDATE:
259 for index_point
in centers:
260 distances[index_point] = numpy.nan
261 center_index = numpy.nanargmax(distances)
269 def __get_initial_center(self, return_index):
271 @brief Choose randomly first center. 273 @param[in] return_index (bool): If True then return center's index instead of point. 275 @return (array_like) First center.<br> 276 (uint) Index of first center. 280 index_center = random.randint(0, len(self.
__data) - 1)
284 return self.
__data[index_center]
287 def __calculate_probabilities(self, distances):
289 @brief Calculates cumulative probabilities of being center of each point. 291 @param[in] distances (array_like): Distances from each point to closest center. 293 @return (array_like) Cumulative probabilities of being center of each point. 297 total_distance = numpy.sum(distances)
298 if total_distance != 0.0:
299 probabilities = distances / total_distance
300 return numpy.cumsum(probabilities)
302 return numpy.zeros(len(distances))
305 def __get_probable_center(self, distances, probabilities):
307 @brief Calculates the next probable center considering amount candidates. 309 @param[in] distances (array_like): Distances from each point to closest center. 310 @param[in] probabilities (array_like): Cumulative probabilities of being center of each point. 312 @return (uint) Index point that is next initialized center. 316 index_best_candidate = 0
318 candidate_probability = random.random()
321 for index_object
in range(len(probabilities)):
322 if candidate_probability < probabilities[index_object]:
323 index_candidate = index_object
326 if index_candidate == -1:
328 elif distances[index_best_candidate] < distances[index_candidate]:
329 index_best_candidate = index_candidate
331 return index_best_candidate
336 @brief Calculates initial centers using K-Means++ method. 338 @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'return_index'). 340 <b>Keyword Args:</b><br> 341 - return_index (bool): If True then returns indexes of points from input data instead of points itself. 343 @return (list) List of initialized initial centers. 344 If argument 'return_index' is False then returns list of points. 345 If argument 'return_index' is True then returns list of indexes. 349 return_index = kwargs.get(
'return_index',
False)
352 centers = [index_point]
358 centers.append(index_point)
362 centers = [self.
__data[index]
for index
in centers]
def __calculate_probabilities(self, distances)
Calculates cumulative probabilities of being center of each point.
def initialize(self, kwargs)
Calculates initial centers using K-Means++ method.
def __create_center(self, return_index)
Generates and returns random center.
K-Means++ is an algorithm for choosing the initial centers for algorithms like K-Means or X-Means...
def initialize(self, kwargs)
Generates random centers in line with input parameters.
def __get_probable_center(self, distances, probabilities)
Calculates the next probable center considering amount candidates.
Random center initializer is for generation specified amount of random of centers for specified data...
def __check_parameters(self)
Checks input parameters of the algorithm and if something wrong then corresponding exception is throw...
def __init__(self, data, amount_centers, amount_candidates=None)
Creates K-Means++ center initializer instance.
def __init__(self, data, amount_centers)
Creates instance of random center initializer.
def __get_next_center(self, centers)
Calculates the next center for the data.
def __get_initial_center(self, return_index)
Choose randomly first center.
def __calculate_shortest_distances(self, data, centers)
Calculates distance from each data point to nearest center.