多媒体技术(之九)

第十一章多媒体数据挖掘的基本方法

多媒体数据挖掘是多媒体技术中一个新兴的研究领域。为此介绍多媒体数据挖掘的相关概念，多媒体数据挖掘模型MDMM；叙述多媒体数据挖掘的关联规则方法与新概念，多媒体数据挖掘的特征匹配技术和一种距离特征的最近邻接快速匹配算法FNNA；以及基于人工神经网络NN的多媒体语音特征挖掘的SOLA算法。掌握这些典型的多媒体数据挖掘方法，有利于发现多媒体数据之间的潜在关系，进行相关的检索与应用。11.1多媒体数据挖掘概述

11.1.1媒体数据挖掘的相关概念

多媒体数据挖掘是目前国内外多媒体技术、数据库技术和信息决策等领域最前沿的研究方向之一，是数据挖掘的一个新兴而且富有挑战性的子领域。1.数据挖掘数据挖掘(DM：DataMining)，又称数据开采，也称为广义的数据库中的知识发现(KDD：Knowledgediscoveryindatabase)。它是从大型数据库中发掘出潜在的、未知的、有用的知识，达到为决策服务的目的，是当前的一个热门课题。目前已有许多DM方法，并在其基础上实现了一些数据挖掘的工具和应用，在经典的交易数据库和大型关系数据库中取得了显著的成就。11.1.1媒体数据挖掘的相关概念2.多媒体数据挖掘信息时代的数据挖掘不仅仅是对数据库中结构化数据进行数据挖掘，更重要的是对丰富而海量的半结构或非结构化的文本、图像、视频和音频等多媒体数据进行挖掘。大量的实际需求以及新兴多学科交叉的迅速发展，使多媒体数据挖掘技术的研究与应用，具有十分重要的意义。多媒体数据挖掘(MDM：Multimediadatamining)是指从多媒体数据中抽取隐藏的知识、多媒体数据关系或其他非显形存储的模式；获取事件的趋向和关联，为用户提供问题求解层次的决策支持能力。它是多媒体数据的存储、管理、检索、分析和表达等多媒体技术与数据挖掘技术的紧密结合。11.1.1媒体数据挖掘的相关概念2.多媒体数据挖掘多媒体数据挖掘主要涉及数据挖掘和多媒体信息处理等研究领域。以往多媒体的研究集中于基于内容的检索（CBR），在某种程度上解决了信息搜索和信息资源发现的问题。但是，人们并不满足信息存取这个层次，因为信息检索只能获取与用户要求相关的“信息”，而不能从大量多媒体数据中发现和分析出其中蕴含的有价值的“知识”。为此，需要研究比多媒体信息检索更高层次的新方法新技术，即多媒体数据挖掘。为了实现多媒体信息的充分利用，以及基于内容或语义的检索，智能化检索，则需要运用多媒体数据挖掘的相关算法和方法。11.1.1媒体数据挖掘的相关概念3．多媒体数据挖掘系统数据挖掘技术正在不断发展成熟，可以将DM与多媒体数据的数据建模、表示、存储和检索等技术相结合，形成多媒体数据挖掘技术，构建多媒体数据挖掘系统(MDMS：MDMSystem)。多媒体数据挖掘系统可以应用于卫星遥感遥测、医学影像诊断、证劵股市分析、地质勘探、新闻媒体、网上搜索引擎、远程教育等等领域。例如，MDMS系统可以从大量观测到的天文图像中，分析出星体、星系的模式，从大量传输的雷达图像中，分析出星球上火山的模式，从而指导发现和确认新的星体、星系和火山。又如，CONQUEST系统，将卫星数据和地球物理数据结合，发现全球气候变化模式；SKtCAT系统，集成图像处理和数据分类技术，从一个非常大的卫星图像数据集中识别出其所包含的“天体对象”；Siman-erase则是大学设计实现的多媒体数据挖掘器。目前，多媒体数据挖掘研究从总体看，仍然处于初级阶段，需要进一步深入研究，并开发实现更多的多媒体数据挖掘系统。11.1.2多媒体数据挖掘面临的主要挑战1.挖掘对象的复杂性挖掘对象包括文本、图像、图形、音频、视频、网页等多种复杂形式的媒体数据，更大型的数据库、更高维数和属性之间更复杂的关系。多媒体数据信息十分丰富，且呈现半结构化或非结构化的特性，使得数据挖掘要处理的数据量通常十分巨大，甚至达到TB级；更多的属性意味着更高维的搜索空间，可能导致组合爆炸；属性值之间的关系变得更加复杂，使得搜索知识代价极高。当前，有研究用并行处理或抽样的方法处理大规模数据；可根据问题的定义或相关知识选择出需要的属性，并利用一定的概念继承来降低维数；处理属性之间的复杂关系，往往利用一些背景知识，如不同层次的概念所组成的概念树等等。11.1.2多媒体数据挖掘面临的主要挑战2.用户交互和领域知识有效的决策过程往往需要多次交互和反复，即信息反馈。用户的背景知识和指导作用可加快挖掘过程，保证发现的知识的有效性。现阶段，国际领先的多媒体数据挖掘研究成果仍旧无法脱离领域性的局限，其应用范围限制在一个特定的环境中。将相关领域知识融入数据挖掘过程，是一个重要但没有很好解决的问题，对于多媒体数据这种问题尤为突出。11.1.2多媒体数据挖掘面临的主要挑战3.知识的表示和表达机制基于内容或语义的多媒体数据挖掘，必然涉及到“知识”概念。人工智能中知识的作用一是作为问题求解的前提，二是用知识控制问题求解的进程。多媒体数据中挖掘出的信息若以知识的形式表示，可以使问题的求解变得容易，并且具有较高的求解效率。常用的知识表示方式有语义网络、框架或脚本等。知识的表示有利于计算机的处理，但并不适用于用户的理解。因此，知识还需通过有效的表达方式，以更易于接受的形式，如图形、自然语言和可视化技术等，使用户有效地评价和更新知识。11.1.2多媒体数据挖掘面临的主要挑战4.系统集成与证实技术现有的数据挖掘系统不能支持多种平台，要充分发挥系统的功能，挖掘系统需要和其它决策支持系统有机集成。数据挖掘使用特定的分析方法或逻辑形式发现知识，但系统缺乏交互式证实所发现知识的能力。而且有待挖掘数据本身也可能存在错误，数据挖掘技术必须能够确定结论具有何种程度的有效性。此外，还包括知识的维护和更新，目前有研究采用增量更新的方法来维护己有的知识。11.1.3多媒体数据挖掘的基本思想1.解决源多媒体数据的存储管理和数据收集多媒体数据挖掘首先要研究与利用现有的一些多媒体数据库技术，提供较为有效的数据模型(如面向对象模型)和数据库体系结构等方法与手段，以解决源多媒体数据的存储和管理问题。其次，解决相关数据的收集。研究与利用相应的多媒体数据检索技术，如基于内容的检索方法，结合一定的背景知识，抽取数据特征，执行多媒体数据的检索，获取到相关的数据。2.多媒体数据的特征挖掘获取源多媒体数据隐含的有用的知识，很重要的环节是进行多媒体数据的特征挖掘。多媒体数据特征的表示，基本上可以用数值型的结构化数据形式，以利用现有的一些数据挖掘方法，在相关背景知识的辅助下进行知识挖掘。但是，现有数据挖掘方法主要是针对商业数据库和关系数据库，没有充分考虑媒体的特征数据，所以应加以改进，使之适用于多媒体数据的特征数据。11.1.3多媒体数据挖掘的基本思想3.研究多媒体数据挖掘的新方法多媒体数据挖掘面临诸如媒体种类的多样性和复杂性，媒体数据的海量性，挖掘数据预处理的困难性，挖掘模式的艰难性等一系列的难题，因此我们必须用新思维、新方法与高效算法来解决这样的复杂知识发现问题。4.构建多媒体数据挖掘工具综合多媒体数据挖掘的多种方法，充分利用并扩充已有的联机分析处理（OLAP）方法和可视化工具，集成具有一定的开放性和易于开采知识的多媒体数据挖掘器。5.多媒体数据挖掘的基本步骤多媒体数据挖掘过程一般分为三个主要阶段，即数据准备、挖掘操作、知识表示和解释。知识的发现可描述为这些阶段的反复过程。其步骤描述遵从下节多媒体数据挖掘模型MDMM(MDMModel)的要求。11.2多媒体数据挖掘模型MDMM11.2.1MDMM模型结构与数据平台1．挖掘模型的整体结构多媒体数据挖掘模型的整体结构如图10-1所示。模型中包含数据准备模块、数据挖掘模块和结果表达与解释模块。数据准备模块是将多文件和多数据运行环境中的数据，合并处理为集成的数据，存储于多媒体数据库，解决语义的模糊性、数据遗漏和清晰化、简洁化等问题；将集成的数据进行预处理，抽取其特征，存储在特征库，以便有效地支持多媒体数据的查询检索；11.2多媒体数据挖掘模型MDMM11.2.1MDMM模型结构与数据平台

