数据集划分

数据集划分（精选三篇）

数据集划分 篇1

网格工作流可分为抽象网格工作流和具体网格工作流两个生成阶段[1]。在抽象网格工作流阶段,使用工作流语言形式化描述工作流过程,根据节点所提供的服务定义业务的操作过程和状态转移关系,将业务过程转化为服务的有向图形式,实现网格服务与图形节点的映射[7]。即一个图形节点就是一个完成特定功能的网格服务,形成抽象的网格工作流。在网格工作流的具体生成阶段,实现抽象的网格工作流与物理的网格资源的绑定,根据所定义的资源调度策略以及资源的状态,由工作流引擎调度器,生成可执行的具体网格工作流。由于网格的动态性等特点,使用工作流语言形式化描述工作流工程的方式更能满足用户的需求[8,9,10]。

由于网格超强的数据处理能力,网格工作流通常被用于处理复杂的、海量的数据集合[11]。而在数据的具体处理过程中,网格中的某个节点通常仅需整个数据集中一个很小的数据子集。如果对每个网格节点传递整个数据集,不只是增加了数据传输的负担,同时也降低了网格节点的处理速度和灵活性。因此,在网格工作流中,如何控制网格节点数据集的划分已经成为一个研究热点。

Thomas F等在提出抽象网格工作流语言(Abstract Grid Workflw Language,AGWL)后,也探讨了其中的数据集划分方法,但其所提供的方法,都是一种定性的数据集划分,仅是通过定性的块间冗余度,处理数据子集之间的相关性,而并没有基于数据子集间的相关性再继续进行探讨,没有给出基于数据子集相关性的数据集划分。笔者在分析AGWL已有数据集划分方法的基础上,提出一种采用矩阵的形式、考虑数据子集相关性的灵活性的数据集划分方法。

1 AGWL数据集划分方法

AGWL是一种基于XML的语言,由活动、控制流、数据流以及属性和约束条件组成[12,13]。Qin J和Thomas F在其提出的抽象网格工作流语言之上,定义了一套数据集约束,将数据集按照一定的原则,分配到网格节点,提高数据集处理速度的同时,也提高了效率[14],但在数据集的划分时,是一种定性大小的块划分,在涉及到数据集间的相关性时,只是通过一定的块间数据的冗余度方式加以实现,并没有基于相关性给出更深入的讨论。

AGWL提供了两种数据集划分约束规则,element-index和distribution。其中element-index是逗号分隔的冒号表达式,其语法如下:

其中e表示元素索引,c是一个冒号表达式,s1、s2、s3分别为开始索引、结束索引、移动步幅。

distribution表示数据集分组,分组后的各数据子集被传递到各处理节点执行。Qin J和Thomas F已经提出了BLOCK (平均分配)、BLOCK(S)(每个节点分配S个数据子集)、BLOCK(S,L)(每个节点分配S个数据子集,其中L为数据子集的冗余度,表示该节点复制了上一个节点最后的L个数据子集)[14]。但Thomas F等所提供的平均划分以及其他几个划分方法中,都只是一种定性的数据集划分,当把一个数据集划分为多个数据子集时,各数据子集间可能存在依赖关系,而这种定性划分,并不能很好地根据各子数据集的数据依赖关系有效地给出划分方案。针对这一状况,笔者提出了一种基于数据子集相关性的数据集划分方法。采用矩阵的形式,用矩阵值表征数据子集的相关性,通过讨论矩阵的变化,研究数据集的划分。

2 基于矩阵的数据集划分

假设将一个数据集C划分为两个相等的子数据集,处理一个子数据集所需要的时间设为t1,则处理由两个子数据集合成的数据集所需要的时间近似认为是2t1。现假设,分配到不动节点中的子数据集可以并行处理,且存在数据传递,假设一次数据传递所需要的时间为t2,则完成两个子数据集处理所需要的时间为t1+num×t2 (num为产生数据传递的次数)。

如果t1+num×t2>2t1,即数据集划分后处理所需要的时间比划分前所需要的时间还长,则数据集C不需要划分为两个子数据集。对上式变形可得num>t1/t2,设Level=[t1/t2]。

现在分析假设将一个数据集C初步平均划分为N个子数据集,根据数据集C逻辑上相邻依次标记为1,2,3,…,N(图1)。子数据集的划分数N应该尽量大,如果对数据集的划分数过小,则导致最后合并后的划分不是有效的划分。

