CN108805174A - 聚类方法及装置 - Google Patents

Abstract

本申请实施例提供一种聚类方法及装置，方法包括：读取包括多个样本的待处理数据，并将待处理数据RDD对象；在多个样本中随机地确定第一预设数量个目标样本，将第一预设数量个样本分别作为第一预设数量个簇的聚类中心；在多个样本中除目标样本之外的样本中，随机地确定第二预设数量个样本；针对第二预设数量个样本中的每一个，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，直至满足预设条件。如此，能够相对有效地避免得到的结果只是局部最优的。

Description

聚类方法及装置

技术领域

本申请涉及大数据技术领域，具体而言，涉及一种聚类方法及装置。

背景技术

聚类方法在机器学习、数据挖掘等众多领域有着极为广阔的应用。常规的聚类方法中，按照一定的特性可以分为层次聚类、划分式聚类、基于密度聚类、基于网络聚类、核聚类、谱聚类等多种。对应地，层次聚类有brich、rock、Chameleon等，划分式聚类有K-means及其变种等，密度聚类有dbscan、OPTICS等，网格聚类有sting、clique等。在这些聚类方法中，最常见的莫过于K-means。尽管K-means有着如圆形分布的先验假设、预先指定聚类类别数等的缺陷，但其相对较低的计算复杂度还是让其成为大受欢迎的算法。但在需要处理的数据量巨大的情况下，现有的K-means的计算复杂度仍旧较大，并且容易容易陷入局部最优的问题。

发明内容

有鉴于此，本申请的目的包括提供一种聚类方法及装置，以改善上述问题。

为了达到上述目的，本申请实施例采用如下技术方案：

第一方面，本申请实施例提供一种聚类方法，应用于基于Spark框架的终端设备，所述方法包括：

通过所述Spark框架读取包括多个样本的待处理数据，并将所述待处理数据RDD对象；

在所述多个样本中随机地确定第一预设数量个目标样本，将所述第一预设数量个样本分别作为所述第一预设数量个簇的聚类中心；

在所述多个样本中除所述第一预设数量个目标样本之外的样本中，随机地确定第二预设数量个样本，其中，所述第二预设数量为所述第一预设数量的预设倍数；

针对所述第二预设数量个样本中的每一个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新；

在更新之后不满足预设条件时，重新在所述多个样本中除所述第一预设数量个目标样本之外的样本中，确定第二预设数量个样本，并将重新确定的第二预设数量个样本划分到相应的簇以对各簇的聚类中心的值进行更新。

可选地，根据本申请实施例第一方面提供的聚类方法，所述预设条件包括：

各簇的聚类中心更新前的值与更新后的值的夹角的平均值小于预设角度；

根据所确定的第二预设数量个样本对各簇的聚类中心的值进行更新的次数达到预设次数。

可选地，根据本申请实施例第一方面提供的聚类方法，所述终端设备中预设有聚类中心更新率；

根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，包括：

以所述聚类中心更新率为所述第一平均值的权重，以1与所述聚类中心更新率的差值为该簇的聚类中心的当前值的权重，计算所述第一平均值及该簇的聚类中心的当前值的加权平均值，将该簇的聚类中心的值更新为得到的加权平均值。

可选地，根据本申请实施例第一方面提供的聚类方法，所述方法还包括：

在满足所述预设条件中任意一个时，根据所述多个样本对各簇的聚类中心进行更新；

当更新之后不满足所述预设条件时，重新根据所述多个样本对各簇的聚类中心进行更新。

可选地，根据本申请实施例第一方面提供的聚类方法，根据所述多个样本对各簇的聚类中心进行更新，包括：

针对所述多个样本中的每个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第二平均值，并将该簇的聚类中心的值更新为该第二平均值。

第二方面，本申请实施例还提供一种聚类装置，应用于基于Spark框架的终端设备，所述装置包括：

数据读取模块，用于通过所述Spark框架读取包括多个样本的待处理数据，并将所述待处理数据RDD对象；

中心确定模块，用于在所述多个样本中随机地确定第一预设数量个目标样本，将所述第一预设数量个样本分别作为所述第一预设数量个簇的聚类中心；

