（计算机软件与理论专业论文）基于聚类分析的数据关联与可视化研究.pdf

基于聚类分析的数据关联与可视化研究 学科：计算机软件与理论 研究生签名：尤磊元磊 指导老师签名： 弦衣彬、 i 捅姜 数据挖掘是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的高 级处理过程。关联规则挖掘用于从大量数据中揭示项集之间的有趣关联或相关联系，是数 据挖掘的一项重要研究内容，在现实生活中有着广泛的应用。 学生学籍管理系统中存在着大量学生学习成绩信息，我们希望采用数据挖掘中的方 法对成绩数据进行分析，获取相关信息供教学部门参考。本文是在学生成绩聚类分析的基 础上，采用f p g r o w t h 算法分析聚类结果中的学生簇( 反映学生学习趋势) 与该簇学生所具 有因素的关联关系，从而分析影响学生学习成绩的因素。 本文主要开展并完成了以下研究工作：( 1 ) 深入了解关联规则挖掘的理论与研究现状， 重点研究了f p g r o 、t h 算法，在对f p g r o w t h 算法分析的基础上提出了一种改进策略， 提高了挖掘效率，并通过实验验证了改进算法的有效性；( 2 ) 将改进的f p g r o w t h 算法应 用到学生成绩关联分析系统中，通过对每簇学生的因素采用f p g r o w t h 算法分析，得出 学生学习成绩波动起伏与学生因素间的关联关系，进一步分析得出影响学生学习的主要因 素，包括学习主动性、个性特征等；( 3 ) t 解可视化技术在数据挖掘中的研究与应用，并 采用三维图形显示影响学生学习的因素及相关因素间的关联关系。 本文采用改进的f p g r o w m 关联挖掘算法分析影响学生学习的因素，较采用统计分 析技术能更深一步得出因素间的关联关系，提高了挖掘效率，挖掘结果对有关教学部门也 有一定参考意义。 关键词：数据挖掘；关联分析；频繁模式；f p w e e r e s e a r c ho nd a t aa s s o c i a t i o na n dv i s u a l i z a t i o nb a s e d c l u s t e r i n ga n a l y s i s d i s c i p l i n e ：c o m p u t e rs o f t w a r ea n dt h e o r y s t u d e n ts i g n a t u r e ：y 肼必 s u p e r v i s o rs i g n a t u r e ：义沁9 。ko a b s t r a c t d a t am i n i n gi sap r o c e s s i n gp r o c e d u r eo fe x t r a c t i n gc r e d i b l e ，n o v e l ，e f f e c t i v ea n d u n d e r s t a n d a b l e p a t t e r n s f r o md a t a b a s e s a s s o c i a t i o na n a l y s i sf o u n di n t e r e s t i n gr o l e so r c o r r e l a t i v i t yo fi t e m so nab i gs c a l ed a t a b a s e ，w h i c hi sa ni m p o r t a n tt e c h n o l o g yi nd a t am i n i n g a n di sw i d e l yu s e di nr e a ll i f e t h e r ei sal a r g ea m o u n to fs t u d e n ts c o r ei n f o r m a t i o ni nt h es t u d e n tm a n a g e m e n ts y s t e m w eh o p eu s ed a t am i n i n gm e t h o d st oa n a l y z et h o s ed a t a , t og e tr e 1 e v a n ti n f o r m a t i o nf o r t e a c h i n gd e p a r t m e n t s r e f e r e n c e t h ep a p e rb a s e do nt h es t u d e n t s s c o r ec l u s t e r i n gs y s t e m ，i t a d o p tp t - g r o w t ha l g o r i t h mt oa n a l y z es t u d e n tc l u s t e r ( w h i c hr e f l e c t i n gt h et r e n do fs t u d e n t l e a r n i n g ) o fc l u s t e r i n gr e s u l t sa n dt h ec l u s t e rs t u d e n t s f a c t o r sa s s o c i a t e dr e l a t i o n sa n da n a l y z e t h ei m p a c to fs t u d e n ts c o r ef a c t o r sa c c o r d i n g l y t h ep a p e rh a sc o m p l e t e dt h ef o l l o w i n gr e s e a r c hw o r k ：( 1 ) u n d e r s t a n d i n gt h ea s s o c i a t i o n r u l e st h e o r ya n dt h ea c t u a l i t yo fr e s e a r c h ，m a i n l ys t u d y so nf p g r o w t ha l g o r i t h m ，p r o p o s e sa b e t t e r m e n ts t r a t e g yt oe n h a n c et h ee f f i c i e n c yo fm i n i n gb a s e do nt h ea n a l y s i so fa l g o r i t h ma n d v a l i d a t et h ev a l i d i t yo fi m p r o v e da l g o r i t h mb ye x p e r i m e n t ( 2 ) a p p l y i n gt h ei m p r o v e d a l g o r i t h mt os t u d e n ts c o r e sa s s o c i a t i o na n a l y s i ss y s t e m ，t h r o u g hu s e sf p g r o w t ha l g o r i t h m a n a l y z ee a c hs t u d e n tc l u s t e r sf a c t o rt og e ta s s o c i a t i o nr o l e sb e t w e e ns t u d e n t s f l u c t u a n ts c o r e a n ds t u d e n t s f a c t o r s ，i ti sf u r t h e ra n a l y z e dt h a tt h em a i nf a c t o ri m p a c t i n gs t u d e n ts t u d yi n c l u d i n g l e a r n i n gi n i t i a t i v e ，p e r s o n a l i t yc h a r a c t e r i s t i c s ( 3 ) u n d e r s t a n d i n gr e s e a r c ha n da p p l i c a t i o no f v i s u a l i z a t i o nt e c h n o l o g yi nd a t am i n i n ga n du s i n g3 dg r a p h i c st os h o wt h ef a c t o r si m p a c t i n g s t u d e n t s s t u d ys c o r ea n da s s o c i a t i o nr o l e sb e t w e e nf a c t o r s u s i n gi m p r o v e df p g r o w t ha l g o r i t h mc o m p a r ew i t hu s i n gs t a t i s t i c a lm e t h o d st oa n a l y s i s f a c t o r sw h i c hi m p a c t i n gs t u d e n t s s t u d ys c o r ec a nf i t r t h e ra n a l y s i sa s s o c i a t i o nr o l e sb e t w e e n f a c t o r s ，i n c r e a s i n gm i n i n ge f f i c i e n c y , t h em i n i n gr e s u l th a sac e r t a i nr e f e r e n c et o r e l a t e d t e a c h i n gd e p a r t m e n t k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o na n a l y s i s ；f r e q u e n tp a t t e r n ；f p t r e e 学位论文独创性声明 学位论文独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的学位论文是我个人在导师 指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，学位论文中不包含其他人已经发表或撰写过的研究成果，不包含本人已经申请学位 或其他用途使用过的成果。与我一同工作的同志对本研究所作的任何贡献均已在论文中作 了明确的说明并表示致谢。 学位论文与资料若有不实之处，本人承担一切相关责任。 学位论文作者签名：毛缸 指导教师签名：氐彤、 同 期：辛ff 1 7 学位论文知识产权声明 学位论文知识产权声明 本人完全了解西安工业大学有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权属西安工业大学。本人保证毕业离校后，使用学位论文工作成果或用 学位论文工作成果发表论文时署名单位仍然为西安工业大学。学院有权保留送交的学位论 文的复印件，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以采用影印、缩印或其他复制手段保存学位论文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：范磊 指导教师基名：乌代矽一、 日 期：o 扩r f j 7 1 绪论 1 i 课题研究来源和背景 1 绪论 随着数据库技术的迅速发展，数据库管理系统的广泛应用，许多商务、科学和行政事 务的计算机化，以及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步，全球 信息系统及万维网的流行，致使各行各业产生和积累了大量的数据，这些激增数据的背后 隐藏着许多重要的信息，人们希望能够对这些海量数据进行更高层次的分析，以期根据现 有数据能分析预测未来的发展趋势，数据挖掘技术应运而生。 在学校的信息化建设中，学生信息管理系统记录了在校学生每个学期的学习成绩信 息。目前我们面对的教务处学生成绩数据库是一个多维的关系数据库，它不仅有学生的高 考入学成绩还有学生各个学期的各科考试成绩，而且近几年随着学生数量的增加，数据库 中存储的成绩信息也在不断增长，我们急切地需要从这些海量数据中发现潜在的有用信息 以期帮助学校的相关部门掌握更多的学生信息。数据挖掘技术适合了我们对学生学习成绩 分析处理的要求，这种技术也正因此而得到越来越广泛的应用。 本课题是在对学生聚类分析的基础上展丌的，课题组已经完成了对学生聚类分析的过 程，已采用k m e a n s 算法和自组织神经网络s o m 算法按照学生的学习成绩对学生进行聚 类分析，在聚类结果中，每一个簇反映了本簇学生的学习趋势( 逐渐上升或逐渐下降等) ； 并已采用传统的统计分析方法对聚类分析结果结合学生的内外部因素进行了分析。为了更 深入地了解学生学习成绩与学生的内外部因素间的关系，我们需要采用关联挖掘技术做更 深一步的分析。 本文研究的主要目的有两个：第一是对数据挖掘、聚类分析、关联分析的概念、原理 及关联分析挖掘算法进行分析研究，第二是将关联分析算法应用到学生成绩数据库中，分 析学生所处的内外部因素对学生学习成绩的影响以及影响程度。 本文研究的主要内容是关联分析的研究与应用及可视化技术在数据挖掘中的应用。主 要是在按照学生学习成绩对学生聚类分析的基础上，将学生聚类的结果与学习因素调查表 信息结合建立关联挖掘库，采用f p g r o w t h 算法挖掘学生学习成绩的趋势与学生所处内外 部因素间( 如：家庭经济条件、父母受教育程度、学校学习风气、学习主动性等) 的关联关 系( 如：学习主动性强的学生学习成绩有上升趋势等) ，进而分析得出影响学生学习的因素； 并采用可视化技术显示同一簇间影响学生学习的内外部因素间的关联关系及不同簇间影 响学生学习的主要因素的关联信息。 两安工业大学硕士学位论文 1 2 数据挖掘概述 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括如下几 层含义：数据必须是真实的、大量的、实际应用中产生的；数据可能是有噪音的、模糊的； 发现的信息或知识是用户感兴趣的、可接受的、可理解的、可运用的。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，从一开始就是面向应 用的，它不仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观 乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关 联、使用已有的数据对未来的活动进行预测。 数据挖掘是一个多交叉领域，源于数据库技术、数据仓库、机器学习、统计学、数据 可视化、信息检索、和高性能计算。其他有贡献的领域包括：神经网络、模式识别、空间 数据分析、图像数据库、信号处理、人工智能、知识库系统、知识提取及许多应用领域， 包括商务、经济学和生物信息学【”。 1 2 1 数据挖掘分类 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同类型数据 挖掘系统。这样，就需要对数据挖掘系统给出一个清楚的分类。这种分类可以帮助用户区 分数据挖掘系统，确定最适合其需要的数据挖掘系统【l l 。 根据不同的标准，数据挖掘系统可以分类如下： ( 1 ) 根据数据库类型分类： 数据挖掘所基于的数据库类型有：关系型、事务型、面向对象型、推论型( d e d u c t i v e ) 、 空间型、时序型、多媒体型、异质型( h e t e r o g e n e o u s ) 、主动型( a c t i v e ) 、遗留型( 1 e g a c y ) 、文 本挖掘和基于网络信息的挖掘等。 ( 2 ) 根据得到的知识分类： 数据挖掘系统可以根据所挖掘的知识类型分类。即根据数据挖掘的功能，如特征化、 区分、关联、分类聚类、孤立点分析和演变分析、偏差分析、类似性分析等。 此外根据所挖掘的知识的抽象层次进行划分，包括概化知识( 在高抽象层) 、原始层知 识( 在原始数据层) 、多层次知识( 考虑若干抽象层) 。一个高级数据挖掘系统应当支持多抽 象层的知识发现。 ( 3 ) 根据所采用的技术分类： 神经网络：从结构上模仿生物神经网络，是一种通过训练来学习的非线性预测模型。 可以完成分类、聚类和特征挖掘等任务。 决策树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类产生规则， 典型的决策树方法有分类回归树等，其典型应用为分类规则的挖掘。 2 西安工业大学硕士学位论文 遗传算法：是一种新的优化技术，基于生物进化概念设计了一系列的过程来达到优化 的目的。这些过程有基因组合、交叉、变异和自然选择等。遗传算法易于并行计算，并且 已经应用于分类和其他优化问题。 粗糙集理论：是一种研究不确定性问题的数学工具，作为集合论的扩展，主要用于研 究不完全和不完整信息描述的数据挖掘技术。可以用于分类，进行特征归约和最小属性子 集归约。 模糊逻辑：通过隶属度函数定义分类系统的“模糊”阈值或边界，从而可以产生人们易 于理解的分类规则。 最近邻技术：通过k 个与之相近的历史记录的组合来辨别新的记录，也称为k 一最近 邻技术。主要应用于分类、聚类和偏差分析等。 可视化技术：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者，决 策者可以通过可视化技术交互式的分析数据关系。 1 2 2 数据挖掘功能 数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下六类功能【l 】： ( 1 ) 概念描述 数据库中通常存放大量的细节数据。然而，用户通常希望以简洁的描述形式观察汇总 的数据集。这种数据描述可以提供一类数据的概貌，或将它与对比类相区别。此外，用户 希望方便、灵活地以不同的粒度和从不同的角度描述数据集。这种描述性数据挖掘称为概 念描述。 ( 2 ) 关联分析 关联分析就是从大量数据中发现项集之间有趣的关联或相关联系。随着大量数据不停 地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量 商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定。 ( 3 ) 分类和预测 分类和预测是两种数据分析形式，可以用于提取描述重要数据的模型或预测数据未来 的趋势。分类和预测的应用十分广泛，例如，可以建立一个分类模型，对银行的贷款客户 进行分类，以降低贷款的风险；也可以通过建立分类模型，对工厂的机器运转情况进行分 类，用来预测机器故障的发生。 ( 4 ) 聚类分析 根据最大化类内相似性、最小化类间相似性的原则进行聚类，使得在同一个类中的对 象具有很高的相似性，而与其它类中的对象具有很小的相似性。聚类形成的每个类可以看 作一个对象类，由它可以导出规则。聚类也便于将观察到的内容组织成分层结构，把类似 的事件组织在一起。 ( 5 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模式不一致。这些数据对 3 西安工业大学硕士学位论文 象就是孤立点。许多数据挖掘算法试图使孤立点的影响最小化，或者排除它们。但在一些 应用中孤立点本身可能是非常重要的信息。例如在欺诈探测中，孤立点可能预示着欺诈行 为。 ( 6 ) 演变分析 数据演变分析描述行为随时间变化的规律和趋势，并对其建模。可以从股票交易数据 中挖掘出整个股票市场和特定公司的股票演变规律，以帮助预测股票市场的未来走向，帮 助对股票投资做出决策。 1 2 3 数据挖掘步骤 数据挖掘一般要经过确定业务对象、数据预处理、数据挖掘、结果评估、知识应用等 一系列过程，最后将分析结果呈现在用户面前【2 】。 ( 1 ) 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步，挖掘的最后结 果是不可预测的，但要探索的问题应是有预见的，盲目性的数据挖掘是不会成功的。 ( 2 ) 数据预处理 数据清理：清除噪声或不一致数据； 数据集成：将多个异种数据源结合起来用于挖掘； 数据选择：搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于 数据挖掘应用的数据；对于大量数据集，也可以采用取样技术，取样的方式有多种，一般 根据数据挖掘的目的和对数据挖掘的影响而灵活选用。 数据转换：将数据进行某种转换操作，然后将转换后的值作为新的变量存放在样本 数据中，而转换的目的是为了把数据和将来要建立的模型做得更好。分析模型是否真正适 合挖掘算法是数据挖掘成功的关键。 ( 3 ) 数据挖掘 选择合适的算法和技术对所得到的经过预处理的数据进行挖掘，如关联分析、聚类分 析、时间序列分析等，挖掘过程所需的控制参数在挖掘前由专家或用户提供。 ( 4 ) 结果评估 根据某种评估标准对挖掘的结果进行解释评估，比较不同模型的效果，预报各种不同 类型分析工具的结果，在进行各种比较和预报的评价之后，给出一系列标准的图表，供用 户进行定量评价。数据挖掘系统往往采用可视化技术将评估后所得知识提交给用户。 ( 5 ) 知识的应用 将分析得到的知识集成到业务信息系统的组织结构中去，指导企业生产实践、经营和 决策，提高企业自身的竞争优势，增加企业的经济效益，适用社会发展的需要。 1 1 2 4 数据挖掘现状 从数据库中发现知识( k d d ) - - 词首次出现在1 9 8 9 年举行的第十一届国际联合人工智 4 西安工业大学硕士学位论文 能学术会议上。到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了8 次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统 应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。1 9 9 9 年，亚太 地区在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的k n o w l e d g ea n d d a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和信 息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至 到了脍炙人口的程度。 目前，国内外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究进一步 发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高；传统的统计 学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包括：k d d 商业软 件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。用户主要集 中在大型银行、保险公司、电信公司和销售业。国外很多计算机公司非常重视数据挖掘的 开发应用，m m 和微软都成立了相应的研究中心进行这方面的工作，此外，一些公司的 相关软件也开始在国内销售，如s p s s 。国内从事数据挖掘研究的人员主要在大学，也有 部分在研究所或公司。所涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的 实际应用以及有关数据挖掘理论方面的研究。 1 3 关联分析概述 ， 1 3 1 关联分析简介 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系【1 j 。随着大量数据不停 的收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量 商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉 购物和贱卖分析。 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不 同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这 种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买 牛奶，同时也购买面包( 和什么类型的面包) 的可能性有多大? 通过帮助零售商有选择地经 销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一 步刺激顾客一次去商店同时购买这些商品。 1 3 2 关联分析现状 对关联分析的研究主要集中在以下几个方面： 提高原有算法的效率：在解决最大频繁项目集的生成问题上，为了提高对空间和时间 的利用效率，对数据库的扫描次数进行了缩减，提高了算法的效率。 结合其它理论对关联规则进行研究：引入粗糙集概念，使关联规则发现的模式具有较 西安工业大学硕士学位论文 高的解释能力和精确度。为了解决数量关联规则提取过程中的连续属性离散化问题采用了 聚类方法；通过引入神经网络的概念，提出用相互激活与竞争网络来进行数据库中的关联 规则的发现等。可以看出通过引入其他领域的先进理论，丰富了关联规则研究的内容，提 高了算法的有效性。 不同形式关联规则的研究：关联规则最早是由购物篮分析开始的，但是随着研究的扩 展和深入，关联规则的应用范围不断扩大，因此出现了多种形式关联规则的研究。由最简 单的单维、单层、布尔关联规则逐渐向复杂形式扩展。在基本关联规则的基础上提出了布 尔型加权关联规则和广义模糊型加权关联规则算法，由单层的关联规则扩展为多层次关联 规则的研究。另外对于关联规则挖掘指导思想也出现了变化，提出了概念指导的关联规则 的挖掘算法和基于概念格的关联规则的提取算法。 1 4 本文的主要工作与结构安排 1 4 1 主要工作 本文主要包括以下几个方面的工作： 阅读文献资料，分析研究数据挖掘的技术、方法、步骤、知识表达等； 研究聚类分析、聚类分析算法、聚类算法对学生分类的过程；分析研究可视化技术 在数据挖掘中的应用； 研究关联分析、关联分析算法及相关分析，分析f p g r o w t h 算法的原理并改进算法； 将f p g r o w t h 改进算法应用到对学生成绩挖掘库中，并利用实验验证算法的有效性 和适用性，采用可视化技术显示挖掘结果，制作一套完整的挖掘系统软件； 使用v c + + 、s q l s e r v e r 完成配套软件的编写工作。 1 4 2 论文的结构安排 论文共分为七章，各章的主要内容概述如下： 第一章：绪论。概述了论文选题的目的和意义、数据挖掘的分类、数据挖掘的功能、 关联分析的发展现状等，并对本人在该课题中的工作进行了详细的描述。 第二章：聚类分析研究。本章主要介绍了有关聚类分析的基本知识及目前课题组对学 生聚类挖掘的简介。 第三章：关联分析研究。本章主要介绍了关联分析的基本概念、关联分析的分类、关 联分析的几种常用算法、关联规则价值的衡量方法，以及相关分析的概念。 第四章：可视化技术研究。本章主要介绍了可视化技术的基本概念、数据可视化的几 种主要技术以及可视化技术在数据挖掘系统中的应用。 第五章：f p g r o w t h 算法的改进。本章主要从f p g r o w t h 算法的基本思想、特点及算 法的复杂度三个方面对算法进行分析与研究。对算法在在构造f p t r e e 时的步骤提出了对 应的改进措施，并运用实例进行了验证，从而证明了算法改进的实用性和正确性。 6 西安丁业大学硕士学位论文 第六章：f p g r o w t h 算法的应用研究。本章主要讲述了学生成绩关联挖掘系统的建立 过程，包括关联数据预处理和关联分析在系统中的应用。结合学生的聚类成绩信息重点对 关联运行结果从两方面进行分析与研究，其一是关联结果中各簇出现的频繁1 项集的分 析研究；其二是分析各簇的频繁项集之间的关联关系。并采用相关分析技术对关联结果进 行进一步的分析。 第七章：结论与展望。 7 2 聚类分析研究 2 聚类分析研究 聚类与分类不同，它要划分的类是未知的，聚类就是将数据对象划分成为多个类或簇。 给定一个n 个对象或元组的数据库，一个划分方法通过优化一个评价函数构建数据的k 个划分，每个划分表示一个聚类，并且k 曼n 。也就是说，它将数据划分为k 个组，同时 满足如下的要求：( 1 ) 每个组至少包括一个对象；( 2 ) 每个对象必须属于且只属于一个组。 但是在某些模糊划分技术中第二个要求可以放宽。一个好的划分的一般准则是：在同一个 类中的对象之间尽可能“接近”或相关，而不同类中的对象之间尽可能“远离”或不同。 2 1 聚类分析基本概念 聚类分析问题可描述为：给定m 维空间r 。中的n 个向量，把每个向量归属到s 个聚 类中的某一个，使得每个向量与其聚类中心的距离最小。聚类分析问题的实质是一个全局 最优问题，在这里m 可认为是样本参与聚类的属性个数，n 是样本的个数，s 是由用户预 先设定的分类数目，且满足s5 n 。 定义对于m 维空间r 。中的向量x i = x i l ，x t 2 ，x i 。 ，x j = x j l ，x j 2 ，x j 。) 向量x j 与x 之间的距离为： d i =丽 ( 2 1 ) 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多 数应用采用了以下两个比较流行的启发式方法：( 1 ) k m e a n s 算法，在该算法中，每个簇 用本簇中对象的平均值来表示。( 2 ) k - m e d o i d 算法，在该算法中，每个簇用接近聚类中心 的一个对象来表示。这些启发式聚类方法对在中小规模的数据库中发现球状簇是很适用 的。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进 一步地扩展。 划分算法典型地采用两阶段反复循环过程：( 1 ) 指定聚类，即指定一个数据对象到某 一个聚类，使得它与这个聚类中心的距离比它与其它聚类中心的距离要近；( 2 ) 修改聚类 中心。算法的结束条件是不再有数据被重新分配。可以选择一个反映聚类效果的目标函数， 当函数达到最优解时满足终止标准。这一类算法中，有的算法在对每一个数据对象的每一 次指定后就修改一次聚类中心( 如s o m 方法) ，有的算法当对所有的数据对象都指定完后 才修改一次聚类中心( 如k - m e a n s 方法) ，对这类方法来说，存在两个基本问题，即：如何 计算距离和如何修改聚类中心。计算距离时，对数值属性主要的方法是采用明考夫斯基距 离中的欧氏距离，而对符号属性则可以采用海明距离。 在数据规模较小以及数据对象维数较低的情况下，传统的划分聚类算法可以将数据全 部读入到内存进行计算，而随着数据量的增加，需要和磁盘进行多次数据交换，花费大量 西安t 业大学硕士学位论文 的i o 时问；又由于划分聚类算法通常需要大量的距离计算( 数据对象之间以及它们与聚 类中心之间的) ，从而导致运行时间开销较大，效率较低。这直接限制了它们在一些相关 领域中的实用性。如何对以惊人速度增长的数据量进行聚类，如何提高算法的执行效率以 及可扩展性就成为了许多算法需要解决的问题。 2 2 学生聚类分析系统简介 课题组已采用k - m e a n s 算法和自组织神经网络s o m 算法按照学生的学习成绩对学生 进行了聚类分析，并结合学生因素信息采用传统统计分析方法对影响学生学习的因素进行 了分析。本文的关联分析是建立在k - m e a n s 聚类算法基础上的。 2 2 1k - m e a n s 算法简介 k m e a n s 聚类算法是一种在无类标号数据中发现簇和簇中心的方法。选择期望的簇中 心数k ，k - m e a n s 过程反复移动中心以极小化整个簇内方差。该算法的基本思想如下： 给定一个包含n 个数据对象的数据库，以及要生成的簇的数目k ，随机选取k 个对象 作为初始的k 个聚类中心，然后计算剩余各个样本到每一个聚类中心的距离，把该样本 归到离它最近的那个聚类帆d 所在的类，对调整后的新类使用平均值的方法计算新的聚类 中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束且聚类平均误差准则函 数e 已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确，若不正确，就 要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法 中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变化。平均误差准则 函数e 定义如公式2 2 所示： e = 二删i p - m ，i ( 2 2 ) 这里e 是数据库中所有对象的平方误差的总和，p 是空间中的点，表示给定的数据样 本，m 。是簇c l 的平均值。在算法迭代的过程中e 的值在不断减小，最终收敛至一个固定 的值，同时该准则也是衡量算法是否正确的依据之一。 该算法的基本流程如下： ( 1 ) 给定大小为n 的数据集，令i ；1 ，选取k 个初始聚类中心z i ( i ) ，j = l ，2 ，3 ，k ； ( 2 ) 计算每个数据对象与聚类中心的距离d ( x i , z j ( i ) ) d ( x i ，z k ( i ) ) = m i n d ( x j ，z k ( i ) ) ，i - 1 , 2 ，3 ，n ) ( 2 3 ) 其中i = l ，2 ，3 ，n , j = l ，2 3 。k ，如果满足式2 3 则x 。w k ； ( 3 ) 计算k 个新的聚类中心 束。 z j ( i 删= 言秘 ( 4 ) 判断：若乙( i + 1 ) 粗；( i ) ，j = 1 ，2 ，3 ，k ，则i _ i + 1 ，返回( 2 ) ，否则该算法结 西安丁业人学硕十学位论文 2 2 2k - m e a n s 应用简介 课题组将k - m e a n s 算法应用到学生聚类挖掘系统中，采用k m e a n s 算法按照学生学 习成绩对学生进行聚类。通过运行k m e a n s 聚类挖掘系统，我们可以得到学生簇： 图2 1 聚类分析得到的部分簇 图2 1 中，左边簇的特点是本簇学生学习成绩总体上处于缓慢上升的阶段，且成绩基 本在平均分以上波动。右边簇的特点是本簇学生学习成绩在平均分以上缓慢波动。 课题组选取了几个典型的簇，采用了传统的统计分析技术分别对这些簇的学生的内外 部因素进行了分析，如图2 2 是采用统计分析得到的某簇学生的因素统计表。 图2 2 某簇的因素统计图 图2 2 是某簇的因素统计图，通过此图可以看出该簇中每个因素出现的次数。通过对 1 0 西安工业大学硕士学位论文 几个典型簇的分析，课题组得出学习主动性强是影响学生学习的主导因素之一。 仅仅了解影响学生学习的主导因素是不够的，我们还要深入了解某个因素对学生的影 响程度以及某个因素与其它一些因素的关联关系，即学生受某个因素影响的同时还受其它 那些因素的影响。也就是某个因素与其它哪些因素共同出现的关系，我们采用数据挖掘中 的关联挖掘来分析。 3 关联分析研究 3 关联分析研究 关联规则( a s s o c i a t i o nr u l e s ) 挖掘是数据挖掘研究领域的一个重要研究方向2 1 ，它由美 国i b ma l m a d e nr e s e a r c hc e n t e r 的r a k e s ha g r a w a l 等人于1 9 9 3 年首先提出，是描述数 据库中数据项之间存在的一些潜在关系的规则。 3 1 关联分析概念 设i = 1 1 ，1 2 ，i m ) 是项的集合，d = t l ，t 2 , ，t n ) 是一个事务数据库，其中每个事务t 是项的集合，使得t _ c i 。每个事务有一个标识符，称为t i d 。如果i 的一个子集x 满足 x c t ，则称事务t 包含项目集x 。一个关联规则就是形如x j y 的蕴涵式，xi 、y c i 、 x n y - o 。 规则x ；y 在交易数据库中的支持度( s u p p o r t ) 就是交易集中包含x 和y 的交易数与 所有交易数之比，记为s u p p o r t ( x y ) ，即s u p p o r t ( x j y ) = 1 1 t ：x u y 曼t , t d ) i | dj 。 规则x j y 在交易数据库中的置信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与包含x 的交易数之比，记为c o n f i d e n c e ( x 辛y ) ， 即c o n f i d e n c e ( xjn = l t ：x u y t ，t d ) l | t ：x c _ t ，t d i 。 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据 集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说，只有支持率和置信度 均较高的关联规则才可能是用户感兴趣、有用的关联规则。 同时满足最小支持度阈值( m i n s u p ) 和最小置信度阈值( m i n o n f ) 的规则称为强规则 ”】。关联规则挖掘的任务就是要挖掘出事务数据库d 中所有的强规则。 项的集合称为项集。包含k 个项的项集称为k 一项集。项集的出现频率是包含项集的事 务数，简称为项集的频率、支持计数或计数。项集满足最小支持度m i ns u p ，如果项集的 出现频率大于或等于m i n _ s u p 与事务数据库中事务总数的乘积。如果项集满足最小支持 度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频繁k - 项集的集合通常记作k 。 频繁项目集有如下三个性质，这些性质是所有关联规则算法的基础： 性质l ：子集支持 设a 和b 是两个不同的项目集，如果a _ c b 则s u p p ( a ) s u p p ( b ) 。因为数据库d 中 所有支持b 的交易也一定支持a 。 性质2 ：非频繁项目集的超集是非频繁的 如果a 在数据库d 中不满足最小支持度条件，即s u p p ( a ) 鱼, n i ns u p ，则a 的每一个超 集b 也不是频繁的。由性质1 可得s u p p ( b ) 盔u p p ( a ) 鱼n i n _ s u p ，因此b 也不是频繁的。 性质3 ：频繁项目集的所有非空子集都是频繁的 如果项目集b 是数据库d 中的频繁项目集，即s u p p ( b ) m i ns u p ，则b 的每个子集 1 2 西安工业大学硕七学位论文 a 也是频繁的。由性质1 可得s u p p ( a ) s u p p ( b ) a n i n _ s u p ，因此a 也是频繁的。 关联规则的挖掘是一个两步的过程： 找出所有的频繁项集：根据定义，这些项集出现的频繁性至少等于预定义的最小支 持度计数。 由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信 度。 在以上两个步骤中，第二步较容易，挖掘关联规则的总体性能由第一步决定。 3 2 关联分析分类 我们将关联规则按不同的情况进行分类： 基于规则中处理的值类型，关联规则可以分为布尔关联规则和量化关联规则。布尔 关联规则考虑的关联是项的在与不在，它显示了这些变量之间的关系；而量化关联规则可 以与多维关联或多层关联规则结合起来运用，对数值型字段进行处理，将其进行动态的分 割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如： 性别( 女) j 职业( 秘书) ，是布尔型关联规则；性别( 女) 平均收入( 2 3 0 0 ) ，涉及的收入是 数值类型，所以是一个数值型关联规则。 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关 联规则中，规则不涉及不同抽象层的项或属性；多层的关联规则可以在不同抽象层发现规 则。例如：b u y s ( i b m 台式机) j b u y s ( s o n y 打印机) ，是一个细节数据上的单层关联规则； b u y s ( 台式机) j b u y s ( s o n y 打印机) ，是一个较高层次和细节层次之间的多层关联规则。 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关 联规则中，项或属性每个只涉及一个维，如用户购买的物品；而在多维的关联规则中，规 则涉及两个或多个维。例如：啤酒j 尿布，这条规则只涉及到用户购买的物品；性别( 女) j 职业( 秘书) ，这条规则就涉及到两个属性的信息，是两维上的一条关联规则。 3 3 关联分析算法 3 3 1a p r i o r i 算法 a p f i o f i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法使用频繁项 集性质的先验知识。算法使用一种称作逐层搜索的迭代方法，k - 项集用于探索( k + 1 ) 一项集。 首先，找出频繁1 项集的集合。该集合记作l 1 ，l 1 用来找频繁2 一项集的集合k ，而b 用来找l 3 ，如此下去，直到不能找到频繁k 项集。找每个l k 需要一次数据库扫描。 a p f i o f i 性质：频繁项集的所有非空子集也都是频繁的。根据定义，如果项集i 不满 足最小支持度m i ns u p ，则i 不是频繁的，即p ( i ) m i r 。如果项a添加到i，则结果_sup 项集( 即i u a ) 不可能比i 更频繁出现。因此i u a 也不是频繁的，即p ( i u a ) m i n _ s u p a 该性质属于一种特殊的分类，称作反单调，是指如果一个集合不能通过测试，则它的所有 话安【业大学硕十学位论文 超集也都不能通过相同的测试。 a p r i o r i 算法采用了连接和剪切两步：( 1 ) 连接步：为找l k ，通过l k 1 与自己连接产生 候选k 项集的集合。该候选集的集合记作c k 。设l 1 和l 2 是k i 中的项集。记号l i j 表示 l i 的第j 项( 例如，i i k - 2 表示l l 的倒数第3 项) 。为方便计，假定事务或项集中的项按字典 次序排序。执行连接l k 1 l k - l ，其中l k 1 的元素是可连接的，如果它们前( k - 2 ) 个项相同。 即是，l k 1 的元素l l 和1 2 是可以连接的，如果( 1 l 1 卜1 2 1 ) 八( 1 1 【2 】_ 1 2 2 ) ( 1 l 3 = 1 2 1 3 ) ( 1 l k 一2 = 1 2 k 一2 ) a ( 1 l