面向人口收入管理的数据挖掘研究与应用

赵京胜，张 鹏，孙宇航

（青岛理工大学 通信与电子工程学院，山东 青岛266033）

0 引 言

Apriori算法是一种反复迭代的算法，针对该算法的固有缺陷，Brin等人曾提出了DIP（dynamic itemset counting）改进方法，利用动态评估项集支持度来减少对数据库扫描的次数；Park等人提出了基于散列桶计数的方法，提高了频繁集的发现效率；Agrawal等提出了压缩扫描事务项的方法，有效缩短了扫描无效事务项的时间［1］。这些改进方法大多局限于数据结构为树的形式，很少涉及矩阵结构的应用。近几年矩阵结构作为Apriori算法改进过程中的另一焦点，效果显著。

针对聚类K－Means算法聚类过程中类内和类间距离的研究，李永森等提出了距离代价函数，综合了类内和类间距离函数；张逸清等在算法的目标函数中加入了一个新的数据项，用于衡量其它邻近聚类中心与当前聚类中心的距离平方和［2］。尽管目前对K－Means算法的改进方案众多，但缺少对初始聚类中心点选取方面的研究，而初始聚类中心点的选取很大程度上影响了后续聚类过程的效率。

本文基于数据挖掘算法的改进和对传统数据管理系统的功能拓展，以经典Apriori算法和K－Means算法分析为基础，证实了改进算法的实际应用效果，并以经典信息管理技术为支撑，搭建了一套面向人口收入数据的数据挖掘管理系统，以提升数据管理能力和分析效率。

1 关联Apriori算法的研究与改进

1.1 关联Apriori算法分析

设I＝ ｛i1，i2，…，im｝是一个项目集合，D 表示数据库事务集，TI；A、B 为集合T 中的项集，关联规则为：AB，其中AI、BI且A∩B＝。文献［3］给出了支持度、置信度等相关的定义。

Apriori算法作为经典关联规则挖掘算法，其核心原理为：首先按照逐层搜索的迭代方式，通过Lk－1的自连接产生候选K－项集的集合，记作Ck，多次扫描数据库后从Ck中寻找支持度不低于用户设定的最小支持度阈值的项集；然后从频繁项目集中构造不低于用户设定的最小置信度阈值的规则。算法能较准确有效地生成频繁项集，其主要缺点为［4，5］：

（1）候选集Ck的不断产生使得连接项集越来越多，庞大的计算量延缓了算法运行效率。

（2）多次扫描数据库，冗余候选集增加了扫描次数，提高了对I／O 负载的要求。

1.2 关联Apriori算法改进

基于矩阵删列的改进型MA－Apriori算法，旨在解决原算法无效候选集的产生导致算法效率低下的问题。

（1）将数据库映射为0－1矩阵［］m×n，表示为

其中，行m 代表I 中的项，列n 代表D 中的事务，若矩阵中的元素IiDj（i＜＝m，j＜＝n）＝0则表示事务库D 中第j个事务不含I 项集合的第i项。

（2）由频繁－1－项集产生候选项集2，设［IiD1］和［IiD2］（i＝1，2，……m）是L1中的两个可连接项集，判断［IiD1］［IiD2］的内积值与最小支持计数的大小，若其值不低于最小支持计数，保留这对项集组合作为频繁－2－项集L2的项集，否则，不予考虑作为L2的项集。其中，列［IiD1］与矩阵其它列做n－1次内积，保证不产生重复内积过程，除去列［IiD1］外，列［IiD2］与矩阵剩余列做n－2 次内积，以此类推，直至矩阵中所有列均和其它不同列做过内积运算并保留内积结果不低于最小支持计数的组合项集。最后，保留下来的组合项集生成为频繁－2－项集。

由（K－1）－项集分裂后所得的（K－2）－项集中所包含的项在 （K－2）－项集的出现频率必须满足K－2次。当候选集Ck（K≥4）中某项不满足K－项集分裂后在上一级K－1－项集中的出现频率K－1，那么，为减少后续矩阵计算的冗余度，删掉当前矩阵中事项出现频率低于项目集所包括项个数的事物列。

（3）算法继续到K－项集时，如果频繁集Lk所包含的频繁项目数小于K＋1，则算法中止，不必再进行K＋1项目集的运算。因为对于K＋1 项目集，一定有K＋1 个K项目子集。

