（计算机应用技术专业论文）基于内容的多媒体检索系统.pdf

摘要 近年泉，计算枫应用农备群行业迅速普及，许多领域郝建立了各自的数据库， 数据量日虢增加，并将一部分可公开的信息在万缎网上发布；万维网上的各类多 媒 零数据燹是爆炸瞧地增长，迅逮发展为包摇文字、霆豫、声音务秘类型数据豹 数据仓库。面对这样庞大的数据食库，数错挖掘必不可少，尤其怒针对多媒体数 据露戆检索系统更为震要。 然而，目前大多数检索系统仍然是基于描述的检索系统，对予图像等媒体数 据 楚是在强像接述黪基趱土建立标辱| 嚣掭浚( 蘩关键字、橛蘧等) 、撬行检索，这 样的标引隧意性较大，检索结果质量较差。为此，本文引入了一种基于内容的检 索系统。它提取鍪缘本赛懿特征( 餐蘩蕨魏、绞璎等季睾 垂) 建立搽雩 褰棘浚，梭 索时计算特征的相似性并采用查询求精的方法，查询结果质量较高。 本文罄先奔绥了鼗据撼箍理论，茏萁怒万臻辩数据挖掘与多媒体数据库，势 针对此基于内容的检索系缆。分析了其中的多媒体目标模型，查询树，鸯询求精 等搂鍪。辩诧系统进行蠢漆率与鸯全率试耱，对不同长囊、不目嫌体类型的文裆 进行检索，得出了较为理想的结果。最后，又试验证明了落询求辛i 彗的必要j 胜。 关键词：数据挖掘、多媒体、查询挝、查询装糖、蠢准率、套全枣 a b s t r a c t i nt h e p a s ty e a r s ，t h e r e i sa q u i c kd e v e l o p m e n t o f c o m p u t e r a p p l i c a t i o ni n ag r e a td e a lo fv o c a t i o n s ，a n dm a n yd a t a + b a s e sa r eb u i l t i nm o s td o m a i n s ，t h eq u a n t i t yo fd a t ai n c r e a s e de v e r yd a y ，a n ds o m eo f t h e ma r ei s s u e do nt h ew e b ：a l lk i n d s0 fm u l t i m e d i a d a t ao fw e b e x p l o d e d ，a n dt h ew e b i s g r o w i n gu pt o ad a t aw a r e h o u s ei n c l u d i n go f t e x t ，i m a g e s ，a u d i ot y p eo fd a t a i nt h e f a c eo fa s o h u g ew a r e h o u s e ， d a t a m i n i n g i s a b s o l u t e l yn e c e s s a r y ，t h e r e t r i e v a l s y s t e m s f o r m u l t i m e d i ad a t a * b a s e sa r em o r en e c e s s a r y m o r e o v e r ，m o s to fr e t r i e v a ls y s t e m sa r es t i l lb a s e do nd e s c r i p t i o n n o w t h e ys e tu pi n d e x a n di d e n t i f i c a t i o nf o ri m a g ed a t aa n dr e t r i e v a l a l s ob a s e so n i m a g ed e s c r i p t i o n ( k e yw o r d s ，t i t l e ，e t c ) ，t h i s k i n do f i n d e xi sr a n d o m ，a n dt h eq u a l i t yo ft h er e t r i e v a lr e s u l ti sn o te v e r yw e l l s ot h i sp a p e rr e c o m m e n d sar e t r i e v a ls y s t e m ，w h i c hb a s e do i lc o n t e n t t h i ss y s t e me x t r a c t st h ei m a g ec h a r a c t e ri t s e l f ( c o l o r ，t e x t u r e ，e t c ，) t o s e t u p i n d e xa n d i d e n t i f i c a t i o n ，c o m p u t e s t h e s i m i l a r i t y o ft h e c h a r a c t e r sw h e nr e t r i e v a la n dm a k e su s eo ft h e q u e r y r e f i n e m e n t m e t h o d ，t h eq u a l i t yo ft h eq u e r yr e s u l ti sa l lr i g h t a b o v e a l l ，t h i s p a p e r i n t r o d u c et h e t h e o r y o fd a t a m i n i n g ， e s p e c i a l l ya b o u tw e b d a t am i n i n ga n dm u l t i m e d i ad a t a b a s e ；a n di nf a c e o ft h er e t r i e v a ls y s t e mw h i c hb a s e do nc o n t e n t ，r e c o m m e n dt h ec o n c e p t o fm u l t i m e d i ao b je c tm o d e l ，q u e r yt r e e ，q u e r yr e f i n e m e n t ，e t c t e s tt h e p r e c i s i o na n dr e c a l lo ft h i ss y s t e m ，r e t r i e v a lt h ed o c u m e n t so fd i f f e r e n t l e n g t ha n dm u l t i m e d i at y p e ，a n dg e tap e r f e c tr e s u l t 。f i n a l l y ，c e r t i f i c a t e t h en e c e s s a r yo ft h eq u e r yr e f i n e m e n t k e y w o r d ：d a t am i n i n g ，m u l t i m e d i a ，q u e r yt r e e ，q u e r y r e f i n e m e n t p r e c i s i o n ，r e c a l l 独创性声明 本人声明所呈交的学位论文是本人在导师指移下进行的研究工 乍和取得的 磷究成暴，豫了文中特剐擒以搽演秘致滚之处乡 ，论文中不包含其熟入懑筑发表 或撰写遵稔研究成采，丧不餐含隽获褥盘壅叁鲎凌箕谴教育辊掏懿攀位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学霞论文终餐签名： 锄姻 签字曩麓：2 0 0 3 年6 麓1 9 基 学位论文版权使用授权书 本学位论文作者完全了解基鲞盘茔有关保留、使用学位论文的规定。 特授权燕鲞盘鲎可以将学蛾论文韵全部或部矜内容编入有关数据库进行检 索，势采惩彩印、壤印或扫臻等复裁手段保存、挺编以供查藏窝借溷。弱意学按 蠢鏊家有必帮门或祝梅送交论文戆复印律帮磁鑫。 ( 保密的学位论文在解密聪适用本授权说明) 学位论文终蠹签名： 冻匆套0 导，季然名： 签字日期；2 0 0 3 年6 月1 9 囤 签字隔期：2 0 0 3 年6 月2 2 曰 第一章概述 1 1 数据挖掘的概念 第一章概述 简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。还有一些术语， 具有和数据挖掘类似，但稍有不同的含义，如数据库中知识挖掘、知识提取、数 据模式分析、数据考古和数据捕捞。许多人把数据挖掘视为另一个常用的术语 数据库中的知识发现或k d d 的同义词。而另一些人只是把数据挖掘视为数据库中 知识发现过程的一个基本步骤。知识发现过程如图l l 所承，由以下步骤组成： 1 数据清理与集成( 消除噪声或不一致，多种数据源可以组合在起) 2 数据选择与变换( 从数据库中检索与分析任务相关的数据，数据变换或 统一成适合挖掘的形式，如通过汇总或聚集操作) 3 数据挖掘( 基本步骤，使用智能方法提取数据模式) 4 模式评估与知识表示( 根据某种兴趣度度量，识别表示知识的真正有趣 的模式，使用可视化和知识表示技术，向用户提供挖掘的知识) 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为新 的知识存放在知识库中。根据这种观点，数据挖掘只是整个过程中的一步，尽管 是最重要的一步发现隐藏的模式。 数据挖掘是知识发现过程的一个步骤。然而，在产业、媒体和数据库研究界， 比较长的术语“数据库中知识发现”更流行。术语数据挖掘就是数据中挖掘有趣 的知识的过程。基于这种观点，典型的数据挖掘系统具有以下主要成分见图1 2 ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电 子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库 服务器负责提取相关数据。 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知识 可能包括概念分层，用于将属性值组织成不同的抽象层。用户确信方面的知识也 可以包含在内。可以根据非期望性评估模式的兴趣度使用这种知识。领域知识的 第一章概述 其他例子有兴趣度限制或阀值或元数据( 例如，描述来自多个异种数据源的数据) 。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用 于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚集在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式 评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 对于有效的数据挖掘，尽可能深的将模式评估推进到挖掘过程中，会将搜索限制 在有兴趣的模式上。 - 图形用户界面：此成分在用户和数据挖掘系统之间通信，允许用户与系统 交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中 间结果进行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模 式或数据结构，评估挖掘的模式、以不同的形式对模式可视化。 从数据仓库观点，数据挖掘可以看作联机分析处理( o l a p ) 的高级阶段。然而， 通过结合更高级的数据理解技术，数据挖掘比数据仓库的汇总型分析处理走的更 远。数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学习、高 性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空 间数据分析。 1 2 数据挖掘产生的历史背景 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数 据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的 信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程 设计和科学探索等。 第一章概述 图1 1 数据挖掘一知识发现过程的一个步骤 第耄概述 数 图1 - 2 典型的数据挖掘系统结构 数据挖搦蹙信息技术融然演化的结果。演化过獠的见证是数据库业界开发以 下功能：数据收集和数据库创建，数据篱理( 包括数据存储和检索，数据库事务 簸瑾) ，疆及数据努撬羁理麟( 涉及数据仓库秘数援攘攥) 。镶蘩，羧摆竣案积数 据库创建机制的早期开发己成为稍后数据存储和检索、查询和事务处理有效机制 开发的必备錾础。随着提供查询和事务处理的大量数据库系统广泛付诸实践，数 攥分提嚣理簇塑然藏为下令嚣标。 自2 0 懒纪6 0 年代以来，数据库和信患技术已经系统地从原始的文件处理演 化到复杂的、功能强大的数据库系统。其不断演化的过程详见图1 - 3 。 在过去豹3 0 年中，计冀艇疆孛 的飞速发曩导致了功能强大静诗簿枫、数摄收 集设备和存储介质的大量供应。这些技术也大大推动了数据库和倍怒产业的发展， 使得大量数据库和信息存储用于事务管理、信息检索斧廿数据分析。 溅在，数据可以存放在不同类型的数据露中。最近出现豹一种数掇簿结构是数掇 第一章概述 仓库。这是多个异种数据源在单个站点以统一的模式组织的存储，以支持管理决 策。数据仓库技术包括数据清理、数据集成和联机分析处理( o l a p ) 。 然而，数据的丰富又带来了对强有力的数据分析工具的需求，大量的数据被 描述为“数据丰富，但信息贫乏”。没有强有力的工具，收集在大型数据库中的数 据变成了“数据坟墓”难得再访问的数据档案。决策者缺乏从这些海量数据 中提取有价值知识的工具。因此，数据和信息之间的鸿沟，要求系统地开发数据 挖掘的工具，将“数据坟墓”转换成用户需要的知识。 随着科学研究的迅速发展，数据挖掘被广泛应用在以下各种领域： ( 1 ) 应用在针对生物医学和d n a 数据分析中。基因研究中一个重要关注点 是d n a 序列的研究，因为这种序列构成了所有的活的生物体的基因代码的基础。 具有挑战性的问题是从中找出导致各种疾病的特定基因序列模式。由于在数据挖 掘中已经有许多有意义的序列模式分析和相似检索技术，因此数据挖掘成为d n a 分析的强有力工具，并在许多方面对d n a 分析起着不小的贡献。数据挖掘的主要 应用包括：异构、分布式基因数据库的语义集成，d n a 序列间相似搜索和比较， 同时出现的基因序列的识别( 关联分析) ，发现在疾病的不同阶段的致病基因( 路 径分析) ，可视化工具和遗传数据分析等。 ( 2 ) 应用在针对金融数据分析中。大部分银行和金融机构都提供丰富多样 的储蓄服务( 如支票、存款和商业及个人用户交易) ，信用服务( 如交易、抵押和 汽车贷款) ，和投资服务( 如提供保险和股票投资服务) 。因此，需要大量相对比 较完整、可靠和高质量的金融数据。这利于使用系统化的数据分和数据挖掘。数 据挖掘的主要应用包括：为多维数据分析和数据挖掘设计和构造数据仓库，贷款 偿还预测和客户信用政策分析，对目标市场客户的分类与聚类，洗黑钱和其他金 融犯罪的侦破等。 ( 3 ) 应用在零售业中。零售业是数据挖掘的主要应用领域，这是因为零售业 积累了大量的销售数据，顾客购买历史记录，货物进出，消费与服务记录，等等。 零售数据挖掘可有助于识别顾客购买行为，发现顾客购买模式和趋势，改进服务 质量，取得更好的顾客保持力和满意程度，提高货品销量比率，设计更好的货品 运输与分销策略，减少商业成本。数据挖掘的主要应用包括：基于数据挖掘的数 据仓库的设计与构造，销售、顾客、耗材、时间和地区的多维分析，促销活动的 有效性分析，顾客保持力( 忠诚度) 的分析，购买推荐和商品参照等。 第一章概述 数据收集和数据库创建 ( 2 0 世纪6 0 年代和更早) 一原始文件处理 数据库管理系统 ( 7 0 年代) 一层次和网状数据库系统 一关系数据库系统 一数据建模工具：实体一联系模型等 一索引和数据组织技术：b + 树、三列等 一查询语言：s q l 等 一用户界面：表单、报告等 一查询处理和查询优化 一事务管理、恢复和并发控制等 一联机事务处理( o l p t ) 高级数据库系统 ( 8 0 年代中期一现在) 一高级数据模型： 扩充关系、面向对象、 对象一关系、演绎 一面向应用 空间的、时间的、多媒体的、 主动的、科学的、知识库 基于w e b 的数据库系统 ( 9 0 年代一现在) 一基于) ( m l 的数据库系统 - w e b 挖掘 数据仓库和数据挖掘 ( 8 0 年代后期一现在) 一数据仓库和o l a p 技术 一数据挖掘和知识发现 新一代综合信息系统 ( 2 0 0 0 ) 图1 3 数据库技术的演化 第一章概述 ( 4 ) 应用在电信业中。电信业已经迅速地从单纯的提供市话和长话服务演 变为提供综合电信服务，如语音、传真、寻呼、移动电话、图像、电子邮件、计 算机和w e b 数据传输，以及其他数据通信服务。利用数据挖掘技术来帮助理解商 业行为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务质量是非常 重要的。数据挖掘的主要应用包括：电信数据的多维分析，盗用模式分析和异常 模式识别，多维关联和序列模式分析，电信数据分析中可视化工具的使用等。 ( 5 ) 应用在工程设计行业中。如设计行业大量可复用的设计图、效果图， 以往工程施工、建成后的照片，存放在数据库中，利用数据挖掘技术更好地利用 已有设计资源。数据挖掘的主要应用包括：设计数据的分析，设计图、效果图的 调用，以往工程施工中的问题分析等。但由于种种原因，在国内这方面的应用还 较少。 1 3 本论文所做工作 由于万维网上的各种多媒体资源越来越丰富，为了满足用户的需求，给用户 提供更多的更需要的多媒体资源，w e b m a r s 系统提供对w e b 上的多媒体资源进行 基于内容的搜索功能。本文作者参与了对此系统的性能测试。 本论文结合数据挖掘尤其是w e b 数据挖掘的理论，引入了更适用于万维网数 据挖掘的基予内容的多媒体检索系统。对此多媒体检索系统中用到的多媒体目标、 查询、查询求精及文本与图像的文件匹配模型进行了分析介绍。提出了查询求精 的重要性，并说明了求精的方法。对此检索系统在检索质量方面的性能测试进行 了阐述，并试验说明了此系统中查询求精的必要性及步骤。另外，简单介绍了一 些其他相似的多媒体检索系统。最后，对此基于内容的多媒体检索系统提出了结 论。 7 第二章数据挖掘理论l jw e b 数据库技术 第二章数据挖掘理论与w e b 数据库技术 数据挖掘是从大量数据中发现有趣模式，这些数据可以存放在数据库、数据 仓库或其他信息存储中。数据挖掘是一个年轻的跨学科的领域，源于诸如数据库 系统、数据仓库、统计学、机器学习、数据可视化、信息检索和高性能计算。其 他涉及的领域包括神经网络、模式识别。空间数据分析。图像数据库。信号处理 和许多应用领域，包括商务、经济学和生物信息学。 2 1 数据挖掘理论 2 1 1 数据挖掘的数据类型 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、 数据仓库、事务数据库、高级数据库系统、展开文件和w w w 。高级数据库系统 包括面向对象和对象关系数据库：面向特殊应用的数据库，如空间数据库、 时间序列数据库、文本数据库和多媒体数据库。 本论文所考虑的是多媒体数据库，尤其是对包含有图像内容的文件的检索。 多媒体数据库存放图像、音频和视频数据。它们用于基于图像内容的检索、声音 传递、视频点播、w w w 和识别口语命令的基于语音的用户界面等方面。多媒体 数据库必须支持大对象，因为像视频这样的数据对象可能需要兆字节级的存储。 还需要特殊的存储和搜索技术。因为视频和音频数据需要以稳定的、预先确定的 速率实时检索，防止图像或声音间断和系统缓冲区溢出，因此这种数据称为连续 媒体数据( c o n t i n u o u s - m e d i ad a t a ) 。 对于多媒体数据库挖掘，需要将存储和搜索技术与标准的数据挖掘方法集成 在一起。有前途的方法包括构造多媒体数据立方体、多媒体数据和多特征提取和 基于相似性的模式匹配。 2 1 2 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般 可以分两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性。预测 第二章数据挖掘理论与w e b 数据库技术 性挖掘任务在当前数据上进行推断，以进行预测。 在某些情况下，用户不知道他们的数据中什么类型的模式是有趣的，因此可 能想并行地搜索多种不同的模式。这样，重要的是，数据挖掘系统要能够挖掘多 种类型的模式，以适应不同的用户需求或不同的应用。此外，数据挖掘系统应当 能够发现各种粒度( 即不同的抽象层) 的模式。数据挖掘系统应当允许用户给出 提示，指导或聚焦有趣模式的搜索。由于有些模式并非对数据库中的所有数据都 成立，通常每个被发现的模式带上一个确定性或“可信度”度量。 下面给出数据挖掘功能及其可以发现的模式类型。 2 1 2 1 概念类描述：特征化和区分 数据可以与类或概念相关联。例如，在m a x c o m p u t e r 商店，销售的商品类包 括计算机和打印机，顾客概念包括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 。用汇总的、简 洁的、精确的方式描述每个类和概念可能是有用的。这种类或概念描述为类概 念描述( c l a s s c o n c e p td e s c r i p t i o n ) 。这种描述可以通过下述方法得到：1 ) 数据特 征化，一般地汇总所研究类( 通常称为目标类( t a r g e tc l a s s ) ) 的数据；2 ) 数据区 分，将目标类与一个或多个比较类( 通常称为对比类( c o n t r a s h n gc l a s s ) ) 进行比 较；3 ) 数据特征化和比较。数据特征化( d a t a c h a r a c t e r i z a t i o n ) 是目标类数据的一 般特征或特性的汇总。通常，用户指定类的数据通过数据库查询收集。例如，为 研究上一年销售增加1 0 的软件产品的特征，可以通过执行一个s q l 查询收集关 于这些产品的数据。 有许多有效的方法，将数据特征化和汇总。一种面向属性的归纳技术可以用 来进行数据的概化和特征化，也可以通过一步步地与用户交互将数据特征化。 数据特征的输出可以用多种形式提供。包括饼图、条图、曲线、多维数据立 方体和包括交叉表在内的多维表。结果描述也可以用概化关系( g e n e r a l i z e d r e l a t i o n ) 或规则形式( 称作特征规则) 提供。 数据挖掘系统应当能够产生一年之内在m a x c o m p u t e r 花费$ 1 0 0 0 以上的顾 客特征汇总的描述。结果可能是顾客的一般轮廓，如年龄在3 0 4 5 、有工作、有很 好的信用等级。系统将允许用户在任意维下钻，如在o c c u p a t i o n 下钻，以便根据 他们的职业来观察这些顾客。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一个或多个对 第二章数据挖掘理论与w e b 数据库技术 比类对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数据 库查询检索。例如，你可能希望上一年销售增加1 0 的软件产品与同一时期销售 至少下降3 0 的那些产品进行比较。用于数据区分的方法与用于数据特征化的类 似。 输出的形式类似于特征描述，但区分描述应当包括比较度量，帮助区分目标 类和对比类。用规则表示的区分描述称为区分规则( d i s c r i m i n a t i o nr u l e ) 。用户应 当能够对特征和区分描述的输出进行操作。 数据挖掘系统应当能够比较两组m a x c o m p u t e r 顾客，如定期( 每月多于2 次) 购买计算机产品的顾客和偶尔( 即每年少于3 次) 购买这种产品的顾客。结果描 述可能是一般的比较轮廓，如经常购买这种耗材的顾客8 0 在2 0 一4 0 岁之间，受 到大学教育：而不经常购买这种耗材的顾客6 0 或者太老，或者太年轻，没有大 学学位。沿着维下钻，如沿o e 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 m 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 m = b 1 八，a b n ”的规则，其中，a i ( i ( 1 ，m ) ) ，b j ( j ( 1 ，n ) ) 是 属性值对。关联关系x = ，y 解释为“满足x 中条件的数据库元组多半也满 足y 中条件”。 给定m a x c o m p u t e r 关系数据库，一个数据挖掘系统可能发现如下形式的关联 规则： a g e ( x ，“2 2 3 5 ”) a i n c o m e ( x ，“2 0 k 2 9 k ) = b u y s ( x ，“m p 3 ”) g s u p p o r t = 2 ，c o n f i d e n c e = 5 5 目 其中x 是变量，代表顾客。该规则是说，所研究的m a x c o m p u t e r 顾客2 ( 支 持度) 在2 2 - - 3 5 岁，年收入2 0 k - - 2 9 k ，并且在m a x c o m p u t e r 购买m p 3 机。这 个年龄和收入组的顾客购买m p s 机的可能性有5 5 ( 置信度或可信性) 。 这是一个以上属性或谓词( 即a g e ，i n c o m e 和b u y s ) 之间的关联。采用多维 数据库使用的术语，每个属性称为一维，上面的规则可以称作多维关联规则 1 0 第二章数据挖掘理论与w e b 数据库技术 ( 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 e ) 。 假定作为m a x c o m p u t e r 的市场部经理，想知道在一个事务中，哪些商品经常 被一块购买。这种规则的一个例子是： c o n t a i n s ( t ，“c o m p u t e r ”) = c o n t a i n s ( y ，“p r i n t e r ”) 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 ”，则它也包含“p r i n t e r ”的可能性 有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 l a s s o c i a t i o nr o l e ) 。去掉谓词符号，上面的规则可以简单地写成c o m p n t e r 辛p r i n t e r l 1 。5 0 j 。 2 1 2 3 分类和预测 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模型 ( 或函数) ，以便能够使用模型预测类标记未知的对象类。导出模型是基于对训练 数据集( 即其类标记已知的数据对象) 的分析。 导出模型可以用多种形式表示，如分类( i f - - t h e n ) 规则、判定树、数学公 式或神经网络。判定数是一个类似于流程图的树结构，每个节点代表一个属性值 上的测试，每个分支代表测试的一个输出，树叶代表类或类分布。判定树容易转 换成分类规则。当用户分类时，神经网络是一组类似于神经元的处理单元，单元 之间加权连接。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望 预测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时， 通常称之为预测( p r e d i c t i o n ) 。尽管预测可以涉及数据值预测和类标记预测，通常 预测限于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。 相关分析( r e l e v a n c ea n a l y s i s ) 可能需要在分类和预测之前进行，它试图识别 对于分类和预测无用的属性。这些属性应当排除。 假定作为m a x c o m p u t e r 的销售经理，想根据销售活动的三种反应，对商店的 商品集合分类：好的反应，中等反应和没有反应。如想根据商品的描述特性，如 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 ，对这三类的每一种导出模型。结果 分类应最大限度地区别每一个类，提供有组织的数据集图像。假定结果分类用判 第二章数据挖掘理论与w e b 数挺库技术 定树的形式表示。例如，判定树可能把p r i c e 看作最能区分三个类的因素。该树可 能揭示，在p r i c e 之后，帮助进一步区分每类对象的其他特性包括b r a n d 和 p l a c e _ m a d e 。这样的判定树可以帮助理解给定销售活动的影响，并帮助设计未来更 有效的销售活动。 2 1 2 4 聚类分析 聚类分析与分类和预测不同，聚类( c l u s t e r i n g ) 分析数据对象，而不考虑己 知的类标记。一般情况下，训练数据中不提供类标记，因为不知道从何开始。聚 类，可以用于产生这种标记。对象根据最大化类内的相似性、最小化类间的相似 性的原则进行聚类或分组。即对象的簇( 聚类) 这样形成，使得在一个簇中的对 象具有很高的相似性，而与其他簇中的对象很不相似。所形成的每个簇可以看作 对象类，由它可以导出规则。聚类也便于分类编制( t a x o n o m yf o r m a t i o n ) ，将观察 到的内容组织成类分层结构，把类似的事件组织在一起。 聚类分析可以在m a x c o m p u t e r 的顾客数据上进行，以便识别顾客的同类子群。 这些簇可以表示每个购物目标群。图2 - 1 显示了一个城市内顾客的2 一d 图。数据 点的三个簇是显而易见的。 2 1 2 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模式不一致。这 些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而 丢弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更 有趣。孤立点数据分析称作孤立点挖掘( o u t l i e r m i n i n g ) 。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并使用距 离度量，到其他聚类的距离很大的对象被视为孤立点。基于偏差的方法通过考察 一群对象主要特征上的差别识别孤立点，而不是使用统计或距离度量。 第二章数据挖掘理论与w e b 数据库技术 2 1 26 演变分析 图2 1 关于一个城市内顾客位置的2 - d 图 显示3 个聚类，每个聚类的“中心” 用“+ ”标记 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋势， 并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类， 这类分析的不同特点包括时间序列分析、序列或周期模式匹配和基于类似性的数 据分析。 2 1 3 模式评估兴趣度问题 数据挖掘系统具有产生数以万计的模式或规则的潜在能力。但是，对于给定 的用户，在可能产生的模式中，只有小部分是他感兴趣的。一个模式是有趣的 ( i n t e r e s t i n g ) ，如果( 1 ) 它易于被人理解；( 2 ) 在某种程度上，对于新的或测试 数据是有效的；( 3 ) 是潜在有用的；( 4 ) 是新颖的。如果一个模式符合用户确信 的某种假设，它也是有趣的。有趣的模式表示知识。 第二章数据挖掘理论与w e b 数据库技术 存在一些模式兴趣度的客观度量。这些度量基于所发现模式的结构和关于它 们的统计。对于形如x = y 的关联规则，一种客观度量是规则的支持度( 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 ( ylx ；即包含x 的事务也包含y 的概率。更形式地，支持度和置信度定义为： s u p p o n ( x = y ) = p ( x u y ) c o n f i d e n c e ( x = y ) = p ( yi x ) 一般地，每个兴趣度度量都与一个阀值相关联，该阀值可以由用户控制。例 如，不满足置信度阀值5 0 的规则可以认为是无趣的。低于阀值的规则可能反映 噪声、异常或少数情况，可能不太有价值。 尽管客观度量可以帮助识别有趣的模式，但是仅有这些还不够，还要结合反映 特定用户需要和兴趣的主观度量。例如：对于市场经理，描述频繁在m a x c o m p u t e r 购物的顾客特性的模式应当是有趣的；但对于同一数据库，分析雇员业绩模式的 分析者，它可能不是有趣的。此外，有些根据客观标准是有趣的模式可能反映一 般知识，因而实际上并不令人感兴趣。主观兴趣度度量基于用户对数据的确信。 这种度量发现有趣的模式，如果它们是出乎意料的( 对照用户的确信) ，或者提供 用户可以采取行动的策略信息。在后一种情况下，这样的模式称为可行动的 ( a c t i o n a b l e ) 。意料中的模式也可能是有趣的，如果它们证实了用户希望验证的假 设，或与用户的预感相似。 数据挖掘系统能否产生所有有趣的模式涉及数据挖掘算法的完全性。期望数 据挖掘系统产生所有可能的模式是不现实的和低效的。实际上，应当根据用户提 供的限制和兴趣度对搜索聚焦。对于某些数据挖掘任务，这通常能够确保算法的 完全性。关联规则挖掘就是一个例子，那里，使用限制和兴趣度度量可以确保挖 掘的完全性。 数据挖掘系统是否仅产生有趣的模式是数据挖掘的优化问题。对于数据挖掘 系统，仅产生有趣的模式是非常期望的。这对于用户和数据挖掘系统是非常有效 的，因为这样就不需要搜索所产生的模式，以便识别真正有趣的模式。在这方面 已经有了进展。然而，在数据挖掘中，这种优化仍然是个挑战。 为了有效地发现对于用户有价值的模式，模式兴趣度度量是必需的。这种度 4 第二章数据挖掘理论与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 上的信息只是很小的一部分是相关的或有用的。据分析9 9 的w e b 信息对9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上的很小很小一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴 趣的，而且会淹没所希望得到的搜索结果。 第二章数据挖掘理论与w e b 数据库技术 然而，正是这些挑战推动了可用于因特网上多媒体信息检索的各种搜索引擎 的开发与研究工作。 2 2 iw e b 数据挖掘的概念 万维网数据挖掘可以定义为w w w 上有用信息的发现和分析。万维网数据挖 掘是一门综合技术，涉及领域非常广泛，如：数据挖掘、信息学、计算机语言学、 人工智能等领域。w e b 数据挖掘从数据挖掘而来，但由于万维网上数据信息的特 点往往以多媒体形式出现，使得它又不同于一般的数据挖掘，它所面临的挑 战更大。 2 2 2w e b 挖掘的任务 通常w e b 把挖掘可以分为3 个子任务：资源发现、信息提取、概括。 1 ) 资源发现：是指从w e b 上搜索可用的信息； 2 ) 信息提取；是从已经发现的资源中提取出有用的信息。 3 ) 概括：是对w e b 信息自学习的过程，通过学习抽取一定的规则。 一般来说，w e b 挖掘的数据来源途径有两个：搜索引擎的结果集和w e b 上的 在线消息。这两种方式各有所长，需要视具体的应用而定。目前，已经有几种资 源发现模型广泛应用于i n t e r n e t 上：目录浏览模型( w a i sa n d g o p h e r ) 、检索 模型( a r c h i ea n da l t av i s t a ) 等。本文讨论的是一种既可用于浏览也可进行全文检 索的多媒体搜索引擎，另外在4 _ 3 节中还提到了一些其他的多媒体检索系统。 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 挖掘的分类图。内容挖 掘是从w e b 上自动查找或检索可用资源；结构挖掘就是概括出w e b 站点和w e b 页的结构信息：使用记录的挖掘是从服务器访问日志、用户策略、用户对话和事 务处理信息中得到用户的访问模式和感兴趣的信息，并试图预测用户的行为。 1 6 第二章数据挖掘理论与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 c b 使用记录挖掘：是指从服务器日志( 主要包括每个用户的浏览行为) 中 发现用户的访问模式，通过使用记录挖掘为用户提供个性化服务。w e b 服务器一 般会自动保存用户的请求信息以及访问w e b 页面的方式等，这些记录被称为同志。 使用记录挖掘不仅要找出用户经常访问的u r l 路径，而且也要找出用户有可能要 访问的相关站点的链接。 第二章数据挖掘理论与w e b 数据库技术 2 3 多媒体数据库及其检索系统 2 3 1 多媒体数据库简介 多媒体数据库是指存储和管理大量多媒体对象的数据库，如音频数据、图象 数据、视频数据、序列数据以及超文本数据( 包含文本、文本标记( t e x tm a r k u p ) 和链接) 。由于音频视频设备、c d - - r o m 和因特网的流行和普及，多媒体数据库 系统变得日益常见。典型的多媒体数据库系统包括n a s a ( 宇航局) 的e o s ( 地球 观测系统1 ，各种图像和音频视频数据库，人类基因数据库，和因特网数据库。 2 3 2 信息检索和数据库系统 信息检索是与数据库系统并行发展了很多年的一个领域。与数据库系统不同， 信息检索研究的主要不是结构数据的查询和事务处理的问题，而是研究大量文本 文档的信息组织和检索。典型的信息检索问题是基于用户的输入( 如关键字或样 例文本) 定位相关的文档。典型的信息检索系统有联机图书馆目录系统和联机文 档管理系统。 由于信息检索和数据库系统处理的是不同类型的数据，数据库中的一些常见 问题并不出现在检索系统中，如并发控制、恢复、事务管理和更新。同样信息检 索中的一些问题不出现在传统的数据库系