样本选取模块，用于在所述多个样本中除所述第一预设数量个目标样本之外的样本中，随机地确定第二预设数量个样本，其中，所述第二预设数量为所述第一预设数量的预设倍数；

第一划分模块，用于针对所述第二预设数量个样本中的每一个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

第一更新模块，用于计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，在更新之后不满足预设条件时，重新在所述多个样本中除所述第一预设数量个目标样本之外的样本中，确定第二预设数量个样本，并将重新确定的第二预设数量个样本划分到相应的簇以对各簇的聚类中心的值进行更新。

可选地，根据本申请实施例第二方面提供的聚类装置，所述预设条件包括：

各簇的聚类中心更新前的值与更新后的值的夹角的平均值小于预设角度；

根据所确定的第二预设数量个样本对各簇的聚类中心的值进行更新的次数达到预设次数。

可选地，根据本申请实施例第二方面提供的聚类装置，8.根据权利要求7所述的聚类装置，其特征在于，所述终端设备中预设有聚类中心更新率；所述第一更新模块根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新的方式为：

以所述聚类中心更新率为所述第一平均值的权重，以1与所述聚类中心更新率的差值为该簇的聚类中心的当前值的权重，计算所述第一平均值及该簇的聚类中心的当前值的加权平均值，将该簇的聚类中心的值更新为得到的加权平均值。

可选地，根据本申请实施例第二方面提供的聚类装置，所述聚类装置还包括：

第二更新模块，用于在满足所述预设条件中任意一个时，根据所述多个样本对各簇的聚类中心进行更新，当更新之后不满足所述预设条件时，重新根据所述多个样本对各簇的聚类中心进行更新。

可选地，根据本申请实施例第二方面提供的聚类装置，所述第二更新模块根据所述多个样本对各簇的聚类中心进行更新的方式为：

针对所述多个样本中的每个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第二平均值，并将该簇的聚类中心的值更新为该第二平均值。

相较于现有技术而言，本申请实施例具有以下有益效果：

本申请实施例提供的一种聚类方法及装置，应用于基于Spark框架的终端设备。终端设备通过Spark框架读取包括多个样本的待处理数据，并将读取到的数据形成RDD对象。在该多个样本中随机确定第一预设数量个目标样本分别作为第一预设数量个簇的聚类中心，在多个样本中除第一预设数量个目标样本之外的样本中，随机确定第二预设数量个样本，再将第二预设数量个样本划分至相应的簇中。然后计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，直至满足预设条件。通过前述过程，不必在每次更新时都根据全部样本进行更新，降低了计算复杂度，并且能够在一定程度上避免容易收敛于局部最优的问题。

附图说明

为了更清楚地说明本申请实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本申请的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。

图1为本申请实施例提供的一种终端设备的连接框图；

图2为本申请实施例提供的一种聚类方法的流程示意图；

图3本申请实施例提供的聚类方法的又一流程示意图；

图4为本申请实施例提供的一种聚类装置的功能模块框图。

图标：100-终端设备；110-存储器；120-处理器；130-通信单元；200-聚类装置；210-数据读取模块；220-中心确定模块；230-样本选取模块；240-划分模块；250-第一更新模块；260-第二更新模块。

具体实施方式

为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。

因此，以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。

目前有不少的聚类方法适合在大数据环境下使用，但K-means是其中相对好用的一种。在此以基于Spark框架的场景为例，对一些实施方式中的K-means进行阐述：

(1)在给定样本中随机地确定k个样本，这k个样本中的每一个代表了一个簇的聚类中心，其中，k为预先指定的聚类类别数，即所需划分的簇的数量；

(2)在给定样本里的剩余的样本中，计算每个样本与各簇的聚类中心的距离，将该样本划分到与该样本距离最近的聚类中心所代表的簇；

(3)计算每个簇中的各样本的平均值，将该簇的聚类中心的值更新为该平均值。

(4)不断重复第(2)至第(3)步，直到满足相应条件。

然而，经发明人研究发现，在上述方式中，为了保证收敛，每次迭代(更新)都会使用全部的样本直接作为簇的新聚类中心的学习样本，这样恰恰会导致K-means容易收敛于局部最优。并且，在上述的方式中每次簇中心的迭代都是直接使用新的值，而完全忽略更新之前的聚类中心的值，这导致K-menas容易收到一些离群样本的干扰。此外，在数据量较大的情况下，上述方法的K-means的时间复杂度仍旧偏高。