MA－Apriori算法的流程如图1所示。

图1 MA－Apriori算法流程

为验证算法的有效性，采用UIC 机构提供的国外人口收入数据。原始数据共32561条记录，以二维表形式存储。每条记录11个属性：工作性质、受教育程度、受教育时间、婚姻状况、职业、家庭角色、人种、性别、工作时间、所处国家和薪资范畴，其中受教育时间和工作时间为数值型，剩余属性均为字符串。

图2 实例应用效果对比

由算法运行结果可知，改进前后算法最终生成的关联规则是一致的，包括以下规则：

薪资＞50K＝＝＞男性置信度1.0

薪资＜＝50K＝＝＞工作时间40小时置信度0.75

工作时间40小时＝＝＞薪资＜＝50K 置信度0.75

男性＝＝＞薪资＞50K 置信度0.6

1.3 Apriori算法和MA－Apriori算法的性能分析

Apriori算法在时间上的消耗主要是由连接产生的项目集个数和扫描上一频繁项集中项集的次数所引起的。候选项集的产生是呈指数增长的，例如104个1－频繁项目集可能产生项目集近107个的2－候选集［6］。

MA－Apriori算法基于矩阵形式，事务矩阵中0、1以位方式进行存储，减少了内存占用，随着计算次数的增加数据量逐渐减少，而且针对多维数据效果更加明显。而列之间的与运算等同于有效的剪枝，运算本身所具有的计算特性简化了候选集的产生过程，使得候选项集的数量相应减少，由图2可以看出候选集和频繁集产生的阶段性结果，其中，Apriori算法生成候选集3的项集并没有成为频繁集L3中的项集，可见这一步的计算无效，改进后的MAApriori算法在生成频繁集L2后立即停止运行，避免了无效候选集产生。改进后的MA－Apriori算法在时间和空间上都有了一定的优化。

2 聚类K－Means算法的研究与改进

2.1 聚类K－Means算法分析

聚类是在预先不知道分类数目的情况下，将数据集划分成若干不同的类，使得类内数据对象尽可能相似，类间尽可能相异。其中较为常用的一种基于距离的算法是KMeans算法［3，7］。

设X 为包含n 个对象的数据集合，那么X＝｛X1，X2，X3，……Xn｝，从X 中任意选取K 个对象作为初始聚类中心集合，记为Z，则Z＝｛Z1，Z2，Z3……Zk｝且满足k≤n。通过K 个初始中心对数据集合X 进行K 个划分，每一个划分代表一个簇，利用两点间距离公式来计算初始聚类中心与数据集合X 对象间的距离，按计算结果将对象分配到距离最近的组。于是，数据集合X 经划分后得到K 个聚类簇记作C，C＝｛C1，C2，C3……Ck｝。不断更新聚类中心点，直到聚类中心点不再发生改变，最终得到最优的聚类中心点C’＝｛C1’，C2’，C3’……Ck’｝。

K－Means算法作为经典的聚类算法，其明显的不足是聚类没有指明初始化均值的方法，常用的随机选取聚类初始点存在不确定性。

2.2 聚类K－Means算法改进

针对K－Means算法随机选取对象作初始聚类中心的缺陷进行改进，提出一种基于确定初始聚类中心点的算法IM－K－Means，算法流程如图3所示。

图3 IM－K－Means算法流程

（1）设X＝｛X1，X2，X3，……Xn｝为包含n 个对象的数据集合，对X 中的数据进行升序排序，从X 集合中依次取出｛X1，X2｝放入集合N1，｛X3，X4｝放入集合N2……直至X集合中的所有对象都被取出，则得到K 个存放原数据集中两个对象的集合N ＝｛｛N1｝、｛N2｝……｛Nk｝｝。因无法保证X 集合中数据个数的奇偶性，因此，将n－2（k－1）对象放入到最后一个分组Nk。

K 个集合存放着数据集合X 中距离最近的两个数据对象，这样的分类很大程度上避免了随机选取的不确定性，保证了K 个初始聚类中心在选取过程中数据空间均匀分布，避免了初始聚类中心存在集中取点的可能性。

