CN103473255A - 一种数据聚类方法、系统及数据处理设备 - Google Patents

Abstract

本发明适用于数据处理领域，提供了一种数据聚类方法、系统及数据处理设备。所述方法包括以下步骤：输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；从所述数据集中选择k个块数据对象作为初始类中心；计算各个对象到所述初始类中心的距离；根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；计算各个类的中心作为新的类中心；重复执行所述根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类的步骤；以及所述计算各个类的中心作为新的类中心的步骤，直至算法收敛，获得数据集的划分结果。本发明可以直接对具有块特性的数据进行处理，而不需要对块数据进行压缩处理，避免了信息的丢失，得到的聚类结果比对块数据压缩后的聚类效果更佳。

Description

一种数据聚类方法、系统及数据处理设备

技术领域

本发明属于数据处理领域，尤其涉及一种数据聚类方法、系统及数据处理设备。

背景技术

随着数据自动生成和采集技术的迅猛发展，许多领域产生了记录人们行为细节的海量数据，为行为模式挖掘提供了可能。这些描述被采集对象行为的数据具有一种共同特征，即每个对象的行为是通过多条记录集合来刻画的，我们将记录对象行为特征的数据集称为一个块数据。比如一个客户的购买行为或通话行为是通过该客户在一个时间段的购买明细或通话明细体现的。通过对块数据进行深入挖掘，有助于我们对客户的行为进行分析和预测。然而，当前的机器学习算法不能对块数据直接进行处理，必须将其转换成标准的数据进行处理，致使数据中存在的潜在行为特征可能被忽略。

发明内容

本发明的目的在于提供一种数据聚类方法、系统及数据处理设备，旨在解决现有技术中存在的当前的机器学习算法不能对块数据直接进行处理，必须将其转换成标准的数据进行处理，致使数据中存在的潜在行为特征可能被忽略的问题。

本发明是这样实现的，一种数据聚类方法，所述方法包括以下步骤：

输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；

从所述数据集中选择k个块数据对象作为初始类中心；

计算各个对象到所述初始类中心的距离；

根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；

计算各个类的中心作为新的类中心；

重复执行所述根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类的步骤；以及所述计算各个类的中心作为新的类中心的步骤，直至算法收敛，获得数据集的划分结果。

本发明的另一目的在于提供一种数据聚类系统，所述系统包括：

输入模块，用于输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；

选择模块，用于从所述数据集中选择k个块数据对象作为初始类中心；

距离计算模块，用于计算各个对象到所述初始类中心的距离；

分配模块，用于根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；

类中心计算模块，用于计算各个类的中心作为新的类中心；

循环控制模块，用于控制重复执行分配对象和计算类中心的步骤，直至算法收敛，获得数据集的划分结果。

本发明的另一目的在于提供一种包括上面所述的数据聚类系统的数据处理设备。

在本发明中，通过迭代过程把数据集划分为不同类别，使得评价聚类性能的准则函数达到最优。首先从数据集中随机选择k（期望的类别数）个块数据对象作为初始类中心；然后按照块数据之间的距离描述，计算数据集中的每一个块对象到初始类中心之间的距离，将每个块对象分配到离其最近的中心，形成k个类；通过容斥原理计算每个类的中心作为新的类中心；重复分配对象和计算类中心的步骤，直至算法收敛。本发明实施例能够快速地对现实世界中广泛存在的块数据进行聚类，是一种既高效又实用的划分聚类方法。本发明实施例可以直接对具有块特性的数据进行处理，而不需要对块数据进行压缩处理，避免了信息的丢失，得到的聚类结果比对块数据压缩后的聚类效果更佳。另外，本发明实施例还能够处理大规模数据。

附图说明

图1是本发明实施例提供的数据聚类方法的实现流程示意图。

图2是本发明实施例提供的34个城市的聚类结果图。

图3是本发明实施例提供的数据聚类系统的结构示意图。

具体实施方式

为了使本发明的目的、技术方案及有益效果更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

请参阅图1，为本发明实施例提供的数据聚类方法的实现流程，其包括以下步骤：

在步骤S101中，输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；

