（计算机应用技术专业论文）关联规则数据挖掘频繁项目集发现算法的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 数据挖掘是当今人工智能和数据库研究方面最富活力的领域。数据挖掘 是指从大量的数据中发现潜在的、有用的知识的过程。关联规则数据挖掘则 是数据挖掘的一个主要研究内容。而频繁项目集的发现是关联规则数据挖掘 的核心问题。 本文充分论述了典型的频繁项目集发现算法a p r i o r i 算法、a p r i o r it i d 算法，及已有的对于频繁项目集发现算法相关的改进措施的优缺点。在此基 础上，本文给出了对于频繁项目集发现算法的一些新的、有效的改进措施。 首先提出了动态自适应的方法，明显减少了事务数据库的扫描次数；其次提 出了逐渐减小事务数据库中事务记录长度的方法，大大地提高了频繁项目集 发现算法的时间效率；最后在项目集的搜索方面，根据项目集的有序性，采 用了二分法查找的方法，大大节省了系统在项目集搜索方面的时间。根据以 上所提出的改进措施，又综合已有的改进算法的优点，本文给出了一个频繁 项目集发现的新的算法a p r i o r ia u t o 算法。该综合算法在减小数据库扫 描次数、减少候选项目集的数量及提高算法用于搜索的时间效率等方面都得 到了明显的有效的改进。 关键词：数据挖掘；关联规则；a p f i o f i 算法；a p r i o r i _ a u t o 算法 哈尔滨工程大学硕士学位论文 a b s t r a c t d a t am i n i n gi so n eo ft h em o s ta c t i v er e s e a r c hf i e l d s ，e s p e c i a li nt h ef i e l d so f a r t i f i c i a li n t e l l e g i n c ea n dd a t a b a s er e a s e a r c h d a t am i n i n gi sak i n do fp r o c e s st h a t r e v e a l sp o t e n t i a lu s e f u lk n o w l e d g ef r o mm a s s i v ed a t a t h ea s s o c i a t i o nr u l e m i n i n gi sam a i nr e s e a r c ha s p e c to f d a t am i n i n g a n dt h ed i s c o v e r yo f t h ef r e q u e n t i t e ms e t si sak e yp r o b l e mo f t h ea s s o c i a t i o nr u l em i n i n g i nt h et h e s i sw ef u l l yd e s c r i b et h em o s tt y p i c a ld i s c o v e r ya l g o r i t h m so ft h e f r e q u e n ti t e ms e t s ，a p r i o r ia l g o r i t h ma n da p r i o r i _ t i da l g o r i t h m ，a n dd i s c u s st h e a d v a n t a g e sa n dt h ed i s a d v a n t a g e so fs o m ee x i s t e n ti m p r o v e dm e t h o d s b a s e do n t h e s ew o r k sw ep r e s e n ts e v e r a ln e we f f e c t i v ei m p r o v e dm e t h o d sf o rt h ed i s c o v e r y a l g o r i t h mo ft h ef r e q u e n ti t e ms e t s f i r s t ，t h ed y n a m i cs e l f - a d a p t i v em e t h o di s p r e s e n t e di no r d e rt oo b v i o u s l yr e d u c et h et i m e so fs c a n n i n g 订a n s a c f i o n sd a t a b a s e s e c o n d ，w ep r e s e n tt h em e t h o do fg r a d u a l l yr e d u c i n gt h el e n g t ho ft r a n s a c t i o n r e c o r d st oc o n s u m e d l yi m p r o v et h ee f f i c i e n c yo ft h ef r e q u e n ti t e ms e t sd i s c o v e r y a l g r o t h m a tl a s t ，o nt h ea s p e c to fs e a r c h i n gt h ei t e ms e t s ，a c c o r d i n gt ot h eo r d e r a l n a t u r eo ft h ei t e ms e t s ，t h eb i n a r ys e a r c h i n gm e t h o di sa d o p t e dt oi m p o r v et h e s e a r c h i n ge f f i c i e n c y b a s eo nt h e s en e wi m p r o v e dm e t h o d so nt h ea b o v e ，a n d f u l l yc o n s i d e r i n gt h ea d v a n t a g e so ft h ee x i s t i n gi m p r o v e dm e t h o d s ，t h ea u t h o r p r e s e n t san e wd i s c o v e r ya l g o r i t h mo ft h ef r e q u e n ti t e ms e t p r i o r i _ a u t o a l g o r i t h m t h ea l g o r i t h mh a so b v i o u sa n de f f e c t i v ei m p r o v e m e n t so nt h ea s p e c t s o fr e d u c i n gt h ed a t a b a s es c a n n i n gt i m e s ，r e d u c i n gt h ec a n d i d a t ei t e ms e t sa m o u n t a n di m p r o v i n gt i m ee f f i c i e n c yo f t h es e a r c h i n g 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 nr u l e s ，a p r i o r ia l g o r i t h m ，a p r i o r i _ a u t o a l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： ：函滏主乡 日期：0 由。厂年中月p 日 哈尔滨工程大学硕士学位论文 1 1 课题目的和意义 第1 章绪论 在激烈的市场竞争中，信息对于企业的生存和发展越来越起到至关重要 的作用，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据 库中表达信息的数据亦随着时间和业务的发展而急剧膨胀，人们需要对数据 进行更高层次的处理，从中找出规律和模式，以帮助人们更好的利用数据进 行决策和研究。目前的数据库系统虽然可以实现高效的数据录入、查询、统 计等功能，却无法发现数据中存在的关系和规则，无法根据现有的数据预测 未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据 爆炸但知识贫乏”的现象，面对“人们被数据淹没，人们却饥饿于知识”的 挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出 其强大的生命力。数据挖掘是目前国际上在数据库、数据仓库和信息决策领 域最前沿的研究方向。它已引起国内外众多学者的高度重视，成为一个具有 迫切现实需要的很有前途的热点研究课题。 数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法 构造数据模型的方式也不相同，在进行数据挖掘时可采用许多不同的方法， 例如关联规则发现、神经网络、决策树、遗传算法和可视化技术等，同时同 一方法下又有数以百计的派生方法。挖掘大型事务数据库中的关联规则是数 据挖掘研究的重要问题之一。该问题自1 9 9 3 年被a g r a w a l 等提出以来，一直 受到广泛关注与重视，提出有效的挖掘算法成了研究的热点。 对关联规则需求的产生来自于超级市场，关联规则是发现交易数据库中 不同商品( 项) 之间的联系，这些规则找出顾客购买行为模式，如购买了某一 商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货 存安排以及根据购买模式对用户进行分类。在作出这些安排之后，超级市场 就有可能提高销售量，这也就是关联规则提出和发展的原动力。 关联规则挖掘算法中一种广为人知的算法就是a p r i o r i 算法，a g r a w a l 等 人继1 9 9 3 年提出的a i s 1 1 算法后、1 9 9 4 年又提出了改进的算法即a p r i o r i 和 哈尔滨工程大学硕士学位论文 a p r i o r i t i d 2 1 。这些关联规则挖掘算法的基本思想都是基于频繁项目集的发现 算法的基础上的，即关键问题就是求满足用户指定最小支持度的项目集。而 频繁项目集发现算法的瓶颈一是候选项目集的数量，二是事务数据库的扫描 次数。本课题在研究分析a p r i o r i 算法及其已有的相关改迸措施的基础上，针 对频繁项目集的发现算法瓶颈问题，并对其在存诸空间需求、时间效率等方 面提出了有效的改进措旋，同时利用所提出的新改进措施，建立一个关联规 则数据挖掘的实验系统，利用该系统实现了频繁项目集的发现及关联规则的 挖掘。 1 2 国际国内研究现状及进展 r a g r a w a l 等人提出了关联规则的挖掘问题以后，该问题的研究得到了 长足地发展。到目前为止，其主要的研究方向有： 1 、多循环方式的挖掘算法 此类算法包括a g r a w a l 等人提出的a i s | “，a p r i o r i 、a d r i o r i t i d1 2 ，p a r k 等人提出的d h p 3 l ，s a v a s e r e 等人的p a r t i t i o n 4 1 及t o i v o n e n 提出的抽样算法 s a m p l i n g t 5 1 等等。其中最有效和有影响的算法为a p r i o r i ，d h p 和p a r t i t i o n 等。 此类算法需对事务数据库进行多次扫描，第k 次扫描时利用第k 1 次扫描产 生的结果。 2 、增量式更新算法 关联规则的增量式更新算法主要有两类： 一类是由d w c h e u n g 等人提出的f u p 【6 博法。此算法解决了最小支持度 和最小置信度不变的情况下，当一个新的事务数据集d b 添加到旧的事务数据 库d b 中时，如何生成d b u d b 中的关联规则。 另一类是由华中理工大学的冯玉才等提出的两种高效的增量式更新算法 i u a ( i n c r e m e n t a lu p d a t i n ga l g o r i t h m ) 和p i u a ( p a r a l l e li n c r e m e n t a lu p d a t i n g a l g o r i t h m ) j 。这类算法主要考虑当给定事务数据库d b 不变，在最小支持度 和最小可信度发生变化时，如何生成数据库d b 中的关联规则。因为人们在 发现关联规则时，常常需要不断地调整最小支持度和最小可信度来聚集到那 些真正令其感兴趣关联规则上，因而此类算法具有很重要的意义。 2 哈尔滨工程大学硕士学位论文 3 、并行发现算法 并行挖掘关联规则的主要算法有：a g r a w a l 等人提出的c d ( c o u n t d i s t r i b u t i o n ) 、c a d ( c a n d i d a t ed i s t r i b u t i o n ) 、d d ( d a t ad i s t r i b u t i o n ) 【8 j p a r k 等 人提出的p d m i 9 1 ，c h u e n g 等人提出的算法d m a 【州和f d m e l l l 等。 4 、多层关联规则挖掘 在许多实际应用中，由于数据库或数据仓库中的原始数据往往过于具体， 因此可能导致了许多项目集往往没有足够的支持数，因此要想在原始的概念 层次上发现强的( s t r o n g ) 和有趣的( i n t e r e s t i n g ) 关联规则是比较困难的。另外， 而用户可能关心的知识则是更为抽象的概念( 如某一类的项目) 。由于概念层 次在要挖掘的数据库中经常是存在的，因此，数据挖掘系统应提供一种在多 个抽象层挖掘关联规则的功能，并容易在不同的抽象层间转换。目前己有许 多基于概念层次的关联规则挖掘算法，如m lt 2 l 1 及其变种m lt 1 l a 、 m lt m l l 、m lt 2 l a 等【1 m 。 5 、多值属性关联规则挖掘 关联规则可分为布尔型关联规则和多值属性关联规则。多值属性又可分 为数量属性和类别属性。目前提出的挖掘多值属性关联规则的算法大多是将 多值属性关联规则挖掘问题转化为布尔型关联规则挖掘问题，即将多值属性 的值划分为多个区间，每个区间算作一个属性，将类别属性的每一个类别当 作一个属性。 6 、基于约束的关联规则挖掘 基于约束的关联规则挖掘是在提供布尔表达式约束情况下的关联规则发 现问题。这种布尔表达式约束允许用户指定他所感兴趣的关联规则的集合， 这种约束不仅可以用来对事务数据库进行预加工，而且可以把它集成在挖掘 算法内部，从而提高算法的执行效率。 7 、其它方向 除了以上列举的比较常见的研究方向外，还有其它些研究方向，如： 发现关联规则的语言、挖掘长模式和密集数据集、挖掘相关性和因果关系、 发现比例规则、发现周期和日历关联规则、挖掘多维关联规则等等。 哈尔滨工程大学硕士学位论文 1 3 课题的主要工作与论文组织 1 3 1 课题的主要工作 本课题的主要工作是： 1 、充分研究与分析频繁项目集发现算法及相关的已有的改进措施的各自 优缺点。 2 、在此基础上，针对于频繁项目发现算法的两个瓶颈问题，提出一些新 的、有效的解决措施，以提高算法效率。具体改进措施可从以下几个方面着 手： ( 1 ) 在数据库扫描方面，由算法自适应确定扫描次数，以减少数据库扫 描次数。 ( 2 ) 在求候选项目集的支持度时，通过减少数据库记录长度的方法，有 效降低事务记录的子集个数，以提高算法的效率。 ( 3 ) 在项目集的搜索方面，充分利用项目集的有序性，大幅度地提高算 法用于项目集搜索的时间效率。 3 、结合自己提出的改进措施并综合已有改进措施的优点，给出一种新的 频繁项目集发现算法。 4 、利用自己提出的新的频繁项目集发现算法，建立一个关联规则数据挖 掘实验系统。 1 3 2 论文的组织 本论文共分为五章。第一章绪论，介绍了本课题的研究目的和意义及本 课题目前国内国际的研究动态。第二章数据挖掘理论研究，介绍了数据挖掘 的相关理论与技术，包括数据挖掘的定义、数据挖掘的数据来源、数据挖掘 的分类与方法、数据挖掘的体系与步骤、数据挖掘的相关技术及其在行业中 的应用等。第三章关联规则挖掘与频繁项目集发现算法，介绍了关联规则的 挖掘的基本概念、关联规则的挖掘过程及关联规则挖掘两个典型的频繁项目 集发现算法a p r i o r i 算法与a p r i o r i t i d 算法。第四章频繁项目集发现算法 哈尔滨工程大学硕士学位论文 的改进，给出了针对频繁项目集发现算法的有效的改进措施并提出了一个新 的频繁项目集发现算法a p r i 嗵a u t o 算法。第五章基于a p r i o r ia u t o 算 法的关联规则挖掘实验系统，给出了针对于a p r o r ia u t o 算法的实验系统的 建立，包括系统的整体结构、系统主要数据结构的设计、主要算法的实现， 及系统运行说明等。最后给出的本课题研究结论。 哈尔滨工程大学硕士学位论文 第2 章数据挖掘理论研究 2 1 数据挖掘的提出与定义 2 1 1 数据挖掘的提出 随着信息技术的发展，人们收集和积累的数据越来越多，今天的我们会 发现自己陷入数据的海洋，无怪乎有人晾呼：“我们正被数据淹没，却饥渴于 知识”，在这种情况下，出现了如何从这些浩如烟海的数据中提取有用的信息， 为人们生活和社会发展的各方面提供正确决策的问题。如何才能不被信息的 汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据 真正成为一个企业的资源，只有充分利用它为企业自身的业务决策和战略发 展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。 因此面对“我们正被数据淹没，却饥渴于知识”的挑战，1 9 8 9 年8 月在 美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上首次出现 k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，知识发现或在数据库中发现知识) 这 个术语，1 9 9 5 年，在美国计算机年会( a c m ) 上，提出了数据挖掘( d m ，d a t a m i n i n g ) 概念作为知识发现过程的关键步骤，但是现在人们对于k d d 和d m 这两个概念通常不加以区别，所以往往混用。目前数据挖掘蓬勃发展，将会 越来越显示出其强大的生命力。 2 1 2 数据挖掘的定义 数据挖掘( d m ，d a t a m i n i n g ) t 1 3 1 【1 4 【l s l 【i q 就是从大量的、不完全的、有噪 声的、模糊的、随机的原始数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程。 人们把原始数据看作是形成知识的源泉，就像是从矿石中采矿一样。原 始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的， 如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的 方法可以是数学的或非数学的、演绎的或归纳的。发现的知识可以被用于信 息管理、查询优化、决策支持、过程控制等。总之，数据挖掘是一门涉及到 不同的领域，尤其是数据库、人工智能、数理统计、可视化、并行计算等学 6 哈尔滨工程大学硕士学位论文 科的交叉学科【1 7 】，如图2 - 1 所示。 图2 - 1 数据挖掘技术涉及的其它学科 数据挖掘过程就是一个利用各种分析工具在原有的、大量的数据( 数据 矿山) 中发现和建立数据间关系的模型，并用所建立的模型进行预测的过程。 但是数据挖掘所建立的模型必须要在现实生活中进行验证。因此数据挖掘工 作要做的就是使模型得到更为容易、更为方便，使其所做出的预测更为准确、 实用。 2 2 数据挖掘的数据来源 数据挖掘所依赖的数据来源多种多样，可以是常用的关系数据库、事务 数据库、文本数据库、多媒体数据库等，主要取决于用户的目的及所处的领 域i l ”。目前，数据挖掘的数据主要来源于关系数据库与数据仓库。 l 、关系数据库 随着数据库技术的飞速发展，在现有的业务系统中拥有大量的数据库， 如超市的客户购物数据库、销售部门的进、销、存数据库等。但是随着时间 的推移以及相应的业务的变化，这些数据库的数据格式会发生变化，因此在 对其进行数据挖掘时需要进行必要的整理。 2 、数据仓库 随着数据仓库技术的发展，数据仓库成为数据挖掘的一个重要的数据来 源。数据仓库中的数据在导入数据仓库时已经进行了相应的清理，数据的不 一致性问题都已经解决了，这样在进行数据挖掘就没必要再进行清理了。 通常数据挖掘都要事先把数据从数据仓库中耿到数据挖掘库或数据集市 7 哈尔滨工程大学硕士学位论文 中( 如图2 - 2 所示) 。数据挖掘库可能是数据仓库的一个逻辑子集，也可以是 一个单独建立的数据挖掘库。 图2 - 2 数据挖掘库与数据仓库结构图 3 、事务数据库 由于一个巨大的数据仓库的建立是一项巨大的工程，如果仅仅是为了数 据挖掘，通常是建立一个只读的数据挖掘库将相关的事务数据库中进来，将 其作为数据集市来进行数据挖掘( 如图2 - 3 所示) 。 同囤 图2 - 3 数据挖掘库与事务数据库 4 、高级数据库 随着数据技术的发展，数据库在各个领域得到了广泛的应用。由原形来 单一关系的数据库发展到面向对象数据库、事务数据库、空间数据库、对象 关系数据库、文本数据库、多媒体数据库。同样，数据挖掘的数据来源也可 以来源于这些类型的数据库系统。 2 3 数据挖掘所发现的知识 与数据挖掘所采用的方法相对应，数据挖掘能够发现的知识模式可分以 下5 类【1 3 】 1 3 ： 1 、广义型知识( g e n e 脚i z a t i o n ) 指类别特征的概括性描述知识。根据数据的微观特性发现其表征、带有 普遍性、较高层次概念上的、宏观的知识，是对数据的概括、精炼和抽象。 它反映了同类事物共同性质。 哈尔滨工程大学硕士学位论文 2 、关联型知识( a s s o c i a t i o n ) 反映事物之间依赖或关联关系的知识，如果多项属性问存在关联，那么 其中一项的属性值即可依据其他属性值预测； 3 、分类知识( c l a s s i f i c a t i o n & c l u s t e r i n g ) ( 1 ) 特征型知识：反映同类事物的共同性质的知识。 ( 2 ) 差异型知识：反映不同事物之间属性差别的知识。 4 、预测型知识 根据时间序列型数据，根据历史的和当前的数据推测未来数据，也可以 认为是以时间为关键属性的关联知识。 5 、偏差型知识 是对差异和极端特例的描述，揭示事物偏离常规的异常现象。如标准类 外的特例、数据聚类外的离群值等。 2 4 数据挖掘分类与方法 2 4 ，1 数据挖掘的分类 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘对象分， 有关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据库、 多媒体数据库、异构数据库、遗产数据库以及w e b 等。根据挖掘方法，可分 为机器学习方法、统计方法、神经网络方法和数据库方法，在机器学习中可 细分为：归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗传算法等。 根据开采目标可分为，数据处理、预测、回归、分类、关联分析、模型可视 化、探索性数据分析等 1 3 h 1 6 1 。应该注意的是，具体应用中可以根据数据挖 掘的不同目标和挖掘方法的不同使用情况，选择适合的方法或把不同的方法 组合使用。 2 4 2 数据挖掘方法 数据挖掘方法有多种，其中比较典型的有分类分析、聚类分析、关联分 析、序列模式分析、可视化、偏差分析、粗糙集和模糊集理论等。 9 哈尔滨工程人学硕+ 学位论文 1 、分类分析( c l a s s i f i c a t i o na n a l y s i s ) 分类分析指对数据库中的一组对象进行分析，找出其共同属性，构造分 类模型( 分类器) ，然后利用分类模型对其它的数据对象进行分类预测) 。若 预测的变量是离散的，这类问题就称为分类( c l a s s i f i c a t i o n ) ，若预测的变量 是连续的，则称之为回归( r e g r e s s i o n ) 。分类与回归都可用于预测。预测的 居的是根据历史数据记录构造出的分类模型自动推导出对原有数据的推广描 述，以实现对未来数据进行预测。 要构造分类模型，需要一个训练样本数据集作为输入，训练样本数据集 又称训练集( t r a i n i n gs e t ) 。分类可描述为：给定一训练数据的集合t ( 训练 集或训练数据库) ，t 中的元素记录出若干个属性描述。在所有属性中有且仅 有一个属性作为类别属性( c a t e g o r y ) 。属性集合用矢量x = ( x l ，x 。) 表示， 其中x ，( 1 = i ； 用c 表示类别属性，c = c i ，c k ，即数据集有k 个不同的类别。那么，t 就 隐含地确定了一个从矢量x 到类别属性c 的映射函数h ：f f x ) - c ，分类的目 的就是采用某种方法( 模型) 将该隐含函数h 表示出来。 在分类分析中，分类模型( 分类器) 的构造方法有统计方法、神经网络 方法及机器学习方法等。统计方法包括贝叶斯法和非参数法( 近邻学习或基 于事例的学习) ，对应的知识表示为判别函数和原型事例。神经网络方法主要 是多层前向神经网络的误差反向传播( e r r o r b a c k p r o p a g a t i o n ，b p l 算法【2 0 】，它 的模型表示是前向反馈神经网络模型，该算法的本质是一种非线性的判别函 数。机器学习方法包括决策树法和规则归纳法，前者对应的表示是决策树或 判别树，后者则一般为产生式规则。另外，近年来又出现了一种称为粗糙集 ( r o u g hs e t ) 新的理论方法，它将知识表示为产生式规则。 2 、聚类分析 聚类分析与分类分析不同，是把一组物理或抽象对象按相似性归为若干 类别，也称为“无监督分类”。其目的是使同一类别中的对象间的距离尽可能 小，而不同类别中又象间的距离尽可能大。对于一个很大的多维数据集，在 数据空间中数据点通常不会均匀分布，数据聚类方法可以找出稀疏和稠密的 位露，进而发现数据集的整个分布模式。当要分析的数据缺乏描述信息或者 是无法组织成任何分类模式时，利用聚类分析方法可以自动得到类别结果。 1 0 哈尔滨工程大学硕士学位论文 - - _ - _ - _ - _ _ _ - - _ _ _ - - _ _ _ - _ - _ _ _ _ - _ _ _ _ - - _ _ _ _ _ _ i i i _ - - _ _ - _ - _ _ _ 一 聚类分析采用的方法通常包括统计方法，机器学习方法和神经网络方法。 统计中的聚类分析是基于几何距离的聚类，它是一种基于全局比较的聚 类，要求所有的数据必须预先给定，而不能动态增加新的数据对蒙。对于每 一次聚类决策，它对于所有数据或己存在的聚类都同等对待而忽略其距离远 近。并且需要考察所有的对象才能决定类的划分，因此计算复杂度较高。 在机器学习中，分类学习的样本或数据对象没有类别标识，学习的样本 需要聚类学习算法自动确定。 神经网络中一种主要的聚类分析方法就是无监督自学习方法即自组织神 经网绍方法是，如k o h o n e n 【2 0 自组织特征映射方法和竞争学习网络。 聚类分析的用途很广泛。在商业上对消费者进行分类；在生物学中，可 以被用于研究生物的分类；在网络中对不同的类型文档进行分类等。聚类分 析作为数据挖掘中的一种方法，它可以单独作为一种数据挖掘工具，也以作 为其它数据挖掘算法在其他分析算法一个预处理过程。 常用的聚类分析算法有：分裂法、层次法、基于密度的方法、基于网络 的方法和基于模型的方法等。 3 、关联分析 关联分析的目的在于生成部分数据的概要。关联分析最常用的技术是关 系规则挖掘。 关联规则是于1 9 9 3 年由a g r a w a l 等人在对市场购物蓝问题( m a r k e t b a s k e t a n a l y s i s ) 进行分析时首次提出，用以发现商品销售中的顾客购买模式， 是数据中一种简单但很实用的规则。关联规则挖掘f a s s o e i a t i o nr u l em i n i n g ) 是数据挖掘研究的一个重要分支，是近年来研究较多、应用较广泛的神数 据挖掘方法。并且关联规则模式也是一种比较重要的知识模式。 关联规则挖掘的目的是挖掘隐藏在数据问的相互关系，如购物数据集中， 它能发现形如“在一次购买活动有8 0 的顾客在购买面包和黄油的同时也购 买了牛奶”的规则知识，可描述为：面包+ 黄油 牛奶，其可信为8 0 。关联 规则挖主要挖掘对象是事务数据库。其任务就是在事务数据库中找出具有用 户给定的最小支持度m i n s u p 和最小可信度m i n c o n f 的关联规则。 关联规则发现的研究趋势是从单一概念层次关联规则的发现发展到多 概念层次的关联规则的发现，即在具体应用中采掘规则可以作用到数据库不 哈尔滨工程大学硕士学位论文 同的层面上，比如在分析超市销售事务数据库过程中，从数据库原始字段如 面包、牛奶提升到更抽象的概念食品，就有可能发现更为抽象的规则： 二是通过采用减少数据库扫描次数、采样、并行数据挖掘等技术提高算法效 率。 4 、序列分析及时间序列 序列分析和时间序列说明数据中的序列信息和与时间相关的序列分析。 序列分析和关联分析相似，其目的也是为了挖掘数据之间的联系。并且 序列模式分析时同样也需要由用户输入最小置信度和最小支持度。但前者的 侧重点在于分析数据间的前后序列关系。如，它能发现数据库中形如“在某 一段时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ，”之类的 知识，即序列a b c 出现的频度较高。序列模式分析的任务就是在给定交 易序列数据库中，挖掘出在数据库中出现的高频序列。 5 、偏差分析 偏差分析技术用于抽取数据中的偏差或异常，这类偏差或异常通常包括 不适合于标准类的异常、相邻两时间段内信息的改动、处于模式边缘的冗余 等。偏差分析的一个重要特征就是它强以有效地过滤大量的不感兴趣的模式。 6 、可视化技术 可视化技术是指用图形、图像的方式来显示知识，是数据挖掘中一种很 重要的技术1 2 “。它拓宽了传统图表的功能，使用户对数据的剖析更清楚。通 过可视化技术可以把数据库中的多维数据变成多种图形，这对提示数据的状 况、内在本质及规律性起到了很大作用。 可视化数据挖掘可以分为数据可视化、数据挖掘结果可视化、数据挖掘 过程可视化和交互式数据可视化挖掘等。 7 、粗糙集方法 粗糙集理论( r o u g hs e tt h e o r y ) 1 2 2 1 用来描述知识的不精确性和不完全性。 粗糙集的一些理论和方法可用来从数据库中发现分类规则，其基本思想是将 数据库中的属性分为条件和结论属性，对数据库中的记录根据各个属性的 不同属性值分成相应的子集，然后基于条件属性划分的子集与结论属性划分 的子集闻的上下近似关系生成判定规则。 粗糙集方法与传统的统计及模糊集【2 3 1 方法不同的是它只依赖数据内部 1 2 哈尔滨_ 丁程大学硕士学位论文 的知识，用数据之间的关系表示知识的不确定性：而后者需要依赖先验知识列 不确定性进行定量描述，如统计分析中的先验概率、模糊集理论中的模糊度 等。用粗集处理不确定性问题的最大优点在于不需要数据的预先或附加的信 息，而且容易掌握。 2 5 数据挖掘的体系结构与数据挖掘的步骤 2 5 1 数据挖掘的体系结构 典型的数据挖掘系统的体系构成【1 3 l l 如图2 - 4 。其中，数据库、数据仓库 或者是其他一些信息存储媒介为数据挖掘的工作对象；数据库接口主要是响 应数据挖掘引擎的请求，提取相应的数据；应用领域知识库主要用来指导挖 掘的过程。以及用来评价挖掘出来的候选模式：数据挖掘模块是整个系统的 核心部分，包括针对各种应用而开发的挖掘子模块，如关联规则挖掘模块、 分类分析模块、聚类分析模块等；图形用户界面主要是为方便用户与数据挖 掘系统的交互，由用户提出挖掘任务、指定重要的挖掘参数以及由当前返回 的结果指导进行更进一步的挖掘工作。 图2 - 4 典型的数据挖掘系统 哈尔滨工程大学硕十学位论文 2 5 2 数据挖掘步骤 数据挖一般过程1 3 】 【1 6 1 1 8 】【1 9 】如图2 - 5 所示。 图2 - 5 数据挖掘的一般过程 数据挖掘过程不是一个线性过程，包括很多反馈回路在内，是一个多次 的循环反复的过程，每一个步骤一旦与预期目标不符，都要回到前面的步骤， 重新调整，重新执行。 数据挖掘的过程可粗略地分为：问题定义( t a s kd e f m i f i o n ) 、数据准备 ( d a mp r e p a r a t i o na n dp r e p r o c c s s i n g ) 、数据挖掘( d a t am i n i n g ) ，以及模型 解释与评价( i n t e r p r e t a t i o na n de v a l u a t i o n ) 等4 个阶段。主要步骤如下： l 、问题定义 了解应用的范围，预先准备相关的知识，了解最终用户的目标。通过对 各种挖掘算法的对比而确定可用的挖掘算法。 2 、数据准备 数据准备又可分为三个步骤：数据选择( d a ms d e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据变换与压缩( d a mt r a n s f o r m a t i o n ) 。 ( 1 ) 数据选择 1 4 哈尔滨工程夫学硕十学位论文 数据选择的目的是确定发现任务的操作对象，即目标数据，是根据用户 的需要从原始数据库中抽取的一组数据。 ( 2 ) 数据预处理 数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、 完成数据类型转换等。当数据挖掘的对象为数据仓库时，一般来说，数据预 处理已经在生成数据仓库时完成了。 ( 3 ) 数据变换与压缩 数据变换与压缩的主要目的是根据任务的目标查找有用的特征来表示数 据。即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特征 或变量个数。般方法是把数据投影到某个空间上以利于问题解决。 3 、数据挖掘 ( 1 ) 选择数据挖掘方法。根据挖掘目标，选择相应的数据挖掘方法，如 统计分析、机器学习、模式识别方法和人工神经元方法等。 ( 2 ) 选择数据挖掘算法。选择实现算法有两个考虑因素：一是不同的数 据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际系统 的要求。 ( 3 ) 数据挖掘。查找感兴趣的模式，建立模型。 4 、模型解释与评价 ( 1 ) 结果表达 将由数据挖掘阶段得出的模型，用直观的、便于用户理解和使用的方式 表示出来，可利用可视化方法表示为图表形式等。 ( 2 ) 结果评价 筛选和评价挖掘结果中的有用部分，查找可接受的结果。 ( 3 ) 知识巩固 把挖掘出的知识结合到执行系统中，了解这些知识的作用或证明这些知 识。 2 6 与数据挖掘相关技术 数据挖掘本身是多种技术的综合实现，与相关技术相互依赖又互不相同。 哈尔滨工程大学硕士学位论文 2 6 1 数据仓库 数据仓库( d a t aw a r e h o u s i n g ，d w ) 是面向主题的、集成的、不可更新的 ( 稳定性) 、随时间不断变化( 不同时间) 的数据集合，用以支持经营管理中的决 策制定过程。是一个作为决策支持系统和联机分析应用数据源的结构化数据 环境f 1 3 】【l s 】。 这个定义给出了数据仓库的四个特性： ( 1 ) 面向主题 主题是数据归类的标准，每个主题基本对应一个宏观分析领域。 ( 2 ) 集成性 数据进入数据仓库之前，必须迸数据加工和集成。即要对原始数据中的 矛盾之处进行统一，还要将原始数据结构做一个从面向应用向面向主题的主 题转变。 ( 3 ) 稳定性 指数据仓库反映的是历史数据的内容，而不是日常事务处理产生的数据， 数据经加工和集成进入数据仓库后很少修改或根本不修改。 ( 4 ) 不断变化性 数据仓库是不同时间的数据集合，它要求数据仓库中的数据保存时限能 满足进行决策分析的需要，而且数据仓库中的数据都要标明数据的历史时期。 数据仓库随时间变化不段增加新的数据内容以及删除旧的内容。 数据仓库是利用计算机和数据库技术的最新发展，把整个企业中不同地 理位置、不同存储格式和不同通信方式的数据按一定要求集成在一起，并能 把当前使用的业务信息分离出来，保证关键任务的联机事务处理应用的安全 性和完整性，同时可以访问各种各样的数据库。数据仓库不是单一的产品， 而是由软硬件技术组成的环境。它把各种数据库( 源数据库) 集成为一个统一 的数据仓库( 目标数据库) ，并且把各种数据转换成面向主题的格式，能从异 构的数据源中定期抽取、转换和集成所需要的数据，便于最终用户访问，并 能从历史的角度进行分析，最后做出战略决策。 数据仓库并非是一个仅仅存储数据的简单的信息库，而是一个“以大型 数据管理信息系统为基础，附加在这个数据库系统之上并存储了从企业所有 业务数据库中获取的综合数据并能利用这些综合数据为用户提供经过处理后 1 6 哈尔滨工程大学硕士学位论文 的有用信息的应用系统”。如果说传统数据库系统的重点是快速、准确、安全、 可靠地将数据存进数据库的话，数据仓库的重点则是能够准确、安全、可靠 地从数据库中取出数据，经过加工转换成有规律信息之后，再供管理人员使 用。 数据仓库技术更多的是一种管理技术，是当今信息管理技术的主流，是 促进企业正确管理与决策的重要决策支持工具，通常，在现有数据库的基础 上，建立和开发数据仓库就能将企业中多个数据源中的数据相集成，从而建 立企业业务的完整视图，可使经营者从历史角度更好地理解企业的行为和运 行状态，跟踪业务趋势，综合运用操作型数据和分析型数据，进行预测、分 析制定计划并做出战略决策，以利于企业的经营目标和未来的发展，并给企 业带来巨大的经济效益。 数据仓库作为一个系统，从理论上应该包含数据仓库、仓库管理和分析 工具3 个基本部分，其结构形式如图2 - 6 所示。 数据源 仓库管理 数据仓库分析工具 图2 - 6 数据仓库系统结构图 2 6 ，2 知识发现 数据库中的知识发现 1 3 】( k n o w l e d g ed i s c o v e r yi nd a m b a s e s ，k d d ) 是 于1 9 8 9 年出现的，现在比较认可的一个定义是f a y y a d 等给出的，即： 数据库中的知识发现是从数据中识别出有效的、新颖的、潜在有用的， 哈尔滨工程大学硕士学位论文 以及最终可理解的模式的高级过程。 由于数据库技术和机器学习技术的发展以及为了满足人们实际工作的需 要，数据库中的知识发现技术逐渐发展起来。一般将k d d 中进行知识学习 的阶段称为数据挖掘，它是整个数据库的知识发现过程一个非常重要的处理 步骤，的以往往两者混用。一般来说，在工程应用领域中多称数据挖掘，而 在研究领域中则多称为数据库中的知识发现。 2 6 3 联机分析处理 联机分析处理( o n l i n e a n a l y t i c a lp r o c e s s i n g ，o l a p ) 【1 3 1 1 7 】f 18 1 ，即共享多 维信息的快速分析。联机分析处理是独立于数据仓库的种技术概念，其基 本思想是公司的决策者应能灵活地操纵公司的数据，以多维的形式从多方面 和多角度来观察公司的状态并了解公司的变化。数据挖掘与联机分析处理都 属于分析型工具，但两者有关明显的区别。数据挖掘是一种挖掘型工具，它 能自动地、有效地从大量数据中发现潜在的数据模式，作出预测性分析，它 是现有的一些人工智能、统计学等成熟技术在特定的数据库领域中的应用。 而联机分析处理是一种自上而下、不断深入的分析工具。由用户提出问题或 假设，o l a p 从上至下深入地提取关于该问题或假设的详细信息。 2 6 4 客户关系管理 数据挖掘在客户关系管理( c u s t o m e r r e l a t i o n s h i p m a n a g e m e n t ，c r m ) 的 应用，能够提高企业的商业智能，能够为企业获得可靠的信息支持策略和商 业决策，提高企业的竞争优势。 文献【1 3 】【2 4 1 给出了数据挖掘在c r m 中的应用领域，包括三个方面： ( 1 ) 通过预测客户保留度，保留好的客度； ( 2 ) 通过建立交叉销售模型，标识下一步策略： ( 3 ) 通过建立标识模型，获得潜在客户。 一个好的c r m 系统结构如图2 7 所示，由此也可以看出数据挖掘在c r m 中的应用关系。数据挖掘是客户关系管理的主要工具，可以独立作为工具， 也可以嵌入在c r m 或数据仓库的展示工具中。 哈尔滨工程大学硕士学位论文 图2 7c r m 系统结构图 2 6 5 与数据挖掘的其它相关技术 另外数据挖掘与人工智能技术、统计分析技术等都有着相应的联系。这 两门学科也都是致力于模式发现和预测。数据挖掘就是利用了统计分析和人 工智能技术的算法及技术，把这些高深复杂的技术封装起来，使人们不用自 己掌握这些技术也能完成同样的功能，并且更专注于自己所要解决的问题。 数据挖掘与这两者的区别主要在于算法对大数据量的适应性，数据挖掘 的算法必须面对大数量数据( 如数1 0 万条记录以上) 有很好的性能。另外数 据挖掘是面向解决工程问题的。 2 7 数据挖掘在行业中的应用 在各个领域，人们已经认识到了数据挖掘技术带来的应用前景。 数据挖掘技术以及应用此技术所获得知识和信息可以被广泛的应用于科 学研究、