（2）对集合N 中的每个集合求均值，所得结果记为Ci（i＝1，2，……k），Ci＝｛C1，C2，C3……Ck｝，删去集合中重复的对象后即为初始聚类中心点，然后按照原算法计算中心点均值直至准则函数收敛。

将IM－K－Means算法用于本文实例，使用32561 组样本数据来验证两种算法的聚类效果。图中横轴代表测试数据个数，纵轴代表工作时间值，算法对比结果如图4和图5所示。

图4 K－Means应用实例聚类效果

图5 IM－K－Means应用实例聚类效果

2.3 K－Means算法和IM－K－Means算法的性能分析

根据K－Means算法的执行过程可知，通过对n 个对象到k 个聚类中心点的择取过程需要k×n 次距离计算，而将样本分配到最近的类中并不断计算类中样本平均值直至不再发生变化，经历t次迭代。所以，K－Means算法的时间复杂度至少为O（knt）。

IM－K－Means算法在原算法基础上增加了对样本排序的过程，采用性能较稳定的堆排序，时间复杂度为O（nlog2n）。设树深度为h，则n个结点的完全二叉树深度为log2（h＋1），重建堆时结点比较次数：2［log2（n－1）＋log2（n－2）＋…log22］＜2nlog2n。尽管样本排序增加了算法复杂度，但排序后的两两相邻元素存放一组，类内距离接近最小值，由此生成的初始聚类中心点与最终聚类中心点的确定过程缩短，欧式距离的计算次数为（n－2）×k，迭代次数一定小于t次。

对人口收入数据中的工作时间进行测试，对比算法迭代次数的性能差异，测试结果如图6所示。

图6 算法迭代次数对比

3 基于数据挖掘改进算法的人口收入管理系统

为提高数据管理系统的性能，搭建了基于数据挖掘算法的人口收入管理系统，将MA－Apriori算法和IM－KMeans算法作为数据挖掘技术平台，采用JSP＋Tomcat6.0＋MySQL技术实现［8］。系统功能框架图如图7所示。

3.1 Ma－Apriori算法在系统中的实现

传统管理系统增加数据挖掘的关联规则分析，在提升系统算法效率的同时成为专家探究各属性间关联情况，获取隐藏规律的有效手段［9］。

MA－Apriori算法的平台化实现主要功能有：可手动设置最小支持度和最小置信度，查看在不同支持度和置信度情况下所输出的关联规则情况；关联规则表以Excel表输出，便于专家书面分析研究。图8 结果是以最小支持度为0.22，最小置信度0.8计算所得，共产生11条强关联规则。

图7 系统整体功能框架

图8 关联规则

由规则置信度对应的相关联属性可知婚姻状况对薪资的影响程度是非常强烈的，据杂志《今日美国》刊登的一篇关于美国未婚男女收入调查显示，在美国366所中等规模城市中，年龄在22－30岁之间、单身无子女的女性平均年收入为27K，同年龄段的未婚男性平均年收入为24K；相对婚姻状况，受教育程度对薪资的影响程度次之。据教育专家的一些看法，所受教育等级的不同是导致收入差异的根本原因，美国高中毕业后选择上大学的女性几乎达到3／4，相比之下，男性约为2／3，而且大学毕业后继续深造的女性要比男性高出1.5倍，与规则分析相近。

3.2 IM－K－Means算法在系统中的实现

将IM－K－Means算法应用在人口收入管理系统中，针对大量原始数据散乱无序的状况，按属性条件进行聚类分析，实现对人口收入信息的高效整合与组织［10］。图9、图10以受教育时间为例对原始数据聚为两类，设置受教育时间最大值为16.0，最小值为0.5进行聚类。

图9 第一类聚类结果

图10 第二类聚类结果

第一类为受教育时间16—9 年，对应受教育程度为Doctorate（博士）—HS－grad（高中），共有28308条数据。在基本信息管理中按薪资范畴＞50K 条件查询，共有117条结果，而受教育程度在HS－grad（高中）之上的人数占84%，可以说明第一类聚类程度的集中性，类内之间的相近。据美国联邦调查局的一项报告表明，成人学历水平的高低以收入差异作为主要体现方式之一，已获取高中以上学历的成人收入是未获取高中文凭的四倍，获取硕博学位的成人年均收入为79946 元，而持有学士学位者的年均收入为54689元。

