论文部分内容阅读
摘要：数据库聚类的一个关键问题是数据库中存储数据的格式与聚类算法所要求的输入数据格式之间的差异，为了弥补这一差异，提出基于模块单元的数据表示方法，该方法能够有效提高数据库的聚类能力。
关键词：数据库聚类；模块单元；数据挖掘；相似性度量
中图分类号：TP311文献标识码：A 文章编号：1009-3044(2007)17-31334-02
Research of Database Clustering Method Based on Modular Units
XU Tian-bing,FENG Da-li
(Department of Computer Information Engineering, Shandong University of Finance, Jinan 250014,China)
Abstract:One critical problem of database clustering is the data model discrepancy between the representation format used to store the target data and the input data format that clustering algorithms expect. Proposes a data representation format that relies on modular units to solve the problem. This method can enhance the database clustering.
Key words:Database clustering; Modular units; Data mining; Similarity measures
1 引言
随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。数据挖掘,也称之为数据库中的知识发现,是从大量的不完全的,有噪声的,模糊的或者随机的数据中提取人们事先不知道的但又是有用的信息和知识的过程[1]。目前,数据挖掘技术已经成为从数据库中提取和分析有用知识的强有力工具。
聚类方法是一种常用的数据挖掘技术，聚类方法在数据库中的应用是一个新的研究热点。对数据库中的数据对象进行聚类，是把数据库中的对象分成子类，使同一类中的对象很相似，不同类中的对象相差很远。然而，传统的聚类算法不能很好地适用于数据库，因为数据库中包含的是结构化的和有关联的数据，数据的存储格式和聚类算法需要的数据输入格式之间存在着很大的差异。现有的数据库聚类方法是采用数据集合的转化方法，其特点是把结构化的数据集合转化为单一的数据文件，传统的聚类工具作用在单一的数据文件上产生聚类结果，但是这种方法会造成数据库中大量有用数据的丢失，同时，对聚类结果的分析也存在着很大的困难。
2 数据库聚类
2.1 数据库聚类的步骤
经过对数据库聚类方法的深入研究，我们归纳出数据库聚类过程可以由以下七个步骤组成：
1）定义对象视图
2）选择相关属性
3）为聚类工具产生合适的输入格式
4）定义相似性度量
5）为聚类算法设定参数
6）运行聚类算法
7）分析得到的聚类结果
以上步骤中，前三步用于对数据库中的数据进行预处理，产生能够适用于聚类算法的数据集合，第四步对于聚类对象定义相似性度量，第5-7步运行聚类算法，得到聚类结果。
2.2 数据库聚类方法的特点
数据集合能以多种形式存储，例如存储在文件、关系数据库、面向对象数据库等。在传统数据分析领域，文件是最简单的常用数据存储格式，在文件中，数据对象（如记录）是通过n维向量来表示的，每个向量代表一个对象，一个对象有n个属性，每个属性有单一的值。目前几乎所有的数据挖掘工具，像聚类工具、归纳工具、统计工具等，都是针对文件格式的数据集合进行分析[2]。
由于数据库的结构比文件结构复杂得多，数据库聚类面临许多特殊问题，这些问题主要包括：
数据库中的对象属于不同类型，因此首先要定义数据库中需要聚类的对象。
数据库中的对象具有一对一、一对多、多对多三种对应关系。
由于对象的属性可能有多个值，对象之间相似性的定义比较困难。
由于对象的属性具有不同的类型，属性之间相似性度量方法的选择比较复杂。
2.3 数据库聚类的对象视图
为了说明数据库聚类的特殊性，我们以一个关系数据库为例，这个关系数据库包含有顾客和购买行为两个数据表，如表1所示，表中带下划线的属性是关键字。在把聚类算法应用在数据库之前，我们要首先确定数据库中的哪类对象需要聚类，当聚类对象确定下来后，下一步就要提取聚类对象的相关属性，由此可以得到聚类对象的对象视图。
表1（a） 顾客信息
表1（b） 购买行为
表2 顾客信息与购买行为连接而成的单值属性数据集合
表3 顾客信息与购买行为连接而成的多值属性数据集合
通常一个关系数据库中包含有多个关系，两个关系之间可以有一对一、一对多和多对多三种对应关系。在表1的数据库中，如果想对（a）数据集合中的“顾客”对象进行聚类，只使用顾客信息表是不够的，因为顾客的许多特性是在购买行为表中体现出来的，顾客信息表与购买行为表之间是一对多的关系。在对“顾客”聚类之前，先要从表1的数据库中提取每个顾客对象的相关信息，提取出来的信息存放在我们称之为“对象视图”的数据结构中，如表3所示。在对象视图中，根据顾客编号，把顾客关系和购买行为关系中的相关元组集成在一个顾客对象上，这里，商品代码、付款方式和付款金额称为顾客关系的关联属性，因为这些属性是从购买行为关系中得到的。
如果两个关系是一对多的，那么这两个关系形成的对象视图通常包含多值属性，多值属性值可以用{}括起来[3]。在表3中，属性“付款金额”有三个值：{400，70，200}，分别表示顾客“张刚”三次购买活动的金额。传统关系中的属性是单值的，如表1和表2所示。大多数用于单值属性的相似性度量方法不能处理多值属性，例如，我们很难计算两个对象“李新红” 的多值属性“付款金额={390，100}”和“赵万军”的多值属性“付款金额=30”之间的相似性度量。有两种常用的解决方法，一种方法是把多值属性值用某个函数计算（如求和、求平均、计数等），形成一个单一值，但这种方法只适用数值型属性，不适合非数值型属性（如“付款方式”属性）；另一种方法是通过“顾客编号”属性把顾客表和购买活动表连接起来，形成一个单值属性数据集合，如表2所示，这种方法的缺陷是，聚类算法把数据集合中的每个元组作为一个单独的对象进行处理，在表2中，“张刚”的三次购买行为分割成三个不同的对象，这样就不是聚类四个顾客，而是聚类七次购买行为，得到的结果和我们的聚类目标相差很大。
3 基于模块单元的数据表示
数据库聚类的主要问题是数据存储格式和聚类算法所要求的数据输入格式的不一致，在数据库中，相关数据可能存放在多个数据表中，数据表之间可以有一对一、一对多、多对多的对应关系，而传统聚类算法认为输入数据是存放在单个文件中。为了弥补二者的差距，我们提出一种基于模块单元的数据表示方法。
定义1 在关系数据模型中，与一个特定对象相关联的元组集合称为模块单元。
关系数据模型中对象的聚类特性可以由模块单元来刻画，对于表1的关系模型，如果对“顾客”对象进行聚类，假定我们感兴趣的信息是顾客的性别和年龄、在不同商品上的付款金额、日付款总额，通过这些信息来确定不同顾客对象之间的相似性。根据元组集合，可以定义三个模块单元来描述每个顾客对象的特征：{性别，年龄}、{商品名称，金额}、{日付款总额，日期}，见图1所示。“顾客编号=1”的顾客对象的特征为：男性，43岁，购买商品P1、P2、P3分别花费400、70、200元，一天内购买商品的总额为670元。
对象的聚类特性可以由模块单元来刻画，我们可以根据两个对象之间对应的模块单元的相似性度量，得到两个对象的相似性度量。
图1
如果对数据库中的对象进行聚类，采用基于模块单元的的数据表示方法，需要包含以下三种机制：
（1）对象识别机制：确定哪些对象需要聚类，这些对象如何唯一识别。在表1中，假定要对“顾客”对象聚类，由于“顾客编号”唯一识别顾客，我们把“顾客编号”作为对象识别机制。
（2）模块单元的确定机制：每个模块单元代表聚类对象的一个特征。模块单元可以用SQL语句来实现，对于图1中的模块单元，可以使用如下的SQL语句：
模块单元1= SELECT 顾客编号，性别，年龄FROM 顾客信息
模块单元2= SELECT 顾客编号，商品代码，付款金额FROM顾客信息，购买行为 WHERE 顾客信息.顾客编号=购买行为.顾客编号
模块单元3= SELECT 顾客编号，SUM（付款金额），日期FROM顾客信息，购买行为WHERE 顾客信息.顾客编号=购买行为.顾客编号 GROUDBY 顾客编号，日期
（3）相似性度量的计算机制：可以使用多种距离度量方法（如欧几里德距离）来计算两个对象之间对应模块单元的相似性度量fi，再根据公式（1）得到两个对象的相似性度量。
4 结束语
数据库聚类的一个重要问题是数据库中存储数据的格式与聚类算法所要求的输入数据格式之间的差异，数据库中的数据通常存放在多个数据表中，因此对象的属性有可能是多值的，而聚类算法的输入数据通常是单值的，运用基于模块的数据表示方法构造的数据库聚类系统较好地弥补了这一差异。实验结果表明，多值属性的聚类结果明显优于单值属性聚类结果，对多值属性聚类结果的分析也更加容易。
参考文献：
[1]Han J,Kamber M. Data Mining Concepts and Techniques[M].Morgan Kaufmann Publishers,2001.
[2]Agrawal R,Imielinski T,Swami A.Mining association rules between sets of items in large database[J].Proc.ACM SIGMOD,1993:207-216.
[3]Ryu T.W,Eick C.F. Similarity measures for multi-valued attributes for database clustering[C]. Proceedings of the Conference on SMART ENGINEERING SYSTEM DESIGN: Neural Networks, Fuzzy Logic,Evolutionary Programming, Data Mining and Rough Sets(ANNIE’98),St.Louis,MO, 1998.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：数据库聚类；模块单元；数据挖掘；相似性度量
中图分类号：TP311文献标识码：A 文章编号：1009-3044(2007)17-31334-02
Research of Database Clustering Method Based on Modular Units
XU Tian-bing,FENG Da-li
(Department of Computer Information Engineering, Shandong University of Finance, Jinan 250014,China)
Abstract:One critical problem of database clustering is the data model discrepancy between the representation format used to store the target data and the input data format that clustering algorithms expect. Proposes a data representation format that relies on modular units to solve the problem. This method can enhance the database clustering.
Key words:Database clustering; Modular units; Data mining; Similarity measures
1 引言
随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。数据挖掘,也称之为数据库中的知识发现,是从大量的不完全的,有噪声的,模糊的或者随机的数据中提取人们事先不知道的但又是有用的信息和知识的过程[1]。目前,数据挖掘技术已经成为从数据库中提取和分析有用知识的强有力工具。
聚类方法是一种常用的数据挖掘技术，聚类方法在数据库中的应用是一个新的研究热点。对数据库中的数据对象进行聚类，是把数据库中的对象分成子类，使同一类中的对象很相似，不同类中的对象相差很远。然而，传统的聚类算法不能很好地适用于数据库，因为数据库中包含的是结构化的和有关联的数据，数据的存储格式和聚类算法需要的数据输入格式之间存在着很大的差异。现有的数据库聚类方法是采用数据集合的转化方法，其特点是把结构化的数据集合转化为单一的数据文件，传统的聚类工具作用在单一的数据文件上产生聚类结果，但是这种方法会造成数据库中大量有用数据的丢失，同时，对聚类结果的分析也存在着很大的困难。
2 数据库聚类
2.1 数据库聚类的步骤
经过对数据库聚类方法的深入研究，我们归纳出数据库聚类过程可以由以下七个步骤组成：
1）定义对象视图
2）选择相关属性
3）为聚类工具产生合适的输入格式
4）定义相似性度量
5）为聚类算法设定参数
6）运行聚类算法
7）分析得到的聚类结果
以上步骤中，前三步用于对数据库中的数据进行预处理，产生能够适用于聚类算法的数据集合，第四步对于聚类对象定义相似性度量，第5-7步运行聚类算法，得到聚类结果。
2.2 数据库聚类方法的特点
数据集合能以多种形式存储，例如存储在文件、关系数据库、面向对象数据库等。在传统数据分析领域，文件是最简单的常用数据存储格式，在文件中，数据对象（如记录）是通过n维向量来表示的，每个向量代表一个对象，一个对象有n个属性，每个属性有单一的值。目前几乎所有的数据挖掘工具，像聚类工具、归纳工具、统计工具等，都是针对文件格式的数据集合进行分析[2]。
由于数据库的结构比文件结构复杂得多，数据库聚类面临许多特殊问题，这些问题主要包括：
数据库中的对象属于不同类型，因此首先要定义数据库中需要聚类的对象。
数据库中的对象具有一对一、一对多、多对多三种对应关系。
由于对象的属性可能有多个值，对象之间相似性的定义比较困难。
由于对象的属性具有不同的类型，属性之间相似性度量方法的选择比较复杂。
2.3 数据库聚类的对象视图
为了说明数据库聚类的特殊性，我们以一个关系数据库为例，这个关系数据库包含有顾客和购买行为两个数据表，如表1所示，表中带下划线的属性是关键字。在把聚类算法应用在数据库之前，我们要首先确定数据库中的哪类对象需要聚类，当聚类对象确定下来后，下一步就要提取聚类对象的相关属性，由此可以得到聚类对象的对象视图。
表1（a） 顾客信息
表1（b） 购买行为
表2 顾客信息与购买行为连接而成的单值属性数据集合
表3 顾客信息与购买行为连接而成的多值属性数据集合
通常一个关系数据库中包含有多个关系，两个关系之间可以有一对一、一对多和多对多三种对应关系。在表1的数据库中，如果想对（a）数据集合中的“顾客”对象进行聚类，只使用顾客信息表是不够的，因为顾客的许多特性是在购买行为表中体现出来的，顾客信息表与购买行为表之间是一对多的关系。在对“顾客”聚类之前，先要从表1的数据库中提取每个顾客对象的相关信息，提取出来的信息存放在我们称之为“对象视图”的数据结构中，如表3所示。在对象视图中，根据顾客编号，把顾客关系和购买行为关系中的相关元组集成在一个顾客对象上，这里，商品代码、付款方式和付款金额称为顾客关系的关联属性，因为这些属性是从购买行为关系中得到的。
如果两个关系是一对多的，那么这两个关系形成的对象视图通常包含多值属性，多值属性值可以用{}括起来[3]。在表3中，属性“付款金额”有三个值：{400，70，200}，分别表示顾客“张刚”三次购买活动的金额。传统关系中的属性是单值的，如表1和表2所示。大多数用于单值属性的相似性度量方法不能处理多值属性，例如，我们很难计算两个对象“李新红” 的多值属性“付款金额={390，100}”和“赵万军”的多值属性“付款金额=30”之间的相似性度量。有两种常用的解决方法，一种方法是把多值属性值用某个函数计算（如求和、求平均、计数等），形成一个单一值，但这种方法只适用数值型属性，不适合非数值型属性（如“付款方式”属性）；另一种方法是通过“顾客编号”属性把顾客表和购买活动表连接起来，形成一个单值属性数据集合，如表2所示，这种方法的缺陷是，聚类算法把数据集合中的每个元组作为一个单独的对象进行处理，在表2中，“张刚”的三次购买行为分割成三个不同的对象，这样就不是聚类四个顾客，而是聚类七次购买行为，得到的结果和我们的聚类目标相差很大。
3 基于模块单元的数据表示
数据库聚类的主要问题是数据存储格式和聚类算法所要求的数据输入格式的不一致，在数据库中，相关数据可能存放在多个数据表中，数据表之间可以有一对一、一对多、多对多的对应关系，而传统聚类算法认为输入数据是存放在单个文件中。为了弥补二者的差距，我们提出一种基于模块单元的数据表示方法。
定义1 在关系数据模型中，与一个特定对象相关联的元组集合称为模块单元。
关系数据模型中对象的聚类特性可以由模块单元来刻画，对于表1的关系模型，如果对“顾客”对象进行聚类，假定我们感兴趣的信息是顾客的性别和年龄、在不同商品上的付款金额、日付款总额，通过这些信息来确定不同顾客对象之间的相似性。根据元组集合，可以定义三个模块单元来描述每个顾客对象的特征：{性别，年龄}、{商品名称，金额}、{日付款总额，日期}，见图1所示。“顾客编号=1”的顾客对象的特征为：男性，43岁，购买商品P1、P2、P3分别花费400、70、200元，一天内购买商品的总额为670元。
对象的聚类特性可以由模块单元来刻画，我们可以根据两个对象之间对应的模块单元的相似性度量，得到两个对象的相似性度量。
图1
如果对数据库中的对象进行聚类，采用基于模块单元的的数据表示方法，需要包含以下三种机制：
（1）对象识别机制：确定哪些对象需要聚类，这些对象如何唯一识别。在表1中，假定要对“顾客”对象聚类，由于“顾客编号”唯一识别顾客，我们把“顾客编号”作为对象识别机制。
（2）模块单元的确定机制：每个模块单元代表聚类对象的一个特征。模块单元可以用SQL语句来实现，对于图1中的模块单元，可以使用如下的SQL语句：
模块单元1= SELECT 顾客编号，性别，年龄FROM 顾客信息
模块单元2= SELECT 顾客编号，商品代码，付款金额FROM顾客信息，购买行为 WHERE 顾客信息.顾客编号=购买行为.顾客编号
模块单元3= SELECT 顾客编号，SUM（付款金额），日期FROM顾客信息，购买行为WHERE 顾客信息.顾客编号=购买行为.顾客编号 GROUDBY 顾客编号，日期
（3）相似性度量的计算机制：可以使用多种距离度量方法（如欧几里德距离）来计算两个对象之间对应模块单元的相似性度量fi，再根据公式（1）得到两个对象的相似性度量。
4 结束语
数据库聚类的一个重要问题是数据库中存储数据的格式与聚类算法所要求的输入数据格式之间的差异，数据库中的数据通常存放在多个数据表中，因此对象的属性有可能是多值的，而聚类算法的输入数据通常是单值的，运用基于模块的数据表示方法构造的数据库聚类系统较好地弥补了这一差异。实验结果表明，多值属性的聚类结果明显优于单值属性聚类结果，对多值属性聚类结果的分析也更加容易。
参考文献：
[1]Han J,Kamber M. Data Mining Concepts and Techniques[M].Morgan Kaufmann Publishers,2001.
[2]Agrawal R,Imielinski T,Swami A.Mining association rules between sets of items in large database[J].Proc.ACM SIGMOD,1993:207-216.
[3]Ryu T.W,Eick C.F. Similarity measures for multi-valued attributes for database clustering[C]. Proceedings of the Conference on SMART ENGINEERING SYSTEM DESIGN: Neural Networks, Fuzzy Logic,Evolutionary Programming, Data Mining and Rough Sets(ANNIE’98),St.Louis,MO, 1998.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。