假设一个子数据集i和另一个子数据集j产生一次数据传递需要一个单位时间。为了进一步说明划分方法,给出以下定义:

定义1数据集划分可以定义为一个加权无向图G(V,E),V=N(即节点数),E=m(即无向图中边的个数)。V是子数据集节点的集合,E是子数据集间产生的数据传递的集合。对于每条边vi都赋予权值wi,wi表示两个节点i,j产生的数据传递的次数。即,如果子数据集i和子数据集j产生了一次数据传递,就将wi赋予权值1,发生了两次数据传递,就将权值赋值为2,依此类推。如果无数据传递,则将权值赋为0。

定义2相邻节点。相邻节点是指数据集划分时候的相邻,而并非无向图上的相邻,如i与i-1或i+1互为相邻节点,可通过顶点的标号加以识别。

根据以上两个定义,一个数据集划分为N个子集的加权无向图及其权值矩阵如图2所示。

节点相互归并,即相邻的子数据集合并,规则:如果相邻节点变的权值大于或等于Level,即该两个数据子集划分后处理所需要的时间比合并在一起处理所需要的时间还长,则这两个节点应该合并为一个节点(因为这两个节点相对于数据集C来说,在逻辑上相邻的),现假设边(i,i+1)的权值大于阀值Level,即应该将顶点i和顶点i+1合并为一个新的顶点i。在此过程中,则应考虑与顶点i或顶点i+1有边的其他顶点k该如何处理,可能出现以下情况:

a.图2中的顶点k与顶点i有权值为w1的边,与顶点i+1的边的权值为0,即顶点k与顶点i发生了w1次通信,与顶点i+1无通信,则归并后,顶点k与新的顶点i的通信应该为w1,即新顶点i与顶点k边的权值为w1;

b.图2中的顶点k与顶点i的边的权值为0,与顶点i+1的边的权值为w2,即顶点k与顶点i无通信,与顶点i+1发生了w2次通信,则归并后,顶点k与新的顶点i的通信应该为w2,即新顶点i与顶点k的边权值为w2;

c.图2中的顶点k与顶点i的边的权值为w1,与顶点i+1的边的权值为w2,即顶点k与顶点i发生了w1次通信,与顶点i+1发生了w2次通信,则归并后,顶点k与新的顶点i的通信应该为w1+w2次,即新的顶点i与顶点k的边的权值为w1+w2。

按以上方法,将逻辑上相邻的节点,根据其权值进行归并,直到无法再继续归并为止,即图中无相邻节点权值大于阀值Level。

如图2所示的无向图,现假设顶点i与顶点i+1的边的权值A>Level,即应该将顶点i+1与顶点i归并,归并为新的顶点i。归并后的新无向图及其相对应的矩阵如图3所示。

所得新矩阵,是将原矩阵的第i+1行与第i行相加,然后将第i+1行赋值为0,表示该行已经归并,实现顶点i+1与顶点i的归并。此时,第i+2行与第i行变为了相邻节点。则继续重复以上过程,进行节点归并。完成数据集的划分。

为了提高算法的收敛速度,在算法的实际执行过程中,设置了一个存储节点归并的标志位下标数组Index[N],初始值全为1,如果节点i、i+1进行了合并,则将Index[i+1]的值置0,这样查找矩阵的相邻节点,就变成了查找Index数组中的相邻值为1的下标。以小的下标为矩阵的行坐标,大的下标为矩阵的列坐标,然后将对应的矩阵权值与设定阈值进行判断比较,决定两个节点是否合并。提高了算法的收敛速度和算法的效率。

对于该算法的结果可能有以下几种情况需要讨论:

a.输出可能为一个单一的节点,即数据集划分后,各数据子集出现了大量的数据交互,数据集的相关性比较强,又重新被合并为一个数据集,在此情况下,可采用同子网下直接互联的高性能计算机平行处理,提高数据的处理效率;

b.输出为N个节点,并且其对应的权值为0,即数据集划分后,各子数据集间没有出现数据的相互交互,即数据基本不相关,因此,可以不受网格所处环境的限制,充分利用网格资源提高数据处理的效率;