利用有效的多媒体数据检索技术，按照用户的需求，对相关特征数据进行查询检索；使用相关的数据挖掘策略，对多媒体数据进行挖掘，从而发现用户感兴趣的知识；根据用户的最终决策目的，分析提取的信息，过滤用户满意的信息，从而挖掘与用户要求相符的隐含知识。如果决策者不满意，则要重复MDMM模型的数据挖掘过程。11.2.1MDMM模型结构与数据平台2．挖掘模型的数据平台构建多媒体数据挖掘系统，应将多媒体数据的数据建模、数据表示、数据存储和检索等多媒体数据库技术与数据挖掘在关系数据库领域中的技术相结合。MDMM模型用多媒体数据库（MDB）实现对各种媒体数据，以及诸如关键字、某图像出现频率等一些附加信息的存储，MDB为模型提供良好的数据平台。采用MDB作为MDMM模型数据平台是因为:①将收集的多媒体数据用多媒体数据库管理系统（MDBMS）来管理，在建立MDB时可完成数据的清洗和集成工作；对已有的MDB，同样也可利用MDBMS来进行此项工作。②多媒体数据类型复杂多样，对其进行特征抽取、知识挖掘，首先要解决数据的存储、管理问题。现有的多媒体数据库技术的研究成果，提供了良好的数据模型、数据表示和数据管理，从而能更加有效地进行特征的抽取。由于特征库采用面向对象数据模型，也是重要的多媒体数据库的数据模型，因此特征库可存放在MDB。11.2.1MDMM模型结构与数据平台③MDB技术提供有效的索引机制与多媒体数据的面向对象模型或超媒体模型的结合，能有效地支持数据的查询、检索和OLAP的执行，提高系统工作的效率。因此，MDMM模型用MDB为多媒体数据的有效管理、特征库的建立、CBR的执行、OLAP操作和多媒体数据的知识挖掘提供强有力的支持。而且多媒体数据仓库(MDW)的构建也要利用MDB技术，存放集成的、历史的和稳定的多媒体数据。11.2.2MDMM模型的主要构件1.数据准备模块包括数据收集和集成、数据简化净化、特征抽取和数据检索选择四个子模块。（1）数据收集通过OLAP和相关的数据收集方式，从原始数据数据库和文件、或外部数据源中收集的原始数据，需要进行数据分析、调整、删减和集成；然后以一定的存储方式存储在多媒体数据库。（2）净化带噪音数据从多个数据库和数据源中抽取的信息和数据存在的问题有：字段值、字段名称的错误；字段内容不详；同一字段的同一内容存在不同的表达方式，造成对数据语义、含义理解的不确切性；数据搜集过程中存在的各种错误等。数据净化的目标是保证所表达数据的一致性，参照完整性和数据精确性。主要采用的措施为：检查拼写错误；去掉重复记录；补充不完全的记录；解决不一致的记录；用测试查询来验证数据；根据验证结果反复迭代这几个步骤。11.2.2MDMM模型的主要构件（3）数据简化有关视频、声频、图像等多媒体数据的维度一般较大，直接进入多媒体数据库必定影响进一步检索和挖掘工作的效率和正确性，同时也不便于数据分析者理解这些数据的内涵。所以在知识决策和数据挖掘中，查询大型数据库时为了减少相应时间，只要不影响查询的要求，应尽量简化维度。例如，图像颜色特征是256维，我们可以将颜色特征值减少到64维或更小。当然，维度的减少会影响查询的效果和精确度，故维度的简化必须符合查询要求。同时可以先不实现某些一段时间内使用率非常低的维度，将它们作为多媒体数据库的暂不加工数据。11.2.2MDMM模型的主要构件（4）数据集成通过上述处理后的数据信息量，可能仍然远远超过我们所要求的、在有限时间内所能处理的信息量。因此还需要进一步的数据集成，以便决定不同属性的使用、不同样本的大小和对要解决问题的不同的精确定义。集成的数据利用MDB技术，存储于一般的MDB或MDW。这个过程要重复多次，并且有很多人为的智力因素的影响，因此到最后才能确定某个任务的定制多媒体数据库。11.2.2MDMM模型的主要构件(5）特征抽取和特征库的构建在查询和使用相关数据之前，先要对多媒体数据进行预处理，抽取其特征值。特征值主要包括颜色、形状、纹理结构、空间信息、行为特征，以及关键字等信息。对于多媒体数据库的数据，特征库存储了许多描述性信息和特征信息。描述信息包括的域有：图像文件名，图像和视频类型（如jpg、bmp、avi、mpeg等），一组已知的与该图像相关的关键字符。特征信息由一组向量集表示，每个视觉特征都有相应的向量，如颜色向量、方向向量、颜色布局向量、边界布局向量和行为向量等。特征库的数据模型和数据类型至关重要，它应能表示媒体数据的各种特征，有效地支持多媒体数据的查询检索。（6）数据检索和相关数据的收集利用有效的多媒体数据检索技术，根据用户要求，检索选择相关特征数据，用于知识的挖掘。如CBR技术，基于空间的检索技术(SBR)，基于语义的模糊检索技术(SBFR)等。11.2.2MDMM模型的主要构件2.数据挖掘模块

实现各类知识发现的模块有多种，如特征器，比较器，分类器、关联器和模糊神经网络等模块，从而发现用户感兴趣的知识。（1）特征器从多媒体数据库的一组相关数据中发现一组多抽象级的典型特征。它为用户提供了上旋和下钻的能力，使用户能看到数据的多层次视图。（2）比较器发现多媒体数据库中一组相关数据不同类之间相区别的特征，以便比较和区分目标类与比较类的一般或特定的特征。例如，显示某一时间，商业Internet与教育Internet的颜色丰富性之间的区别。11.2.2MDMM模型的主要构件（3）关联器从多媒体数据库的一组相关数据中发现一组关联规则。每个关联规则说明了数据库的某些数据项中经常出现的模式或关系。如关联器发现:“静态图像，其频繁使用的颜色，大小和关键字‘大海’之间的关系是什么”的一个关联规则是:“如果图像是大图像，并与‘大海’有关，则图像有64%的可能性是蓝色的”，或“如果图像是小图像，并与‘大海’有关，则图像为深蓝色的可能性是58%”。一个典型的关联规则的形式为：“X→Y[s%,c%]”,X,Y为一组谓词，其中s%:规则的支持度，即X,Y在所有可能的事例中同时发生的可能性。c%:规则的可信度，即在X为真的情况下，Y也真的可能性。（4）分类器根据一些已知的类标志对多媒体数据进行分类。其结果是对多媒体数据集的分类和每一类的特征描述。用决策树表示的分类也可用于预测。11.2.2MDMM模型的主要构件3.模式表达和解释模块在KDD中，如何把挖掘到的模式表达为便于理解的知识，也是一个难以解决好的问题。根据决策需要，区分出最有价值的信息，进行解释，通过决策支持工具提交给决策者。目前挖掘的模式表现，采用可视化的计算机辅助方法，如直观的图形图表等。数据可视化在数据挖掘中非常重要。11.2.3多媒体数据特征立方体

1．数据立方体(Cube)数据立方体是一种用于存储多维数据，并在不同抽象层次实现对这些维的集成查询的抽象数据结构。由于Cube独特的结构，通过上旋、下钻、切片、切块等操作，实现对某部分数据和不同数据层次的访问和集成，很好地支持OLAP操作和多层次的数据挖掘。由于多媒体数据的复杂性，其特征立方体的构建也较一般的数值型数据立方体更为复杂。2．多媒体数据特征立方体的特性多媒体数据特征立方体有多种维，根据MDMM模型由CBR的结果及用户要求的知识类型来决定。11.2.3多媒体数据特征立方体

例如，图像或视频基于某种继承的比特大小；帧的宽度和高度；图像或视频数据的生成时间或最后修改时间；图像或视频数据的类型，如gif、jpeg、bmp、avi等；帧序列的持续时间，对于图像数据则为0；使用预定义的概念继承的关键字；颜色，使用预定义的颜色继承；形状；对象边界定向；对象空间位置，可用其质心的位置定义；对象大小，可用组成它的像素数表示；对象或图像出现的次数等等。这种数据立方体包含的信息实际为特征库信息的子集，其维是特征库中定义的属性的子集，其结构和内容由CBR的结果及用户所要求的知识的类型决定。特征立方体使用的概念继承可以是特征库中所使用的概念继承，也可是面向应用的；可由用户自定义，或系统根据其所包含的信息按某种算法自动生成。11.2.3多媒体数据特征立方体

例如，对于数值维，可根据CBR的结果，对其进行统计，将其值域进行不同次数的均分，以得到该维可以使用的一种概念继承。利用CBR技术，从特征库中选择知识挖掘的相关数据，类似于关系数据库中的选择操作；而根据挖掘要求从检索结果中选择需要的属性来构造立方体的维，类似于关系数据库中的投影操作。11.2.3多媒体数据特征立方体

3．多媒体数据特征立方体的结构简化多媒体数据特征立方体的复杂结构，也可采用以下方法简化其结构。（1）属性删除通过对用户请求进行分析，得到与所需知识相关的属性，再根据属性间的相关性及其阈值，删除与挖掘结果关系弱的属性。（2）属性概括将属性值概括为它的相应高层次的属性值，即把细粒度的数据概括为相应的粗粒度的数据。对于一些特征，如果用RGB模式的颜色，则在特征立方体中要占有3维，而R、G、B的值域又是[0,255]，使得特征立方体较为复杂。对于立方体，每增加一维都会使其结构变得更加复杂，其物理实现也是个极大的难题。实际应用中，一般使用抽象级较高的概念，而不是精确的颜色值表示知识规则，故可利用概念继承，对原有的属性进行概括，以简化数据立方体的结构。例如颜色.可概括为深蓝、浅蓝、深红、浅红等。对于多值属性，如图像的多种颜色，可选取其中具有该颜色的像素数最多的几种颜色，即用最频繁颜色表示该图像的颜色特征，使所对应的数据立方体大为简化。11.3多媒体数据关联规则挖掘技术

关联规则的挖掘是数据挖掘技术中经常使用的技术，它能够揭示大型数据集合中有趣的趋势、模式和规则。关联规则挖掘一般以事务为对象，辨别事务项目之间是否存在某种关联关系。多媒体数据库中人工标识所有媒体对象实际上难于实现，我们在执行挖掘之前，通过自动的或半自动方式获取媒体的内容来进行分析，产生的描述可以是颜色、纹理、形状、行为和大小等。例如，通过图像挖掘，发现人脑结构与大脑功能的关联、医学X光片与病灶的关联等。11.3.1关联规则的挖掘关联规则表示数据库中一组对象之间某种关联关系的规则。1.项集与项集支持度及频繁项集设I={i1,i2,…,im}是m个数据项（项目）的集合，D是一个事务集，其中每一事务T是一个数据项子集，TI，且每一个T有唯一的标识TID。设A为一个数据项集合，即一个由项目构成的集合，称为项集（itemset）。事务T包含项集A，当且仅当AT。项集中项的数量称为项集的长度。一个包含k个数据项的项集称为k项集。例如顾客购买“计算机”的同时也会购买“软件”的购物模式中，集合{计算机,软件}就是一个2项集。项集的支持度(support)是指一个项集的出现频度，即在事务集D中包含该项集的事务记录数。对于X，XI,若D中包含X的事务个数为n，则support(X)=n。如果项集的支持度超过用户给定的项集最小支持度阈值，则称该项集是频繁项集或大项集。11.3.1关联规则的挖掘2.关联规则及其支持度和信任度关联规则是形如XY的逻辑蕴含式，其中XI,YI,且X∩Y=

。如果事务集D中有s%的事务包含X∪Y，则称关联规则XY的支持度为s%。若项集X的支持度记为Support(X)，规则的信任度confidence为support(X∪Y)/support(X)，则关联规则XY的支持度和信任度的形式分别描述如下：support(XY)=D中包含(X∪Y)的事务的百分比confidence(XY)=support(X∪Y)/support(X)例如，顾客购买“计算机”的同时也会购买“软件”的购物模式的关联规则可描述为：计算机软件[support=2%,confidence=60%]挖掘关联规则就是找出这样一些规则，它们的规则支持度和信任度，分别满足（如大于或大于等于）用户指定的规则的最小支持度阈值和最小信任度阈值。满足最小支持度阈值和最小信任度阈值的关联规则为强规则。11.3.1关联规则的挖掘3.关联规则挖掘方法的分析与讨论发现关联规则需要经历如下两个步骤：(1)找出所有频繁项集。(2)由频繁项集生成满足最小信任度阈值的规则。第二步生成所希望的规则，一个直接的方法是：对于每个频繁项集L，找出L的所有非空子集；对于每个L的非空子集R，若support(L)/support(R)≥最小confidence，，则输出形式为R（L-R）的规则。关联规则挖掘问题的主要难点在于数据量巨大，其算法的效率是关键。由于步骤(2)相对步骤(1)简单，因此重点在步骤(1)，即找出频繁项集。围绕该问题，Apriori算法，重复扫描数据库，在第K次扫描时产生长度为K的频繁项集，称为LK，而在第K+1次扫描时，只考虑由LK中的K项集产生的长度为K+1的候选集CK＋1。该算法的依据是：任何频繁项集的子集也是频繁项集。因此，除第1次扫描外，每次扫描考察的并非所有项目的组合，而是候选集CK。11.3.1关联规则的挖掘Apriori算法中产生候选集CK的方法：用K-1候选集中的项集进行连接操作，再从其结果中删除某些项集，这些项集的某一(k-1)元子集不在k-1元频繁项集中。为了精简候选集的大小和减少对数据库的扫描遍数，又有一些改进方法。例如使用哈希（Hashing）技术有效地改进了候选集的产生过程；把数据库进行分割处理的算法，降低了挖掘过程中I/0操作的次数；使用的抽样方法，可用较小的代价从大型数据库中找出关联规则。通常的关联规则挖掘方法，认为项集I中的项是无重复的。如Apriori等算法的很大缺陷，在于没有考虑事务中项的出现次数，有可能丢失有用的信息。例如，一个关联规则：“2个蓝色的圆纹理密度高”，若不是2个蓝色的圆，则不能得出纹理密度高的结论。所以，不考虑项的出现次数，可能会造成有用信息的丢失，应加以改进。此外，基于大支持度的强规则的定义，在一些图像应用中也不完备。医用图像中，一些经常出现(即支持度很大)的特征，对用户可能是无用的，而一些低支持度的现象，却可能有用。因此，应改进这个强规则的定义，使之具有足够强的关联。11.3.2多媒体关联规则及其新概念

1.两种支持度基于事务的支持度是包含某一项集或证实某一条件的事务数，说明了一项集或断言在一事务集中频繁或具有意义的程度。图像数据集中常把图像作为事务，但同一对象可能在一个图像中重复出现。因此，要引入基于对象的支持度，以反映对象的次数，而不是事务、图像的次数。采用基于事务或基于对象的支持度，应由用户根据要求来选择。允许项在规则中重复出现的关联规则，称为带有重复项的关联规则。11.3.2多媒体关联规则及其新概念

2.几个定义定义1:带有重复项的多媒体关联规则与图像或视频中视觉对象的特征相关联，形式为:a1P1∧a2P2∧a3P3∧……∧anPn→b1Q1∧b2Q2∧……∧bmQm(c%)c%为规则的置信度，Pi和Qj为图像特征的断言，包括拓扑特征、视觉特征或图像大小、关键字等，ai,bj(i∈[l..n],j∈[l..m])为整数，表明对象特征或项集的出现次数。aP为真，当且仅当P的出现次数为a。11.3.2多媒体关联规则及其新概念

定义2:一图像集D中某一断言P的支持度σ(P/D)σ(P/D)为D中所有图像的对象中，在某一概念层次证实断言P的百分比。一个多媒体关联规则P→Q的置信度为：σ((P∧Q)/D)/σ(P/D)，即为D中所有图像，在某一概念层次证实断言P的对象中，在同一层次也证实断言Q的对象的百分比。这种定义的支持度为基于对象的支持度。定义3:足够频繁的模式P数据集D中对于某一概念层次，模式P为足够频繁的，当P的支持度不小于其相应的最小支持度阈值σ'，并且不大于其相应的最大支持度阈值

'。11.3.2多媒体关联规则及其新概念

定义4:足够强的关联规则图像集D的多媒体关联规则P→Q在D中是足够强的，当P和Q是足够频繁的，而且P→Q的置信度大于阈值

'。一个规则的强度和σ'、

'的值，与断言使用的概念层次有关。所有的特征性，如颜色、形状、纹理等，均根据概念继承来定义。11.3.2多媒体关联规则及其新概念

3.两种类型的多媒体关联规则把图像作为事务，对象(或子区域)作为项集，对象的特征作为组成项集的项，可以得到下面的规则:①基于原子视觉特征、带有重复视觉描述的基于内容的多媒体关联规则。原子特征指颜色、纹理形状等，它们是对象依据概念继承定义的特征属性。因此，基于原子视觉特征的关联规则类似于多维、多层次的关联规则。②与空间关系相关的带有重复空间关系的多媒体关联规则。该规则描述对象是对象间的空间关系。每一断言描述两个对象Oa和Ob的空间关系，如Overlap(Oa,Ob)。规则P→Q的P和Q，可包含多个关系的并，而且相同对象的空间断言可重复出现。11.3.3包含出现次数的关联规则发现方法

1.发现方法中频繁的空间断言对象是多维的，并且应考虑概念层次。我们把图像当作由一组一维对象组成的事务，对象可以重复出现，而且只考虑某一特定的概念层次。实际上，如果将下面讨论的算法可加扩充，就可以发现多层次的关联规则。将空间关系分为水平邻近H-next-to，垂直邻近V-next-to,overlap和include。每一个断言P说明了两个对象Oa和Ob间的关系，如Overlap(Oa,Ob)。断言可包含多个空间关系的并。对于空间谓词P(X，Y)，若它是足够频繁的，则X和Y均要足够频繁，且二元组{X,Y}也是足够频繁的。它可用于从最高层到最低层的任何概念层。。要找到频繁的空间断言，首先要找到频繁的1元和2元项集，然后用这些频繁的项集与空间断言组合，把得到的空间断言作为关联规则挖掘过程的1元候选集；接着用算法Max0ccur()发现k元的频繁空间断言。为简化操作，计算频繁的k元项集断言之前，要极小化候选集。11.3.3包含出现次数的关联规则发现方法

2.发现足够频繁的项集算法算法MaxOccur用于发现出现次数足够频繁的项集，以列举在图像集中基于内容的多媒体关联规则。⑴输入D1为一个图像说明集，其项为视觉或非视觉的图像描述；每一属性的概念继承；每一概念层的最小支持度阈值σ'和最大支持度阈值

'。⑵输出出现次数足够频繁的项集。11.3.3包含出现次数的关联规则发现方法

⑶方法生成足够频繁的项集。其伪代码如下：BeginCl←{候选的1元项集及其支持度}Fl←{出现足够频繁的1元项集及其支持度}M←{频繁的1元项集在某一图像中的最大出现次数}计算所有k元项集[1..K]for(i←2；Fi-1≠

；i←i+l)do{/*生成候选集*/Ci←(Fi-1Fi-1)∪{Y⊕X|X∈Fi-1∧Y∈F1∧Count(Y,X)<M[y]}/*利用Apriori属性来生成频繁项集*/Ci←Ci-{c|由c中的项组成的某一(i-1)元项集Fi-1}/*过滤D中的不必要的事务*/Di←FilterTable(Di-1,Fi-1)11.3.3包含出现次数的关联规则发现方法

/*计算支持度*/ForDi中的每一图像Ido{ForCi中的每一cdo{c.support←c.support+Count(c,I)}}}/*保留出现次数高于最小支持度的σ’的频繁项集*//*用最大支持度

'来删除那些出现过于频繁的项集*/结果←∪i{c∈Fi|i>1∧c.support<

'}End项集中的项按某种单调顺序存放。Fi-1Fi-1(i>2)表示前i-2个项相同的i-1元项集进行连接操作，结果仍按原顺序存放。算法中，为了论述简单，K元项目集的支持度用其出现次数的绝对值来表示。其严格定义应为式（11-1）所示。11.3.3包含出现次数的关联规则发现方法

其中表示从事务t的所有项中任取k个进行组合，得到的组合次数，在组合中不能重复出现唯一的对象。3.MaxOccur算法分析算法MaxOccur综合并改进了Apriori算法和其它相关的算法。算法中通过连接(i-1)元频繁项目集和一些频繁的i-1元项目与频繁1元项集，共同生成候选集。Count(y,X)<M[y]用来控制对象在yX中的重复出现次数，不能超过其最大出现次数。在Count(c,I)中，I的任一对象不能重复计算。11.3.3包含出现次数的关联规则发现方法

MaxOccur算法过程综合了Apriori算法和AIS算法中候选集的产生方法：前者只考虑了(i-1)元频繁项目集的连接，可能会丢失一些重复出现的对象信息，而后者则未考虑y∈F1，可能增加一些不必要的与非频繁的1元项目集的并操作。在过滤D中不必要的事务时，Apriori算法仅考虑删除不包含Fi-1中的大项集的事务，未考虑事务中不在Fi-1中出现的项。假设信任度阈值为1，且该算法得到的结果如下:{O2,03,04}，{02,02,04},{02,04,04},{02,02,04,04}则可发现关联规则，如:204→202[100%],02∧204→O2[100%]，03∧04→02[100%],03→02∧04[100%]，202→04[100%],204→02[100%],03→02[100%],03→04[100%]11.3.3媒体空间关系的关联规则挖掘算法

为叙述方便，我们考虑在特定概念层的形状维，该方法同样适用于具有相关概念继承的其它维，如颜色、纹理、行为等。发现足够强的空间关系的关联规则意味着要发现足够频繁的空间断言的组合。首先确定最小的支持度阈值σ'。这里使用出现次数的绝对值作为支持度。第一次对图像集的遍历发现了频繁的1元项，它们出现在每一幅图像中，且在某幅图像最多的出现次数为mi。对这些频繁项进行遍历发现频繁的项对，并计算其支持度。用这些项对构建空间断言，并把它们作为MaxOccur算法第一步的1元项的候选集Cl，接着用MaxOccur来发现频繁k元项集，

11.3.3媒体空间关系的关联规则挖掘算法

从而推导出关联规则，如:H-Next-to(○，□)∧H-Next-to(△，□)→Overlap(○，△)[100%]发现过程的操作使用MM-Spatial算法，发现足够频繁的空间关系集，以列举图像集中空间关系的关联规则。MM-Spatial算法如下：（1）输入D1为一个图像空间关系描述集，其项为视觉或非视觉的图像描述；每一属性的概念继承；每一概念层的最大和最小支持度阈值:σ'、

'。（2）输出出现次数足够频繁的空间关系集。11.3.3媒体空间关系的关联规则挖掘算法

（3）方法生成足够频繁的空间关系集，其伪代码如下：BeginP1←{频繁原子项}P2←{P1×P1中的频繁对}/*用频繁对象建立空间断言*/Cl←{P2×{空间断言集}和它们的支持度}/*得到频繁的具有一个空间关系谓词的断言集*/Fl←{Cl中的频繁项集}/*利用Fl从算法MaxOccur的第3步开始执行*/……End11.3.3媒体空间关系的关联规则挖掘算法

这种空间关系的关联规则挖掘算法，建立在已有的空间关系特征之上。其特征是通过比较对象的质心或矩形块Mbb得到的，并存储在特征库中。该算法能挖掘出支持度大于特定阈值的关于空间关系的关联规则。算法继承了AprioriHybrid算法中频繁项集和候选集的有效生成方法，并克服了原算法不考虑项数量的缺陷。11.3.4多维测度关联规则挖掘

由于多媒体数据的复杂性，非结构化/半结构化性等特殊性质，使传统意义的支持度和关联规则并不能充分适用。例如，单一的支持度不能体现一事务集中频繁和具有意义的程度，需要反复扫描数据库以及需要计算数据集D中所有项目集的支持数等，效率较低。对经常是海量和复杂数据的多媒体数据库，实现这种规则挖掘非常困难。我们使用一个多维测度关联规则算法，能够比较概要地挖掘相关的关联规则，用户可以对其感兴趣的数据项再进行聚焦，使用适合的算法进一步挖掘。这里简要介绍有关的思想与方法。11.3.4多维测度关联规则挖掘

挖掘图像的关联规则，当数据项的数量大或内容复杂时，采用多维空间的测度法。构造n×p阶矩阵Xn×p，其中的行向量表示第i个测度点的坐标（i=1,2,...,n），列向量表示n个测度点的第k个坐标（k=1,2,…,p）。X中的元素应满足的条件为n个数据项的测度是中心化的，X中各列是正交的，则各个测度点间的距离平方为d2ij。取给定表达式中最大值S的前p个最大特征值所对应的正交特征向量，是我们需要的解（k=1,2,…,p），由它们所构成的n×p阶矩阵的各行，给出了n个点的P维空间中的坐标。11.3.4多维测度关联规则挖掘

一种多媒体关联规则挖掘的示意性算法描述如下：（1）c=const()（2）L1←{扫描数据库，生成1元频繁项集及其支持度}（3）C2=apriori-gen(L1)/*利用Apriori算法的函数apriori-gen(L1),由L1产生候选集C2*/（4）L2←{c∈C2|c.support>minsupp}（5）S=build-change(L2)(6)Get-eig(S,x,d)/*求矩阵S的特征向量x和特征值d*/（7）X=subselect(x,d,p);（8）Plot(X).根据特征方程的性质，支持度sij为正值，示意性算法中（1）选取常量c<0(如-1)时，保证所有的特征值都为非负，所得到的解也满足中心化条件。11.3.4多维测度关联规则挖掘

Lk是k频繁项集，其数据结构组成是频繁项集中每个成员有两个域，即数据项集itemset和支持数count。例如，若L2.itemset={{26},{47},{59}},L2.count={8,4,7},表示数据项2与6、数据项4与7、数据项5与9之间的支持数分别为8,4,7。Ck为k频繁项集的候选集，其数据结构与Lk相同。其中minsupp表示最小支持度。函数build-change(L2)的功能是利用L2构造关联矩阵S，然后将其变换为非负定矩阵。例如，若L2.itemset={{26},{47},{59}}，L2.count={8,4,7}，则s26=8，s47=4，s59=7。函数subselect(x,d,p)是从特征值d中选出前p个最大特征值所对应的特征向量。为了将高维空间中的示例间的相对位置，在二维平面中直观地表示，p取值为2，即取前两个最大特征值所对应的特征向量，则矩阵的n行，即为所求的各数据项点在2维空间的测度。11.3.4多维测度关联规则挖掘

Plot（X）函数实现2维空间测度的可视化。它有两个步骤：①保证可视化的实时显屏刷新，即要求对用户的直接操纵有实时反应。这里采用系统和用户同时可以逐渐增加相似个数的功能，开始时缺省的相似个数为1，最大个数为所有例子数，使系统能在0.1秒内作出反应，更新显示。②对于相似度不同的例子，使用不同的颜色表示以示区别。距离到颜色的映射在可视化中有专门的研究。11.4多媒体数据挖掘的特征匹配技术

11.4.1相似性匹配的相关技术1.相似性匹配模式相似性匹配的模式是指媒体中一个对象或其它感兴趣实体的量化或结构化的描述。通常，一个模式由一或多个特征组成。如纹理、颜色和形状。实际应用中，模式可用向量、串和树来表示。模式向量的形式为=(X0,…，Xi-1)，每个元素Xi代表第i+1个特征，n是特征数。模式向量元素的意义决定于描述物理模式本身的测定技术。例如，RGB颜色模式中R、G、B的范围为0-256(或[0,1])。因此向量=(Ravg，Gavg，Bavg)用来表示图像的颜色，其中的三个元素分别表示像素R、G、B平均值。对于基于初始量且连接相对简单的实体和对象，其有效表示模式是串。许多系统采用更有效的树型结构，如k-d树和四叉树。四叉树的节点代表两种信息：标识原子值，定义该原子与其它子结构的物理关系。11.4多媒体数据挖掘的特征匹配技术

2．相似度特征之间的相似度可用于数据检索。相似度通常由一对图像特征描述它们之间的距离来确定，当图像用特征向量描述时，更是如此。从建立索引的角度看，相似度用于两个阶段：第一阶段，删除图像(或对象)与目标图像(或对象)间不必要的匹配。第二阶段，当剩余一小组图像(或对象)时，相似度用来进行充分的辨别，选取结果图像(或对象)。许多种相似度由于其时间复杂性，不能方便生成有效的索引机制。通常采用的方法是欧几里得与加权欧几里得距离函数，以及1维和2维串匹配过程。11.4多媒体数据挖掘的特征匹配技术

3．相似匹配相似匹配算法复杂多样，没有一个能满足所有应用的通用算法，通常根据具体应用进行设计。相似匹配无须用户记住图像或对象的细节，实际上某些特征，如形状，是很难精确描述的。这是与精确匹配的根本区别。相似匹配算法根据相似程度定义距离函数，对数据库对象划分等级。“0”～不匹配，“1”～完全匹配。用户可在请求中指定一个阈值，以限制查询结果，使相似度低于阈值的数据不能被抽取。为了获得精确的结果，距离函数可能很复杂而且费时。此处，距离函数定义在条件级和图像级，即图像相似程度在条件级和图像级高于阈值时，才成为查询的结果