基于此，本申请实施例提出一种聚类方法及装置，应用于基于Spark框架的终端设备，以至少部分地改善上述问题。应当理解，本实施例提供的聚类方法及装置也可以应用于其它框架比如MapReduce，本实施例不以此为限制。下面将对该内容进行详细阐述。

如图1所示，是本申请实施例提供的一种终端设备100的方框示意图，终端设备100可以是任意具有数据处理功能及通信功能的电子设备，例如，可以服务器，具体地，当终端设备100是服务器时，既可以是一个单独的服务器，也可以是多个服务器组成的服务器集群，本实施例对此不做限制。

在本实施例中，终端设备100中可以安装有Spark对应的运行平台，其中，Spark是专为大规模数据处理而设计的快速通用的计算引擎，是开源的类Hadoop MapReduce的通用并行框架。

终端设备100包括聚类装置200、存储器110、处理器120及通信单元130。

在本实施例中，存储器110、处理器120及通信单元130各元件相互之间直接或间接地电性连接，以实现数据的传输或交互。例如，这些元件相互之间可通过一条或多条通讯总线或信号线实现电性连接。聚类装置200包括至少一个可以以软件或固件(firmware)的形式存储于存储器110中或固化在终端设备100的操作系统(Operating System，OS)中的软件功能模块。处理器120用于执行存储器110中存储的可执行模块，例如，聚类装置200所包括的软件功能模块及计算机程序等。

其中，存储器110可以是，但不限于，随机存取存储器(Random Access Memory，RAM)，只读存储器(Read Only Memory，ROM)，可编程只读存储器(Programmable Read-OnlyMemory，PROM)，可擦除只读存储器(Erasable Programmable Read-Only Memory，EPROM)，电可擦除只读存储器(Electric Erasable Programmable Read-Only Memory，EEPROM)等。

处理器120可以是一种集成电路芯片，具有信号处理能力。所述处理器120也可以是通用处理器，如中央处理器(Central Processing Unit，CPU)、网络处理器(NetworkProcessor，NP)、微处理器等；还可以是数字信号处理器(DSP))、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件；处理器120还可以是任何常规的处理器，可以实现或者执行本发明实施例中的公开的各方法、步骤及逻辑框图。

通信单元130用于建立所述终端设备100与其他设备之间的通信连接，以实现数据交互或通信。

应当理解，图1所示的结构仅为示意，终端设备100还可以包括比图1所示更多或更少的组件，也可以具有与图1所示完全不同的配置。在此值得说明的是，图1所示的各组件可以以硬件、软件或其组合实现，本实施例对此不做限制。

如图2所示，是本申请实施例提供的一种聚类方法的流程示意图，该聚类方法能够应用于图1所示的终端设备100。

步骤S201，通过所述Spark读取包括多个样本的待处理数据，并将所述待处理数据形成RDD对象。

其中，RDD是Spark特有的数据模型，所述多个样本是指预先给定的用于聚类的样本。

步骤S202，在所述多个样本中随机地确定第一预设数量个目标样本，将所述第一预设数量个样本分别作为所述第一预设数量个簇的聚类中心。

其中，所述第一预设数量为预先确定的所需的聚类类别数量，即所需划分的簇的数量。

步骤S203，在所述多个样本中除所述第一预设数量个目标样本之外的样本中，随机地确定第二预设数量个样本。

其中，所述第二预设数量为所述第一预设数量的预设倍数。在本实施例中，所述第二预设数量为预先确定的值，表示在每次迭代中需要使用多少样本用于簇的聚类中心的更新，所述第二预设数量通常可以为100-1000。

例如，假设第一预设数量为k，预设倍数为γ，则第二预设数量为k*γ。

步骤S204，针对所述第二预设数量个样本中的每一个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇。

以上述第二预设数量为k*γ为例，针对k*γ个样本中的每一个，计算该样本到达各个簇当前的聚类中心的距离，并确定其中到达该样本的距离最小的聚类中心所对应的簇作为目标簇，再将该样本赋给该目标簇。

步骤S205，计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新。