c.输出为m(m

通过数据集的划分,根据网格节点的处理能力和子集间的数据关联关系,充分利用了网格的协作能力,提高了数据的处理效率。

3 结束语

数据挖掘中客户的特征化及其划分 篇2

关键词：客户关系管理,数据挖掘,聚类分析

一、引言

在激烈的市场竞争中, 客户关系管理 (Customer Relationship Management) 逐渐成为各企业关注的焦点。一个成熟的CRM系统要能够有效地获取客户的各种信息, 识别客户与企业间的关系及所有交互操作, 寻找其中的规律, 为客户提供个性化的服务, 为企业决策提供支持。

在企业与客户的交互操作中, “二八原则”是值得借鉴的, 即2 0%的客户对企业做出8 0%的利润贡献。但究竟谁是那2 0%的客户?又如何确定特定消费群体的消费习惯与消费倾向, 进而推断出相应消费群体或个体下一步的消费行为?这都是企业需要认真研究的问题。

二、客户的特征化及其划分

企业认识客户和潜在客户是在市场保持竞争力的关键。特征分析是了解客户和潜在客户的极好方法, 包括对感兴趣对象范围进行一般特征的度量。一旦知道带来最大利润客户的特征和行为, 就可以直接将其应用到寻找潜在客户之中。有效寻找客户, 认识哪些人群像自己的客户。因此, 在争取客户的活动中, 对感兴趣对象进行特征化及其划分是很有意义的。

对客户的特征化, 顾名思义就是用数据来描述或给出客户 (潜在客户) 特征的活动。特征化可以在数据库 (或数据库的不同部分) 上进行。这些不同部分也称为划分, 通常他们互不包含。

划分分析 (Segmentation Analysis) 通常用于根据利润和市场潜力划分客户。如:零售商按客户在所有零售商店的总体购买行为, 将客户划分为若干描述他们各自购买行为的区域, 这样零售商可以评估哪些客户有最大利润。划分是把数据库分成互不相交部分或分区的活动。一般有两种方法:市场驱动法和数据驱动法。市场驱动法需要决定那些对业务有重要影响的特征, 即需要预先选择一些特征变量 (属性) , 以最终定义得到划分。数据驱动法是利用数据挖掘中的聚类技术或要素分析技术寻找同质群体。

三、数据挖掘的概念

数据挖掘 (Data Mining) 是从大型数据库或数据仓库中提取人们感兴趣的知识, 这些知识是隐含的、事先未知的潜在有用信息。通过数据挖掘提取的知识表示为概念、规则、规律、模式等, 它对企业的趋势预测和行为决策提供支持。

1. 分类分析

分类是指将数据映射到预先定义好的群组或类。分类要求基于数据属性值来定义类别, 通过数据特征来描述类别。根据它与预先定义好的类别相似度, 划分到某一类中去。分类的主要应用是导出数据的分类模型, 然后使用模型预测。

2. 聚类分析

聚类是对抽象样本集合分组的过程。与分类不同之处在于聚类操作要划分的类是事先未知。按照同一类中对象之间较高相似度原则进行划分, 目的是使同一类别个体之间距离尽可能小, 不同类别中个体间距离尽可能大。类的形成是由数据驱动的。

3. 关联规则

关联规则是从大量的数据中挖掘出有价值的描述数据项之间相互关联的知识。关联规则中有两个重要概念:支持度 (Support) 和信任度 (Confidence) 。它们是两个度量有关规则的方法, 描述了被挖掘出规则的有用性和确定性。关联规则挖掘, 希望发现事务数据库中数据项之间的关联, 这些规则往往能反映客户的购买行为模式。

4. 时间序列分析

时间序列分析是通过对过去历史行为的客观记录分析, 揭示其内在的规律, 预测未来行为。它旨在从大量的时间序列中提取人们事先不知道的, 但又是潜在有用的、与时间属性相关的信息和知识。

5. 孤立点分析

数据库中包含那些不符合大多数数据对象所构成规律 (模型) 的数据对象, 称为孤立点。对孤立点挖掘分析可以处理一些特殊事件。

6. 回归分析

在掌握大量观察数据的基础上, 利用数理统计方法, 建立因变量与自变量之间的回归关系函数。回归分析法是定量预测方法之一, 它依据事物内部因素变化的因果关系来预测事物的发展趋势。

四、数据挖掘在C R M中的应用

1. 对客户的相关属性分析

(1) 挖掘客户的特性

DM的第一步就是识别客户群, 挖掘客户特性, 如:了解客户地址、年龄、性别、收入、教育程度、爱好等基本信息, 还有健康、嗜好、配偶、家庭环境等特征信息, 发现其行为规律, 制定吸引客户的策略。

运用分类与聚类方法, 从客户基本库中发现不同的客户群, 用购买模式刻画不同客户群的特征, 针对不同类型的客户, 提供个性化的服务。

(2) 客户行为分析

(1) 客户满意度

客户满意度分析是对其产品或服务的消费经验总体评价, 应用数据挖掘分析方法可以从零散客户反馈的信息中, 分析客户的满意度, 找出客户不满意原因。

(2) 客户忠诚度

客户忠诚度是指客户愿意继续购买该企业产品或服务的倾向。以客户的购买倾向为度, 对客户数据分析, 对高忠诚度的客户继续保持, 对低忠诚度的客户要下功夫将其培养成高忠诚度客户。利用分类、聚类方法将客户分为不同客户群, 并从中确定那2 0%的对企业有8 0%贡献率的最有价值的客户群, 对不同价值贡献率客户采取不同策略和措施。

(3) 客户保持

保持客户的同时不断挖掘潜在客户, 是企业持续发展的重要手段。通过数据挖掘的决策树、神经网络等方法建立预测模型, 识别潜在客户。还可以通过客户盈利能力分析, 帮助企业制定市场策略, 留住有价值的客户, 开发潜在客户。用聚类 (分类) 和关联分析, 发现有价值稳定的客户群, 有价值易流失的客户群, 低价值稳定的客户群和低价值不稳定的客户群, 采取不同的服务 (推销) 和价格策略稳定有价值客户, 转化低价值客户。

(4) 客户跟踪服务

对客户的变动要及时跟踪分析客户变动原因, 防止客户群体的流失, 指导企业合理配置资源, 为客户提供“一对一”个性化服务, 以抓住现有客户并吸引潜在客户。

(5) 客户生命周期价值

基于客户生活方式和购买行为建立客户分群, 计算不同客户分群的生命周期价值, 设计差异化的沟通策略。分析客户不同时期收入、成本、风险, 利用价值理论公式得出客户的价值并提供预测。数据挖掘技术分析和预测不同市场活动情况下客户盈利能力的变化, 帮助企业制定市场策略。

(6) 交叉销售

分析客户消费记录, 发现潜在交叉购买需求, 选择最合适的交叉销售形式。数据挖掘可寻找那些影响客户购买行为的因素, 挖掘隐藏在数据间的表面看似独立事件间的相互关系。如发现“90%的顾客在一次购买活动中购买A商品的同时购买B商品”之类的知识, 展开交叉营销。

(7) 异常分析

异常事件在商业领域中往往具有显著价值, 如:金融欺诈、客户流失等。通过数据挖掘中的偏差分析可以迅速准确地找到异常事件, 制定相应的营销策略。客户流失是异常情况之一, 根据以前的客户流失数据, 包括:客户属性、服务属性、消费属性与流失可能性关联的数学模型, 找出客户流失原因, 建立预测模型推测现有客户的流失情况。

2. 市场分析

预测不同区域消费者对不同产品的消费趋势、季节变化、非规则变化等。采用时序分析方法, 对基于时间序列销售数据进行趋势分析, 预测市场的趋势变化、循环变化、季节性变化、非规则或随机变化。通过对客户关系管理系统分析, 可有效地指导企业在市场、销售、服务等方面将资源分配给有价值的客户, 掌握客户的行为模式, 以应对各种客户行为以及市场变化。

3. 市场划分方法

依据客户消费习惯、收入、偏好、购买频率等因素将客户分类, 使同一细分市场里的客户具有相似偏好和需求。在市场划分前, 先做好如下工作:定义业务目标, 构建市场划分团队, 检查和评估数据需求, 选择恰当的分析层次, 在客户群体中选择好用于分析的样本, 从指定的数据源为样本抽取数据, 清理数据, 然后选择恰当的划分方法。

(1) 预定义划分方法

分析人员根据已有经验分析市场, 分析各个变量和数据, 然后决定划分市场。使用不活跃交易群体, 可能流失客户群体和潜在信用使用群体等进行市场划分。恰当的市场划分取决于商业目标和对客户的了解程度。

(2) 统计划分方法

在客户划分数目太多或对目标群体不是很了解时采用, 这种方法是利用各种数据统计技术划分客户。开展新客户工作或对当前客户所知甚少时, 采用此方法。

(3) 复合划分方法

综合采用预定义划分和统计划分方法, 具体采用何种顺序取决于对客户群体的了解。综合使用两种方法能够敏锐地洞察客户群体。

应用合适的划分方法, 需要看划分效果如何?看这样划分与业务目标是否相关, 是否可理解和容易特征化。这种评估分析可以通过定性和定量两个步骤, 分析的内容主要是判断同一个划分内的客户是否类似 (特征、频度分布) , 每个客户划分是否与其他客户划分都不相同, 每个客户划分是否都有与之对应的面向业务目标与策略。

对潜在客户的挖掘, 往往是在“信息不对称”情况下做出的决策, 这种决策不可避免带有人为因素。因为一般是利用可行 (成熟、廉价、易得) 的技术、手段来减少信息的不确定性与不对称性。这种情况下无法对客户作全面了解和测评, 所得出的结论往往带有个性化因素, 有可能漏掉部分重要客户。

4. 聚类分析以发现客户划分

聚类分析是将数据 (样本) 分割成具有相似特性的群体以实现划分。在聚类分析中, 衡量不同数据在属性上的相似性主要有两种方法:距离与相关系数。数据之间相似性的程度高低, 可以通过数据在空间分布之间的距离衡量其相似性。数据之间的相似性还可以通过在不同变量之间的关联程度来反映。相关系数主要用于衡量不同变量之间的协同程度, 即一个变量变化与另一个变量变化之间的关系。使用距离或相关系数法, 把特征上相似的观察数据值聚在一起, 试图把相异的观察数据分开, 以实现分类划分。聚类分析所形成的结果是一个聚类模型, 分析人员可根据聚类模型, 研究不同类别在各个变量上的特性, 形成一组类别划分规则。

五、结论

客户的特征化及其划分是数据挖掘最直接、最简单而有效的应用。准确掌握顾客的消费偏好改变, 对潜在客户群体建立响应模型, 适时提供客户所需要的服务与信息, 维持与掌握客户的满意度, 有效利用数据挖掘结果做决策。但数据挖掘不是万能的, 在实际应用中还要受到许多条件限制。要有足够合适的数据, 选择恰当的模型和算法, 有决策者的支持等都是有效应用数据挖掘技术的必要条件。

参考文献

[1]Olivia Parr Rud著 朱杨勇等译:数据挖掘实践[M].北京:机械工业出版社, 2003

[2]Jiawei Han, Micheline Kamber著 范明等译:数据挖掘:概念与技术[M].北京:机械工业出版社, 2001

[3]刘友军 吴 建:数据挖掘在CRM中的应用研究[J].商场现代化, 2007 (35) , 37～38

一种基于划分的混合数据聚类算法 篇3

聚类分析作为一种无监督学习方法, 是机器学习研究和数据挖掘应用中的一个重要内容。聚类分析依据“物以类聚”的思想, 根据一定的规则将数据对象划分成多个类, 使得同一类中的对象具有较高的相似度, 而不同类之间的对象差别较大。目前聚类分析已被广泛应用于图像处理、信息检索、生物信息学和社交网络分析等研究领域[1,2]。

近年来, 针对不同的应用, 研究者对聚类分析进行了一系列的研究, 提出了一些有效的聚类算法, 主要包括划分聚类、层次聚类、基于密度的聚类、基于网格的聚类和基于模型的算法[3]。然而, 已有的大多聚类算法仅仅针对数值型或分类型单一类型数据有效, 在混合型数据上将变得失效。而混合型数据在实际生活中普遍存在, 如描述人口的数据集里既有描述年龄、身高、体重的数值型属性, 也有描述民族、性别、血型的分类型属性, 因此设计一个好的混合型数据聚类算法是一个富有挑战性而又必须面对的问题。为了克服这一困难, 一些学者已经进行了深入的研究和探索。例如, 1998年, Huang等人通过把K-Means算法[4]和K-Modes算法[5]直接集成到一起, 将算法推广到K-Prototypes算法[6], 用以解决混合属性数据的聚类问题。2002年, 文献[7]中提出了一种凝聚式层次聚类算法SBAC (SimilarityBased Agglomerative Clustering) 。SBAC算法采用Goodall相似性来度量对象间和类间的相似性。其中, 相似性度量赋于分类型属性中不经常出现的属性值更大的权值。对于数值型属性, 相似性度量不仅考虑特征值的差别大小, 而且考虑值对出现的独特性。2005年, He等人在文献[8]中首先将数据值型属性和分类型属性数据进行聚类, 然后将这些聚类结果看成是分类型数据, 在其上应用分类型数据聚类算法来进行聚类并最终得到混合数据的聚类结果。在已有的混合数据聚类中, 以K-Prototypes为代表的划分式聚类由于算法的高效性、简单易实现等优点在实际应用中得到了广泛的应用。但是, K-Prototypes算法中存在数值型属性和分类型属性之间相异性度量不统一及其权重参数选择困难等问题。因此, 如何基于K-prototypes算法提出划分式的混合数据聚类算法显得尤为必要。

本文首先给出K-Prototypes算法中分类型数据类中心的多Modes表示方式, 接着把传统欧式距离扩展的混合数据用于度量对象和类之间的相异性, 进而提出了一个基于划分的混合数据聚类算法。最后通过在UCI标准数据集上进行实验验证了该算法的可行性和有效性。

1 K-Prototypes算法

K-Prototypes算法[6]是在K-Means算法的基础上利用简单匹配来度量分类型属性的相异度, 进而用来解决混合数据聚类问题。

令X={X1, X2, …, Xn}表示由n个对象组成的数据集。对象Xi (1≤i≤n) 由m个特征A1, A2, …, Ap, Ap+1, …, Am来刻画, 其中A1, A2, …, Ap为数值型属性, Ap+1, Ap+2, …, Am为分类型属性, 属性Aj的值域用Dom (Aj) 表示, 对于分类型属性有Dom (Aj) ={aj (1) , aj (2) , …, aj (nj) }, 其中nj表示属性Aj域值的个数。数据集中的对象Xi∈X可以用一个m维的向量来标记, 即Xi={xi1, xi2, …, xip, xi (p+1) , xi (p+2) , …, xim}, 其中xij∈Dom (Aj) 。聚类中心用Z表示, 相应地, 简记为Zl= (zl1, zl2, …, zlm) 。

在K-Prototypes算法中, 对象之间的相异性度量同时考虑了数值型数据和分类型数据, 并通过参数γ来控制聚类过程中数值型部分和分类型部分贡献的大小。

定义1[6]设ClX是K-Prototypes算法过程中的一个类, 其中Zl为Clh的类中心, 则对象Xi∈X与类中心Zl的距离度量由数值型和分类型两部分组成, 定义如下:

其中dr和dc分别表示对象与类中心在数值型和分类型属性刻画下的不相似度, dr表示欧式距离dc表示简单匹配不相似性度量其中

K-Prototypes算法中最小化如下目标函数:

当wli=1时表示第i个对象属于第l个类, wli=0时表示第i个对象不属于第l个类。

为了使目标函数F在给定的约束条件下达到极小值, K-Prototypes算法基本步骤如下:

Step1从数据集X中随机选取k个对象作为初始类中心;

Step2根据定义1计算对象与类中心之间的距离, 并根据最近原则将每个对象分配到离它最近的类中去;

Step3更新聚类中心, 其中数值属性部分通过计算同一类中对象的平均值得到, 分类型属性部分通过计算聚类中各属性值出现的频率高低来确定;

Step4重复以上Step2, Step3, 直到目标函数F不再发生变化为止。

2 基于划分的混合数据聚类算法

基于K-Means算法扩展的K-Prototypes算法虽然实现了混合类型数据的有效聚类, 但是在聚类过程中仍然存在一些问题。

K-Prototypes算法的聚类中心由数值属性和分类属性两部分组成, 其中数值属性部分利用同一类中各个数据的平均值表示;而分类属性部分根据各属性值出现的频率高低采取频率最高的属性值来代表类中心。然而, K-Prototypes算法中分类型数据的聚类中心采取出现频率高的属性值 (一个属性下单一Mode) 这种方式未能充分考虑到其他出现频率非最高的属性值对聚类中心的影响, 难以准确反映一个类中对象的取值情况。而且当某个属性取值频率最高的属性值多于一个时Mode将不唯一, 选择不同的Mode在计算相异性度量时可能得到完全相反的结论, 进而导致算法不稳定。

其次, 分类属性部分利用简单匹配距离 (对象与类中心相同时相异度为0;否则, 相异度为1) 来衡量对象到类中心的相异度。这种计算方法不能精确描述该对象与该类中心对应类中其他样本的相似程度, 对象是否加入一个类, 不仅要取决对象与原型的差异, 更要取决对象与类中已有对象的总体差异。而且当对象与多个类中心相异度相同时, K-Prototypes算法往往随机将此对象加入到一个类中, 不能准确地划分到相似程度更大的类中。在相异性度量集成欧式距离和简单匹配度量方面, 通过简单的累加得到混合数据的距离度量, 这种方式未能在一个统一的框架下准确地衡量数值数据部分和分类数据部分的相异性。而且在不同类型数据相异度累加时控制贡献大小的参数γ的选择在实际应用中是一个非常困难的问题。

针对K-Prototypes算法以上存在的问题, 本节首先给出一个分类型属性部分多Modes表示类中心的方式, 进一步基于分类属性的多Modes类中心的表示将传统的欧式距离扩展到混合型数据, 使得在相同框架下更加精确地反映混合数据对象与类之间的相异性。进而, 提出了一个划分式的混合数据聚类算法。

定义2设Cl表示数据集X在聚类过程中得到的一个类, 则分类型属性部分多Modes的类中心表示形式定义为:

其中, zlj={ (aj (1) , flj1) , (aj (2) , flj2) , …, (aj (nj) , fljnj) }, p+1≤j≤m。nj表示第j个分类属性下值域中不同取值的个数, fljw (1≤w≤nj) 表示第j个分类属性下值域中取值aw在类Cl中出现的频率。

为了更直观地理解分类型数据部分多Modes类中心的表示方法, 下面通过例子来进行说明。

例1:假设表1所示数据表示聚类过程中得到的一个聚类结果C1中分类型数据部分, 其中包括{X1, X2, X3, X4, X5}5个对象, {A1, A2, A3}3个分类属性。

由表1所示数据, 如果按照K-Prototypes算法中分类型数据部分类中心的计算方法, 得到类C1的Modes为{a, d, f}或{c, d, f}, 因此存在不唯一性, 将可能导致算法不稳定。而根据定义2得到该类的多Modes类中心为Z1c= (z11, z12, z13) , 其中z11={ (a, 0.4) , (b, 0.2) , (c, 0.4) }, z12={ (d, 0.6) , (e, 0.4) }和z13={ (f, 0.6) , (g, 0.4) }。

由定义2可知, 单一对象也可能表示成多Modes形式, 例如分类型数据对象X6= (c, d, f) , 则该对象的多Modes表示形式为X'6= (x'61, x'62, x'63) , 其中x'61={ (a, 0) , (b, 0) , (c, 1) }, x'62={ (d, 1) , (e, 0) }和x'63={ (f, 1) , (g, 0) }。

