## 1, Foreword

It refers to the division of similar data together. The specific division does not care about this kind of label. The goal is to aggregate similar data together. Clustering is an unsupervised learning method.

## 2, General process of clustering

- Data preparation: feature standardization and dimensionality reduction
- Feature selection: select the most effective feature from the original feature and store it in the vector
- Feature extraction: transform the selected features to form new prominent features
- Clustering: measure the similarity based on a certain distance function to obtain clusters
- Evaluation of clustering results: analyze clustering results, such as distance error sum (SSE), etc

## 3, Data clustering method

Data clustering methods can be divided into partition based methods, density based methods and hierarchical methods.

## 4, Criteria for measuring clustering algorithms

Different clustering algorithms have different advantages and disadvantages and different application conditions. Generally speaking, it can be seen from the attributes of data (whether sequence input, dimension), the preset of algorithm model and the processing capacity of the model. The details are as follows:

1. Algorithm processing capacity: the ability to process large data sets (i.e. algorithm complexity); Ability to deal with data noise; The ability to handle arbitrary shapes, including nested data with gaps;

2. Whether the algorithm needs preset conditions: whether the number of clusters needs to be known in advance and whether the user needs to give domain knowledge;

3. Data input attribute of algorithm: whether the result of algorithm processing is related to the order of data input, that is, whether the algorithm is independent of the order of data input; The algorithm has the ability to process many attribute data, that is, whether it is sensitive to the dimension of data and whether it has requirements for the type of data.

## 5, Algorithm implementation

#k-means++ class KMeansClusterAlgorithm(object): ''' this class is k-means cluster algorithm Author: xxx Date: 2022-02-10 ''' def __init__(self, dataset: list, k: int) -> None: ''' initial Args Args: dataset:list. like [[x1,y1],[x2,y2)] k:int. number of cluster what to get ''' self.dataset = dataset self.k = k def point_avg(self, points) -> list: ''' Accepts a list of points, each with the same number of dimensions. NB. points can have more dimensions than 2 Returns a new points which is the center of all the points Args: points:list. a list of points, like [[x,y],[x1,y1],[x2,y2]] Return: new_center: list ''' dimensions = len(points[0]) new_center = [] for dimension in range(dimensions): dim_sum = 0 for p in points: dim_sum += p[dimension] # average of each dimension new_center.append(dim_sum/float(len(points))) return new_center # def update_centers(self, date_set, assignments): def update_centers(self, assignments) -> list: ''' Accepts a dataset and a list of assignments; the indexes of both lists correspond to each other. compute the center for each of the assigned groups. Reture 'k' centers where is the number of unique assignments. Args: dataset: assignments: Return: centers:list ex:[[1,2]] ''' new_means = defaultdict(list) centers = [] for assigment, point in zip(assignments, self.dataset): new_means[assigment].append(point) for points in new_means.values(): centers.append(self.point_avg(points)) return centers def distance(self, a: list, b: list) -> int: ''' caculate two points' distance Args: a:list. point a,ex:[1,3] b:list. point b,ex:[1,3] Return: :int: the distance of two point ''' dimensions = len(a) _sum = 0 for dimension in range(dimensions): difference_seq = (a[dimension] - b[dimension]) ** 2 _sum += difference_seq return sqrt(_sum) def _assign_points(self, centers) -> list: ''' assign each point to an index that corresponds to the index of the center point on its proximity to that point. Return a an array of indexes of the centers that correspond to an index in the data set; that is, if there are N points in data set the list we return will have N elements. Also If there ara Y points in centers there will be Y unique possible values within the returned list. Args: data_points:list ex:[[1,2],[3,4],[5,6]] centers:list ex:[[3,4]] Return: assigments:list ''' assigments = [] for point in self.dataset: shortest = float('Inf') shortest_index = 0 for i in range(len(centers)): val = self.distance(point, centers[i]) if val < shortest: shortest = val shortest_index = i assigments.append(shortest_index) return assigments # def generate_k(self, data_set: list, k: int, centers: list = []) -> list: def _generate_k(self, centers: list = []) -> list: ''' Given data set, which is an list of lists, find the minimum and maximum for each coordinate,a range. Generate k random points between the ranges. Return a list of the random points within the ranges use self.dataset self.k Args: data_set:list. ex:[[1,2],[3,4]] k:int. the number of clusters Return: list ex:[[1,2]] ''' # centers = [] dimensions = len(self.dataset[0]) min_max = defaultdict(int) for point in self.dataset: for i in range(dimensions): val = point[i] min_key = f'min_{i}' max_key = f'max_{i}' if min_key not in min_max or val < min_max[min_key]: min_max[min_key] = val if max_key not in min_max or val > min_max[max_key]: min_max[max_key] = val for _k in range(self.k): rand_point = [] for i in range(dimensions): min_val = min_max[f'min_{i}'] max_val = min_max[f'max_{i}'] rand_point.append(uniform(min_val, max_val)) centers.append(rand_point) return centers def _euler_distance(self, point1: list, point2: list) -> float: ''' Calculate euler distance between two points, support multidimensional Args: point1:list point2:list Return: :float ''' distance = 0.0 for a, b in zip(point1, point2): distance += math.pow(a - b, 2) return math.sqrt(distance) def get_closest_dist(self, point, centroids) -> float: ''' get closest dist between two point Args: point1:list centroids:list. the center of cluster Return: min_dist:float ''' min_dist = math.inf # Initial set to infinity for i, centroid in enumerate(centroids): dist = self._euler_distance(centroid, point) if dist < min_dist: min_dist = dist return min_dist def _kpp_centers(self) -> list: ''' calculate cluster center use self.dataset and self.k Return: cluster_centers:list. self.k(the number of cluster center that user defined) cluster center ''' cluster_centers = [] cluster_centers.append(random.choice(self.dataset)) d = [0 for _ in range(len(self.dataset))] for _ in range(1, self.k): total = 0.0 for i, point in enumerate(self.dataset): # The distance from the nearest cluster center d[i] = self.get_closest_dist(point, cluster_centers) total += d[i] total *= random.random() # The next clustering center is selected by wheel method. for i, di in enumerate(d): total -= di if total > 0: continue cluster_centers.append(self.dataset[i]) break return cluster_centers # def k_means(self, dataset:list, k:int): def k_means_plusplus(self) -> tuple: ''' the enter of k-means cluster algorithm Args: data_set:list. ex:[[1,2],[3,4]] k:int. the number of clusters Return: (assignments, self.dataset):tuple (result list,origin datalist) ''' # k_points = self._generate_k() #[[1,2],[3,4]] k_points = self._kpp_centers() assignments = self._assign_points(k_points) # [1,2,1,1,0,0,4] old_assignments = None times = 0 while assignments != old_assignments: new_centers = self.update_centers(assignments) # [[11.2],[12.2]] old_assignments = assignments assignments = self._assign_points(new_centers) return (assignments, self.dataset)

reference material

https://zhuanlan.zhihu.com/p/...

https://blog.csdn.net/abc2009...

https://blog.csdn.net/weixin_...

https://www.cnblogs.com/wang2...