在本实施例中，针对每个簇，在得到该簇的第一平均值之后，结合该簇的聚类中心的当前值对该簇的聚类中心进行更新。

可选地，在本实施例中，终端设备100中可以预设有聚类中心更新率。对应地，步骤S205可以包括以下步骤：

以所述聚类中心更新率为所述第一平均值的权重，以1与所述聚类中心更新率的差值为该簇的聚类中心的当前值的权重，计算所述第一平均值及该簇的聚类中心的当前值的加权平均值，将该簇的聚类中心的值更新为得到的加权平均值。

假设上述的聚类中心更新率为α，该簇的聚类中心的当前值为old_center，计算得到的第一平均值为new_center，则作为该簇的聚类中心的新值center(即所述加权平均值)可以通过下式计算得到：

center＝α*new_center+(1-α)*old_center

其中，聚类中心更新率可以根据实际情况进行控制，从而能够避免基于部分样本所进行某次更新效果过差所带来的影响。

步骤S206，在更新之后不满足预设条件时，重新在所述多个样本中除所述第一预设数量个目标样本之外的样本中，确定第二预设数量个样本，并将重新确定的第二预设数量个样本划分到相应的簇以对各簇的聚类中心的值进行更新。

换言之，在本实施例中，终端设备100会重复执行步骤S203-步骤S205直至满足所述预设条件。

下面给出一个具体示例，以对步骤S203-步骤S206做详细阐述。

假设在该示例中总共对步骤S203-步骤S206重复执行了1000次，其中，第i次计算得到的第一平均值(即上述的new_center)为v_i，第i次通过计算加权平均值的方式求得的聚类中心的新值(即上述的center)为V_i，假设聚类中心更新率α为0.8，则V_i可以通过下式计算得到：

V_i＝0.8*v_i+0.2*v_i-1

由此可以得知，重复执行上述步骤S203-步骤S205以对聚类中心的值进行更新的过程，实际是通过指数加权平均的方式来实现的，换言之，在本实施例提供的聚类方法中，在每一次更新时都充分考虑了之前更新的值对当前结果的影响，而非孤立地看待或进行每一次更新，如此，能够相对可靠地避免局部收敛的问题。

可选地，在本实施例中，所述预设条件可以包括：

各簇的聚类中心更新前的值与更新后的值的夹角的平均值小于预设角度；

根据所确定的第二预设数量个样本对各簇的聚类中心的值进行更新的次数达到预设次数。

其中，所述预设角度及所述预设次数可以根据实际情况进行灵活设定，本实施例对此不做限制。

此外，发明人还发现如果始终只采用部分样本对各个簇的聚类中心进行迭代更新，可能难以保证完全收敛，所以在根据前述的方式达到预设条件之后，可以进一步使用全部样本对各个簇的聚类中心进行更新。在执行前述步骤的基础上，只需再基于全部样本进行少许次数(通常少于10次)的更新即可，其时间复杂度可忽略不计。

基于此，如图3所示，本实施例提供的聚类方法还可以包括步骤S301和步骤S302。

步骤S301，在满足所述预设条件中任意一个时，根据所述多个样本对各簇的聚类中心进行更新。

其中，步骤S301可以通过如下子步骤实现：

针对所述多个样本中的每个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第二平均值，并将该簇的聚类中心的值更新为该第二平均值。

其中，第二平均值是指当根据全部样本(所述多个样本中的各个样本)对各个簇的聚类中心进行更新之后计算得到的每个簇中各样本的平均值。

步骤S302，当更新之后不满足所述预设条件时，重新根据所述多个样本对各簇的聚类中心进行更新。

在本实施例中，基于全部样本所进行的迭代更新进行到满足所述预设条件时停止。基于上述分析可知，通常会进行少于10次的更新，时间复杂度可忽略不计。

如图4所示，本申请实施例还提供一种聚类装置200，应用于图1所示的终端设备100。所述聚类装置200包括数据读取模块210、中心确定模块220、样本选取模块230、划分模块240及第一更新模块250。

其中，数据读取模块210用于通过所述Spark框架读取包括多个样本的待处理数据，并将所述待处理数据形成RDD对象。

在本实施例中，关于数据读取模块210的描述具体可参考对图2所示步骤S201的详细描述，即步骤S201可以由数据读取模块210执行。