基于以上给出的分类型数据类中心的多Modes表示方式, 下面给出扩展的欧式距离度量。

定义3设数据集X分类型属性部分的两个多Modes表示的类中心分别为Zic= (zi (p+1) , zi (p+2) , …, zim) 和Zjc= (zj (p+1) , zj (p+2) , …, zjm) , 则Zic和Zjc之间的欧式距离定义为:

定义4设ClX是聚类算法过程中的一个聚类结果, Z'l={Zlr, Zlc}为Cl的类中心, 其中Zlr为用均值表示的数值型部分的类中心, Zlc为由定义2中给出的分类型数据的多Modes类中心, 则对象Xi∈X与类中心Z'l之间扩展的欧式距离定义如下:D (Xi, Z'l) =Dr (Xi, Zlr) +Dc (X'i, Zlc) , 其中, Dr (Xi, Zlr) 表示数值型属性部分的欧式距离, 即表示由定义3给出的分类型部分多Modes中心间的扩展的欧式距离, X'i表示对象Xi的多Modes形式。

设X是一个混合型数据集, 将上述给出的扩展的欧式距离应用到K-Prototypes算法中, 目标函数定义为:

以上优化问题是一个非常复杂的非线性规划问题, 和K-Means类型算法类似, 采用逐步优化的策略, 即首先固定聚类中心Z', 最小化目标函数F'得到隶属矩阵W;然后固定隶属矩阵W, 最小化目标函数F'得到新的聚类中心Z';如此迭代, 到目标函数F'不能继续优化为止。