在本发明实施例中，假定待聚类的数据集为X＝{x₁,x₂,L,x_n}，其中 $x_i=\left[\begin{array}{c}{x}_{i,\mathrm{1,1}},x_{i,\mathrm{1,2}},L,x_{i,1,m}\\ x_{i,\mathrm{2,1}},x_{i,\mathrm{2,2}},L,x_{i,2,m}\\ L\\ x_{i,r,1},x_{i,r,2},L,x_{i,r,m}\end{array}\right]$ 是第i个由m个属性，r个明细记录描述的对象，我们将x_i称为一个块数据对象。k是期望的类别数。

在步骤S102中，从所述数据集中选择k个块数据对象作为初始类中心；

在本发明实施例中，从数据集X中选择k个块数据对象作为初始类中心c₁,c₂,L,c_k的步骤，具体为：从数据集X中随机选出k个块对象作为初始类中心。

在步骤S103中，计算各个对象到所述初始类中心的距离；

在步骤S104中，根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；

在本发明实施例中，对象之间的距离取决于对象属性值之间的差异性，对于块数据对象之间的距离采用公式

进行度量，其中x,y表示两个块数据对象，A_i,B_i分别表示两个对象在i个属性下的域值，m为描述对象的特征数或属性数。

在步骤S105中，计算各个类的中心作为新的类中心；

在本发明实施例中，首先通过计算该类中所有对象明细数的均值作为该类的类中心要包含的记录数r；然后统计每一维域值中每一个元素在该类中不同对象中出现的频率，如果域值的个数大于r，则选取频率最高的前r个值作为该维的代表，反之，按照频率由高到低的顺序反复取域值，直到取够r个值；重复上述步骤，得到m列个代表，构成该类的类中心。

在步骤S106中，重复执行步骤S104和S105的步骤，直至算法收敛，获得数据集的划分结果。

在本发明实施例中，通过计算前后类中心的距离，如果二者的距离小于一个给定的阈值，则算法结束。

下面结合本发明实施例提供的方法详细说明该实例实施的具体步骤如下：

1）我们从http://www.wunderground.com/上下载了2011年全国34个省会城市（包括香港和澳门）的天气数据，除了上海是364天的数据，其他城市都是365天的数据，因此每个城市一年的数据是一个典型的块数据。为方便，我们选择了16个没有缺失值的属性描述天气数据的特征。由于属性是数值型特征，我们采用了均匀量化的方法对数值型数据离散化为30个分类型值。

2）假定期望的类别数是2，选择太原和武汉两个城市作为初始类中心。

3）利用定义的距离公式计算每一个城市到太原和武汉之间的距离，并将每一个块数据对象分配到离其最近的中心。

4）计算每一类中的类中心。

5）判断新类中心和初始类中心的距离是否小于给定的阈值。

6）如果小于，则结束，否则转到步骤3），直至算法收敛。

7）聚类结果如图2所示，其中圆圈和五角星表示分成的两类，三角形表示该城市没有2011年的天气数据。

请参阅图3，为本发明实施例提供的数据聚类系统的结构。为了便于说明，仅示出了与本发明实施例相关的部分。所述数据聚类系统包括：输入模块101、选择模块102、距离计算模块103、分配模块104、类中心计算模块105、以及循环控制模块106。所述数据聚类系统可以是内置于数据处理设备中的软件单元、硬件单元或者是软硬件结合的单元。

输入模块101，用于输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；

在本发明实施例中，假定待聚类的数据集为X＝{x₁,x₂,L,x_n}，其中 $x_i=\left[\begin{array}{c}{x}_{i,\mathrm{1,1}},x_{i,\mathrm{1,2}},L,x_{i,1,m}\\ x_{i,\mathrm{2,1}},x_{i,\mathrm{2,2}},L,x_{i,2,m}\\ L\\ x_{i,r,1},x_{i,r,2},L,x_{i,r,m}\end{array}\right]$ 是第i个由m个属性，r个明细记录描述的对象，我们将x_i称为一个块数据对象。k是期望的类别数。

选择模块102，用于从所述数据集中选择k个块数据对象作为初始类中心；

在本发明实施例中，选择模块102，具体用于从数据集X中随机选出k个块对象作为初始类中心。

距离计算模块103，用于计算各个对象到所述初始类中心的距离；

分配模块104，用于根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；

在本发明实施例中，对象之间的距离取决于对象属性值之间的差异性，对于块数据对象之间的距离采用公式

进行度量，其中x,y表示两个块数据对象，A_i,B_i分别表示两个对象在i个属性下的域值，m为描述对象的特征数或属性数。

类中心计算模块105，用于计算各个类的中心作为新的类中心；