第二类受教育程度为8—1年，对应受教育程度为12th（初中）—Preschool（学前教育），主要覆盖受教育程度不高的人群，共有4342条数据。同样在基本信息管理中查找，该受教育程度所对应薪资范畴＜＝50K 的人数占薪资范畴为＜＝50K 总人数的78%，聚类效果明显，第二类与第一类对比收入水平存在显著差异。据联邦普查局调查报告表明，在美国沒有完成高中教育的人，年收入仅19915 元；具有学士或硕士学历者，只有51.4%的人年薪少于50K美元［10，11］。

根据系统运行结果和官方调查报告对比可知，MAApriori算法和IM－K－Means算法在系统中的实际应用效果良好，提高了数据分析效率。

4 结束语

针对传统数据管理系统的局限性，数据挖掘技术与应用系统的结合是一个可供研究的方向。在算法改进的过程中，针对Apriori算法在候选集产生过程中存在的不足，提出优化有效候选集产生的MA－Apriori算法，改进了数据集的存储方式，增加了判断条件，提高了频繁项集生成的准确性；针对K－Means算法初始聚类中心点随机选取的不确定性，提出的IM－K－Means算法，调整了初始聚类中心点的选取方法，缩短了寻找最优聚类中心点的时间，提高了算法效率。在系统实现方面，虽然系统运行良好，但在系统搭建的过程中仍存在一些有待优化、扩展的地方，嵌入系统的聚类算法在实现聚类功能时，耗时过长，这也是在算法改进阶段未能注意到的问题，可以考虑运用其它聚类思想对算法进行进一步的改进。

［1］ZHANG Fengyun.Brief analysis of associative rule and Apriori algorithm ［J］.Computer Knowledge and Technology，2010，6 （22）：6268－6269 （in Chinese）.［张凤云.浅析关联规则及其Apriori算法 ［J］.电脑知识与技术，2010，6 （22）：6268－6269.］

［2］WU Suhui，CHENG Ying，ZHENG Yanning，et al.Survey on K－Means algorithm ［J］.New Technology of Library and Information Service，2011，205 （5）：28－30 （in Chinese）. ［吴夙慧，成颖，郑彦宁，等.K－Means算法研究综述 ［J］.现代图书情报技术，2011，205 （5）：28－30.］

［3］Han Jiawei，Micheline Kamber，Jian Pei.DATA MINING concepts and techniques［M］.Beijing：China Machine PRESS，2012：50－496.

［4］Trnka，Andrej.Market basket analysis with data mining methods［C］／／Networking and Information Technology，2010：446－450.

［5］JI Xiyu，HAN Qiuming，LI Wei，et al.Data mining technology application examples［M］.Beijing：China Machine Press，2009：20－30（in Chinese）.［纪希禹，韩秋明，李微，等.数据挖掘应用实例［M］.北京：机械工业出版社，2009：20－30.］

［6］WANG Xiaojun.Study of data mining based on Apriori algorithm ［C］／／Software Technology and Engineering.2nd International Conference on Knowledge Discovery and Data Mining，2010：400－403.

［7］Kalavathy R.KDD and data mining ［C］／／Information and Communication Technology in Electrical Sciences，2007：1105－1110.

［8］CHEN Jian.Design of college hospital management system based on JSP and MySQL ［J］.Computer and Information Technology，2011，19 （16）：48－49 （in Chinese）.［陈健.基于JSP和MySQL的高校校医院管理管理系统的设计 ［J］.电脑与信息技术，2011，19 （16）：48－49.］

［9］HUANG Min.The design and implementation of community census information management system ［D］.Xi’an：University of Electronic Science and Technology of China，2011：24－30（in Chinese）.［黄敏.社区人口普查信息管理系统的设计与实现 ［D］.西安：电子科技大学，2011：24－30.］

［10］LIU Na.The application of data mining algorithm based on MapReduce to national census system ［D］.Beijing：Capital University of Economics and Business，2011：47－49 （in Chinese）.［刘娜.基于MapReduce的数据挖掘算法在全国人口系统中的应用 ［D］.北京：首都经济贸易大学，2011：47－49.］

［11］USA Today.Women earn far less than men ［EB／OL］.http：／／news.sinovision.net／portal.php.