英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
K-means 算法的修改建议
摘要
K-means算法是最流行的数据聚类算法之一。与此算法，相似类型的数据都试图利用大数据与由重复计算强行聚集在一起。其结果，该算法的计算复杂度非常高。几个研究已经进行了减少这种复杂性。本文介绍了我们的研究，其中提出K-means算法的修改版本以一种改进的技术来划分数据设成与几个检验点值的帮助簇的具体的数字的结果。它需要较少的计算，并加强了精度比传统的K-means算法，以及传统的K-means的某些改进算法
关键词：簇，聚类算法，欧氏距离，数据挖掘
介绍
如今数据已成为人类的财富之一。几乎每一个部门的数据存储以备将来使用。随着数据大小的增加，运用这些数据的技术变得更具挑战性。
如此大量的数据被用于发现新的知识。从本质上讲，数据挖掘（DM）利用这些庞大的数据仓库并从中提取信息[1]。数据挖掘是通过该用户尝试从所存储的数据获取知识的技术。这经常运用于知识发现系统。另外数据挖掘用于设计人工智能系统，机器学习过程和统计制度[2] [3]。
聚类分析是数据挖掘的应用。聚类涉及讲类似于彼此但从属于其他簇的物体不同的物体组合在一起[4]。它对原始数据进行合理的分类方式，使人们可以找出那些在数据集中存在隐藏的图案[5]。聚类是数据挖掘领域以及在机器学习扇区中使用的关键技术之一。它也应用在许多领域，如知识发现，模式识别与分类，数据压缩和矢量量化。它还在生物学，地质学，地理和市场营销的领域发挥重要作用[6]。
分配对象到特定簇需要大量的计算。其中最流行的算法毫无疑问是K-means算法。在该算法中，K-随机的数据点被选择作为聚类中心。然后每一个成员的欧几里得距离是从第k簇的中心来计算。然后，成员由这个距离分配给任何簇。
这个过程需要重复几次，除非任何一个对象移动到了另一个簇。该算法是用于分发数据对象成所需的簇很受欢迎。然而，该算法的主要问题是，它需要大量的计算量，因此需要一个很长的时间。
研究人员提出的k-均值算法有许多改进版本。在论文[ 8 ] [ 9 ]中，研究人员提出要保持2个数据结构，以节省当前最小距离和当前分配的簇名。这个过程在一个大范围内减少了计算，并提供了一个更好的性能比传统的k-均值算法。但是，该算法的主要问题是，“当前最小距离”并不总是正确的最小距离。
如上所述，本文的主要目的是提出修改的k-均值算法，将具有相同的功能，作为传统的k-均值算法。但是，这将克服在上一节中所讨论的问题。本文将提出一种更有效和计算成本更少的算法。
在本文的不同部分，详细阐述了本论文的总体过程和工作方式，并对相关背景进行了详细的阐述，下面是本文的一小段。
在背景研究中，相关的作品以汇总的方式呈现。集中了改进的k-均值聚类算法、改进的初始中心理论和更好的初始聚类概念相关的工作。
在算法部分，提出了算法。下面提供的算法和一些图形化的描述。
结果分析部分着重于结果分析，该算法的结果将与传统的K-means算法的其他修改算法一起比较讨论。
最后的弊端和展望将在结论部分描述。
相关作品
在开始提出算法之前，我们有必要对相关的背景研究讨论，在这一部分对相关的思想和研究进行了简要的讨论。大量的工作已经由K-means算法完成，在这里，为了更好地理解它，我们将最先进行讨论。
在现代世界中，数据变得越来越重要了。大型组织倾向于保持数据的安全性，并将它们储存在这样一种方式，它可以在未来使用。随着数据量的增长，需要以结构化的方式来维护它，这将变得具有挑战性。在数据挖掘技术中，这一挑战是以一种结构化的方式处理的。在这项技术中，如果需要的话，数据挖掘可以从这个数据中得到有用的信息。目前世界上的数据是一个连续的产品业务，可以用在很多好产品上。
聚类是一个将一组对象组织成不相交的过程，这些类被称为簇[9]。这是一个无监督分类的版本，因此不依赖于预定义的类。它试图划分数据集，基于特定的特征，得到簇内比不同的对象更相似的数据组[4] [10-11]。
k-means的算法是一种基于划分的聚类方法[ 12 ]。在传统的k-means算法K随机点是从整个数据集作为主要的聚类中心。然后计算每个对象和每个聚类中心之间的距离。最后，每个对象被分配到最近的簇。找到距离欧几里得公式。
所以整个算法可描述如下[ 16 ]：输入：N-物体和聚类输出数：K -聚类0＜n＜n个数据成员。任意选择的对象为初始聚类中心。计算每个对象之间的距离和每个聚类中心。将每个对象分配到最近的簇，用欧式公式计算距离，公式为：
其中，i=1hellip;..N; j=1hellip;hellip;..k;
d(xi, mi)是数据i和簇j之间的距离。计算每个集群中的每个对象的平均值作为新的聚类中心，使用以下公式：
其中， i=1,2hellip;hellip;..k;
Ni是当前簇里对象的数目。
重复以上步骤，直到满足收敛准则。
在传统的k-均值算法中，需要大量的计算，这是一种蛮干的算法。因此，我们必须计算每个对象的距离，从它的聚类中心，无论是移动的或从集群中。即使从一个聚类中心的最接近的对象，需要确保它不靠近任何其他聚类中心。结果将会导致大量的计算。
参考[ 8 ] [ 9 ]表明研究人员提出了一种改进的算法，有一个改进的初始中心。在这里，他们把整个数据集按距离计算出的距离进行排序。然后将数据集分成相等的k-portions。此值取决于数据集以及用户的需要。在每个数据集的中心点作为初始聚类中心，所有其他属性距离与这些中心使用欧氏距离公式计算。之后，数据点被分配到最近的群集中心也被称为质心。此方法中使用了2个数据结构：一个用于存储当前群集中心的标签，另一个用于保存当前群集中心的距离。在第一次迭代的聚类中心的距离计算，再次测量。如果距离小于前一阶段计算的距离，则群集中心和距离更新，否则该点仍然在同一个群集。这个过程继续，直到满足收敛准则。这2个数据结构把这个修改成一个更好的算法。作为性能提高，该算法提供了一个更好的精度比传统的k-均值算法。但是，这个算法的问题是，目前的最小距离的以前的迭代可能不是最好的最小距离为下一次迭代。因为每一次的聚类中心进行重新计算，每个对象的距离的变化。但从上一次迭代中使用的最小距离可能会导致一些错误。
参考文献[ 17 ]显示研究人员提出了一种寻找一个更好的初始中心，以及初始中心的数目，这是在这里的算法是基于k-means的能力，以避免替代的随机性。在子合并策略的帮助下，将分类结果与合成算法相结合，得到了比传统的k-means算法更好的性能。
提出算法
在前一节中提到的k-均值算法的一个新的和更好的变体，将在本文中提出。在这一节中，将提供该算法及其定义。一些数据也会有更好的理解。
在传统的k-means算法中，每一次迭代中都有一个聚类中心和每个数据点之间的距离。这使得算法更复杂，增加了计算的数量。为了减少计算，一个检查点的值将被用于在该算法。这将减少大规模的计算。首先： 假设一个数据集在N数据的对象中可用，每个对象都有Di (i=1hellip;..n)的属性。输出就是k聚类，k根据客户的需要来设定。
此算法：
步骤1：找到每个数据对象的离原点的欧几里德距离：(0i,0jhellip;hellip;0n).
在这里，我们随机选择的数据对象作为初始原点。然后我们发现欧氏距离相对于原点的每个数据对象之间。
步骤2：根据在前面的步骤中找到的距离排序的N数据对象然后升序.
步骤3：划分数据集为K等于集群。 ķ将根据用户的要求或在数据集的类型来确定。这将作为主群集。
为了建立初始聚类，这一步是必要的。根据我们现在所需要的数量，我们将整个数据集分成相等的部分。对于每一种情况，可能不是这样的情况，因为在每一个数据集可能有不相等的对象。例如，如果我们有1000个数据对象，我们必须将它们分为3个集群，那么集群中的每一个对象可以有333333334个对象。
步骤4：对于每个群集，考虑中间点作为主群集中心。也就是说，如果有N个数据成员和K群集，主群集中心将有Gamma; ( (n/k)/2)˥th个对象。
由于这个数据集是从从初始起源的距离，所以中心点将是最重要的点，在每个集群中，所有的数据对象将有一个主要统一的距离。
步骤5：查找集群中心之间的距离。如果有K个簇，将有K-距离。除以2的距离，并存储Dij的值（i，j= 0,1，... K）。这里Dij表示从聚类中心i到聚类中心j的距离的中间点。此Dij将用作一个检查点值。
例如，如果集A和B具有聚类中心Ai和Bi，并且假设Ai和Bi之间的距离的中心点和将表示的点的距离是两个相等的聚类中心。因此，如果需要的话，它可被用来确定新的群集为任何数据对象，。
步骤6：查找从它被分配给该群集中心的每个数据对象二的欧几里得距离di（ⅰ= 1. K）
步骤7：比较存储在Dij中di的距离
如果该距离小于或等于Dij，那么对象停留在先前簇中。
也就是说，从当前集群中心的距离小于2个聚类中心点的距离。作为一个结果，我们可以得出这样的结论：该对象是接近其当前集群。因此，我们不需要计算距离从其他集群中心。此检查点的值将确保我们需要更少的计算量。
其他计算相对于与该距离越过检查点值的中心数据对象的欧几里得距离。即，如果超过Dij并且该对象是聚类中心i，则计算相对于聚类中心j中的距离的簇中。
这意味着对象可以更接近于其他群集中心。要确定这一点，我们必须计算相对于其他集群中心的距离。
现在比较的距离。将数据对象分配给来自其中心的群集，其距离较短。
重新计算聚类中心以每个对象目前在一个集群的意思。这个点可以是一个不存在于我们当前数据集或可以是我们数据集的当前对象的一个假想点。这不会影响我们的算法的结果。
返回到步骤4，然后重复，直到满足收敛准则。在集群中心被改变后，没有一个数据对象从一个集群移动到另一个集群。该结果在集群的对象保持不变，因此该中心也保持不变。现在我们可以得出结论，我们已经实现了最后的集群。这是我们将相似的对象分组在一起，不同于其他集群
图1显示2个群集中心1和2和一个对象。该图还显示聚类中心之间的中点D12。我们假设对象镍是先前分配给集群中心1。现在我们发现NIJ从集群1的距离。如果距离小于或等于两个中心的平均距离（D12），那么对象停留在以前的群集。
图2显示了另一种可能性。如果有任何关于聚类中心对象的当前距离大于两簇的平均距离然后计算相对于其他聚类中心的欧氏距离的物体。如果新的距离小于前一个，则对象移动到新的群集。
图1.根据中心的距离确定聚类中心
图2.根据中心的距离确定聚类中心
结果分析
在这一节中，我们分析了我们所提出的算法的有效性和准确性。我们用虹膜的实验，新的甲状腺和心脏超声数据集[ 18 ]。这些数据集也被用来在参考[ 9 ]。因此我们可以有更明显的结果。
表1.算法性能比较
全文共6058字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[154772]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
|
数据组 |
算法 |
准确性 |
|
(%) |
||
|
传统k-means |
63.14 |
|
|
虹膜 |
||
|
[9]中的算法 |
88.66 |
|
|
提出的算法 |
90.0 |
|
|
传统k-means |
67.10 |
|
|
新甲状腺 |
||
|
[9]中的算法 |
85.11 |
|
|
提出的算法 |
85.11 |
|
|
传统 K-Means |
71.42 |
|
|
心脏超声数据集 |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