基于以上给出的多Modes表示形式的类中心和扩展的混合数据欧式距离度量, 基于划分的混合数据聚类算法描述如下。

Step1从数据集X中随机选取k个不同的对象作为初始聚类中心;

Step2根据定义4给出的扩展的欧式距离计算对象与类中心之间的相异度, 按照最小化原则将数据集中的数据对象划分到离它最近的聚类中心所代表的聚类中;

Step3更新聚类中心, 其中数值属性部分通过计算同一类中对象的平均值得到, 分类型属性部分根据定义2得到多Modes形式表示的类中心;

Step4重复以上Step2, Step3, 直到目标函数F'不再发生变化为止。

3 实验分析

为了验证本文提出算法的有效性和可行性, 从UCI真实数据集中挑选了4组数据集Teaching assistant evaluation (TAE) 、Heart disease (Heart) 、Australian Credit approval (Credit) 和Contraceptive method choice (CMC) , 并将本文提出的算法和K-Prototypes算法进行比较。4组数据集的信息描述如表2所示。

为了评估算法的有效性, 下面采用聚类精度、纯度、召回率和调整的德兰指标[9]4个指标对聚类结果评价。设数据集X是由n个对象组成, C={C1, C2, …, Ck}是聚类结果, P={P1, P2, …, Pk'}是数据的真实划分。ai表示正确分到第i类中的对象数, bi表示误分到第i类中的对象数, ci表示应该分到第i类却没有分到的对象数, nij是Ci和Pj中共同包含的对象数, 即nij=|Ci∩Pj|;ei是Ci中的对象数, dj是Pj中的对象数。聚类精度AC (accuracy) 、纯度PR (precision) 、召回率RE (recall) 和调整的德兰指标ARI (adjusted rand index) 4个指标分别定义如下:

如果聚类结果越接近于数据集的真实类划分, 那么AC, PE, RE和ARI的值就越大。

在实验中, 为了避免各个不同数值特征之间由于度量单位不同对距离计算的影响, 在聚类之前需要对数值型数据进行标准化。标准化公式为:

其中1≤i≤n, 1≤j≤p, Xij表示第i个数据第j个属性下的取值, X'ij为Xij规范化之后的值。max (X·j) 和min (X·j) 分别表示整个数据集第j个属性的最大值和最小值。

由于划分式聚类算法的聚类结果受初始类中心选择的影响, 不同的初始类中心可能有不同的聚类结果, 所以在4组数据集上分别随机选择100组类中心, 使每个算法运行100次, 通过计算平均聚类质量来验证算法的有效性。在4个数据集上, 本文提出的算法和K-Prototypes算法在不同评价指标下的聚类算法性能比较分别如表3-表6表示。

通过分析表3-表6, 在数据集Teaching assistant evaluation、Heart disease、Australian Credit approval和Contraceptive method choice上, 本文提出的基于划分的聚类算法得到了较好的聚类效果, 总体上优于传统的K-Prototypes算法。以上实验结果表明本文给出的分类型数据的多Modes类中心表示法及其扩展的欧式距离是有效的。

4 结语

本文为了克服传统的K-Prototypes算法中存在的问题, 首先给出了一种分类型数据类中心的多Modes表示方式并基于此将欧式距离扩展到混合数据, 进而设计了一个基于划分的混合型数据聚类算法。通过与传统的K-Prototypes算法进行实验比较, 实验结果表明本文提出的聚类算法总体上优于传统的K-Prototypes算法。

参考文献

[1]Xu Rui, Wunsch II Donald.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks, 2005, 16 (3) :645-678.

[2]孙吉贵, 刘杰, 赵连宇.聚类算法研究[J].软件学报, 2008, 19 (1) :48-61.

[3]Han Jiawei, Kamber Micheline, Pei Jian.Data Mining:Concepts and Techniques[M].3rd ed.San F rancisco:Morgan Kaufmann, 2012.

[4]Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceeding of the 5th Berkeley Symposium on Mathematical Statistics and Probability Berkeley, 1967.

[5]Huang Zhexue.A fast clustering algorithm to cluster very large categorical data sets in data mining[C]//Proceedings of the SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery Canada, 1997.

[6]Huang Zhexue.Extensions to the K-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery, 1998, 2:283-304.

[7]Li Cen, Biswas Gautam.Unsupervised learning with mixed numeric and nominal data[J].IEEE Transactions on Knowledge and Data Engineering, 2002, 14 (4) :673-690.

[8]He Zengyou, Xu Xiaofei, Deng Shengchun.Clustering mixed numeric and categorical data:A cluster ensemble approach[EB/OL].2005.http://arxiv.org/pdf/cs.AI/0509011.