200字范文 > k-均值聚类算法_聚类算法-K-均值算法

k-均值聚类算法_聚类算法-K-均值算法

时间：2018-08-03 20:22:39

k-均值聚类算法

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

K-Means算法简介 (Introduction to K-Means Algorithm)

K-means clustering algorithm computes the centroids and iterates until we it finds optimal centroid. It assumes that the number of clusters are already known. It is also calledflat clusteringalgorithm. The number of clusters identified from data by algorithm is represented by ‘K’ in K-means.

K-均值聚类算法计算质心并进行迭代，直到找到最佳质心为止。它假定群集的数目是已知的。它也称为平面聚类算法。通过算法从数据中识别出的聚类数量以K均值中的“ K”表示。

In this algorithm, the data points are assigned to a cluster in such a manner that the sum of the squared distance between the data points and centroid would be minimum. It is to be understood that less variation within the clusters will lead to more similar data points within same cluster.

在该算法中，将数据点分配给群集，以使数据点和质心之间的平方距离之和最小。应当理解，簇内的较少变化将导致相同簇内的更多相似数据点。

K均值算法的工作 (Working of K-Means Algorithm)

We can understand the working of K-Means clustering algorithm with the help of following steps −

我们可以通过以下步骤来了解K-Means聚类算法的工作原理-

Step 1− First, we need to specify the number of clusters, K, need to be generated by this algorithm.

步骤1-首先，我们需要指定此算法需要生成的簇数K。

Step 2− Next, randomly select K data points and assign each data point to a cluster. In simple words, classify the data based on the number of data points.

步骤2-接下来，随机选择K个数据点并将每个数据点分配给一个群集。简单来说，就是根据数据点的数量对数据进行分类。

Step 3− Now it will compute the cluster centroids.

步骤3-现在它将计算群集质心。

Step 4− Next, keep iterating the following until we find optimal centroid which is the assignment of data points to the clusters that are not changing any more −

步骤4-接下来，继续进行以下迭代，直到找到最佳质心，即将数据点分配给不再变化的群集的最佳质心-

4.1− First, the sum of squared distance between data points and centroids would be computed.

4.1-首先，将计算数据点和质心之间的平方距离之和。

4.2− Now, we have to assign each data point to the cluster that is closer than other cluster (centroid).

4.2-现在，我们必须将每个数据点分配给比其他群集(质心)更近的群集。

4.3− At last compute the centroids for the clusters by taking the average of all data points of that cluster.

4.3-最后，通过获取该群集的所有数据点的平均值来计算群集的质心。

K-means followsExpectation-Maximizationapproach to solve the problem. The Expectation-step is used for assigning the data points to the closest cluster and the Maximization-step is used for computing the centroid of each cluster.

K均值遵循期望最大化方法来解决此问题。期望步骤用于将数据点分配给最接近的群集，而最大化步骤用于计算每个群集的质心。

While working with K-means algorithm we need to take care of the following things −

使用K-means算法时，我们需要注意以下事项-

While working with clustering algorithms including K-Means, it is recommended to standardize the data because such algorithms use distance-based measurement to determine the similarity between data points.

在使用包括K-Means的聚类算法时，建议对数据进行标准化，因为此类算法使用基于距离的度量来确定数据点之间的相似性。

Due to the iterative nature of K-Means and random initialization of centroids, K-Means may stick in a local optimum and may not converge to global optimum. That is why it is recommended to use different initializations of centroids.

由于K均值的迭代性质和质心的随机初始化，K均值可能会停留在局部最优中，而可能不会收敛于全局最优。因此，建议使用不同的质心初始化。

用Python实现 (Implementation in Python)

The following two examples of implementing K-Means clustering algorithm will help us in its better understanding −

以下两个实施K-Means聚类算法的示例将帮助我们更好地理解-

例子1 (Example 1)

It is a simple example to understand how k-means works. In this example, we are going to first generate 2D dataset containing 4 different blobs and after that will apply k-means algorithm to see the result.

这是了解k均值工作原理的简单示例。在此示例中，我们将首先生成包含4个不同Blob的2D数据集，然后将应用k-means算法查看结果。

First, we will start by importing the necessary packages −

首先，我们将从导入必要的包开始-

%matplotlib inlineimport matplotlib.pyplot as pltimport seaborn as sns; sns.set()import numpy as npfrom sklearn.cluster import KMeans

The following code will generate the 2D, containing four blobs −

以下代码将生成2D，其中包含四个斑点-

from sklearn.datasets.samples_generator import make_blobsX, y_true = make_blobs(n_samples=400, centers=4, cluster_std=0.60, random_state=0)

Next, the following code will help us to visualize the dataset −

接下来，以下代码将帮助我们可视化数据集-