中心确定模块220用于在所述多个样本中随机地确定第一预设数量个目标样本，将所述第一预设数量个样本分别作为所述第一预设数量个簇的聚类中心。

在本实施例中，关于中心确定模块220的描述具体可参考对图2所示步骤S202的详细描述，即步骤S202可以由中心确定模块220执行。

样本选取模块230用于在所述多个样本中除所述第一预设数量个目标样本之外的样本中，随机地确定第二预设数量个样本，其中，所述第二预设数量为所述第一预设数量的预设倍数。

在本实施例中，关于样本选取模块230的描述具体可参考对图2所示步骤S203的详细描述，即步骤S203可以由样本选取模块230执行。

划分模块240用于针对所述第二预设数量个样本中的每一个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇。

在本实施例中，关于划分模块240的描述具体可参考对图2所示步骤S204的详细描述，即步骤S204可以由划分模块240执行。

第一更新模块250用于计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，在更新之后不满足预设条件时，重新在所述多个样本中除所述第一预设数量个目标样本之外的样本中，确定第二预设数量个样本，并将重新确定的第二预设数量个样本划分到相应的簇以对各簇的聚类中心的值进行更新。

在本实施例中，关于第一更新模块250的描述具体可参考对图2所示步骤S205的详细描述，即步骤S205可以由第一更新模块250执行。

其中，所述预设条件可以包括：

各簇的聚类中心更新前的值与更新后的值的夹角的平均值小于预设角度；

根据所确定的第二预设数量个样本对各簇的聚类中心的值进行更新的次数达到预设次数。

可选地，终端设备100可以中预设有聚类中心更新率。

对应地，第一更新模块250根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新的方式可以为：

以所述聚类中心更新率为所述第一平均值的权重，以1与所述聚类中心更新率的差值为该簇的聚类中心的当前值的权重，计算所述第一平均值及该簇的聚类中心的当前值的加权平均值，将该簇的聚类中心的值更新为得到的加权平均值。

可选地，所述聚类装置200还可以包括第二更新模块250。

其中，第二更新模块260用于在满足所述预设条件中任意一个时，根据所述多个样本对各簇的聚类中心进行更新，当更新之后不满足所述预设条件时，重新根据所述多个样本对各簇的聚类中心进行更新。

在本实施例中，关于第二更新模块260的描述具体可参考上述内容中对图3所示步骤S301和步骤S302的详细描述，即步骤S301和步骤S302可以由第二更新模块260执行。

可选地，在本实施例中，第二更新模块260根据所述多个样本对各簇的聚类中心进行更新的方式可以为：

针对所述多个样本中的每个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第二平均值，并将该簇的聚类中心的值更新为该第二平均值。

综上所述，本申请实施例提供的一种聚类方法及装置，应用于基于Spark框架的终端设备。终端设备通过Spark框架读取包括多个样本的待处理数据，并将读取到的数据形成RDD对象。在该多个样本中随机确定第一预设数量个目标样本分别作为第一预设数量个簇的聚类中心，在多个样本中除第一预设数量个目标样本之外的样本中，随机确定第二预设数量个样本，再将第二预设数量个样本划分至相应的簇中。然后计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，直至满足预设条件。通过前述过程，不必在每次更新时都根据全部样本进行更新，降低了计算复杂度，并且能够在一定程度上避免容易收敛于局部最优的问题。

在本申请所提供的实施例中，应该理解到，所揭露的装置和方法，也可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，附图中的流程图和框图显示了根据本申请的多个实施例的装置、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现方式中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

另外，在本申请各个实施例中的各功能模块可以集成在一起形成一个独立的部分，也可以是各个模块单独存在，也可以两个或两个以上模块集成形成一个独立的部分。

所述功能如果以软件功能模块的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本申请各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

以上所述，仅为本申请的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应以权利要求的保护范围为准。

Claims (10)

1.一种聚类方法，其特征在于，应用于基于Spark的终端设备，所述方法包括：

通过所述Spark读取包括多个样本的待处理数据，并将所述待处理数据形成RDD对象；

在所述多个样本中随机地确定第一预设数量个目标样本，将所述第一预设数量个样本分别作为所述第一预设数量个簇的聚类中心；

