来源:数据分析师 CPDA | 时间:2019-10-16 | 作者:admin
每个机器学习工程师都想用他们的算法实现准确的预测。这种学习算法一般分为两类——监督的和非监督的。K-means聚类是一种无监督算法,其中可用的输入数据没有标记的响应。
类型的聚类
聚类是一种无监督学习,其中数据点根据其相似程度分组成不同的集合。集群主要有两类:
分层聚类
划分聚类
层次聚类进一步细分为:
烧结的集群
分裂聚类
分区聚类进一步细分为:
k - means聚类
模糊c均值聚类
分层聚类
分层聚类使用树状结构,就像这样:
在聚集集群中,有一种自底向上的方法。我们开始时将每个元素作为一个单独的集群,然后将它们合并成连续的更大的集群,如下所示:
分裂式集群是一种自顶向下的方法。我们从整个集合开始,然后继续将其划分为依次较小的集群,如下所示:
划分聚类
划分聚类分为k -均值聚类和模糊c -均值聚类。
在K -means集群中,对象被划分为若干个集群,每个集群的编号为K。因此,如果我们说K = 2,则对象被分为两个集群,即c1和c2,如下所示:
在这里,比较特征或特征,并将所有具有相似特征的对象聚集在一起。
模糊c均值与k均值非常相似,因为它将具有相似特征的对象聚集在一起。在k-means集群中,单个对象不能属于两个不同的集群。但是在c语言中,对象可以属于多个集群,如下所示。
什么是k?
K-Means聚类是一种无监督学习算法。与监督学习不同,这种聚类没有带标签的数据。K-Means将对象划分为具有相似点和不同于属于另一个集群的对象的集群。
“K”是一个数字。您需要告诉系统需要创建多少集群。例如,K = 2表示两个集群。有一种方法可以求出给定数据K的最佳值。
为了更好地理解k-means,让我们以板球为例。想象一下,你收到了来自世界各地的许多板球运动员的数据,这些数据提供了运动员在过去十场比赛中得分和三柱出局的信息。根据这些信息,我们需要将数据分为两个集群,即击球手和投球手。
让我们看看创建这些集群的步骤。
解决方案:
指定数据点
这里,我们将数据集绘制在“x”和“y”坐标上。y轴上的信息是得分,x轴上是球员的三柱门。
如果我们绘制数据,这是它的样子:
进行聚类
我们需要创建集群,如下图所示:
考虑相同的数据集,我们使用K- means聚类(取K = 2)来解决这个问题。
K -means聚类的第一步是随机分配两个中心体(K=2)。两个点被指定为中心点。注意,这些点可以在任何地方,因为它们是随机的点。它们被称为中心体,但最初,它们不是给定数据集的中心点。
下一步是确定每个数据点与随机分配的中心点之间的距离。对于每一个点,距离都是从两个质心开始测量的,无论哪个距离更小,这个点都分配给那个质心。你可以看到数据点与中心体相连,在这里用蓝色和黄色表示。
下一步是确定这两个簇的实际形心。原始的随机分配的质心将被重新定位到集群的实际质心。
计算距离和重新定位质心的过程一直持续到我们得到最终的星系团。然后质心重新定位停止。
正如上面所看到的,形心不再需要重新定位,这意味着算法已经收敛,我们有两个具有形心的集群。
K-Means集群的应用
K-Means集群用于现实生活中的各种例子或业务案例,如:
学业成绩
诊断系统
搜索引擎
无线传感器网络
学业成绩
根据分数,学生被分为A、B、C等。
诊断系统
医学界使用k-means来创建更智能的医疗决策支持系统,特别是在肝病的治疗方面。
搜索引擎
集群是搜索引擎的支柱。当执行搜索时,需要对搜索结果进行分组,搜索引擎通常使用集群来完成这一任务。
无线传感器网络
聚类算法的作用是找到簇头,将簇内的所有数据收集到各自的簇中。
距离测量
距离度量决定了两个元素之间的相似性,并影响簇的形状。
K-Means聚类支持各种距离度量,如:
欧氏距离度量
曼哈顿距离测量
平方欧几里得距离
余弦距离测量
欧氏距离度量
最常见的情况是确定两点之间的距离。如果我们有一个点P和点Q,欧几里得距离就是一条普通的直线。它是欧几里得空间中两点之间的距离。
两点之间的距离公式如下:
平方欧几里得距离
这和欧几里得距离测量是一样的,但是最后不取平方根。公式如下:
曼哈顿距离测量
曼哈顿距离是水平分量和垂直分量的简单和,或者是沿直角坐标轴测量的两点之间的距离。
注意我们取的是绝对值这样负数就不会起作用。
公式如下:
余弦距离测量
在这种情况下,我们取两个向量之间的夹角,这两个向量是由原点上的点连接而成的。公式如下:
K-Means集群是如何工作的?
下图展示了k-means集群的工作原理:
K-Means算法的目标是在给定的输入数据中找到集群。有几种方法可以做到这一点。我们可以通过指定K的值来使用试错法(例如,3、4、5)。
另一种方法是使用肘部技术来确定K的值。一旦我们得到K的值,系统将随机分配多个中心点,并测量每个数据点到这些中心点的距离。因此,它将这些点分配给距离最小的相应的形心。所以每个数据点都会被分配到离它最近的质心。因此我们有K个初始簇。
对于新形成的簇,计算新的质心位置。与随机分配的质心相比,质心的位置移动了。
同样,每个点的距离都是从新的质心点开始测量的。如果需要,将数据点重新定位到新的质心,重新计算平均位置或新的质心。
如果质心移动,迭代继续进行,表示没有收敛。但是一旦质心停止移动(这意味着集群过程已经收敛),它将反映结果。
让我们使用一个可视化示例来更好地理解这一点。
我们有一个杂货店的数据集,我们想要找出有多少集群需要分散。为了找到最优的集群数量,我们将其分解为以下几个步骤:
步骤1:
弯管法是找出簇数的最佳方法。肘方法构成了数据集上运行的K-Means集群。
接下来,我们使用平方和内的方法来寻找给定数据集可以形成的最优集群数量。平方和内(WSS)定义为集群中每个成员与其质心之间距离的平方和。
每个K值测量WSS,取WSS最少的K值作为最优值。
现在,我们在WSS和集群数量之间绘制一条曲线。
这里,WSS在y轴上,集群数量在x轴上。
可以看到,随着K值从2增加,WSS的值有一个非常缓慢的变化。
所以,你可以把肘部的点值作为k的最优值,它应该是2,3,或者最多4。但是,除此之外,增加集群的数量不会显著地改变WSS中的值,它会得到稳定。
步骤2:
假设这些是我们的交付点:
我们可以随机初始化两个点,称为聚类中心。
这里,C1和C2是随机分配的质心。
步骤3:
现在测量每个位置到形心的距离,并将每个数据点分配给形心,形心是最接近它的。
这是如何进行初始分组:
步骤4:
计算第一组数据点的实际质心。
步骤5:
将随机形心重新定位到实际形心。
步骤6:
计算第二组数据点的实际质心。
步骤7:
将随机形心重新定位到实际形心。
步骤8:
一旦集群变得静态,k-means算法就被认为是收敛的。
中心体c1和c2的最终星系团如下图所示:
k - means聚类算法
假设我们有x1 x2 x3……x(n)作为输入,我们想把它分成K个簇。
形成集群的步骤如下:
步骤1:选择K个随机点作为聚类中心,称为中心体。
步骤2:通过实现欧氏距离(即,计算其到每个质心的距离)
步骤3:通过取分配的点的平均值来识别新的中心体。
步骤4:不断重复步骤2和步骤3,直到达到收敛
让我们详细查看一下其中的每个步骤。
步骤1:
我们随机选择K(中心体)我们把它们命名为c1 c2…ck,我们可以说:
其中C是所有质心的集合。
步骤2:
我们将每个数据点分配到其最近的中心,这是通过计算欧氏距离来实现的。
其中dist()为欧式距离。
在这里,我们计算每个x值到每个c值的距离,即x1-c1、x1-c2、x1-c3之间的距离,等等。然后我们找出哪个是最小的值并将x1赋给那个特定的形心。
类似地,我们求出x2和x3的最小距离。
步骤3:
我们通过对分配给该星系团的所有点求平均值来确定实际的形心。
其中Si是分配给第i个簇的所有点的集合。
这意味着原来的点,也就是我们认为的质心,会移动到新的位置,也就是每个基团的质心。
步骤4:
不断重复步骤2和步骤3,直到达到收敛。
演示:k - means聚类
问题陈述-沃尔玛想要在佛罗里达州开一个连锁店,它想要找到最佳的店面位置来最大化收入。
这里的问题是,如果他们开了太多的商店,彼此之间很近,他们就不会赚钱。但是,如果商店距离太远,他们就没有足够的销售范围。
解决方案——像沃尔玛这样的组织是电子商务巨头。他们的数据库中已经有了客户的地址。因此,他们可以利用这些信息并执行K-Means聚类来找到最佳位置。