（计算机软件与理论专业论文）聚类算法研究及在客户忠诚度分析中的应用.pdf

摘要 y s 毛乏7 3 i 随着信息技术l l l 勺高速发展，数据库应用的规模、范固和深度不断扩大，积累了 大量的数据，这些数据仅仅依靠数据库的查询检索机制已经远远不能满足现实需要， 数据挖掘正是为迎合这种需要而产生并迅速发展起来的一种新的数据处理技术。数 据挖掘( d a t am i n i n g ) ，也称数据库的知识发现( 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 ) 是 指从大量的原始数据中挖掘出隐含的、有用的、尚未发现的知识和信息，聚类分析 是数据挖掘的重要组成部分。所谓聚类，是将一个数据单位的集合e 数据源) 分割成 几个称为簇或类别的子集。聚类分析是根据事物本身的特性研究对被聚类对象进行 类别划分的方法。聚类分析依据的原则是使同一聚簇中的对象具有尽可能大的相似 性，丽不同聚簇中的对象具有尽可能大的相异性，聚类分析主要解决的问题是如何 在没有先验知识的前提下，实现满足这种要求的聚簇的聚合。 由于聚类分析在现实数据处理中的重要性和特殊性，近年来在该领域的研究取 得了长足的发展，涌现出了许多聚类分析的方法，如基于划分( p a r t i t i o n - b a s e d ) 的聚 类方法、基于层次( h i e r a r c h i c a l b a s e d ) 的聚类方法、基于密度( d e n s i t y b a s e d ) 的聚类 方法、基于网格( g r i d b a s e d ) 的聚类方法、基于模型( m o d e l b a s e d ) 的聚类方法等等。 这些方法所涉及的领域几乎遍及人一c 智能科学的方方面而，丽且在特定的领域中、 特定的情形下取得了良好的效果。但是当处理数据为大数据量、具有复杂数据类型 的数据集合时，则仍存在若干尚来解决的问题，主要基于聚类分析方法进行了研究， 主要：【作包括： 1 、聚类分析结果的精确性问题。聚类结果的精确性是指聚类分析对原始数据集 进行划分后，箨予类别闸边界的明确性及各被聚类对象所属类别的准确性。现有聚 类算法往往对较小的数据集聚类精度较高，丽一旦数据对象增多，往往得不到令人 满意的聚类结果。所以，本文就如何提高聚类算法的聚类准确性进行了研究。 2 、时问复杂度和空间复杂度过大的问题。由于数据集中数据的增大和数据复杂 性的提高，数据挖掘算法无论是从算法运算的时问上，还是从算法本身所需要的存 储空问上都急剧的膨胀，使得在现有资源下很难实现数据集的最终聚类。本论文在 对各类算法深入分析的基础上，选取一种复杂度较低的算法进行了现实数据中较大 数据集的聚类尝试。 3 、基于层次的聚类方法的改进。在聚类分析方法中，基于层次的方法是处理较 大数据集中鞍为常用的方法之一，该类方法在有限的资源( 如内存、c p u ) 下，通过 采用定的算法结构，得到尽可能好的聚类结果。但是该类算法不足之处在于阈值 收敛速度过慢，对任意形状的聚类结果较差，从而给该方法的应用带来了障碍。本 文提出了针对基于层次方法的改进。 4 、聚类结果可视化的解决方案。信息可视化是当前人机交互进行数据挖掘的前 提，由1 ：数据集合规模的不断扩大，如何将高维数据通过二维空问表示出来，并简 洁的、有效的为用户提供一个数据的可视化界而成为研究热点。本文就在数据挖掘 尤其是聚类结果可视化方面存在的问题进行了深入的分析和阐述，并且给出了相应 的解决方案。 本论文的组织结构为：第一章为引言，进行背景知识介绍，阐述了数据仓库和 数据挖掘的基本概念以及数据挖掘所包含的主要内容；第二章重点论述了聚类数据 挖掘的方法及评价标准，对各类算法进行总结评价；第三章面列较大数据集对现有 的层次聚类算法中存在的缺点提出相应的解决方案，在不增加算法复杂度的基础上， 提高算法的聚类精确性；第四章阐述了聚类结果可视化，对现有数据挖掘中数据可 视化技术存在的问题进行总结，最后给出一种在二维空问中表示多维数据的方法， 应用于聚类结果的可视化；第五章采用聚类分析和分层可视化对海尔销售数据进行 聚类分析，帮助决策层区分不同的客户群，从而制定相应的服务政策：第六章对提 出的设计进行简要的评述，对该沦文所作的研究 一作做出总结，并阐明今后课题的 主要研究方向。 关键词：数据挖掘，聚类分析，聚类特征，簇，信息可视化，平行坐标 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，t h es c o p e so fd a t ab a s ea p p l i c a t i o n b e c o m e sm o r ea n dm o r ew i d e ，t h ed a t a b a s eq u e r yc a nn o td e a lw i t ht h eh u g eq u a n t i t y d a t a ，d a t am i n i n ge m e r g e sa n dd e v e l o p s ，w h i c hi s u e wd a t aa n a l y s i st e c h n o l o g ya n d h e l p st h ed e c i s i o n - m a k e rt om a k es e r v i c ep o l i c y d a t am i n i n g ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) m e a n st h a t t h ek n o w l e d g ea n di n f o r m a t i o ni sd i s c o v e r e df r o mt h ed a t a s e t ， w h i c hi sc o n n o t a t i v e ，u s e f o la n du n d i s c o v e r e d c l u s t e r i n ga n a l y s i si sa ni m p o r t a n tp a r to f t h ew h o l ed a t am i n i n gs y s t e m c l u s t e r i n gi st h ep r o c e s so f g r o u p i n gt h ed a t ai n t oc l a s s e s o rc l u s t e r ss ot h a to b j e c t sw i t h i nt h es a m ec l u s t e rh a v eh i g hs i m i l a r i t yi nc o m p a r i s o nt o o n ea n o t h e r ，b u ta r e v e r yd i f f e r e n tt oo b j e c t si no t h e r c l u s t e r s d i s s i m i l a r i t i e sa r ea s s e s s e d b a s eo nt h ea t t r i b u t ev a l u e sd e s c r i b i n gt h eo b j e c t s c l u s t e r i n gp r o c e s s e sa r ea l w a y sc a r r i e d o u ti nt h ec o n d i t i o nw i t h o u t p r e - k n o w nk n o w l e d g e ，s ot h em a i n t a s ki st os o l v et h a th o w t og e tt h ec l u s t e r i n gr e s u l ti nt h i sp r e m i s e b e c a u s eo ft h ei m p o r t a n c ea n ds p e c i a l i z eo f t h ec l u s t e ra n a l y s i si nd a t am a n a g e m e n t ， t h er e s e a r c hi nt h i sf i e l dg e tag r e a ta d v a n c e m e n ti nr e c e n ty e a r s ，an u m b e ro fc l u s t e r i n g a l g o r i t h m sh a sb e e nf o u n d e d ，i ng e n e r a l ，m a j o rc l u s t e r i n gm e t h o d sc a nb ec l a s s i f i e di n t o t h ef o l l o w i n g c a t e g o r i e s ：p a r t i t i o n i n gm e t h o d s ，h i e r a r c h i c a lm e t h o d s ，d e n s i t y b a s e d m e t h o d s ，g r i d b a s e dm e t h o d s ，m o d e l - b a s e dm e t h o d s ，b e s i d e st h e s e ，s o m ec l u s t e r i n g a l g o r i t h m si n t e g r a t et h ei d e a so fs e v e r a lc l u s t e r i n gm e t h o d s a l t h o u g ha l l t h e s em e t h o d s h a v eg o tg r e a ta c h i e v e m e n ti nd i f f e r e n tf i e l d s ，t h e s em e t h o d sa l lm e e td i f f i c u l t i e sw h e n p r o c e s s i n gh u g eq u a n t i t y d a t a s e t s oi nt h i s p a p e rw ea n a l y s i st h er e a s o n t oc l u s t e r a n a l y s i s ，a n dg i v et h ed e t a i lr e s o l v e n t s t h ef o l l o w i n gp r o b l e m s w i l lb ed i s c u s s e d ： 1 t h ea c c u r a c yo ft h ec l u s t e r i n ga l g o r i t h m ：t h ea c c u r a c yo ft h ec l u s t e r i n gm e t h o d s r e f e r st ot h ep a r t i t i o n i n ga c c u r a c ya n dd e s t i n a t i o no ft h eo r i g i n a ld a t as e t i ti se a s yf o r p r e s e n tc l u s t e r i n ga l g o r i t h mt op r o c e s st h ed a t as e tw i t hr e g u l a rp a r t i t i o n i n gc h a r a c t e r s ， b u ti ti su n s a t i s f i e dw i t hh u g eq u a n t i t yd a t as e tf o rp r e s e n ta l g o r i t h m s ot h i sp a p e rw i l l d i s c u s st h a th o wt oe n h a n c et h ec l u s t e r i n ga l g o r i t h m s a c c u r a c y 2 r h el a r g ec o m p l e x i t yo ft i m ea n d s p a c ec o n s u m i n g b e c a u s eo f t h eh u g e q u a n t i t y a n dh i g hc o m p l e x i t yo ft h eo r i g i n a ld a t as e t ，d a t am i n i n gn e e d sm o r ea n dm o r et i m ea n d m e m o r y t od e a lw i t ht h e s ed a t as e t s i ti sn o ta c c u r a c yi nl i m i t e dr e s o u r c e b a s e do nt h e c l u s t e r i n ga l g o r i t h m sa n a l y s i s ，t h i sp a p e rs e l e c t sa c l u s t e ra l g o r i t h mw i t hl o w c o m p l e x i t y t od e a lw i t hh u g e q u a n t i t yd a t a s e t 3 a m e l i o r a t i o no fh i e r a r c h i c a l b a s e dm e t h o d t h eh i e r a r c h i c a l b a s e dm e t h o di so n e o ft h ec l u s t e r i n g a n a l y s i sm e t h o d st o d e a lw i t h b i gs i z e d a t as e t s w i t ht h el i m i t e d i r e s o u r c e ，s u c ha sm e m o r y , c p u ，a n ds oo n ，i tc a ng e tt h eb e s tc l u s t e r i n gr e s u l tb y u s e s o m ea l g o r i t h ms t r u c t u r e b e c a u s eo fs l o w l yi nc l u s t e r i n gr e s u l t ，c o n v e r g e n t ，a n dp o o ri n c l u s t e r i n g r a n d o md a t as e t s ，t h e r ea r es o m eo b s t a c l e si nu s i n g s o m ea l g o r i t h m sf o r h i e r a r c h i c a l b a s e dm e t h o di sd i s c u s s e di nt h i sp a p e r 4 c l u s t e r i n gr e s u l tv i s u a l i z a t i o n i n f o r m a t i o nv i s u a l i z a t i o ni st h ep r e c o n d i t i o nf o r h u m a nc o m p u t e ri n t e r a c t i o nt od a t am i n i n g b e c a u s eo ft h ed a t as e t se x t e n d ，i ti sah o t p o t t h a th o wt oe x p r e s st h eh i g hd i m e n s i o n a l i t yd a t ai n2 - d i m e n s i o n a l i t ys p a c e ，a n dp r o v i d ea c o m p a c ta n de f f e c t i v ev i s u a l i z a t i o ni n t e r f a c ef o rt h eu s e ea d e t a i la n a l y s i sa n de x p a t i a t e f o rt h ec l u s t e r i n gr e s u l tv i s u a l i z a t i o nj sg a v ei nt h i sp a p e l t h i st h e s i sc o n s i s t so fs i xs e c t i o n s c h a p t e ro n ed e p i c t st h eb a c k g r o u n dk n o w l e d g e a n di l l u s t r a t e st h em o s ti m p o r t a n tc o n t e n ti nd a t am i n i n g c h a p t e rt w od e s c r i b e st h e m e t h o da n dc r i t e r i o no fc l u s t e r i n ga n a l y s i s ，a n da p p r a i s e st h ec l u s t e r i n ga l g o r i t h m s c h a p t e rt h r e eg i v e a l la m e l i o r a t i o no ft h eh i e r a r c h i c a l b a s e da l g o r i t h mf o rt h eh u g e q u a n t i t yd a t as e t s ，i te n h a n c e t h ea c c u r a c ya n dn o ta d da l g o r i t h mc o m p l e x i t y c h a p t e rf o u r d i s c u s s e st h ec l u s t e r i n gr e s u l tv i s u a l i z a t i o n ，m a k es u m m a r i z ef o rd a t av i s u a l i z a t i o n ，i n t h i sc h a p t e rw eg i v eam e t h o dt od e s c r i p th i g hd i m e n s i o n a l i t yd a t ai n2 - d i m e n s i o n a l i t y s p a c e ，a n du s ei t i nc l u s t e r i n gr e s u l tv i s u a l i z a t i o n c h a p t e rf i v eg i v e sc u s t o m e rc l u s t e r a n a l y s i so f h a i e rw h i c hb a s e do nt h em b i r c i - ia l g o r i t h ma n dh i e r a r c h i c a lv i s u a l i z a t i o n ， i th e l d st h ed e c i s i o n m a k e r se s t a b l i s hd i f f e r e n ts e r v i c e sf o rd i s s i m i l a rc u s t o m e rc l u s t e r s c h a p t e r s i x g i v e s t h ea n n o t a t i o no ft h ed e s i g n ，s u m m a r i z et h e r e s e a r c hw o r k ，a n d i l l u s t r a t et h ef u t u r er e s e a r c hw o r k k e y w o r d s ：d a t am i n i n g ，c l u s t e r i n ga l g o r i t h m ，c l u s t e r i n gf e a t u r e ，c l u s t e r , i n f o r m a t i o n v i s u a l i z a t i o n ，p a r a l l e lc o o r d i n a t e i i 第一章绪论 第一童绪论 随着计算机与信息技术的发展，在支配人类社会三大要素( 能源、材料和信息) 中，信息愈来愈显示出其重要性和支配性，而随着人类活动范围扩展，节奏加快， 以及技术的进步，人们能以更快速容易而廉价的方式获取和存储数据，这就使得数 据和信息量以指数形式向上增长，如何有效的对现有数据进行管理，如何通过已有 的历史数据预测未来的行为，或者说从这些海量数据中发现知识。这一切导致了数 据仓库和数据挖掘领域的出现“”。 1 1 选题背景与研究意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据 越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层 次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录 入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数 据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸 但知u 贫乏”的现象。1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能联合 会议的专题讨论会上首次出现数据库的知识发现( k d d ) 这个术语”“1 。 1 1 1 数据挖掘定义 数据挖掘( d a t am i n i n g ) ，也称数据库的知识发现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ) 是指从大量的原始数据中挖掘出隐含的、有用的、尚未发现的知识和信息 ”。1 。而更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中寻找模式 的决策支持过程。数据挖掘作为一门交叉性学科，涉及到机器学习、模式识别、统 计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。 从数据库巾发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等 许多方面。随着对这种技术进行支持的三种基础技术海量数据集、强大的多处 理器讨算机、数据挖掘算法的逐渐成熟，数据挖掘技术的研究也进入了一个迅猛发 展的时期。 1 1 2 数据挖掘的一般过程 有时人们把数据挖掘作为数据库的知识发现的同义词，而另一部分人只是把数 i 黾一钐一向碟一舒 图1 1 数据挖掘的般过程 ( 1 ) 数据预处理 k d d 的处理对象是大量的数据，这些数据一般存储在数据库系统中，是长期积 累的结果。但往往不适合直接在这些数据上面进行知识挖掘，需要做数据准备工作。 般来说针对源数掘进行的数据准备主要包括三方而的内容： 1 ) 数据选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据 挖掘应用的数据。 2 ) 数据清理 现实世界的数据一般是脏的、不完整的和不一致的。数据清理例程试图填充 空缺的值，识别孤立点、消除噪声，并纠正数据中的不一致。 3 ) 数据转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的，建立一 个真币适合挖掘算法的分析模型是数据挖掘成功的关键。 4 ) 数据归约 数据归约得到数据集的压缩表示，它通常比原数据集小得多，数据归约必然 会损失数据集中的部分信息，当损失的信息与挖掘目的相关性不大时，采用归 约后的数据集能够产生同样的( 或j l 乎同样的) 分析结果。 数据预处理是k d d 的第一个步骤，也是比较重要的一个步骤。数据准备是否做 好将影响到数据挖掘的效率和准确度以及最终模式的有效性。 ( 2 ) 数据挖掘 数据挖掘是k d d 最关键的步骤，也是技术难点所在。研究k d d 的人员中大部 分都在研究数据挖掘技术，采用较多的技术有决策树、分类、聚类、粗糙集、关联 规则、神经网络、遗传算法等。数据挖掘根据k d d 的目标选取相应算法的参数， 分析数据，得到可能形成知i = 的模式模型。 ( 3 ) 评估、解释模式模型 筇一帝缔论 上面通过数据挖掘得到的模式模型，有可能是没有实际意义或没有实用价值的， 也有可能是其不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的， 因此需要评估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验， 有些模式也可以直接用数据来检验其准确性。这个步骤还包括把模式以易于理解的 方式呈现给用户。 ( 4 1 巩固知识，运用知识 用户理解的、并被认为是符合实际和有价值的模式模型形成了知识。在发现知 识的同时还要注意对知识做一致性检查，解决与以i j 得到的知识互相冲突、矛盾的 地方，使知识得到巩固。发现知识是为了运用，如何使知识能被运用也是k d d 的 步骤之一。运用知识有两种方法：一种是只需看知识本身所描述的关系或结果，就 可以对决策提供支持；另一种是要求对新的数据运用知识，由此可能产生新的问题， 而需要对知识做进一步的优化。 k d d 过程可能需要多次的循环反复，每个步骤一旦与预期目标不符，都要回 到前面的步骤，重新调整重新执行。 1 1 3 数据挖掘的分类 由于数据挖掘源于多个学科，因此数据挖掘研究产生了大量的、各种不同类型 的数据挖掘系统。因此，就需要对数据挖掘系统给出一个清楚的分类。其中，根据 挖掘知识类型，可以分为关联分析、分类和预测、聚类分析、特征化和区分、孤立 点分析、演变分析等等”。 特征提取 特征提取日的是对数据进行浓缩，给出它的紧凑描述。作为一种数据挖掘任务， 特征提取不是数据的简单枚举，而是产生数据的特征化和比较描述，其中的特征化 提供给定数据汇集的简洁汇总，而概念或类的比较则提供两个或多个数据汇集的比 较描述。 关联分析 关联分析是指在数据库的记录或对象问抽取关联性。它展示了数据间未知的依 赖关系。根据这种关联性就可从任数据对象的信息来推断另一数据对象的信息。 关联性是一种统计意义上的关系，并以黉信度因子衡量关联的程度。因此，为了发 现出有意义的关联规则，需要给定两个闽值：最小支持度和最小可信度。目前，关联 分析研究已经从单概念层次关联规则的发现发展到多个概念层次的关联规则的发 现。 分类分析 分类是最基木的一种认知形式。数据分类就足对数掘集中的每一类数据，挖掘 第一章绪论 出关于该类数据的捕述或模型。而这些数据库中的类是事先利用训练数据建立起来 的。作为数据挖掘的个重要主题、数据分类在统汁学、机器学习、人工智能等领 域中得到了较早的研究，只是近些年来，人们才将它与数据库技术结合起来解决实 际问题。在数据挖掘中，分类算法的研究成果较多，常用的数据分类算法有：c a r t ， c 4 5 ，i d 3 ，s l i q 等。 - 聚类分析 在机器学习中，数据分类称为监督学习，而数据聚类则称为非监督学习，两者 所采用的方法相差甚远。数据聚类是将物理的或抽象的对象分成几个群体，在每个 群体内部、对象之问具有较高的相似性，而在不同的群体之间，相似性则比较低。 一般地，一个群体也就是一个类，它与数据分类不同的是，聚类结果主要基于当前 所处理的数据，我们事先并不知道类目结构及每个对象所属的类别。另外，数据聚 类计算量巨大，其时间复杂度也要比数据分类大很多。在第二章我们会对聚类的相 关问题进行详细的讨论。 在解决实际问题时，经常要同时使用多种模式。分类分析和特征提取是使用最 普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因为在 建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的产生是 在受髓督的情况下进行的。一般在建立这些模式时，使用一部分数据作为样本，用 另一部分数据来检验、校正模式。聚类分析、关联分析、序列模式分析则是非监督 知识，因为在模式建立前结果是未知的，模式的产生不受任何监督。 1 2 国内外研究现状 k d d 一词首次 王；现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上。 迄今为l i ：，由美国人：l ：智能协会主办的k d d 国际研讨会已经召丌了7 次，规模由原 来的专题讨论会发展到国际学术大会，人数由二三卜人到七八百人，论文收录比例 从2 x 1 到6 x 1 ，研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略 和技术的集成，以及多种学科之问的相互渗透。其他内容的专题会议也把数据挖掘 和知识发现列为议题之一，成为当前计算机科学界的一大热点。此外，数据库、人 工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专 刊。 1 9 9 7 年亚太地区在新加坡细织了第一次规模较大的p a k d d 学术研讨会，很有特 色。从1 9 9 7 开始已经连续五年召丌数据仓库予数据挖掘年会。此外，数据库、人工 智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。 在国外列数据挖掘技术进行深入研究的同时，国内也相继开展了对k d d 的研究。 第一章绪论 但这些研究的工作主要集中，二应用上，理论l 的研究较少，还有待人工智能和数据 库技术人员的j 泛参与。 就目前为止，数据挖掘应用方面的商品工具和软件，大致可以归纳为下列主要 类型： 传统主观导向系统：这是针对专业领域应用的系统，如基于技术分析方法对金 融市场进行分析。采用的方法从简单的走向分析商到基于高深数学基础的分形理论 和谱分析。这种技术需要有经验模型为前提属于这类商品有美国的m e t a t a k ，s u p e r c h a f f s c a n d l e s t i c kf o r e c a s t e r 和w a l ls t r e e tm o n e y 等。 传统统计分析：这类技术包括相关分析、回归分析及因子分析等。一般先由用 户提供假设，再山系统利用数据进行验证。缺点是需经培训后才能使用，同时在数据 探索过程中，用户需要重复进行一系列操作。属于这类商品有美国的s a s 。s p s s 和 s t a r g r a p h i s 等。由于近年来更先进的d m 方法的出现和使用，这些厂商在原有系统中 综合一些d m 部件，以获得更完善的功能。以上两科t 技术主要基于传统的数理统计和 数学的基础上，早已开始用于数据分析方而。 神经元网络( n n ) 技术：神经元网络技术是属于软计算( s o f t c o m p u t i n g ) 领域内一 种重要方法，它是多年来科研人员进行人脑神经学习机能模拟的成果，已成功地应 用于各y _ q k 部门。在d m ( k d d ) 的应用方面，当需要从复杂或不精确数据中导出概念 和确定走向比较困难时，利用神经网络技术特别有效。n n 有多种结构，但最常用 的是多层b p ( b a c kp r o p a g a t i o n ) 模型。它已广泛地应用于各种d m ( k d d ) s e 具和软件 中。有些是以n n 为主导技术，例如俄罗斯的p o l ya n a l y s t ，美国的b r a i nm a k e r , n e u r o s e l l 和o w l 等。n n 技术也已广泛地作为一种方法嵌入各种d m 成套软件中。 其缺点是用它来分析复杂的系统诸如金融市场，n n 就需要复杂的结构为数众多神 经元以及连接数，从而使现有的事例数( 不同的纪录数) 无法满足训练的需要。另外 由受训后的n n 所代表的预测模型的非透明性也是其缺点，尽管如此，它还是广泛 而成功地为各种金融应用分析系统所采用。 决策树：在知识工程领域，决策树是种简单的知识表示方法，它将事例逐步 分类成代表不同的类别。由于分类规则是比较直观的，因而比较易于理解，这种方法 一般限于分类任务。在系统中采用这种方法的有美国的i d l s ，法国的s i p i n a 。英 国的c l e m e n t i n c 和澳大利亚的c 5 0 。 进化式程序设计( e v o l u t i o n a r yp r o g r a m m i n g ) ：这种方法的思路是：系统自动生 成有关目标变量对其他多种变量依赖关系的假设，并形成以内部编程语言表示的程 序。内部程序( 假设) 的产生过程是进化式的，类似于遗传算法过程。当系统找到较 好地描述依赖关系的一个假设n _ j ，就对这程序进行各种不同的微小修正，生成予程 序组，再在其巾选择能更好地改进预测精度的子程序，如此依次进行，最后获得达 箫。章绪论 到所需精度的最好程序兀寸，由系统的专有模块将所找到的依赖关系由内部语言形式 转换成易于为人们理解的显式形式，如数学公式，预测表等。由于采用通用编程语 言，这种主法在原则上能保证任何一啼 依赖关系和算法都能用这种语言来描述。这 种方法的商用产品还只见诸俄罗斯的p o l y a n a l y s t 。该没计在金融和医疗方面的应用 都获得了很好的结果。 基于事例的推理方法( c b r c a s e b a s e dr e a s o n i n g ) ：这种方法的思路非常简单， 当预测未来情况或进行正确决策时，系统寻找与现有情况相类似的事例，并选择最 佳的相同的解决方案，这种方法能用于很多问题求解，并获得好的结果，其缺点是 系统不能生成汇总过去经验的模块或规则。采用这种方法的系统有美国的p a t t e r n r e c o g n i t i o nw o r k b e n c h 和法国的k a t e t o o l s 。 遗传算法( g a - - g e n e t i e a l g o r i t h m s ) ：严格说束，d m 不是g a 应用的主要领域， 它是解决各种组合或优化问题的强有力的手段，但它在现代标准仪器表中也用来完 成d m 任务。这种方法的不足之处是：这种问题的生成方式使估计所得解答的统计 意义的某一种机会不再存在。另外一方面，只有专! l k 人员才能提出染色体选择的准 则和有效地进行问题描述与生成。在系统中包含遗传算法的有美国的g e n e h u n t e r 。 非线性回归方法：这种方法的基础是，在预定的函数的基础上，寻找目标度量 对其它多种变量的依赖关系。这种方法在金融市场或医疗诊断的应用场合，比较好 的提供可信赖的结果。在俄罗斯的p o l y a n a l y s t 以及美国的n e u r o s h e l l 系统中包括了 这种技术。 上面所列d m 技术不可能是详尽的囊括，因为多年来数理统计分析以及a i 的研 究提供了种类繁多特点各异的手段，d m 开发人员完全可以根据不同任务加以选择 使用，另外近年来在软计算( s o f tc o m p u t i n g ) 和不确定信息处理( d e a l i n gw i t h u n c e r t a i n t yo fi n f o r m a t i o n ) 方法的研究，促使d m ( k d d ) 技术向更深层次发展。 上面所列举的d m 方法主要是针对表格形式数据库的处理，它通过记录和条目 的方式组织在一起，这种数据称作结构型数据( s t r u c t u r e dd a t a ) 。在实际应用中，还 有一类像文本和网页形式的数据，称作非结构型数据( u n s t r u c t u r e dd a t a ) 。它来自不 同的信息源，如文本图像影视和音响等，当然文本是最主要的一种非结构数据。1 9 9 5 年分析家已预言，像文本这样非结构型数据将是彳1 蛾存贮方面占支配地位的数据形 式。到1 9 9 8 年初，在i n t e r n e t 上的信息网页数，已超过5 亿。随着i n t e r n e t 的扩展 和大量在线文本的出现，将标志这巨大的非结构型数据海洋中，蕴藏着极其丰富的 有用信息即知识。人们从书本巾获取知识方法是阅读和理解。开发一种工具能协助 用户从非结构数据中抽取关键概念以及快速而有效地检索到关心的信息，这将是一 个非常引人入胜的研究领域。日前，基于图书索引检索以及超文本技术的各类搜索 引擎，能协助用户寻找所需信息，但要深入发掘这类数据中的有用信息，尚需要更 第章绪论 高层次的技术支持，人1 ：智能领域有关知识表示及获取的方法( 如语义网络概念映射 等) ，以及自然语言理解的研究成果，可望被采用。除此之外还可能要涉及到语言学 心理学等领域。目前已日 现针对文本的d m 二1 ：具，如i b m 公司的t e x tm i n e r ，n e t q u e s t i o n ，w e dc a w l e r 和m e g a p u t e r 公司的t e x ta n a l y s t 等。 1 3 研究内容目标 随着数据仓库和数据挖掘技术的f _ i 益发展，数据挖掘技术研究目标主要集中在 一下几点： 1 、处理不同类型数据 绝大多数数据库是关系型的，因此在关系数据库上有效地执行数据挖掘是至关 重要的。但是在不同应用领域中存在各种数据和数据库，而且经常包含复杂的数据 类型，例如结构数据、复杂对象、事务数据、历史数据等。由于数据类型的多样性 和不同的数据挖掘日标，一个数据挖掘系统不可能处理各种数据。因此针对特定的 数据类型，需要建立特定的数据挖掘系统。 2 、数据快照和时问戳 现实数据席通常是庞人、动态、不完全、不玳确、冗余和稀疏的，这给知识发 现系统提出了许多难题。数据库中数据的不断变化造成先前发现的知识很快过时， 利用数据快照和时间戳方法可解决这问题。前者特别适用于阶段性搜集的数据， 但需要额外空问存储快照。数据的不准确性使知识挖掘过程需要更强的领域知识和 更多的抽样数据，同时导致发现结果的不正确：不完全数据包括缺少单个记录的属 性值或缺少关系的字段：重复出现的信息称为冗余信息，为避免将对用户毫无意义 的函数发现作为知识发现的结果，系统必须了解数据库的固有依赖。另外数据的稀 疏性和不断增加的数据量增加了知识发现的难度。 3 、数据挖掘算法的有效性和可测性 海量数据库通常有上百个属性和表及数百万个元组。g b 量级数据库已不鲜见， t b 量级数据库已经出现，高维大型数据库不仅增大了搜索空间，也增加了发现错误 模式的可能性。因此必须利用领域知识降低维数，除去无关数据，从而提高算法效 率。从个大型数据库中抽取知识的算法必须商效、可测量，即数据挖掘算法的运 行时问必须可预测，且可接受，指数和多项式复杂性的算法不具有实用价值。但当 算法用有限数据为特定模型寻找适当参数时，有时会导致物超所值，降低效率。 4 、交互性用户界面 数据挖掘的结果应准确地描述数据挖拥的要求，并易于表达。从不同的角度考 察发现的知识，并以不同形式表示，用高层次语言和图形界面表示数据挖掘要求和 第一章绪论 结果。目前许多知识发现系统和工具缺乏与用户的交互，难以有效利用领域知识， 对此可以利用贝叶斯方法和数据库本身的演泽能力发现知识。 5 、在多抽象层上交互式挖掘知识 很难预测从数据库中会挖掘出什么样的知识，因此一个高层次的数据挖掘查询 应作为进一步探询的线索。交互式挖掘使用户能交瓦地定义一个数据挖掘要求，深 化数据挖掘过程，从刁i 同角度灵活看待多抽象层i ：i 6 j 数据挖掘结果。 6 、从不同数据源挖掘信息 局域网、。域网以及i n t e r n e t 网将多个数据源联成一个大型分布、异构的数据库， 从包含不同语义的格式化和非格式化数据中挖掘知识是对数据挖掘的一个挑战。数 据挖掘可以揭示大型异构数据库中存在的普通查询不能发现的知识。数据库的巨大 规模、广。泛分布及数据挖掘方法的计算复杂性，要求建立并行分布的数据挖掘。 7 、私有性和安全性 数据挖掘能从不同角度、不同抽象层上看待数据，将影响到数据挖掘的私有性 和安全性。通过研究数据挖掘导致的数据非法侵入，可改进数据库安全方法以避 免信息泄漏。 8 、和其它系统的集成 方法功能单一的发现系统的适用范嗣必然受到一定的限制。要在更广泛的领域 发现知识，系统就应该是数据库、知识库、专家系统、决策支持系统、可视化工具、 网络等技术的集成。 9 、i n t e r n e t 上的知识发现 从w w w 信息的海洋中可以发现大量的新知识，已有资源发现工具发现含有关 键值的文本。h a n 等人提出利用多层次结构化方法，通过对原始数据的一般化，构 造多层次的数据库。 1 4 本文研究的主要内容 本文重点阐述了如何利用层次聚类算法串行解决数据挖掘聚类分析系统的原 理与解决方案，对现有解决方案存在的主要问题进行系统的分析，在此基础上，着 重对其中的关键技术和解决方法进行了论述。 首先，文章对数据仓库和数据挖掘的基本知识进行了介绍，描述了数据挖掘中 的聚类分析算法，对现有聚类分析算法的复杂度和相应的聚类精度进行比较分析： 其次，针对大规模数据集聚类分析的特点，综合各算法的特点，对现有层次聚 类算法做h 改进，在不增加空问复杂度的前提下，很大程度的提高了聚类结果的精 确性： 第一章绪论 然后，本文就聚类分析中的聚类结果可视化方面详细的加以阐述，提出一种分 层可视化方法，以解决大数据量的显示问题，实现了聚类分析工具与用户的交互； 最后，在算法和分层可视化的基础上完成聚类分析器的构建，并将该聚类分析 器应