[译]使用人工智能K均值聚类算法对数据进行分类

By robot-v1.0

本文链接 https://www.kyfws.com/ai/classifying-data-using-artificial-intelligence-k-m-zh/

01月01日, 0001 - 37 分钟阅读 - 18068 个词 阅读量 0

使用人工智能K均值聚类算法对数据进行分类（译文）

原文地址：https://www.codeproject.com/Articles/5256294/Classifying-Data-Using-Artificial-Intelligence-K-M

原文作者：Arthur V. Ratz

译文由本站 robot-v1.0 翻译

前言

A simple introduction to using K-Means Clustering for data analysis.

使用K-Means聚类进行数据分析的简单介绍.

下载KMeans_Clustering.zip-136 KB(Download KMeans_Clustering.zip - 136 KB)
下载KMeans_Clustering_EXE.zip-50.7 KB(Download KMeans_Clustering_EXE.zip - 50.7 KB) "(“)集群的主要目的不仅在于建立集群,还在于建立良好而有意义的集群(The primary aim of clustering is not just to make clusters, but to make good and meaningful ones)" – Analytics Vidhya((” – Analytics Vidhya () https://www.analyticsvidhya.com/(https://www.analyticsvidhya.com/) )()).(.)

介绍(Introduction)

最佳的多目标聚类是最流行的,同时也是好奇的有监督的机器学习问题,它发生在计算机科学的许多领域,例如数据和知识挖掘,数据压缩,矢量量化,模式检测和分类,Voronoi图,推荐引擎(RE)等.聚类分析过程本身使我们能够揭示输入数据集上展现的各种趋势和见解.(An optimal multi-objective clustering is one of the most popular, and, at the same time, curious supervised machine learning problems, that occurs in many fields of computer science such as data and knowledge mining, data compression, vector quantization, patterns detection and classification, Voronoi diagrams, recommender engines (RE), etc. The process of clustering analysis itself allows us to reveal various of trends and insights exhibited on the input dataset.)

聚类分析(CA)过程使我们能够确定特定数据之间的相似性和差异,对数据进行划分,例如使相似数据通常属于特定组或聚类.例如,我们可以基于余额和贷款额度标准对信用卡客户的数据进行聚类分析,以揭示应为特定客户提供哪些特殊优惠.在这种情况下,我们要做的就是将所有客户数据划分为多个群集,然后向相似的客户提供相同的报价.这通常是通过执行多元数值数据,多元数值数据聚类分析来完成的.(The cluster analysis (CA) process allows us to determine the similarities and differences between specific data, partitioning the data in such as a way that the similar data normally belongs to a specific group or cluster. For example, we can perform the clustering analysis of the data on a credit card customer to reveal what special offers should be given to a specific customer, based on the balance and loan amount criteria. In this case, all that we have to do is to partition all customers data into the number of clusters, and, then give the same offer to the similar customers. This is typically done by performing the multi-variate numerical data the multi-variate numerical data clustering analysis.)

执行实际聚类的主要目标是将具有相关联的特征数字n维矢量的一组数据项安排到称为"簇"的同质组中.通常,可以将整个聚类问题表述为某个目标相似性函数最小化问题.作为相似性目标函数,使用了各种代数概念. n维欧几里得空间中向量之间的欧几里得距离是最流行的概念之一,在许多现有的聚类分析技术和算法中都得到积极使用.下图说明了执行数据聚类的示例:(The main goal of performing the actual clustering is to arrange a set of data items having an associated numeric n-dimensional vector of features into the number of homogeneous groups, called - “clusters”. In general, the entire clustering problem can be formulated as a certain objective similarity function minimization problem. As the similarity objective function, various of algebraic notions are used. The Euclidean distance between vectors in an n-dimensional Euclidean space is one of the most popular notions that is actively used in the vast of the existing clustering analysis techniques and algorithms. The figure below illustrates an example of performing data clustering:)

从上图可以看到,各种数据被分为三个集群,每个集群包含最相似的数据.(As you can see from the figure above, the various data are partitioned into the number of three clusters, each one is containing the most similar data.)

在基于最小化相似性目标函数的已知聚类算法中,k均值算法得到最广泛的应用.给定真实n维空间中的t个数据点集和整数k,问题在于确定欧几里德空间中的k个点集(称为中心),并最大程度地减少与每个数据点的均方距离到最接近的质心.这种度量通常称为平方误差失真,这种类型的聚类属于基于方差的聚类类别.(Among the known clustering algorithms, that are based on minimizing a similarity objective function, k-means algorithm is most widely used. Given a set of t data points in real n-dimensional space, and an integer k, the problem is to determine a set of k points in the Euclidean space, called centers, as well as to minimize the mean squared distance from each data point to its nearest centroid. This measure is often called the squared-error distortion and this type of clustering belongs to the variance-based clustering category.)

基于k均值的聚类与许多其他聚类和位置问题密切相关.这些包括欧几里德k中间值(或多源Weber问题),其目的是使到最近中心的距离的总和最小化;几何k中心问题,其目的是使每个点到最大点的最大距离最小化.其最近的中心.(Clustering based on k-means is closely related to a number of other clustering and location problems. These include the Euclidean k-medians (or the multisource Weber problem) in which the objective is to minimize the sum of distances to the nearest center and the geometric k-center problem in which the objective is to minimize the maximum distance from every point to its closest center.)

基于使用k-means算法来解决聚类问题的一种最流行的启发式方法基本上依赖于一种简单的迭代方法来找到一组聚类. k均值算法有多种变体.具体来说,在本文中,我们将重点介绍由劳埃德(Lloyd)提出的算法讨论.(One of the most popular heuristics for solving the clustering problem based on using the k-means algorithm basically relies on a simple iterative method for finding a set of clusters. There is a number of variations of the k-means algorithm. Specifically, in this article, we will spotlight our discussion on the algorithm, proposed by Lloyd.)

此外,我们将讨论经典k均值算法优化的多个方面,旨在提高聚类的实际质量以及提供以下算法的有效性能.(Moreover, we will discuss about the number of aspects of the classical k-means algorithm optimization aiming to improve the actual quality of clustering as well as to provide an efficient performance of the following algorithm.)

另外,我们将介绍各种度量标准,使我们能够评估聚类过程的质量,例如惯性或Dunn指数.(Also, we will introduce various of metrics that allow us to evaluate the quality of clustering process such as the inertia or Dunn index.)

最后,我们将讨论在C#.NET中优化的k-均值算法的有效实现.(Finally, we will discuss about an efficient implementation of the optimized k-means algorithm in C#.NET.)

背景(Background)

在本章中,我们将介绍和制定k-means聚类算法,其中包括算法级优化的数量,这些算法使我们能够大幅度提高聚类的质量,并提高聚类过程本身的性能.(In this chapter, we will introduce and formulate the k-means clustering algorithm, including the number of algorithm-level optimization that allow us to drastically improve the quality of clustering, as well as increase the performance of the clustering process itself.)

聚类分析(CA)基础(Clustering Analysis (CA) Fundamentals)

聚类分析(CA)是将一组数据项分为一定数量的组的过程,每个组包含最相似的项.这些组称为"集群". “群集"本身通常用于更好地了解正在分析的数据,数据压缩或新颖性检测.(Clustering Analysis (CA) is the process of arranging a set of data items into a certain number of the groups, each one containing the items that are the most similar. These groups are called “clusters”. The “clustering” itself is commonly used for providing a better understanding of the data being analyzed, data compression or novelty detection.)

聚类分析是数据挖掘和统计数据的重要组成部分,它基本上依赖于使用数字监督机器学习算法,该算法允许我们执行实际的聚类.这些算法通常提供各种方法,这些方法通常可以具体解决整个聚类问题.至少有3种流行的聚类算法,例如k均值或模糊c均值聚类,以及期望最小化(EM)算法,用于解决部分或不完整的数据聚类问题等.(The clustering analysis is an essential part of the data mining and statistics, that basically relies on the using of the number supervised machine learning algorithms that allow us to perform the actual clustering. These algorithms typically provide the various of approaches how specifically the entire clustering problem can be solved in general. There’re at least three popular clustering algorithms, such as either k-means or fuzzy c-means clustering, as well as the expectation-minimization (EM) algorithm addressing a partial or incomplete data clustering problem, etc.)

此外,关于如何确定特定数据的相似性以及如何将这些数据排列成簇的想法和观点也很多.确定数据相似性的一种流行方法是测量特定数据之间的实际欧几里得距离,然后根据最小距离标准将它们分组为簇.以下方法主要用于确定可以轻松表示为n维欧几里得空间中矢量数量的数据的相似性.这些向量中的每一个都包含许多数字特征(Also, there’re the vast of ideas and points of view on how to determine the similarity of specific data and arrange these data into clusters. A popular approach for determining the similarity of data is to measure the actual Euclidean distance between specific data and group them into clusters based on the smallest distance criteria. The following approach is primarily used for determining the similarity of the data that can be easily represented as the number of vectors in n-dimensional Euclidean space. Each of these vectors consists of the number of numerical features)$ \ bar {u} =\ {u_1,u_2,u_3,…,u_ {n-1},u_n } $(*$\bar{u}={u_1,u_2,u_3,…,u_{n-1},u_n}$*)两个向量之间的实际距离(*The actual distance between two vectors*)$ \ bar {u} $(*$\bar{u}$*)和(*and*)$ \ bar {v} $(*$\bar{v}$*)可以使用以下欧几里德距离公式来测量:(*can be measured by using the following Euclidean distance formula:*)

$ {\ left \ Vert {} {D} \ right \ Vert {}} ^ 2 =\ sum_ {i =1} ^ n {(u_i-v_i)} ^ 2 $(*${\left\Vert{}{D}\right\Vert{}}^2=\sum_{i=1}^n{(u_i-v_i)}^2$*),在哪里(*, where*)$ {D} $(*${D}$*)-的两个向量之间的距离(*- the distance between two vectors of*)$ \ bar {u} $(*$\bar{u}$*)和(*and*)$ \ bar {v} $(*$\bar{v}$*),(*,*)$ u_i $(*$u_i$*)和(*and*)$ v_i $(*$v_i$*)-的(*- the*)$ i $(*$i$*)向量的第th个分量(*-th component of vectors*)$ \ bar {u} $(*$\bar{u}$*)和(*and*)$ \ bar {v} $(*$\bar{v}$*),(*,*)$ n $(*$n$*)-要素数量(即欧几里得空间的尺寸);(*- the number of features (i.e. dimensions of the Euclidean space);*)

下图说明了两个数据向量之间的欧几里得距离计算:(The figure below illustrates the Euclidean distance between two data vectors computation:)

根据该公式,当且仅当每个分量之间的实际差异(即平方距离D的总值)最小时,两个向量才是最相似的.(According to this formula, two vectors are the most similar if and only if the actual difference between each of the components, and, thus, the overall value of the squared distance D , is the smallest.)

为了执行多维数据聚类,我们将使用快速且强大的k-means算法来替代其他算法,因为它相对有效,可为截然不同或分离良好的合成数据提供最佳聚类结果.以下算法仅使用上面列出的欧几里德距离公式基于距离测度.(To perform the multidimensional data clustering, we will use the fast and robust k-means algorithm in the favor of the other algorithms, it’s relatively efficient, providing the best clustering results for the distinct or well-separated synthetic data. The following algorithm is solely based on the distance measure by using the formula of Euclidean distance listed above.)

K-means是基于质心的聚类算法,能够产生聚类,每个聚类由一个特定的质心表示. “质心"是中央数据矢量(即点),可能会或可能不会包含在每个新建群集的结果数据集中.根据聚类的主要思想,如果基于最小距离标准,两个数据向量与其最接近的质心两个相似,则这两个向量也相似(例如,彼此之间的距离最小).作为每个新建聚类的质心,我们基本上选择一个向量,该向量代表给定数据向量集的"质心”,然后找到与其最近的质心距离最小的所有点.(K-means is the centroid-based clustering algorithm, capable of producing the clusters, each one is represented by a specific centroid. A “centroid” is a central data vector (i.e. point) that might or might not be included in the resultant set of data for each newly built cluster. According to the main idea of the clustering, if two data vectors are similar two its nearest centroid, based on the smallest distance criteria, then these two vectors are also similar (e.g. having the smallest distance of one to another). As a centroid for each newly built cluster we basically select a vector, representing a “center-of-the-mass” for a given set of data vectors, and, then, find all points having the smallest distance to its nearest centroid.)

在我们以k-means聚类算法为基础进行讨论之前,让我们讨论使用所讨论的算法生成聚类的一些主要注意事项:(Before we ground our discussion on the k-means clustering algorithm, let’s discuss about some of the main considerations of producing clusters using the algorithm discussed:)

单个群集中的所有数据点必须彼此相似.(All the data points within a single cluster must be similar to one another;)
来自不同群集的特定数据点必须尽可能不同.(Particular data points from different clusters must be as different as possible;) 根据第一个考虑,基于群集内距离标准,分配给单个群集的所有数据点必须相似.群集内距离是单个群集内数据点之间的距离,并且相似数据点之间的距离不得超过群集内距离.(According to the first consideration, the all data points assigned to a single cluster must be similar based on the intra-cluster distance criteria. The intra-cluster distance is a distance between data points within a single cluster, and the distance between to similar data points must not exceed the intra-cluster distance.)

进而,群集间距离(即特定群集(例如,群集中心)之间的距离)必须远大于最大群集内距离,以提供高质量的群集.绝对不同的数据点之间的距离必须大于或等于群集之间的距离.集群内和集群间距离之间的差异如下图所示:(In turn, the inter-cluster distance, which is the distance between specific clusters (e.g. the clusters centers), must be much greater than the maxima intra-cluster distance to provide the high quality of clustering. The distance between the absolutely different data points must be greater than or equal to the inter-cluster distance. The difference between intra- and inter-cluster distances is shown in the figure below:)

以下注意事项是最佳聚类过程的基本原理.(The following considerations are the fundamental principles of the optimal clustering process.)

导入和准备数据集(Importing And Preparing The Dataset)

在这里,我们将深入探讨将要使用k-means算法进行聚类的综合数据的性质,以及如何通过使用以下方法生成综合输入数据集:(Here, we will delve into the discussion of the nature of the synthetic data we’re about to cluster using the k-means algorithm, as well as how to generate the synthetic input collection of data by using) Python’s Sklearn 图书馆.(library.)

首先,让我们在执行实际的聚类之前先看看综合数据. “合成"一词基本上是指满足特定需求或某些条件的数据,这些数据无法在原始实际数据中显示.如上所述,其中所有项目都分为几组的数据集就是这些合成数据的示例.(The first of all, let’s take a look at the synthetic data prior to performing the actual clustering. The term of “synthetic” basically refers to the data that meets the specific needs or certain conditions that cannot be revealed on the original real data. A dataset, in which all items are arranged into several groups is an example of those synthetic data, mentioned above.)

正如我们已经讨论过的,k均值算法可用于对多维数据进行聚类,其中每个项目均由n维欧几里得空间中的一个向量表示,该向量是一组数字特征.同样,集合中的每个向量都与其组,类别或类别的特定标签相关联:(As we’ve already discussed, the k-means algorithm can be used for clustering the multidimensional data, in which each item is represented by a vector in n-dimensional Euclidean space, which components is a set of numeric features. Also, each vector in the set is associated with a specific label of its group, class or category:)

从上图中可以看出,数据集中的每个项目都是一对5维要素向量及其特定的类标签,以下项目所属.每个向量的数字特征基本上表示特定的参数浮点值.例如,这可以是信用卡余额,财务中的贷款金额,生物学中植物的各种特征或任何其他内容.每个特定项目的标签是数字或字符串值,用于标识分配了以下项目的组项目.此外,我们将为每组项目使用整数标签[0; N].(As can see from the figure above, each item in the dataset is a pair of 5-dimensional vector of features and its specific class label, to which the following item belongs. The numerical features of each vector basically represent specific parameter floating-point value. This could be, for example, a credit card balance, loan amount in finance, various characteristics of plants in biology, or whatsoever. A label of each particular item is a numerical or string value identifying a group items to which the following item is assigned. Further we will use the integer labels [0;N] for each group of items.)

为了生成以下数据集,我们将实现下面列出的Python脚本:(To generate the following dataset, we will implement a Python script listed below:)

import numpy as np
import pandas as pd
from sklearn.datasets.samples_generator import make_blobs

X, labels = make_blobs(n_samples=1000, n_features=5, centers=6, cluster_std=0.60, random_state=0)
df = pd.DataFrame({'X': X[:,0], 'Y': X[:,1], 'Z': X[:,2], 'C': X[:,3], 'T': X[:,4], 'Label': labels}, columns=['X','Y','Z','C','T','Label'])
df.to_csv(r'd:\dataset.csv', index = None, header=None)

在此代码中,我们将导入(In this code, we will import the) make_blobs 从功能(function from) sklearn.datasets.samples_generator 模块并使用它来生成一组数据项及其标签.以下函数接受几个参数,例如要生成的项目数(module and use it to generate a set of data items along with their labels. The following functions accepts several of arguments such as the number of items to generate) n_samples = 600 ,每个项目向量的特征数(, the number of features of each item’s vector) n_features=5 ,簇数(, the number of cluster) centers = 6 ,集群的标准偏差(, standard deviation of the clusters) cluster_std = 0.60 和随机数生成器状态(, and random numbers generator state) random_state=0 .以下函数返回向量或其所生成的标签的数组的元组.(. The following function returns a tuple of arrays of either vectors or its labels being generated.)

生成数据集后,现在将以下数据集导出为.csv文件格式.为此,我们将使用(After we’ve generated the dataset, let’s now export the following dataset to .csv file format. To do that we will use the) Python’s Pandas 数据框.的(data frame. The) Pandas 通常使用通用模板实例化的数据框,将两个参数传递给数据框构造函数(data frame normally instantiated with generic template, passing two arguments to the data frame constructor) df = pd.DataFrame(…) .第一个参数是一个列表,其中包含先前生成的数据集的每一列的数据:(. The first argument is a list containing data for each column of the dataset previously generated:) {'X': X[:,0], 'Y': X[:,1], 'Z': X[:,2], 'C': X[:,3], 'T': X[:,4], 'Label': labels} 第二个是列标签名称的列表:(and the second one is the list of column label names:) columns=['X','Y','Z','C','T','Label'] .创建数据框后,我们现在可以将数据导出到.csv文件.通常通过调用来完成(. After we’ve created the data frame, we now can export the data to .csv-file. This typically done by invoking) df.to_csv(r'dataset.csv', index = None, header=None) 方法.(method.)

最后,C#.NET中的代码可以使用以下数据集执行实际的聚类.(Finally, the following dataset can be used by the code in C#.NET to perform the actual clustering.)

K均值聚类算法(K-Means Clustering Algorithm)

初始化(Initialization)

k均值算法的初始化阶段在直观上非常简单.在初始化阶段,通常在执行实际聚类之前,先在欧几里得空间中选择k个随机点作为一组初始质心.(The initialization phase of the k-means algorithm is rather intuitively simple. During the initialization phase, we normally select k – random points in the Euclidean space as a set of initial centroids prior to performing the actual clustering.)

但是,以下方法具有许多缺点,这导致出现次优聚类问题.具体而言,在大多数情况下,随机选择的质心之间的距离不是最佳的(例如,特定质心之间的距离非常小).通常,以下两种主要结果会导致群集质量下降或性能下降.(However, the following method has the number of disadvantages, which leads to the sub-optimal clustering problem occurrence. Specifically, the distance between randomly selected centroids, in the most cases, is not optimal (e.g. the distance between particular centroids is very small). The following normally has two main outcomes in either a poor quality of clustering or sufficient performance degrades.)

显然,要执行最佳聚类,我们需要一种略有不同的方法来找到最佳的初始质心集,如下所述.(Obviously, that, to perform an optimal clustering, we need a slightly different approach for finding an optimal set of initial centroids, discussed below.)

K-Means ++初始化(K-Means++ Initialization)

作为次优聚类问题的一种解决方法,我们将制定k-means ++初始化算法,该算法可使我们极大地提高经典k-means过程提供的聚类质量,并提高其性能并降低计算量.复杂.通常,我们使用k-means ++替代方案来实现两个主要目标:(As a workaround to the sub-optimal clustering problem, we will formulate the k-means++ initialization algorithm that allows us to drastically improve the quality of clustering provided by the classical k-means procedure, as well as to increase its performance and lower the computational complexity. Normally we use the k-means++ alternative to achieve two main goals:)

在已知的缺点和局限性方面提高经典k均值算法提供的聚类的收敛性和质量;(Improve the convergence and quality of clustering provided by the classical k-means algorithm, over its known shortcomings and limitations;)
提供NP-hard k-means聚类过程的更好性能,优化迭代,从而将其计算复杂度降低到仅(Provide a better performance of the NP-hard k-means clustering procedure, optimizing the iterations, and, thus, reducing its computational complexity to only)$ p =O(log(k))$($p = O(log(k))$),在哪里(, where)$ k $($k$)-初始质心的数量,而无需重新设计整个算法本身;(- the number of initial centroids, without re-engineering the entire algorithm itself;) 整个初始化过程基本上都依赖于执行几个步骤,例如Euclidean,Lloyd或本地k-means ++.欧几里得步骤是一个初步步骤,在此过程中,我们将基于最大欧几里得距离量级执行搜索以找到一对第一和第二初始质心.反过来,劳埃德的步骤在k-means ++和k-means聚类过程本身中很常见.在此步骤中,我们实际上是预先构建了一组初始聚类,将每个点映射到特定的现有质心上,从而构建了一个初始聚类.通常这样做是为了找到具有最佳距离的点和质心. k-均值++是最后的步骤,在此步骤中,我们将测量点与每个已经存在的质心之间的距离,并根据最大距离度量来选择新的最佳质心.(The entire initialization procedure basically relies on performing the several steps such as either Euclidean, Lloyd’s or native k-means++. Euclidean step is a preliminary step, during which we are performing a search to find a pair of the first and second initial centroids, based on the maxima Euclidean distance magnitude. In turn, the Lloyd’s step is very common to both k-means++ and k-means clustering procedures itself. During this step we actually pre-build a set of initial clusters, mapping each point onto a specific existing centroid, and, thus, building an initial cluster. This is typically done to find a point and centroid with an optimal distance. The k-means++ is the final step during which we survey the distances between a point and each already existing centroid, selecting new optimal centroids, based on the largest distance measure.)

根据k-means ++程序,我们不再需要随机播种任意点(According to the k-means++ procedure, we no longer have a need to randomly seed arbitrary points)$ \ forall p \ in \ mathbb {R} ^ {n} $($\forall p\in \mathbb{R}^{n}$)在欧几里得空间中,并在执行实际聚类之前将它们用作初始质心的集合.虽然,初始质心的数量(in the Euclidean space and use them as the set of initial centroids prior to performing the actual clustering. Although, the number of initial centroids)$ k $($k$)仍然必须指定.(still must be specified.)

在k-means ++初始化阶段,我们将在那些已经存在的数据点中随机选择第一个质心(During the k-means++ initialization phase, we will be randomly selecting only the first centroid, among those already existing data points)$ \ forall {t_k} \ in {T} $($\forall {t_k}\in {T}$),然后使用略有不同的算法来选择其他质心.让我们回想一下,在这种情况下,使用k-means ++过程选择的每个质心都是一组现有数据点中的一个点(, and then use a slightly different algorithm to select the other centroids optimally. Let’s recall that, in this case, each centroid being selected using k-means++ procedure is a point in the set of already existing data points)$ T $($T$),而不是n维欧几里得空间中的任意点.(, rather than an arbitrary point in the n-dimensional Euclidean space.)

k-means ++算法的主要思想是,质心计算的整个过程基本上都取决于所选择的质心之间的最佳距离.强烈建议质心之间的实际距离必须尽可能大.(The main idea of the k-means++ algorithm is that the entire process of centroids computation basically relies on the measure of optimal distance between those centroids being selected. It’s highly recommended that the actual distance between centroids must be as largest as possible.)

在执行初始化时,我们一直在寻找具有最佳距离的质心.随机选择第一个质心之后(While performing the initialization, we all the way keep on finding centroids with an optimal distance. After we’ve randomly selected the first centroid)$ {c_1} $(${c_1}$)我们可以计算一个点作为第二个质心(we can compute a point as the second centroid)$ {c_2} $(${c_2}$)距质心最大的距离(with the largest distance to centroid)$ {c_1} $(${c_1}$),这是第一大距离.然后,我们计算一个特定点及其最近的质心(, and, that is the first-largest distance. Then, we compute a specific point and its nearest centroid)$ {c_1} $(${c_1}$)要么(or)$ {c_2} $(${c_2}$)因此,点与质心之一之间的距离是第二大距离.以下几点为第三质心(so that the distance between the point and one of the centroids is the second-largest distance. The following point is taken as the third centroid)$ {c_3} $(${c_3}$).寻找第四个质心(. To find the fourth centroid)$ {c_4} $(${c_4}$)我们做的完全一样,计算与质心之一的距离第三大的点(we do exactly the same, computing a point with the third-largest distance to one of the centroids)$ {c_1} $(${c_1}$),(,)$ {c_2} $(${c_2}$)要么(or)$ {c_3} $(${c_3}$), 等等.(, and so on.)

k-means ++算法的公式如下:(The k-means++ algorithm can be formulated as follows:)

给定一组数据点(Given a set of data points)$ T =\ {t_1,t_2,t_3,…,t_ {n-1},t_n } $(*$T={t_1,t_2,t_3,…,t_{n-1},t_n}$*)和初始簇数(*and the number of initial clusters*)$ k $(*$k$*);(*;*)
随机选择一个点(Randomly select a point)$ \ forall {t} $($\forall{t}$)作为第一个质心(as the first centroid)$ c_1 =RND \ {\ overline {T} } $($c_1 = RND{\overline{T}}$);从一组输入点开始.在这种情况下,我们可以采用任何现有观点(; from an input set of points. In this case, we can take any existing point)$ \ forall {t} $($\forall{t}$)不受任何限制;(in the set without any limitations;)
计算距离(Compute the distance)$ d(t_k)$($d(t_k)$)集合中每个点的第一个质心(of each point in the set to the first centroid)$ c_1 $($c_1$)然后选择一个点(and select a point)$ t_j $($t_j$)距离最大的是下一个质心(with the largest distance as the next centroid)$ c_2 =\ forall {t_j} | max_j \ {d(t_j)} $($c_2 = \forall{t_j}|max_j{d(t_j)}$);(;)
计算距离(Compute the distance)$ d(t_k)$($d(t_k)$)在已选择的一组质心中,每个点到其最近质心的距离(例如(of each point to its nearest centroid in a set of centroids that have already been selected (e.g.)$ C =\ {c_1,c_2,c_3,…,_ c {n-1},c_n } $(*$C = {c_1,c_2,c_3,…,_c{n-1},c_n}$*));(*);*)
选择一个点(Select a point)$ t_s $($t_s$)距离最大的是下一个质心(having the largest distance as the next centroid)$ c_m =\ forall {t_s} | max_s \ {d(t_s)} $($c_m = \forall{t_s}|max_s{d(t_s)}$),并将其添加到形心集((, and add it to the set of centroids ()$ C \ leftarrow c_m $($C\leftarrow c_m$));();)
继续执行步骤3和4,直到所需数量的(Proceed with steps 3 and 4 until the required number of)$ k $($k$)选择了质心;(centroids have been selected;) 根据k-means ++过程,在计算其他质心之前,必须确保至少已选择了两个质心.在此阶段,必须使用随机选择的点的单个值作为第一个质心来初始化所得的质心集.(According to the k-means++ procedure, we must make sure that at least two centroids have already been selected before computing the other centroids. During this phase, the resultant set of centroids must be initialized with a single value of randomly selected point as the first centroid)$ c_1 $($c_1$).第二个质心(. The second centroid)$ c_2 $($c_2$)通过计算距离选择(is selected by computing the distance)$ d(t_k)$($d(t_k)$)每个点的第一个质心(of each point to the first centroid)$ c_1 $($c_1$)然后选择一个点(and choosing a point)$ \ forall {t_j} $($\forall{t_j}$)与以下质心的最大距离.通常在执行实际聚类之前这样做是为了改善聚类间距离.之后,第二个质心(with the largest distance to the following centroid. This is typically done to improve the inter-cluster distance prior to performing the actual clustering. After, the second centroid)$ c_2 $($c_2$)已经成功选择,我们添加以下几点(has been successfully selected, we add the following point)$ c_m =t_j $($c_m = t_j$)到质心集(to the set of centroids)$ C \ leftarrow c_m $($C \leftarrow c_m$).以下微不足道的操作基本上涉及正在讨论的算法的欧几里德步骤.图5示出了选择第一和第二初始质心的过程.(. The following trivial operation basically refers to the Euclidean step of the algorithm, being discussed. The Fig. 5 illustrates the process of selecting the first and second initial centroids)$ c_1 $($c_1$)和(and)$ c_2 $($c_2$), 分别:(, respectively:)

由于两个质心(Since both centroids)$ c_1 $($c_1$)和(and)$ c_2 $($c_2$)已经被选中,现在,我们可以计算其余的其他质心(例如(have already been selected, now, we can compute the rest of other centroids (e.g.)$ c_3,c_4,c_5,… $($c_3,c_4,c_5,…$)).为此,对于每个点,我们必须迭代计算距离(). To do that, for each point, we must iteratively compute the distance)$ d(t_k)$($d(t_k)$)到集合中所有现有质心(to all existing centroids in the set)$ C $($C$)并关联当前点(and associate the current point)$ t_k $($t_k$)带质心(with centroid)$ c_n $($c_n$)对于该距离,直到每个点都属于特定质心之前,其跟随距离是最小的.对于k-means ++和经典k-means算法而言,此步骤都很常见,称为"劳埃德步骤”.然后,根据本机k-means ++算法,(for which the following distance is the smallest until each of the points would belong to a particular centroid. This step is very common for both k-means++ and classical k-means algorithms and called the “Lloyd’s step”. Then, according to the native k-means++ algorithm, a point)$ t_s $($t_s$)距最近的质心最大的距离(with the largest distance to its nearest centroid)$ c_n $($c_n$)被选为下一个质心(is selected as the next centroid)$ c_m \ leftarrow t_s $($c_m\leftarrow t_s$),并添加到形心(, and added to the set of centroids)$ C $($C$).通常,我们重复以下计算,直到找到所需数量的质心为止.查找集合中其他质心其余部分的整个过程如图6所示.下面:(. Normally, we repeat the following computations until the required number of centroids has been found. The entire process of finding the rest of other centroids in the set is shown in Fig.6. below:)

您可能已经注意到,我们通常会进行k-means ++初始化过程,直到最终最终选择了一组质心以及在劳埃德算法步骤中构建的初始簇数.此外,该数量的初始集群被添加到已经存在的集群的输出集合中,并且通过为每个特定的现有集群重新计算质量幅度的中心(即"质心”)来产生新的集群.反过来,这允许在算法级别上改善k均值聚类的性能.本文的后续章节之一将彻底讨论以下主题.(As you’ve might already noticed, we normally proceed with k-means++ initialization process until we’ve finally ended up with a set of centroids being selected as well as the number of initial clusters built during the algorithm Lloyd’s step. Further, this number of initial clusters is added to the output set of already existing clusters and the new clusters are produced by re-computing a center of the mass magnitude (i.e. “centroids”) for each particular existing cluster, being processed. This, in turn, allows to improve the performance of the k-means clustering at the algorithm level. The following topic is thoroughly discussed in one of the succeeding chapters of this article.)

在前面的段落中,我们已经讨论过k-means ++初始化过程主要基于找到最佳距离最大的质心.但是,正如我们所看到的那样,用于查找初始质心的最佳集合的算法可能会有所不同.具体来说,我们可以计算成对的点之间的距离,然后选择距离最大的那些点.显然,以下算法失败,因为作为质心的两个或多个任意点之间的距离可能不是最佳的.例如,我们发现了一组三个质心(In the previous paragraphs, we’ve already discussed that the k-means++ initialization process is mainly based on finding the centroids with the largest optimal distance. However, as it might have seemed to us, the algorithm for finding an optimal set of initial centroids could be different. Specifically, we can compute the distance between pairs of points and then select those points with the largest distance. Obviously, that, the following algorithm fails since the distance between to two or more arbitrary points taken as the centroids might not be an optimal. For example, we’ve found a set of three centroids)$ c_1 $($c_1$),(,)$ c_2 $($c_2$)和(and)$ c_3 $($c_3$).形心对之间的距离(. The distances between pairs of centroids)$ c_1 $($c_1$)和(and)$ c_2 $($c_2$), 以及(, as well as)$ c_2 $($c_2$)和(and)$ c_3 $($c_3$)是最佳的,但是之间的距离(are optimal, but the distance between)$ c_1 $($c_1$)和(and)$ c_3 $($c_3$)不是.以下原因是我们仍然需要遵循k-means ++初始化过程的证明.(is not. The following cause is the proof that we still need to conform to the k-means++ initialization procedure, instead.)

实际上,k-means ++初始化过程是解决最佳初始质心选择的唯一可能算法.以下过程仅基于选择质心之间具有最佳距离的技术,从而确保k均值算法本身将在聚类过程的最初步骤中成功收敛,从而显着减少了执行的操作数量.此外,还有多种k-means ++算法变体,例如基于距离或基于概率的变体.然而,由于一些随机化问题,类似于通用k均值初始化的基于概率分布的k均值++程序有时往往会提供较差的初始质心选择结果.(In fact, the k-means++ initialization procedure is the only possible algorithm addressing an optimal initial centroids selection. The following procedure is solely based on a technique of selecting centroids having an optimized distance between them, and, thus, ensuring that k-means algorithm itself will successfully converge at the very first steps of the clustering process, significantly reducing the number of operations performed. Also, there’s the number of k-means++ algorithm variations such as either distance- or probability-based. However, probability distribution-based k-means++ procedure, similar to the generic k-means initialization, sometimes tends to provide poor results of the initial centroids selection, due to the several randomization issues.)

最后,在下面的图表中,我们将通过使用k-means ++过程或通用k-means随机初始化来比较初始质心选择的结果:(Finally, in the chart below we will compare the results of the initial centroids selection by using the either k-means++ procedure or the generic k-means random initialization:)

执行K均值聚类(Performing K-Means Clustering)

在详细讨论了初始化阶段之后,让我们花点时间简要了解一下k均值聚类过程.根据k-means算法的主要思想,我们需要将距离最小的点排列到多个称为"簇"的组中,并且由于已经生成了新构建的簇,因此需要为每个簇重新计算质心,使用以下段落中讨论的方法,基于找到"质心"幅度的过程.(After we’ve thoroughly discussed about the initialization phase, let’s now spend a moment and take a short glance at the k-means clustering procedure. According to the main idea of the k-means algorithm we need to arrange points with the smallest distance into multiple of groups called “clusters”, and, since the newly built clusters have been produced, re-compute a centroid for each of these clusters, based on the process of finding the “center of the mass” magnitude, using the method discussed in the next paragraphs.)

简要介绍之后,让我们制定经典的k均值算法,该算法非常简单:(After brief introduction, let’s formulate the classical k-means algorithm, which is very simple:)

给定一组(Given a set of)$ k $($k$)–重心(– centroids)$ C =\ {c_1,c_2,c_3,…,c_ {k-1},c_k } $(*$C={c_1,c_2,c_3,…,c_{k-1},c_k}$*)和一组数据点(*and a set of data points*)$ T =\ {t_1,t_2,t_3,…,t_ {n-1},t_n } $(*$T={t_1,t_2,t_3,…,t_{n-1},t_n}$*);(*;*)
对于每个质心(For each centroid)$ \ forall {c_i} $($\forall{c_i}$),找到点子集(, find a subset of points)$ \ hat {T} $($\hat{T}$)距当前质心最近的距离(having the nearest distance to the current centroid)$ c_i $($c_i$)并将这些点与以下质心相关联,以创建一个新建的群集;(and associate these points with the following centroid, creating a newly built cluster;)
根据"质心"幅度重新计算每个新建群集的质心,并将每个新质心附加到质心集上(Re-compute the centroids of each of the newly built clusters based on the “center-of-the-mass” magnitude, appending each new centroid being computed to the set of centroids)$ C $($C$);(;)
进行检查,以确保每个现有群集的质心都没有改变,并且所选的点不在同一群集中(例如,我们没有生成包含重复点的相似群集,而这些重复点在以前构建的群集中已经发生);(Perform a check if the centroid of each already existing cluster has not changed and the points selected are not within the same clusters (e.g. we’re not producing the similar clusters, containing duplicate points, which have already occurred in the previously built clusters);)
如果不是,则继续执行步骤1,2和3,否则终止k-means聚类过程;(If not, proceed with steps 1,2 and 3, otherwise terminate the k-means clustering process;) 既然如此,我们已经获得了一组初始质心(Since, we’re already given a set of the initial centroids)$ C $($C$)对于每个特定的质心(for each specific centroid)$ c_i $($c_i$)我们可以计算出包含以下数据点的聚类(we can compute a cluster containing the data points in)$ T $($T$),到当前质心的距离(, for which the distance to the current centroid)$ c_i $($c_i$)是最小的.为此,针对每个特定点(is the smallest. To do that, for each particular point)$ t_k \ in T $($t_k \in T$),我们必须计算到每个质心的距离(, we must compute a distance to each of the centroids)$ c_i \ in C $($c_i \in C$),确定质心(, determining the centroid)$ c_j $($c_j$)与当前点的距离最小(with the smallest distance to the current point)$ t_k $($t_k$),并分配点的子集(, and assigning a subset of points)$ \ hat {T} $($\hat{T}$)到带有质心的新建群集(to a newly built cluster with centroid)$ c_j $($c_j$).以下操作基本上是指算法的劳埃德步骤,如前所述.(. The following operation basically refers to the Lloyd’s step of the algorithm, previously discussed.)

在计算了新的聚类之后,是时候重新计算质心,以便在聚类过程的下一个阶段产生新的聚类了.这通常通过使用"质量中心"方程式完成,从而得出以下计算结果.对于所有点,要找到质心(After we’ve computed the new clusters, it’s time to re-compute the centroids to have an ability to produce the new clusters during the next phase of the clustering process. This is typically done by using the “center-of-the-mass” equation, that yields the following computation. To find a center of the mass, for all points in)$ \ hat {T} $($\hat{T}$)我们必须计算n维欧几里得空间中每个坐标的平均值/均值(we must compute an average/mean of each coordinate in the n-dimensional Euclidean space)$ t_k \ in \ mathbb {R} ^ n $($t_k\in\mathbb{R}^n$).这是一个说明这种计算的方程式:(. Here’s an equation that illustrates such computation:)

$ v_i =\ frac {1} {c_i} * \ sum_ {j =1} ^ {c_i} x_j $(*$v_i=\frac{1}{c_i}*\sum_{j=1}^{c_i}x_j$*)

哪里(where)$ v_i $($v_i$)是新的质心(is the new centroid of the)$ i $($i$)–第簇,(– th cluster,)$ c_i $($c_i$)-中的点数(- the number of points in the)$ i $($i$)–第簇,(– th cluster,)$ x_j $($x_j$)-属于(- a point belonging to the)$ i $($i$)–第簇(– th cluster)$ \ forall x_j \ in \ hat {T} $($\forall x_j \in \hat{T}$);(;)

进行这些计算的结果是,我们获得了一个点,代表了新星团的质心.通常,我们进行以下计算,直到为每个现有群集找到新的质心为止:(As the result of performing those computations, we’ve obtained a point, representing a new cluster’s centroid. We normally proceed with the following computations until we’ve found a new centroid for each of the already existing clusters:)

此外,我们将使用这些质心找到新的聚类,并按照前面段落之一讨论的k均值算法的相同Lloyd步骤进行操作.(Further, we will use these centroids to find the new clusters, proceeding with the same Lloyd’s step of the k-means algorithm, discussed in one of the previous paragraphs.)

最后,这是聚类过程的另一个方面,我们将讨论k-means算法的停止标准.至少可以使用三个标准来确定何时必须精确终止k均值聚类过程:(Finally, here’s one more aspect of the clustering process that we will discuss is the k-means algorithm stopping criteria. There are at least three criterions that can be used to determine when exactly the k-means clustering process must be terminated:)

重新计算的新质心不会改变,并且等于已经存在的簇的质心;(The new centroids that have been re-computed don’t change and are equal to the centroids of already existing clusters;)
新群集由先前构建的群集中已经出现的相同数据点组成;(The new clusters consist of the same data points that have already occurred in the previously built clusters;)
已经达到了迭代的极限;(The limit of iterations has been reached;) 在以下条件之一的情况下,考虑到以下过程已成功收敛,因此我们可以终止k均值聚类过程,并且最终获得了所需数量的(Under one of these conditions we can terminate the k-means clustering process, considering that the following process has successfully converged, and we’ve ended up with a required number of)$ k $($k$)-簇,每个簇包含最相似的数据点.(- clusters, each one is containing the most similar data points.)

评估K均值聚类算法(Evaluating K-Means Clustering Algorithm)

评估指标的数量众多,例如惯性量级或Dunn指数,可以用来衡量聚类的质量.通过评估惯性,我们实际上计算了所有点到每个聚类的质心的距离之和,然后将这些总和相加.实际上,通过计算惯性,我们可以评估集群内距离的总和.最后,我们认为,随着聚类质量的提高,惯性值越小.以下公式说明了惯性度量的计算:(There’s the number of evaluation metrics, such as either the inertia magnitude or Dunn index, that allow us to measure a quality of clustering. By evaluating the inertia, we actually compute the sum of distances of all points to the centroid of each cluster, and, then add up each of these sums together. Actually, by computing the inertia we evaluate the sum of intra-cluster distances. Finally, we consider that as the lesser the inertia value as the quality of clustering is higher. The following formula illustrates the inertia metric computation:)

$ I =\ sum_ {i =1} ^ {k} \ sum_ {j =1} ^ {c_i} | x_j-c_i | ^ 2 $(*$I=\sum_{i=1}^{k} \sum_{j=1}^{c_i}|x_j-c_i|^2$*)

,在哪里(, where)$ I $($I$)–惯性值,(– the inertia value,)$ k $($k$)–集群数,(– the number of clusters,)$ c_i $($c_i$)–的质心(– the centroid of)$ i $($i$)–第簇,(– th cluster,)$ x_j $($x_j$)-的(- the)$ j $($j$)–第一点(– th point within the)$ i $($i$)–第簇.(– th cluster.)

而且,惯性值可用于确定执行最佳聚类的聚类的初始数量.在这种情况下,我们依次增加初始群集的数量(Also, the inertia value can be used to determine the initial number of clusters for performing the most optimal clustering. In this case we sequentially increase the number of initial clusters)$ k $($k$)然后计算惯量,直到惯性值没有变化并且变得恒定为止.之后,取初始簇数(and then compute the inertia, until the inertia value has not varied and becomes constant. After that, take the initial number of clusters)$ k $($k$)惯性值未更改.(for which the inertia value has not been changed.)

Dunn索引是另一个可以用来有效评估聚类质量的指标.以下度量原则上表示群集间距离的最小值与群集内距离的最大值之间的比率.与惯性值不同,邓恩指数的大小很大程度上取决于簇之间的距离.在大多数情况下,要提供高质量的聚类,我们希望最大化Dunn索引值.下面的公式说明了Dunn指数的计算:(Dunn index is another metric by using which we can effectively evaluate the quality of clustering. The following metric basically represents a ratio between the minimum of inter-cluster distances and the maximum of intra-cluster distances. Unlike the inertia value, the Dunn index magnitude largely depends on the distance between clusters. In the most cases, to provide a high-quality clustering we want to maximize the Dunn index value. The formula below illustrates the Dunn index computation:)

$ Dunn_ {index} =\ frac {min \ {集群间\空间距离}}} {max \ {集群内\空间距离}} $(*$Dunn_{index}=\frac{min{inter-cluster \space distances}}{max{intra-cluster \space distances}}$*)从上式可以看出,当且仅当最小群集间距离最大时,才能获得Dunn索引的最大值.同样,当最大集群内距离最小时,我们得到相同的Dunn指数最大值.并且,以下是集群本身的理想情况,因为我们构建了一组最合适的集群,每个集群都包含最相似的项目,而远距离集群本身的特定项目之间的差异非常大.(*As you can see from the formula above, the maximum value of Dunn index can be obtained if and only if the minima inter-cluster distance is the highest. Also, we get the same maximum of Dunn index when the maxima intra-cluster distance is the smallest. And, the following is the ideal case of the clustering itself, since we build a set of the most appropriate clusters, each one is containing the items which are the most similar, whilst the difference between specific items from the distant clusters itself is very high.*)

使用代码(Using the code)

在这里,我们将讨论如何实现功能数量,执行k均值聚类.我实现的第一个功能是(Here, we will discuss how to implement the number of functions, performing the k-means clustering. The very first function I’ve implemented is the function) LoadDataFromFile(...) 从.csv文件加载多维集群数据集:(that loads the multi-dimensional clustering dataset from .csv file:)

        static List<tuple<list<double>, string>> LoadDataFromFile(string filename)
        {
            // Instantiate a list of items
            List<tuple<list<double>, string>> Items =
                new List<tuple<list<double>, string>>();

            // Open .csv-file for reading
            using (System.IO.StreamReader file =
                new System.IO.StreamReader(filename))
            {
                string buf = "\0";
                // Read .csv-file line-by-line
                while ((buf = file.ReadLine()) != null)
                {
                    List<double> features = new List<double>();
                    // Split each line into a list of values
                    foreach (string param in buf.Split(',').ToArray())
                        // For each value perform a check if it's a floating-point value
                        // using regular expressions parser
                        if (Regex.Match(param, @"[.]", RegexOptions.IgnoreCase).Success)
                            // If so, add the current value to the list of item's features
                            features.Add(Double.Parse(param, CultureInfo.InvariantCulture));

                   // Add each pair of a vector of features and its label to the list of items
                   Items.Add(new Tuple<list<double>, string>(features,
                        buf.Split(',').ElementAt(buf.Split(',').Length - 1)));
                }

                // Close the file
                file.Close();
            }

            // Return the list of items
            return Items;
        }
    
</list<double></double></double></tuple<list<double></tuple<list<double></tuple<list<double>

上面列出的以下代码打开一个.csv文件,并从文件中读取每一行,并将其迭代地拆分为值列表.对于每个值,它都会检查其浮点值.如果是这样,它将以下值附加到要素列表中,以构建多维矢量,然后将其与标签一起添加到项目列表中(例如,当前行中的最后一个逗号分隔值).在执行结束时,以下函数将返回一个元组列表,其中包含要素向量及其标签.(The following code listed above, opens a .csv-file and reads each line from the file, iteratively splitting it into a list of values. For each value it performs a check if its a floating-point value. If so, it appends the following value to the list of features, building a multi-dimensional vector, which is then added to the list of items along with its label (e.g. the last comma-separated value in the current line). At the end of execution the following function returns a list of item tuples consisting of a vector of features and its label.)

EuclDist(...) -我预先实现的另一个功能.以下函数执行多元欧几里得距离值计算,并分别接受两个主要参数(例如要素的第一向量和第二向量)以计算这两个向量之间的距离(即``相似性''):(- another function that I’ve implemented beforehand. The following function performs the multi-variate Euclidean distance value computation and accepts two main arguments such as either the first and second vectors of features, respectively, to compute the distance (i.e. “similarity”) between these two vectors:)

        static double EuclDist(List<double><double> params1, 
            List<double><double> params2, bool squared = false)
        {
            double distance = .0f;
            // For each dimension, compute the squared difference
            // between two features and accumulate the result in 
            // the distance variable
            for (int Index = 0; Index < params1.Count(); Index++)
                distance += Math.Pow((params1[Index] - params2[Index]), 2);

            // Return a squared or regular distance value
            return !squared ? Math.Sqrt(distance) : distance;
        }    
</double></double>

此函数有两种专门用于规则或平方欧几里德距离计算的功能.作为以下函数执行的结果,我们获得了特征的两个n维向量之间的欧几里得距离的浮点值.以下功能主要由(There’re two specializations of this function for either a regular or squared Euclidean distance computation. As the result of the following function execution, we get a floating-point value of the Euclidean distance between two n-dimensional vectors of features. The following function is primarily used by) Euclidean_Step(...) 和(and) Lloyd_Step(...) 用于计算特定距离值的函数:(functions to compute the specific distance values:)

        static int Euclidean_Step(List<tuple<list<double>, 
            string>> items, int centroid)
        {
            List<tuple<int, double="">> dists = new List<tuple<int, double="">>();
            // For each item compute the distance two an already existing centroid
            for (int Index = 0; Index < items.Count(); Index++)
                // Add each distance to the list of distances
                dists.Add(new Tuple<int, double="">(Index, 
                    EuclDist(items[centroid].Item1, items[Index].Item1, true)));

            // Find an item with the maxima distance to the centroid specified
            return dists.Find(obj => obj.Item2 == 
                dists.Max(dist => dist.Item2)).Item1;
        }    
</int,></tuple<int,></tuple<int,></tuple<list<double>

上面列出的以下函数接受项目列表的两个主要参数以及被选为第一个质心的项目的索引.(The following function listed above, accepts two main arguments of the list of items as well as the index of the item selected as the first centroid.)

Lloyd_Step(...) 是调用的主要功能,我们基本上执行了实际的聚类. k-means ++和k-means例程均使用以下函数将数据集按距质心列表中每个质心最近的距离进行分区.这是Lloyd_Step(…)函数的实现:(is the main function by invoking which we basically perform the actual clustering. The following function is used by both k-means++ and k-means routines to partition the dataset by the nearest distance to each of the centroids in the list of centroids. Here’s an implementation of Lloyd_Step(…) function:)

        static List<Tuple<int, List<int>>> Lloyd_Step(
            List<Tuple<List<double>, string>> items, 
            List<int> centroids, List<List<double>> c_mass = null)<tuple<int, list=""><tuple<list<double><int><list<double>
        {
            List<tuple<int, list="">>> clusters =
                new List<tuple<int, list="">>>();

            // Pre-build a set of new clusters based on the centroids index values
            if (centroids != null)
            {
                for (int Index = 0; Index < centroids.Count(); Index++)
                    clusters.Add(new Tuple<int, list="">>(
                        centroids[Index], new List<int>()));
            }

            else
            {
                for (int Index = 0; Index < c_mass.Count(); Index++)
                    clusters.Add(new Tuple<int, list="">>(Index, new List<int>()));
            }

            for (int Index = 0; Index < items.Count(); Index++)
            {
                double dist_min = .0f; int cluster = -1;

                if (centroids != null)
                {
                    // For each item compute the distance to each centroid
                    // finding an item with the smallest distance to a current centroid
                    for (int cnt = 0; cnt < centroids.Count(); cnt++)
                    {
                        double distance = EuclDist(items[Index].Item1,
                            items[centroids[cnt]].Item1, true);

                        if ((distance <= dist_min) || (cluster == -1))
                        {
                            dist_min = distance; cluster = cnt;
                        }
                    }

                    // Assign the following item to a cluster with centroid
                    // having the smallest distance
                    var cluster_target = clusters.Find(
                        obj => obj.Item1 == centroids[cluster]);

                    if (cluster_target != null)
                        cluster_target.Item2.Add(Index);
                }

                else
                {
                    for (int cnt = 0; cnt < c_mass.Count(); cnt++)
                    {
                        // For each item compute the distance to each centroid
                        // finding an item with the smallest distance to a current centroid
                        double distance = EuclDist(items[Index].Item1, c_mass[cnt], true);
                        if ((distance <= dist_min) || (cluster == -1))
                        {
                            dist_min = distance; cluster = cnt;
                        }
                    }

                    // Assign the following item to a cluster with centroid
                    // having the smallest distance
                    var cluster_target = clusters.Find(
                        obj => obj.Item1 == cluster);

                    if (cluster_target != null)
                        cluster_target.Item2.Add(Index);
                }
            }

            // Return a list of clusters
            return clusters;
        }    
</int></int,></int></int,></tuple<int,></tuple<int,></list<double></int></tuple<list<double></tuple<int,>

上面列出的以下功能接受三个参数,即项目输入列表,质心索引列表或代表新聚类中心的点列表.对于每个项目,它都会计算到列表中每个质心或点的欧几里得距离,然后执行搜索以找到该距离最小的质心.然后,它将以下项分配给质心距离最小的聚类.以下函数实际上执行整个数据集分区.最后,以下函数返回一个元组列表,每个元组都由一个质心索引和一个项目索引列表组成.(The following function listed above, accepts three arguments of either an input list of items, list of centroids indices or a list of points representing the new clusters centers. For each item it computes the Euclidean distance to each centroid or point in the list, performing a search to find a centroid for which this distance is the smallest. Then it assigns the following item to a cluster with a centroid having the smallest distance. The following function actually performs the entire dataset partitioning. Finally, the following function returns a list of tuples, each one is consisting of a centroid index and a list of item indices.)

为了执行k-means ++初始化,我们将实现以下功能,该功能基本上依赖于使用(To perform k-means++ initialization, we will implement the following function that basically relies on using the) Euclidean_Step(...) 和(and) Lloyd_Step(...) 功能:(functions:)

static Tuple<List<int>, List<Tuple<int, List<int>>>> KmeansPlusPlus(
    List<Tuple<List<double>, string>> items, int k)
{
    // Initialize a list of centroids with a single centroid
    // randomly selected
    List<int> centroids = new List<int>() {
        new Random().Next(items.Count())
    };

    if (centroids.Count() == 1)
        // Compute the second centroid by invoking the Euclidean_Step(...)
        // function and append it to the list of centroids
        centroids.Add(Euclidean_Step(items, centroids[0]));

    List<Tuple<int, List<int>>> targets = null;
    // Compute the other initial centroids
    for (int count = k - 2; count >= 0; count--)
    {
        // Perform a Lloyd's step to obtain a list of initial clusters
        List<Tuple<int, List<int>>> clusters =
            Lloyd_Step(items, centroids);

        double dist_max = .0f; int cmax_index = -1, dmax_index = -1;
        // For each cluster compute an item with the largest distance
        // to its centroid
        for (int Index = 0; Index < clusters.Count(); Index++)
        {
            int centroid = clusters[Index].Item1;
            for (int pt = 0; pt < clusters[Index].Item2.Count(); pt++)
            {
                double distance = EuclDist(items[centroid].Item1,
                    items[clusters[Index].Item2[pt]].Item1);

                if ((distance > dist_max) ||
                    (cmax_index == -1) || (dmax_index == -1))
                {
                    dist_max = distance;
                    cmax_index = Index; dmax_index = pt;
                }
            }
        }

        if (count > 0)
            // Add the following item index to the list of centroids
            centroids.Add(clusters[cmax_index].Item2[dmax_index]);

        targets = (clusters.Count() > 0) && (count == 0) ? clusters : null;
    }

    // Return a tuple of a list of centroids and a list of pre-built clusters
    return new Tuple<List<int>, List<Tuple<int, List<int>>>>(centroids, targets);
}

为了执行实际的k均值聚类,我们将实现以下功能:(To perform the actual k-means clustering we will implement the following function:)

static List<Tuple<int, List<int>>> KMeans(
    List<Tuple<List<double>, string>> Items, int k)
{
    // Find k - initial centroids using k-means++ procedure
    Tuple<List<int>, List<Tuple<int,
        List<int>>>> result = KmeansPlusPlus(Items, k);

    // Instantiate the list of target clusters
    List<Tuple<int, List<int>>> clusters_target =
        new List<Tuple<int, List<int>>>();

    List<int> centroids = result.Item1;
    List<Tuple<int, List<int>>> clusters = result.Item2;

    while (clusters.Count() > 1)
    {
        // Re-compute the centroids of the pre-built clusters
        List<List<double>> centroids_new =
            RecomputeCentroids(clusters, Items);

        // Perform a Lloyd step to partition the dataset
        List<Tuple<int, List<int>>> clusters_new =
            Lloyd_Step(Items, null, centroids_new);

        // Perform a check if we're not producing the same clusters
        // and the k-means procedure has not converged.
        // If not, proceed with the next clustering phase
        for (int clu = 0; clu < clusters.Count(); clu++)
        {
            if ((Compare(clusters[clu].Item2, clusters_new[clu].Item2)))
            {
                clusters_target.Add(clusters[clu]);
                clusters.RemoveAt(clu); clusters_new.RemoveAt(clu); clu--;
            }
        }

        if (clusters_new.Count() > 1)
            clusters = clusters_new;
    }

    return clusters_target;
}

上面列出的功能执行实际的k均值聚类.首先,它调用(The function listed above performs the actual k-means clustering. First, it invokes) KmeansPlusPlus(...) 函数以获取初始质心和预构建簇的列表.之后,它将执行一次简单的迭代,在此过程中将重新计算已经存在的群集的质心.此外,这些新质心被(function to get a list of initial centroids and pre-built clusters. After that, it performs a simple iteration during which the centroids of already existing clusters are re-computed. Further, those new centroids are used by) Lloyd_Step(...) 函数将整个数据集划分为一组新的群集.然后执行k-means过程是否收敛并且我们没有产生相同的聚类的检查.如果不是,则继续进行k均值聚类过程的下一次迭代.否则,以下函数将返回新建群集的列表.为了重新计算新的质心,我实现了以下功能:(function to partition the entire dataset into a set of new clusters. Then it’s performing a check if the k-means procedure has converged and we’re not producing the same clusters. If not, it proceeds with the next iteration of the k-means clustering process. Otherwise, the following function returns a list of newly built clusters. To re-compute the new centroids I’ve implemented the following function:)

static List<List<double>> RecomputeCentroids(
    List<Tuple<int, List<int>>> clusters,
    List<Tuple<List<double>, string>> Items)
{
    List<List<double>> centroids_new =
        new List<List<double>>();

    // For each cluster re-compute the new centroids
    for (int clu = 0; clu < clusters.Count(); clu++)
    {
        List<int> c_items = clusters[clu].Item2;
        List<double> centroid = new List<double>();
        // For a list of items, compute the average of each coordinate
        for (int i = 0; i < Items[c_items[0]].Item1.Count(); i++)
        {
            if (Items[c_items[0]].Item1.Count() > 0)
            {
                double avg = .0f;
                for (int Index = 0; Index < c_items.Count(); Index++)
                    avg += Items[c_items[Index]].Item1[i] / c_items.Count();

                centroid.Add(avg);
            }
        }

        // Add a new centroid to the list of centroids
        centroids_new.Add(centroid);
    }

    // Return a list of new centroids
    return centroids_new;
}

为了获取新的质心,我们通常为单个聚类中的每个项目计算每个坐标的平均值(即``质心''),以获得一个点,该点是特定聚类的质心.(To get the new centroids, we normally compute an average (i.e. “center-of-the-mass”) of each coordinate for each item within a single cluster to obtain a point which is a centroid for a specific cluster.)

另外,还有另一个功能可以执行以下操作:检查旧群集和新群集是否不相交.具体来说,如果新建立的集群不包括在旧集群中:(Also, there’s another function that performs a check if the old and new clusters are not intersecting. Specifically, if the newly built clusters are not included in the old ones:)

static bool Compare(List<int> list1, List<int> list2)
{
    return list2.Intersect(list1).Count() == list2.Count();
}

最后,让我们讨论使用上面介绍的函数执行实际k均值聚类的主要代码:(Finally, let’s discuss about the main code that performs the actual k-means clustering by using the functions we’ve introduced above:)

static void Main(string[] args)
{
    Console.WriteLine("K-Means Clustering Algorithm v.1.0 by Arthur V. Ratz @ CodeProject.Com");
    Console.WriteLine("======================================================================");

    string filename = "\0";
    Console.Write("Enter a filename: ");
    filename = Console.ReadLine();

    int k = 0;
    Console.Write("Enter a number of clusters: ");
    k = Int32.Parse(Console.ReadLine()); Console.WriteLine();

    List<Tuple<List<double>, string>> Items =
        LoadDataFromFile(filename);

    List<Tuple<int, List<int>>> clusters_target =
           KMeans(Items, k);

    for (int clu = 0; clu < clusters_target.Count(); clu++)
    {
        Console.WriteLine("Cluster = {0}", clu + 1);
        for (int Index = 0; Index < clusters_target[clu].Item2.Count(); Index++)
        {
            for (int Item = 0; Item < Items[clusters_target[clu].Item2[Index]].Item1.Count(); Item++)
                Console.Write("{0} ", Items[clusters_target[clu].Item2[Index]].Item1[Item]);

            Console.WriteLine("{0}", Items[clusters_target[clu].Item2[Index]].Item2);
        }

        Console.WriteLine("\n");
    }

    Console.ReadKey();
}

以下代码通过调用以下代码从.csv文件加载数据集:(The following code loads the dataset from .csv-file by invoking the) LoadDataFromFile(...) 函数,然后执行KMeans(…)函数以执行实际的聚类.最后,它输出聚类的结果:(function and then executes the KMeans(…) function to perform the actual clustering. Finally, it outputs the results of clustering:)

兴趣点(Points of Interest)

正如我们已经讨论的那样,可以通过使用k-means ++初始化过程来彻底优化整个k-means聚类过程.在这种情况下,使用k-means ++初始化对聚类过程的质量和性能都有好处,从而能够将经典的NP-hard k-means算法的总体计算复杂度降低到仅(As we’ve already discussed, the entire k-means clustering process can be drastically optimized by using the k-means++ initialization procedure. In this case, the using of k-means++ initialization benefits in both the quality and performance of the clustering process, providing an ability to reduce the overall computational complexity of the classical NP-hard k-means algorithm to just)$ p =O(log(k))$($p = O(log(k))$),在哪里(, where)$ k $($k$)是结果集中的簇数.除了一组最佳初始质心外,k-means ++初始化可用于生成一组初始聚类,然后从k-means聚类过程开始.同样,使用k-means ++初始化可确保k-means聚类过程得以完成并成功地以最小的迭代次数收敛,从而提供实际聚类的最合适结果.具体而言,每个群集将包含最相似的数据点,尤其是在执行排他群集操作时,在此期间,每个点都分配给特定群集,并且不能同时包含在多个群集中.(is the number of clusters in the resultant set. Besides of the set of optimal initial centroids, k-means++ initialization can be used for producing a set of initial clusters, the k-means clustering process starts with. Also, the using of k-means++ initialization ensures that the k-means clustering process will be completed and successfully converge with the minima number of iterations, providing the most appropriate results of the actual clustering. Specifically, each cluster will contain the most similar data points, especially while performing the exclusive clustering operations, during which, each of the points is assigned to a particular cluster and cannot be included in more than one cluster simultaneously.)

此外,使用各种现有的高性能计算(HPC)库和框架,可以轻松地将执行实际k均值聚类的顺序代码片段的性能转换为并行,从而提供聚类过程本身的更多性能.(Moreover, the performance of sequential code fragments, performing the actual k-means clustering can be easily transformed into parallel using the various of existing high-performance computing (HPC) libraries and frameworks, providing even more performance of the clustering process itself.)

历史(History)

2020年1月11日-本文的第一版已经发布(Jan 11, 2020 - The first version of this article has been published)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。

C# Linux Windows Visual-Studio Dev Design Architect VS2019 新闻翻译