在所述多个样本中除所述第一预设数量个目标样本之外的样本中，随机地确定第二预设数量个样本，其中，所述第二预设数量为所述第一预设数量的预设倍数；

针对所述第二预设数量个样本中的每一个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新；

在更新之后不满足预设条件时，重新在所述多个样本中除所述第一预设数量个目标样本之外的样本中，确定第二预设数量个样本，并将重新确定的第二预设数量个样本划分到相应的簇以对各簇的聚类中心的值进行更新。

2.根据权利要求1所述的聚类方法，其特征在于，所述预设条件包括：

各簇的聚类中心更新前的值与更新后的值的夹角的平均值小于预设角度；

根据所确定的第二预设数量个样本对各簇的聚类中心的值进行更新的次数达到预设次数。

3.根据权利要求2所述的聚类方法，其特征在于，所述终端设备中预设有聚类中心更新率；

根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，包括：

以所述聚类中心更新率为所述第一平均值的权重，以1与所述聚类中心更新率的差值为该簇的聚类中心的当前值的权重，计算所述第一平均值及该簇的聚类中心的当前值的加权平均值，将该簇的聚类中心的值更新为得到的加权平均值。

4.根据权利要求2或3所述的聚类方法，其特征在于，所述方法还包括：

在满足所述预设条件中任意一个时，根据所述多个样本对各簇的聚类中心进行更新；

当更新之后不满足所述预设条件时，重新根据所述多个样本对各簇的聚类中心进行更新。

5.根据权利要求4所述的聚类方法，其特征在于，根据所述多个样本对各簇的聚类中心进行更新，包括：

针对所述多个样本中的每个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第二平均值，并将该簇的聚类中心的值更新为该第二平均值。

6.一种聚类装置，其特征在于，应用于基于Spark框架的终端设备，所述装置包括：

数据读取模块，用于通过所述Spark框架读取包括多个样本的待处理数据，并将所述待处理数据形成RDD对象；

中心确定模块，用于在所述多个样本中随机地确定第一预设数量个目标样本，将所述第一预设数量个样本分别作为所述第一预设数量个簇的聚类中心；

样本选取模块，用于在所述多个样本中除所述第一预设数量个目标样本之外的样本中，随机地确定第二预设数量个样本，其中，所述第二预设数量为所述第一预设数量的预设倍数；

划分模块，用于针对所述第二预设数量个样本中的每一个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

第一更新模块，用于计算每个簇中各样本的平均值作为第一平均值，根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新，在更新之后不满足预设条件时，重新在所述多个样本中除所述第一预设数量个目标样本之外的样本中，确定第二预设数量个样本，并将重新确定的第二预设数量个样本划分到相应的簇以对各簇的聚类中心的值进行更新。

7.根据权利要求6所述的聚类装置，其特征在于，所述预设条件包括：

各簇的聚类中心更新前的值与更新后的值的夹角的平均值小于预设角度；

根据所确定的第二预设数量个样本对各簇的聚类中心的值进行更新的次数达到预设次数。

8.根据权利要求7所述的聚类装置，其特征在于，所述终端设备中预设有聚类中心更新率；所述第一更新模块根据所述第一平均值及该簇的聚类中心的当前值对该簇的聚类中心的值进行更新的方式为：

以所述聚类中心更新率为所述第一平均值的权重，以1与所述聚类中心更新率的差值为该簇的聚类中心的当前值的权重，计算所述第一平均值及该簇的聚类中心的当前值的加权平均值，将该簇的聚类中心的值更新为得到的加权平均值。

9.根据权利要求7或8所述的聚类装置，其特征在于，所述聚类装置还包括：

第二更新模块，用于在满足所述预设条件中任意一个时，根据所述多个样本对各簇的聚类中心进行更新，当更新之后不满足所述预设条件时，重新根据所述多个样本对各簇的聚类中心进行更新。

10.根据权利要求9所述的聚类装置，其特征在于，所述第二更新模块根据所述多个样本对各簇的聚类中心进行更新的方式为：

针对所述多个样本中的每个样本，计算该样本与各簇的聚类中心的距离，将该样本划分到与该样本的距离最近的聚类中心所在的簇；

计算每个簇中各样本的平均值作为第二平均值，并将该簇的聚类中心的值更新为该第二平均值。