在本发明实施例中，首先通过计算该类中所有对象明细数的均值作为该类的类中心要包含的记录数r；然后统计每一维域值中每一个元素在该类中不同对象中出现的频率，如果域值的个数大于r，则选取频率最高的前r个值作为该维的代表，反之，按照频率由高到低的顺序反复取域值，直到取够r个值；重复上述步骤，得到m列个代表，构成该类的类中心。

循环控制模块106，用于控制重复执行分配对象和计算类中心的步骤，直至算法收敛，获得数据集的划分结果。

在本发明实施例中，通过计算前后类中心的距离，如果二者的距离小于一个给定的阈值，则算法结束。

综上所述，本发明实施例通过迭代过程把数据集划分为不同类别，使得评价聚类性能的准则函数达到最优。首先从数据集中随机选择k（期望的类别数）个块数据对象作为初始类中心；然后按照块数据之间的距离描述，计算数据集中的每一个块对象到初始类中心之间的距离，将每个块对象分配到离其最近的中心，形成k个类；通过容斥原理计算每个类的中心作为新的类中心；重复分配对象和计算类中心的步骤，直至算法收敛。本发明实施例能够快速地对现实世界中广泛存在的块数据进行聚类，是一种既高效又实用的划分聚类方法。本发明实施例可以直接对具有块特性的数据进行处理，而不需要对块数据进行压缩处理，避免了信息的丢失，得到的聚类结果比对块数据压缩后的聚类效果更佳。另外，本发明实施例还能够处理大规模数据。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，所述的存储介质，如ROM/RAM、磁盘、光盘等。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (8)

1.一种数据聚类方法，其特征在于，所述方法包括以下步骤：

输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；

从所述数据集中选择k个块数据对象作为初始类中心；

计算各个对象到所述初始类中心的距离；

根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；

计算各个类的中心作为新的类中心；

重复执行所述根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类的步骤；以及所述计算各个类的中心作为新的类中心的步骤，直至算法收敛，获得数据集的划分结果。

2.如权利要求1所述的方法，其特征在于，假定待聚类的数据集为X＝{x₁,x₂,L,x_n}，其中 $x_i=\left[\begin{array}{c}{x}_{i,\mathrm{1,1}},x_{i,\mathrm{1,2}},L,x_{i,1,m}\\ x_{i,\mathrm{2,1}},x_{i,\mathrm{2,2}},L,x_{i,2,m}\\ L\\ x_{i,r,1},x_{i,r,2},L,x_{i,r,m}\end{array}\right]$ 是第i个由m个属性，r个明细记录描述的对象，将x_i称为一个块数据对象；k是期望的类别数。

3.如权利要求1所述的方法，其特征在于，从所述数据集中选择k个块数据对象作为初始类中心的步骤，具体为：从数据集X中随机选出k个块对象作为初始类中心。

4.如权利要求1所述的方法，其特征在于，对象之间的距离取决于对象属性值之间的差异性，对于块数据对象之间的距离采用公式

进行度量，其中x,y表示两个块数据对象，A_i,B_i分别表示两个对象在i个属性下的域值，m为描述对象的特征数或属性数。

5.如权利要求1所述的方法，其特征在于，首先通过计算该类中所有对象明细数的均值作为该类的类中心要包含的记录数r；然后统计每一维域值中每一个元素在该类中不同对象中出现的频率，如果域值的个数大于r，则选取频率最高的前r个值作为该维的代表，反之，按照频率由高到低的顺序反复取域值，直到取够r个值；重复上述步骤，得到m列个代表，构成该类的类中心。

6.一种数据聚类系统，其特征在于，所述系统包括：

输入模块，用于输入需要聚类的具有块数据特征的n个对象组成的数据集和期望的类别数k；

选择模块，用于从所述数据集中选择k个块数据对象作为初始类中心；

距离计算模块，用于计算各个对象到所述初始类中心的距离；

分配模块，用于根据计算出的距离，将每一个块数据对象分配到离其最近的中心，形成k个不相交的类；

类中心计算模块，用于计算各个类的中心作为新的类中心；

循环控制模块，用于控制重复执行分配对象和计算类中心的步骤，直至算法收敛，获得数据集的划分结果。

7.如权利要求6所述的系统，其特征在于，选择模块，具体用于从数据集X中随机选出k个块对象作为初始类中心。

8.一种包括权利要求6或7任一项所述的系统的数据处理设备。

Images