（计算机应用技术专业论文）基于web的多媒体数据挖掘的研究与设计.pdf

中文摘要 过去数十年中，科技飞快的发展，数据存储发生了爆炸性的增长。 科学数据、医疗数据、人口统计数据、财经数据和市场数据等等的大 量出现，使我们迫切需要找到一种能在这浩似大海的数据里快速、有 效地发现知识的工具和方法。数据挖掘因此应运而生，并成为数据库 系统和新的数据应用的一个有希望的、欣欣向荣的前沿学科。多媒体 数据库是数据库技术的新兴领域。它研究的对象已从传统的单一的字 符类型的信息媒体发展为包括图形、图象、声音和字符的多种类型的 信息媒体。由于研究对象的多样化，因而多媒体数据库技术提出了很 多比传统数据库技术更为复杂和更为新颖的研究课题。 本文首先介绍了数据挖掘的概念和背景知识以及数据挖掘中的 新兴领域多媒体数据挖掘的方法和理论。接着针对多媒体数据挖 掘，结合作者的实践，介绍了一个基于w e b 的多媒体数据挖掘系统的 设计和实现。 本文对多媒体数据挖掘用基于描述的检索对多媒体数据建立索 引和标识，在检索的过程中利用文档挖掘的一些策略对多媒体数据进 行检索，如z ：统计法、支持向量机等，简化了多媒体数据检索的方法， 提高了检索的速度。在程序实现过程中，我们利用n e t 中的x m lw e b s e r v i c e 实现了对数据库的各种功能操作的封装。 关键词：多媒体数据挖掘、近邻匹配算法、x m lw e b 服务、分词 a b s t r a c t i nt h ep a s ty e a r s ，t h e r ei saq u i c kd e v e l o p m e n ti nt h et e c h n o l o g y w i t h t h ed a t ae x p l o d i n g ，i ti se a g e rt of i n dat o o lt od i s c o v e r yu s e f u lk n o w l e d g e f r o mt h eh u g ed a t aq u i c k l ya n de f f e c t i v e l y d a t am i n i n gi st h er i g h tt o o l a n db e c o m i n gap r o m i s i n ga n dp r o s p e r o u ss u b j e c t m u l t i m e d i ad a t a b a s e i san e wf i e l di nt h ed m a n di t sr e s e a r c ho b j e c ti sn o to n l yt h es i n g l e i n f o r m a t i o n ，b u ta l s ot h ei n f o r m a t i o ni n c l u d i n gm a n yk i n d s ，f o re x a m p l e ： g r a p h s ，p i c t u r e sa n da u d i o s b e c a u s em u l t i m e d i ad a t a b a s ei sc o m p r i s e d l o t so ft y p e so fo b j e c t s ，i ti sm o r ed i f f i c u l ta n dc o m p l e xt or e s e a r c h t h i st h e s i sf i r s ti n t r o d u c e st h ec o n c e p ta n dh i s t o r yo ft h ed ma n dt h e t h e o r yo ft h em u l t i m e d i ad m ，t h e ni n t r o d u c e st h ek e yt e c h n o l o g i e si na m u l t i m e d i ad m s y s t e md e v e l o p e db yt h ea u t h o r , s u c ha sn e a rn e i g h b o r m a t c h i n ga r i t h m e t i c , z 2 s t a t i s t i c sa r i t h m e t i ca n ds oo n f i n a l l yc o m b i n i n gw i t l lt h ea u t h o r sp r a c t i c e s ，t h i st h e s i si n t r o d u c e s t h er e s e a r c ha n dd e s i g no fam u l t i m e d i ad ms y s t e mo nt h ew e b t h e s y s t e mc r e a t e st h ei n d e xa n di d e n t i f i c a t i o nb a s e do nd e s c r i p t i o na n dt a k e s a d v a n t a g eo ft h em e a n so ft h ed o c u m e n td m ，w h i c hs i m p l i f i e st h e m u l t i m e d i ad a t as e a r c h i nt h ep r o g r a mt h i st h e s i se n v e l o p st h ef u n c t i o n s o ft h ed a t a b a s eu s i n gx m lw e bs e r v i c e k e y w o r d ：m u l t i m e d i ad a t am i n i n g ，n e a rn e i g h b o rm a t c h i n ga r i t h m e t i c ， x m lw e bs e r v i c e ，d i v i d i n g w o r d s 独创性声明 奉入声秘所壁交的学往论文是本人在导筛搔导下送行的研究工 乍和取得的 研究成粜，除了文中特别加以标、漩和致谢之处外，论文中不包含其他人融经发表 域撰写遗鹣研究绒采，也不包含为获褥鑫鎏盘蹩或冀谴教育机构懿学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 住了明确懿说明并表示了甾 意。 学位论文作者签名：粼中签字醐：圳j 年硼胎日 学位论文版权使用授权书 本学位论文作者完全了解基盗盘壁有关保留、使用学彼论文的规定。 特授权泰注盘燮可以将学位论文的全部或部分内窖编入有关数据霹进行检 索，并采愆影印、缩印或掴描等复制手段傈存、汇编以供蕊阏和借阅。同意学校 向国家有关部门或机构送交论文的复印传筹磁盘。 ( 保密的学位论文在解密看遥用本授权说明) 学位论文作者签名： 群# 导鄹签名； 雠；一墨 签字嚣鬻：瑚_ 簿 凳f 8 髫 签字目裁：岁霉卢嗣弦e l 第一章概述 1 1 数据挖掘的概念 第一章概述 简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。还有一些术语， 具有和数据挖掘类似但稍有不同的含义，如数据库中知识挖掘、知识提取、数 据模式分析、数据考古和数据捕捞。许多人把数据挖掘视为另一个常用的术语 数据库中的知识发现或k d d 的同义词。而另一些人只是把数据挖掘视为数据 库中知识发现过程的一个基本步骤。知识发现过程如图1 - 1 所示，由以下步骤 组成： 1 ) 数据清理( 消除噪声或不一致) 2 ) 数据集成( 多种数据源可以组合在一起) 3 ) 数据选择( 从数据库中检索与分析任务相关的数据) 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为 新的知识存放在知识库中。根据这种观点，数据挖掘只是整个过程中的一步， 尽管是最重要的一步发现隐藏的模式。 数据挖掘是知识发现过程的一个步骤。然而，在产业界、媒体和数据库研 究界，比较长的术语“数据库中知识发现”更流行。术语数据挖掘就是数据中 挖掘有趣的知识的过程。 基于这种观点，典型的数据挖掘系统具有以下主要成分( 见图1 - - 2 ) ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、 电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓 库服务器负责提取相关数据。 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知 识可能包括概念分层，用于将属性值组织成不同的抽象层。用户确信方面的知 识也可以包含在内。可以根据非期望性评估模式的兴趣度使用这种知识。领域 知识的其他例子有兴趣度限制或阀值或元数据( 例如，描述来自多个异种数据 源的数据) 。 第一章概述 图1 一l 数据挖掘视为知识发现过程的一个步骤 2 第一章概述 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于 特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互，以 便将搜索聚焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式 评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 对于有效的数据挖掘，尽可能深的将模式评估推进到挖掘过程之中，会将搜索 限制在有兴趣的模式上。 图形用户界面：此成分在用户和数据挖掘系统之间通信，允许用户与系统交 互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中 间结果进行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库 模式或数据结构，评估挖掘的模式、以不同的形式对模式可视化。 图1 2 典型的数据挖掘系统结构 从数据仓库观点，数据挖掘可以看作联机分析处理( o l a p ) 的高级阶段。 第一章概述 然而，通过结合更高级的数据理解技术，数据挖掘比数据仓库的汇总型分析处 理走的更远。 数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学习、 高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理 和空间数据分析。 1 2 数据挖掘产生的历史背景 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量 数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获 取的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、 工程设计和科学探索等。 数据挖掘是信息技术自然演化的结果。演化过程的见证是数据库业界开发 以下功能( 见图1 - 3 ) ：数据收集和数据库创建，数据管理( 包括数据存储和检 索，数据库事务处理) ，以及数据分析和理解( 涉及数据仓库和数据挖掘) 。例 如，数据收集和数据库创建机制的早期开发已成为稍后数据存储和检索、查询 和事务处理有效机制开发的必备基础。随着提供查询和事务处理的大量数据库 系统广泛付诸实践，数据分析和理解自然成为下一个目标。 自2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理 演化到复杂的、功能强大的数据库系统。自7 0 年代以来，数据库系统的研究和 开发己经从层次和网状数据库系统发展到关系数据库系统( 数据存放在关系表 结构中) 、数据建模工具、索引和数据组织技术。此外，用户通过查询语言、用 户界面、优化的查询处理和事务管理，可以方便、灵活地访问数据。联机事务 处理( o l t p ) 将查询看作只读事务，对于关系技术的发展和广泛地将关系技术 作为大量数据的有效存储、检索和管理的主要工具做出了重要贡献。 自8 0 年代中期以来，数据库技术的特点是广泛接受关系技术，研究和开发 新的、功能强大的数据库系统。这些使用了先进的数据模型，如扩充关系模型、 面向对象模型、对象一关系模型和演绎模型。包括空间的、时间的、多媒体的、 主动的和科学的数据库、知识库、办公信息库在内的面向应用的数据库系统百 花齐放。涉及分布性、多样性和数据共享问题被广泛研究。异种数据库和基于 i n t e r a c t 的全球信息系统，如w w r 也已出现，并成为信息产业的生力军。 在过去的3 0 年中，计算机硬件稳定的、令人吃惊的进步导致了功能强大的 计算机、数据收集设备和存储介质的大量供应。这些技术大大推动了数据库和 信息产业的发展，使得大量数据库和信息存储用于事务管理、信息检索和数据 4 第一絮撬逮 数据收集和数据库创建 ( 2 0 世纪6 0 年代和更早) 一原始文律处瑾 数据库管瑷系统 ( 7 0 年代) 一屠浚耱网状数疆瘁系统 一关系数据库系统 数攥建模王县；实体联鬈摸型等 一索弓f 和数据组织技术：b + 树、三列等 一查询语言；s q l 等 一露户舞嚣；表萃、激告等 一查询处理和查询优化 一事务管理、恢复和多# 发控制等 一联梳事务处遴( o l p t ) 高级数搬库系统 ( 8 0 年代率期一现在) 高级数据模型： 扩充关系、嚣悫对象、 对苏一关系、演绎 一面向应用 空瀚翡、瓣瘸靛、多媒体懿、 主动的、科学的、知识库 藏予w e b 的数据库系统 ( 9 0 年代一现攘) 慕子x m l 的数据痒系统 w e b 挖掘 数据仓库和数据挖掘 ( 8 0 年代磊蘩一戮在) 一数据仓库和0 l a p 技术 数据挖搬零知识发现 凝一代综合信息系统 ( 2 0 0 伊一) 圈1 3 数据库技术的演化 蘩一章撰述 分析。 现农，数据可以存放在不同类型的数据库中。最近溢现雏种数据库结构 是数据仓库。这是多个舞种数据源在单个站点以统一的模式组织的存储，以支 持管理决策。数据仓库技术包括数据清理、数疆集成和联祝分析处瑾( o l a p ) 。 o l a p 熄一种分析技术，具有汇总、合并和聚集功能，以及从不同的角度观察 信怠的麓力。尽管o l a p 工兵支持多维分析帮决策，对于深层次的分轿，如数 据分类、聚类和数据随时间变化的特征，仍然需要其他分析工具。 数据静丰富带来了辩强有力的数据分析工麓的需求，大量静数据被描述为 “数据丰富，但信息贫麓”。快速增长的海量数据收集、存放在大型和海量数据 律中，没有强露力静工羹，理解它餐己缝运远越过了人翡缝力。结栗，浚集在 大型数搬库中的数据变成了“数据坟墓”难得再访问的数据档案。这样，重 簧斡凌定常常不是基于数据库牵信惠丰鬻豹数攥，孬是筵于决麓者蘸纛觉，霞 为决策错缺乏从海量数据中提取有价值知识的工具。此外，考虑当前的专家系 统技术，逶零，这释系绫猿蓑瘸户或簇缓专家久王逮将籍谖赣入翔谖黪。不幸 的是，这一过稷常常有偏差和错误，并且耗时、费用高。数据挖掘工具进行数 据分羲，霹淡发瑗重要瓣数据模式，鼹舞务凌策、籍蓼 疼、科学纛医学疆究终 出了巨大的贡献。数据和信息之间的鸿沟要求系统地开发数据挖掘工具，将数 据坟墓转爨藏翔谈“金块”。 随潜科学研究的迅速发展，数据挖掘广泛殿用在各种领域。( 1 ) 应用在针 辩生秘蒺学窝d n a 数懿分辑中。基因臻究孛一个重要关注熹是d n a 黟捌戆磅 究，因为这种序列构成了所有的话的生物体的旗因代码的基础。具有挑战性的 逮趣是从孛找爨导致各糖疾薅瓣特定基麴_ 事列摸式。虫子在数撰挖援审已经毒 许多有意义的序列模式分析和拥似检索技术，因此数据挖掘成为d n a 分析的 强寿力工县，并在许多方嚣对d n a 分褥起着不小戆贡敬。数撰挖握懿主要应 用包括：异构、分布式涟因数据库的语义集成，d n a 序列间相似搜索和比较， 同时出现的基嚣序列熬识别( 关联分摄) ，发现焱疾癀不强阶段豹致因蒸因( 路 径分析) ，可视化工具和遗传数据分析等。( 2 ) _ 陂用在针对金融数据分析中。大 部分银行昶金融机构都提供丰富多样的储蓄骧务( 如支梁、存款秘商业及个人 用户交翳) ，信用服务( 如交易、抵押和汽车贷款) ，和投资服务( 如熬有基金 ( m u t u a lf u n d ) ) 。有些述提供保险和股浆投资服务。因北，存程大量鲶援对比 较完整、可靠和高质量的金融数据。这利于使用系统化的数据分析和数据挖掘。 数据挖搬的主要应用包括：为多维数据分析和数据挖掘设计和构造数掇仓库， 贷款偿还预涣l 和客户信用政策分析，对西标市场( t a r g e t e dm a r k e d n 窖) 客户的 分类与擐类，洗黑钱和其他金融犯罪的侦破等。( 3 ) 应用在零侮业中。零售业 楚数据挖掘的主要应用领域，这是因为零售渡积素了大麓的销俦数据，顾客赡 6 第一鬻撮透 哭历史谌录，货物进出，消费与服务记聚，等等。零售数据挖掇可有助鼍二识别 顾客购瓣行为，发现顾客购买模式和趋势，改进服务质麓，取得更好的顾客保 持力昶满意程度，提亮费晶销爨比率，设计更好的货品运输与分销燕略，减少 商业成本。数据挖掘的擞要应用包括：蕊于数据挖掘的数据仓库的设计与构造， 销售、顾客、产品、时间和地赋的多维分折，键销活动瓣有效性分析，颞客保 持力( 忠诚度) 的分析，购买撩荐和商鼯参照等。( 4 ) 应用在电信业中。电信 业已经迅速地从单纯的提供市落和长话服务演交为提供综合电信服务，如语音、 传真、寄呼、移动电话、图像、电子邮件、计算机和w e b 数据传输，阻及其低 数据通信服务。利用数据挖掘披术来帮助理解商业行为、确定电信模式、捕捉 盗用行梵、更好地年g 雨资源和掇高服务璜量是非常重要酶。数攒挖掘的主要应 用包括：电信数据的多维分析，盗用模式分析朔异常模式识别，多维关联和序 列模式分析，魄信数据分析中可视饱工其的使用等。 1 。3 磺目鹜豢和本文佟老懿王佟 饶创辩技( 黼。v i e w t r a n 。t o m ) 耨一代多攥俸逶舔警台产藩v i e w w e b 秀宽 带运营商提供了良好的多媒体邀营解决方案。v i e w w e b 懿个系统基于i n t e r li a 构檠豹s e r v e r 橇建，袋疆w i n d o w s 2 0 0 0 操作系统。该系统由繁毽予系统，鼗 务子系统，运营支撑予系统，多媒体服务子系统，及客户端五部分组成，为运 瑟亵提供完整瓣宽带多媒俸逶谖簿决方寨。系统漾矮w e b 界委莲潮释管理， 支持大规模用户同时使用。其中的多媒体服务子系统完成接入控制，多点 夥媒体交换及羧潮，多媒髂逶谖存德、点播及畿索等功缝，是v i e w w e b 系统豹 核心处理部分。本系统的多媒体文件包括缀过特殊压缩后的声音、图 表窝塑像文够。为了更好熬浇是熏户静嚣求，绘矮户掇馔更多豹多 媒体资源，系统提供对w e b 上的多媒体资源的搜索功能。因此系统中开发了 令多媒髂售惑搜索系统。 本文作者参与了此项目的开发，在此项目中主要开发在w e b 界面上对系统 熬控嘉l 魏管理。零入在磷完了数摇挖掘之嚣，把数据挖攘驰翅识疲蘑到实黢孛， 在w e b 界面管理中利用多媒体挖掘的知识实现多媒体搜索。 本文下嚣蘑先贪缨了数据挖握粒理论，然蒺奔缨了v i e w w e b 孛鹊多媒体 搜索中用到的关键技术，接着介绍了多媒体搜索系统的结构设计、实现及运行 结果，觳后分绍了作者慰于多媒体挖掘的展望。 7 第二耄数播挖摇理论醭究 嚣二章数据挖掘理论研究 鼗瓣燕舞愚麸大薰数据孛笈凌骞趣摸式，逮些数蘩蜀鞋存羧在鼗辫簿、数 描仓库娥其他信息存储中。数据挖掘悬个年轻的跨学科的领域，源于诸如数 爨痒系统、数耩仓痒、统诗学、援器擎露、数褥霹程藏、萤惠捡索塞斑性瑟计 算。其他涉及的领域包措神经网络、模式识别、空间数据分析、图像数据库、 痿号憝攥帮诲多瘫薅簇壤，氢捺离务、经揍学藕垒魏嵇惑学。 2 。1 数据挖掘理论 ：。薹1 数豢控撼戆数瓣类型 原则上讲，数据挖掘可以谯任何类型的信息存储上进行。避包括荧系数据 疼、鼗摄奄库、事务数据痒、离缓鼗攥瘁系统、展开文件帮w w w 。高级数掭 库系统包括面向对象和对象一关系数据库：面向特殊威用的数搬库，如空间数 攥痒、辩褥廖剜数螽瘁、文零散器摩藕多媒藩数耀痒。挖摇酌挑战释援本虿熊 因存储灌统而异。 零论文繇考您静是多媒蒋数据库。多媒薅数挺瘁存放蘑象、考蘩黎援颓数 据。它f f l 用于基于图像内容的检索、声诲传递、视频点播、w w w 和识别口语 令令戆蒸予语啻黪薅产器嚣等方嚣。多嫘薅数据漳登慧袁撩大瓣象，嚣秀穰稳 频这样的数据对象可能需要兆字节级的存储。避需要特殊的存储和搜索技术。 霆秀程颓帮音频数器嚣螫虢黎是鲢、颈笼稳定熟速率实瓣捡索，耱壹辫象或声 凿间断和系统缓冲区溢出，因此这种数据称为避续媒体数据( c o n t i n u o u s n l e d i a d a t a ) 。 对予多媒体数据库挖掘，需要将存储和搜索技术与标准的数据挖掘方法集 袋在一起。骞蕙途戆方法毯摇构造多媒体鼗囊立方薅、多攥落数据襄多糖薤提 取和基于相似性的模式匹配。 2 , 1 2 数据挖糯臻箍 数据挖摇动戆餍予指定数掇挖掘强务串要我戆模式类鳖。数器挖霰往务一 般可以分两类；描述和预测。描述性挖掘任务捌划数据库中数据的一般特性。 溪穗性挖掘萑务在当嚣数据上避荦亍接蓊，敦遂盼预涎。 8 第二章数据挖掘理论辑究 在蘩些情况下，臻产不知邀链粥鹃数据中竹么类型鲢摸式蹩有趣款，霹此 可能想并行地搜索多种不同的模式。这样，重要的是，数据挖掘系统要能够挖 糖多静类型的模式，以邋应不周的用户器求或不同豹应月。此多 ，数据挖掘系 统应当能够发现各种粒度( 郎不闰的抽象层) 的模式。数据挖獭系统威当允许 用户给跚提示，指导或浆焦有趣模式的搜索。幽于有些模式并非对数据库中的 所有数销都成立，通常每个被笈现的横浅带上一个确定往或“可信度”度量。 下灏给出数据挖掘功能及其可以发现的模式类型。 2 1 2 。1 穰念，类箍述：特征纯帮蘧分 数搬可以与类或概念相关联。例如，在a l l e l e c t r o n i e s 商店，销售的商品类 氆括诗冀杭察群卵极，联客橇念毽括b i g s p e n d e r s 帮b u g g e t s p e n d e r s 。震汇总豹、 简洁的、精确的方式描述每个类和概念w 能是有用的。这种类成概念的描述称 梵类，橇念播述( c l a s s c o n c e p t d e s c f i p f i o n ) 。这种撰述霹戮逶过下述方法褥翻：1 ) 数据特祗化，一般地汇总所研究类( 通常称为目标类( t a r g e tc l a s s ) ) 的数据；2 ) 数据区努，将嚣标类与一个或多个昆较类( 逶露称兔露琵类( c o n t r a s t i n gc l a s s ) ) 进行比较；3 ) 数据特磁化和比较。数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标 类数据豹一觳特往或特绦豹汇憨。逶鬻，雳户撩定类瓣数豢逶遗数舞黪查询毅 集。例如，为研究上一年销售增加1 0 的软件产品的特征，可以通过执行一个 s q l 查游牧集关予这鳖产燕懿数据。 有许多有效的方法，将数据特征化和汇总。例如，基于数据立方体的o l a p 上卷搡穆萄苏矮条羲行建户控剃豹、澄整指定绫瓣数攘汇总。一赞嚣怒j 霆毽翁 归纳技术可以用来进行数据的概化和特征化，而不必一步步地筠用户交互。 数据特援懿耱出霹 ；乏廷多耱影袁提供。包熬锈强、条銎、藤线、多维鼗擐 立方体和包括交叉表在内的多缎表。结果描述也可以用概化关系( g e n e r a l i z e d r e l a t i o n ) 或规粥缮式( 称终特援援剿) 提供。 数据挖掘系统应当能够产擞一年之内在a l l e l e c t r o n i c s 花费$ 1 0 0 0 以上的顾 客特征汇憨豹攒述。结裂可藐怒矮窖熬一致轮磷，如霉龄在4 0 - - 5 0 、鸯工终、 有很好的信用等级。系统将允许用户在任意维下钻，如在o c c u p a t i o r t 下钻，以 便根据披们约驳业来观察这些顾客。 数据区分( d a md i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一个兢多个 对比类对象的一般特性比较。西标类昶对比类熬鼹户擐定，面对应鸵数握通过 数据库落询检索。例如，你可能希望上一年销售增加1 0 的软件产品与阊一时 期销售缴少下降3 0 的郏些产熬进行比较。用予数据区分的方法与用于数据特 征化的类似。 输出熊形式类似于特征描述，但区分描述应当包括比较度爨，帮助区分目 檬类帮辩院类。厢规爱q 表示的区分描述称为区分规则( d i s c r i m i n a n tr u l e ) 。用户 9 第二章数据挖掘理论研究 应当能够对特征和区分描述的输出进行操作。 数据挖掘系统应当能够比较两组a l l e l e c t r o n i c s 顾客，如定期( 每月多于 2 次) 购买计算机产品的顾客和偶尔( 即每年少于3 次) 购买这种产品的顾客a 结果描述可能是一般的比较轮廓，如经常购买这种产品的顾客8 0 在2 0 - - 4 0 岁之间，受到大学教育；而不经常购买这种产品的顾客6 0 或者太老，或者太 年轻，没有大学学位。沿着维下钻，如沿o c c u p a t i o n 维，或添加新的维，如 i n c o m el e v e l 可以帮助发现两类之间的更多区分特性。 2 1 2 2 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 发现关联规则，这些规则展示属性一值频 繁地在给定数据集中一起出现的条件。关联分析广泛用于购物篮或事务数据分 析。 更形式地，关联规则( a s s o c i a t i o nr u l e ) 是形如x ；y ，即“a 1 八八a 。j b l 八a b 。”的规则，其中，a 。( i ( 1 ，m ) ，b ，( j l ，n ) ) 是属性一 值对。关联关系x j y 解释为“满足x 中条件的数据库元组多半也满足y 中 条件”。 给定a l l e l e c t r o n i c s 关系数据库，一个数据挖掘系统可能发现如下形式的 关联规则 a g e ( ) ( ， 2 0 2 9 ”) “i n c o m e ( x , “2 0 k 2 9 k )b u y s ( x , “c p _ p l a y e r ) s u p p o r t = 2 ，c o n f i d e n c e26 0 刈 其中x 是变量，代表顾客。该规则是说，所研究的a l l e l e c t r o n i c s 顾客2 ( 支持度) 在2 0 一2 9 岁，年收入2 0 k - 2 9 k ，并且在a l l e l e o t r o n i c s 购买c d 机a 这个年龄和收入组的顾客购买c d 机的可能性有6 0 ( 置信度或可信性) 。 这是一个以上属性或谓词( 即a g e ，i n c o m e 和b u y s ) 之间的关联。采用多 维数据库使用的术语，每个属性称为一维，上面的规则可以称作多维关联规则 ( m u l t i d i m e n s i o n a la s s o c i a t i o nr u l a 。 假定作为a l l e l e c t r o n i c s 的市场部经理，想知道在一个事务中，哪些商品经 常被一块购买。这种规则的一个例子是 c o n t a i n s ( t , “c o m p u t e r ) jc o n t a i n s ( 工“s o r w a r d ) s u p p o r t = 1 ，c o n f i d e n c e = 5 0 】 该规则是说，如果事务t 包含“c o m p u t e r ”，则它也包含“s o f t w a r e ”的可 能性有5 0 ，并且所有事务的1 包含二者。这个规则涉及单个重复的属性或 谓词( 即c o n t a i n s ) 。包含单个谓词的关联规则称作单维关联规则 ( s i n g l e - d i m e n s i o n a la s s o c i a t i 彻r u l e ) 。去掉谓词符号，上面的规则可以简单地 写成c o m p u t e rjs o f t w a r e 【1 ，5 0 】。 1 0 第二章数据挖掘理论研究 2 1 2 3 分类和预测 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模 型( 或函数) ，以便能够使用模型预测类标记未知的对象类。导出模型是基于对 训练数据集( 即其类标记已知的数据对象) 的分析。 导出模型可以用多种形式表示，如分类( t 狲) 规则、判定数、数学 公式或神经网络。判定数是一个类似于流程图的树结构，每个节点代表一个属 性值上的测试，每个分支代表测试的一个输出，树叶代表类或类分布。判定树 容易转换成分类规则。当用户分类时，神经网络是一组类似于神经元的处理单 元，单元之间加权连接。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希 望预测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数 据时，通常称之为预测( p r e d i c t i o n ) 。尽管预测可以涉及数据值预测和类标记 预测，通常预测限于值预测，并因此不同于分类。预测也包含基于可用数据的 分布趋势识别。 相关分析( r e l e v m r l c ea n a l y s i s ) 可能需要在分类和预测之前进行，它试图识 别对于分类和预测无用的属性。这些属性应当排除。 假定作为灿l e l e c u o n i c s 的销售经理，想根据销售活动的三种反应，对商 店的商品集合分类：好的反应，中等反应和没有反应。如想根据商品的描述特 性，如p r i c e ，b r a n d ，p l a c e _ m a d e ，t y p e 和c a t e g o r y ，对这三类的每一种导出模型。 结果分类应最大限度地区别每一个类，提供有组织的数据集图象。假定结果分 类用判定树的形式表示。例如，判定树可能把p r i c e 看作最能区分三个类的因素。 该树可能揭示，在p r i c e 之后，帮助进一步区分每类对象的其他特性包括b r a n d 和p l a c em a d e 。这样的判定树可以帮助理解给定销售活动的影响，并帮助设计 未来更有效的销售活动。 2 124 聚类分析 聚类分析与分类和预测不同，聚类( c l u s t e r i n g ) 分析数据对象，而不考虑 己知的类标记。般情况下，训练数据中不提供类标记，因为不知道从何开始。 聚类，可以用于产生这种标记。对象根据最大化类内的相似性、最小化类间的 相似性的原则进行聚类或分组。即对象的簇( 聚类) 这样形成，使得在一个簇 中的对象具有很高的相似性，而与其他簇中的对象很不相似。所形成的每个簇 可以看作对象类，由它可以导出规则。聚类也便于分类编制( t a x o n o m y f o r m a t i o n ) ，将观察到的内容组织成类分层结构，把类似的事件组织在一起。 聚类分析可以在a l l e l e c t r o n i c s 的顾客数据上进行，以便识别顾客的同类 子群。这些簇可以表示每个购物目标群。下图显示了一个城市内顾客的2 一d 图。数据点的三个簇是显而易见的。 第二章数舞挖掘理论磷究 t - 奈 图2 1 关于个城市肉颞客往置鞠2 - d 图，箍示了3 个聚类，每个聚类酶 “中心”用“+ ”标记 2 1 2 5 孤立点分析 数据疼中哥戆包含些数据愆象，它铜与数据懿一觳孬受斌模式誉蘩。 这些数据对象怒孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异 霉瑟丢赛。熬嚣，在一黧应簿审( 懿教骗检滚) ，罕觅熬攀辞哥蕤跑歪鬻氆瑷酶 那些更肖趣。孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 。 孤囊杰哥戳建溪绕诗试验捻溯。宅骰定一令数据分毒豉攘察模型，磐傻麓 距离度蠛，到其他聚类的距离很大的对缀被视为孤立点。基于偏差的方法通过 考察一辩对象未要特薤上酶差剃识翳疆立点，瑟不是建建统计璇距离发墨。 2 1 2 6 演交分析 数据演变分析( e v o l u t i o na m l y s i s ) 摧述行为涎时间变化的对象豹靓律或趋 势，并对其建橇。尽管这可能包括时间棺关数据的特征化、区分、关联、分类 或聚类，这类分析的不间特点包括时间序列分据、序列戏周期模式匹配秘基于 类似性的数据分析。 2 。1 。3 横式译倍一兴趣廑阏藤 鼗撵挖摇系统具有产生数黻干诗、蓉至数良万计静禳式或蕊剐的潜张能力。 但是，对于给寇的用户，在可能产生的模式中，只有小部分是他感兴趣的。 一个模式燕骞趣静( i n t e r e s t i n g ) ，魏栗( 1 ) 它荔予被久瑾解；( 2 ) 在某秤 程度上，对于颓的或测试数据悬有效的：( 3 ) 悬潜在有用的；( 4 ) 是新颖的。 热栗一个模式符合雳产确信数莱释镁设，宅氇蹙有趣静。有趣兹模式表黎知谖。 第二章数据挖掘理论研究 存在一些模式兴趣度的客观度量。这些度量基于所发现模式的结构和关于 它们的统计。对于形如x jy 的关联规则，一种客观度量是规则的支持度 ( s u p p o r t ) 。规则的支持度表示满足规则的样本百分比。支持度是概率p ( x u y ) ， 其中，x u y 表示同时包含x 和y 的事务，即项集x 和y 的并。关联规则的 另一种客观度量是置信度( c o n f i d e n c e ) 。置信度是条件概率p ( y i ) ( ) 即包含x 的 事务也包含y 的概率。更形式地，支持度和置信度定义为 s u p p o r t ( x jy ) = p ( x uy ) c o n f i d e n c e 岱jy ) 2p f y i x ) 一般地，每个兴趣度度量都与一个阀值相关联，该阀值可以由用户控制。 例如，不满足置信度阀值5 0 的规则可以认为是无趣的。低于阀值的规则可能 反映噪声、异常或少数情况，可能不太有价值。 尽管客观度量可以帮助识别有趣的模式，但是仅有这些还不够，还要结合 反映特定用户需要和兴趣的主观度量。例如，对于市场经理，描述频繁在 a l l e l e c t r o n i c s 购物的顾客特性的模式应当是有趣的；但对于同一数据库，分析 雇员业绩模式的分析者，它可能不是有趣的。此外，有些根据客观标准是有趣 的模式可能反映一般知识，因而实际上并不令人感兴趣。主观兴趣度度量基于 用户对数据的确信。这种度量发现有趣的模式，如果它们是出乎意料的( 对照 用户的确信) ，或者提供用户可以采取行动的策略信息。在后一种情况下。这样 的模式称为可行动的( a c t i o n a b l e ) 。意料中的模式也可能是有趣的，如果它们 证实了用户希望验证的假设，或与用户的预感相似。 数据挖掘系统能否产生所有有趣的模式涉及数据挖掘算法的完全性。期望 数据挖掘系统产生所有可能的模式是不现实的和低效的。实际上，应当根据用 户提供的限制和兴趣度对搜索聚焦。对于某些数据挖掘任务，这通常能够确保 算法的完全性。关联规则挖掘就是一个例子，那里，使用限制和兴趣度度量可 以确保挖掘的完全性。 数据挖掘系统是否仅产生有趣的模式是数据挖掘的优化问题。对于数据挖 掘系统，仅产生有趣的模式是非常期望的。这对于用户和数据挖掘系统是非常 有效的，因为这样就不需要搜索所产生的模式，以便识别真正有趣的模式。在 这方面已经有了进展。然而，在数据挖掘中，这种优化仍然是个挑战。 为了有效地发现对于用户有价值的模式，模式兴趣度度量是必需的。这种 度量可以在数据挖掘这一步之后使用，根据它们的兴趣度评估所发现的模式， 过滤掉不感兴趣的那些。更重要的是这种度量可以用来指导和限制发现过程， 剪去模式空间中不满足预先设定的兴趣度限制子集，改善搜索性能。 第二章数据挖掘理论研艽 2 2w e b 数据挖掘 万维网目前是一个巨大的、分布广泛的和全球性的信息服务中心，它涉及 新闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其他信息服 务。w e b 还包含了丰富和动态的超连接信息，以及w e b 页面的访问和使用信息， 这为数据挖掘提供了丰富的资源。然而基于以下的分析，w e b 对有效的资源和 知识发现还是具有极大的挑战性。 对有的数据仓库和数据挖掘而言，w e b 似乎太庞大了。w e b 的数据量目前以 几百兆兆字节计算，而且仍然在迅速地增长。许多机构和社团都在把各自大量 的可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制、存储 或集成w e b 上的所有数据。 w e b 页面的复杂性远比任何传统的文本文档复杂得多。w e b 页面缺乏同一的 结构，它包含了远比任何一组书籍或其他文本文档复杂得多的风格和内容。w e b 可以看作一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任 何有关排列次序加以组织。它没有分类索引，更没有按标题、作者、封面页、 目次等的索引。对在这样个图书馆中搜索希望得到的信息是极具挑战性的。 w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信息 还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断 地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。 w e b 面对的是一个广泛的形形色色的用户群体。目前因特网上连接有约五千 万台工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、兴 趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价， 即容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不以 和在等待一段信息中失去耐心。 w e b 上的信息只是很小的一部分是相关的或有用的。据分析9 9 的w e b 信息 对于9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上的很小很小一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感 兴趣的，而且会淹没所希望得到的搜索结果。 这些挑战已经推动了如何高效且实际地发现和利用因特网上资源的研究工作。 2 2 1w e b 挖掘的概念 w e b 挖掘可以定义为w w w 上有用信息的发现和分析。w e b 挖掘是- - f l 综合技 术，涉及领域非常广泛，如：数据挖掘、信息学、计算机语言学、人工智能等 领域。w e b 挖掘从数据挖掘而来，但由于w e b 上信息的特点使得它又不同于数 1 4 第二章数据挖掘理论研究 据挖掘，它所面临的挑战更大。 2 2 2w e b 挖掘的任务 通常w e b 把掘可以分为3 个子任务：资源发现、信息提取、概括。 资源发现：是指从w e b 上搜索可用的信息； 信息提取：是从已经发现的资源中提取出有用的信息。对于文本信息而 言，不仅要考虑文本内容，而且也要考虑文本的结构； 概括：是对w e b 信息自学习的过程，通过学习抽取一定的规则。 一般来说，w e b 挖掘的数据来源途径有两个：搜索引擎的结果集和w e b 上 的在线消息。这两种方式各有所长，需要视具体的应用而定。目前，已经有几 种资源发现模型广泛应用于i n t e r n e t 上：目录浏览模型( w a i sa n dg o p h e r ) 、 检索模型( h r c m ea n dh l t av i s t a ) 、趟立方体( y a h o oa n de x c i t e ) 。许多资源 发现工具大都采用了基于r o b o t 的检索模型，这种方法扫描w e b 上的所有文档， 并建立索引，但它同时也将一些不相关的信息和过时的信息包含进来。因此， 需要开发出新的挖掘工具以更加准确、可靠、局效地发现资源和知识。 2 2 3w e b 挖掘的分类 w e b 挖掘对象包含3 方面的内容：w e b 上的文档信息，w e b 结构数据，用户 浏览w e b 页面的记录数据；相应地，根据挖掘对象的不同可将w e b 挖掘分成3 类：内容挖掘，结构挖掘，使用记录挖掘。图2 2 给出了w e b 挖掘的分类图。 图2 2 w e b 挖掘的分类 内容挖掘是从w e b 上自动查找或检索可用资源；结构挖掘就是概括出w e b 站点 和w e b 页的结构信息：使用记录的挖掘是从服务器访问日志、用户策略、用户 对话和事务处理信息中得到用户的访问模式和感兴趣的信息，并试图预测用户 的行为。 第二章数据挖掘理论研究 w e b 内容挖掘：w e b 内容统掘是从大量w e b 文档的非结构化数据中找出用 户感兴趣的知识，它类似于基于关系数据库的数据挖掘。由于w e b 上的数据是 多种不同类型数据的混合，如文本、图像、声音和视频等，以及w e b 数据的非 结构化属性又使得w e b 挖掘方法不同于数据挖掘方法。当前大多数信息的描述 仍以文本为主，因此，目前关于内容挖掘的讨论主要是针对文本。 w e b 结构挖掘：结构挖掘的目标是生成关于某个w e b 站点的结构和页面 结构的概括信息，因此结构挖掘的重点在于链接信息。给定一个相互关联的w e b 文档集合，通过存储在表格中的元组信息总可以找出一些信息来描述文档之间 的关系。结构挖掘的一个重要内容是w e b 文档本身的结构，它揭示了w e b 页面 的组织方式。w e b 文档的结构信息对于浏览以及其它一些操作如：w e b 页框架之 间的对比、合成等特别有用，在基于结构的w e b 文档分类和聚类中也很重要。 - w e b 使用记录挖掘：是指从服务器日志( 主要包括每个用户的浏览行为) 中发现用户的访问模式，通过使用记录挖掘为用户提供个性化服务。w e b 服务 器一般会自动保存用户的请求信息以及访问w e b