plt.scatter(X[:, 0], X[:, 1], s=20);plt.show()

Next, make an object of KMeans along with providing number of clusters, train the model and do the prediction as follows −

接下来，使KMeans为对象，并提供聚类数，训练模型并按以下方式进行预测-

kmeans = KMeans(n_clusters=4)kmeans.fit(X)y_kmeans = kmeans.predict(X)

Now, with the help of following code we can plot and visualize the cluster’s centers picked by k-means Python estimator −

现在，借助以下代码，我们可以绘制和可视化由k-means Python估计器选择的集群中心-

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=20, cmap='summer')centers = kmeans.cluster_centers_plt.scatter(centers[:, 0], centers[:, 1], c='blue', s=100, alpha=0.9);plt.show()

例子2 (Example 2)

Let us move to another example in which we are going to apply K-means clustering on simple digits dataset. K-means will try to identify similar digits without using the original label information.

让我们转到另一个示例，在该示例中，我们将对简单数字数据集应用K均值聚类。 K-means将尝试在不使用原始标签信息的情况下识别相似的数字。

First, we will start by importing the necessary packages −

首先，我们将从导入必要的包开始-

%matplotlib inlineimport matplotlib.pyplot as pltimport seaborn as sns; sns.set()import numpy as npfrom sklearn.cluster import KMeans

Next, load the digit dataset from sklearn and make an object of it. We can also find number of rows and columns in this dataset as follows −

接下来，从sklearn加载数字数据集并使其成为对象。我们还可以在此数据集中找到行数和列数，如下所示：

from sklearn.datasets import load_digitsdigits = load_digits()digits.data.shape

输出量 (Output)

(1797, 64)

The above output shows that this dataset is having 1797 samples with 64 features.

上面的输出显示此数据集包含1797个具有64个特征的样本。

We can perform the clustering as we did in Example 1 above −

我们可以像上面的示例1一样执行聚类-

kmeans = KMeans(n_clusters=10, random_state=0)clusters = kmeans.fit_predict(digits.data)kmeans.cluster_centers_.shape

输出量 (Output)

(10, 64)

The above output shows that K-means created 10 clusters with 64 features.

上面的输出显示K-means创建了具有64个特征的10个聚类。

fig, ax = plt.subplots(2, 5, figsize=(8, 3))centers = kmeans.cluster_centers_.reshape(10, 8, 8)for axi, center in zip(ax.flat, centers):axi.set(xticks=[], yticks=[])axi.imshow(center, interpolation='nearest', cmap=plt.cm.binary)

输出量 (Output)

As output, we will get following image showing clusters centers learned by k-means.

作为输出，我们将获得以下图像，该图像显示了通过k均值学习的聚类中心。

The following lines of code will match the learned cluster labels with the true labels found in them −

以下代码行将学习到的集群标签与在其中找到的真实标签匹配：

from scipy.stats import modelabels = np.zeros_like(clusters)for i in range(10):mask = (clusters == i)labels[mask] = mode(digits.target[mask])[0]

Next, we can check the accuracy as follows −

接下来，我们可以检查准确性，如下所示：

from sklearn.metrics import accuracy_scoreaccuracy_score(digits.target, labels)

输出量 (Output)

0.7935447968836951

The above output shows that the accuracy is around 80%.

上面的输出表明精度约为80％。

的优点和缺点 (Advantages and Disadvantages)

优点 (Advantages)

The following are some advantages of K-Means clustering algorithms −

以下是K-Means聚类算法的一些优点-

It is very easy to understand and implement.

这是很容易理解和实施的。

If we have large number of variables then, K-means would be faster than Hierarchical clustering.

如果我们有大量的变量，那么K均值将比层次聚类更快。

On re-computation of centroids, an instance can change the cluster.

在重新计算质心时，实例可以更改群集。

Tighter clusters are formed with K-means as compared to Hierarchical clustering.

与分层聚类相比，使用K均值形成更紧密的聚类。

缺点 (Disadvantages)

The following are some disadvantages of K-Means clustering algorithms −

以下是K-Means聚类算法的一些缺点-

It is a bit difficult to predict the number of clusters i.e. the value of k.

预测簇的数量(即k的值)有点困难。

Output is strongly impacted by initial inputs like number of clusters (value of k).

输出受到初始输入(例如簇数(k值))的强烈影响。

Order of data will have strong impact on the final output.

数据顺序将对最终输出产生重大影响。

It is very sensitive to rescaling. If we will rescale our data by means of normalization or standardization, then the output will completely change.final output.

它对重新缩放非常敏感。如果我们将通过归一化或标准化来重新缩放数据，那么输出将完全改变。

It is not good in doing clustering job if the clusters have a complicated geometric shape.

如果群集具有复杂的几何形状，则不利于进行群集工作。