点击显示 收起
【摘要】 本文分析了多媒体数据挖掘的需求，介绍了常见的多媒体数据挖掘形式及存在问题，并针对此类问题探讨了基于网格环境下多媒体关联规则数据挖掘方法，该方法是Apriori算法在网格环境下的具体应用。本文通过对实例的分析证明了该方法不仅具有经典Apriori算法的准确性，同时也具备了网格的并行挖掘特性，从而大大的提高了数据挖掘的速度，提高了运算效率。
【关键词】 多媒体 网格技术 数据挖掘 Apriori算法
Associate Data Mining Method Research Based on Grid System
YANG Mu１,HU Yan-mei２
(1.Educational Technology Center;2.Department of Basics of Computer Science,Chengdu Medical College, Chengdu 610083,China)
Abstract：In this paper the requirements of data mining were analyzed and the common forms and existed problems in data mining were introduced.In the light of the problems,the associate data mining method of multimedia based on grid system,which is the application of Apriori algorithm under the grid system was discussed.Through analyzing the instance,the method had proved that it had not only the accuracy of classics Apriori algorithm,but also the characteristics of grid parallel excavation and therefore,it had improved the data mining speed greatly and enhanced the operation efficiency.
Key words:multimedia；grid technology；data mining；apriori algorithm
1 序言
随着信息技术的发展，人们在生活中所接触的数据形式不断地丰富，以存储音频数据、图象数据、视频数据、序列数据以及超文本数据等多媒体对象数据库的数量日益增多［1］。仅仅对这些多媒体数据进行收集与保存已满足不了科研教学及实际应用的需求，人们希望从这些数据中得到更高层的概念和模式，找出蕴涵于其中的有价值的知识和信息。
多媒体挖掘就是从大量的多媒体数据集中，通过综合分析视听特性和语义，发现隐含的、有效的、有价值的、可理解的模式，得出事件的趋向和关联，为求解问题提供高层次的决策支持能力。多媒体挖掘使多媒体的处理和管理从信息存取上升到知识获取的层次。
我们可以这样来描述多媒体数据挖掘［2］：基于多媒体数据的内容特性C，以及这些特性的相关语义，从大型多媒体集M中，发现和分析出隐含的、有效、有价值的、可理解的模式P。
P＜－ζ(M｜C)(1-1)
多媒体数据包含着十分丰富的内容特性，对于这些特性的分析、提取以及获得它们之间的关系和模式都属于多媒体数据挖掘的范畴。常见的多媒体数据挖掘形式有［3］：图像挖掘、视频挖掘、音频挖掘、Web挖掘、多媒体综合挖掘等。
2 多媒体数据挖掘的体系结构及应用
2.1 常见多媒体数据挖掘的系统结构如图1所示图1 多媒体数据挖掘系统结构
Fig.1 Multimedia data mining system frame
2.2 常见的多媒体数据挖掘应用介绍
常见的多媒体数据挖掘方法有［4］：多媒体相似搜索、多维分析、分类和预测分析、多媒体数据的关联挖掘。
多媒体中搜索相似数据包括［5］：基于数据描述与基于数据内容。通过对相似数据的搜索可以在医疗诊断，气象预报，TV制作及电子商务等领域得到广泛的应用［4］。
多媒体数据的分类和预测分析常被应用于天文学、地震学、地理科学领域。
多媒体关联规则挖掘能从大量数据项集中发现有趣的关联或相关联系，从而在商务决策，行为分析、模式匹配等领域被广泛应用［6］。
基于超文本数据的万维网被全球广泛的应用，它涉及新闻、广告、金融、教育、电子政务等领域，对超文本多媒体数据开展数据挖掘将对上述领域信息的检索、数据的分类、决策的评估等方面提供有力的支持。
3 传统的多媒体数据挖掘方法存在的问题及解决方法
3.1 传统的多媒体数据挖掘方法存在的问题
传统的多媒体数据挖掘需要建立数据中心，这往往意味着高投入、高维护成本和低利用率。在其庞大的数据库中进行数据挖掘工作需要消耗大量的计算资源和时间。即使采用了C／S或分布式模式，数据挖掘项目的开展也必将受网络连通性、带宽等方面的要求，还必须预先为数据挖掘运算预留足够多的资源，这样必然影响到系统的灵活性。当系统中的某个网络节点出现故障时就有可能造成任务的失败。
3.2 基于网格的多媒体数据挖掘方法
为了解决存在的上述问题，本文构建了基于网格技术的多媒体关联规则数据挖掘应用平台如图2所示，利用网格技术能将地理上异构分布的各种高性能计算机、数据服务器、大型检索存储系统等通过网络连接集成，对所有资源统一调配和使用，实现计算资源、数据资源和服务资源的有效聚合及共享，是解决制约多媒体数据挖掘应用的有效方法。目前主要的网格体系结构分为两种：一种是五层沙漏结构，它的主要思想是以协议为中心，强调物理资源的共享［7］。另一种是开放网格服务体系结构(Open Grid Services Architecture)［8］，在OGSA中，定义了“网格服务”(Grid Service)概念，并将计算机资源、存储资源、程序、数据库等看作网格服务，服务提供了一组接口，这些接口将解决服务发现、动态服务创建、生命周期管理、通知等问题。用不同方式聚合起来的网格服务可以满足不同部门的数据挖掘需求，完成不同的任务。
网格环境下的多媒体关联分析数据挖掘平台基于OGSA架构的网格应用平台，主要由分散在网格节点中的多媒体集群服务器组成。应用平台为用户图2 基于网格环境下的多媒体关联规则数据挖掘系统的架构
Fig.2 Multimedia association rule data mining system frame in grid
提供统一的WEB访问接口。网格系统中的资源调度服务器将负责，完成多媒体资源的查找、动态服务的创建、资源的调度、访问资源的定位、生命周期管理等工作。最后用户将根据此动态访问实例对多媒体资源进行数据挖掘。网格平台可以充分利用网格中的各种现存网络资源，分散访问请求，避免网络拥塞，提高服务质量，提高数据挖掘系统的利用率及灵活性。
3.2 网格环境下的多媒体关联数据挖掘系统的调度过程
3.2.1 用户经过身份论证，通过网格数据挖掘访问接口向资源调度模块发出一个挖掘请求。
3.2.2 资源调度模块在完成一个挖掘任务调度后，将从队列中接收新的访问请求，并进行资源查找、算法选择、网格资源的分配等工作。其过程主要包含如下几个环节。
●首先在多媒体网格资源目录服务模块中检索出分布在节点中的可挖掘数据仓库（可能存在不只一个数据仓库），数据仓库中的数据是经过初始化处理，并根据多媒体数据的分类进行了特征提取所获得的可挖掘数据。
●根据用户的数据挖掘要求选择可利用的数据挖掘算法。数据挖掘算法为网格环境中已注册并能被网格子节点调用的挖掘方法。为了提高服务质量（QOS），资源调度模块将根据网格节点的服务连接数、网格节点的权值进行负载均衡［7］。
●确定了可挖掘资源及算法后数据挖掘服
务模块将进一步完成数据挖掘子任务的分配、资
源的调度、网格节占的定位、挖掘任务生命周期的设定、各节点挖掘过程的协调、挖掘结果的汇总等工作。
●经过资源的分配生成一个数据挖掘请求实例，实例调用网格节点完成数据挖掘工作。在数据挖掘实施过程中数据挖掘调度模块将进一步协调各子节点的挖掘任务，最后将各结点的挖掘结果汇总并返回给用户。
3.2.3 释放资源。用户完成挖掘任务后必须释放占用的网格资源，等待下一次调用。
图网格节点频繁K-项集与全局K-项集LK的通信模式图
Fig.3 Frequent K-Itemsets communication with global K-Itemsets in grid
4 基于网格环境下Apriori的多媒体关联数据挖掘方法设计
关联分析方法是我们常用的一种多媒体数据挖掘方法。通过对多媒体数据的关联规则分析从相关的多媒体对象集中挖掘出一组关联规则，从而显示一组对象或特征的模式或相互关系的发生频率。一个典型的关联规则为［9］:
X-＞Y［S%,C%］(4-1)
其中，x和y是一组特征描述的谓词，s％是规则的支持度(x，y共同出现的概率)，c％是规则的可信度(x出现时y出现的概率)。
Apriori算法是一种最有影响的挖掘布尔关联规则繁项集的算法［10］。Apriori算法基于频繁项集性质的先验知识，频繁项集的所有非空子集都必须也是频繁的。Apriori算法使用一种称为逐层搜索的迭代方法，用K-项集探索（K+1）-项集。首先，找出频繁1-项集的集合，该集合记为L1，L1用于查找频繁2项集的集合L2，而L2用于找L3如此下去，直到不能找到频繁K-项集。
网格环境下Apriori的多媒体关联数据挖掘算法是利用网格平台对多媒体数据进行关联数据挖掘的一种应用。它首先利用Apriori的频繁项集迭代法在网格节点中找出频繁项集，随后计算频繁项集的支持度与置信度,，并根据阀值对其进行筛选，由此得出我们想要挖掘的强关联规则［11］。
Confidence(A=＞B)=P(A｜B)
=support_count(A U B)(4-2)
我们可以通过这种高效的关联规则分析方法，从网格节点中存贮的多媒体数据记录集中，找出我们想要的强关联规则，发现隐含的、有效的、有价值的、可理解的模式［12］，从而得出事件的趋向和关联，并为进一步高层决策提供有力的支持。
网格节点频繁K-项集与全局K-项集LK的通信模式图
算法描述：
从图3中可以看出整个数据挖掘程序分为全局K-项集LK的计算和网格节点中频繁K-项集的迭代查找。
输入：数据挖掘任务
输出：关联规则
Step1：网格挖掘全局数据调度模块负责对资源的查找、任务的分解和资源分配工作；
step2：启动所有网格节点的数据挖掘子任务；
step3：全局数据调度模块将每个子任务传回的局部K-项集进行汇总、计数，并由此获得全局K-项集LK，并根据最小支持度（min_sup）阀值对全局K-项集LK进行筛选。
Step4：将经过阈值筛选的候选集经过网络发送至网格节点数据挖掘子任务端；
step6：重复step3至step5；
step7：累加每个子任务得出的局部关联规则的suport_count(A)值
stepS：计算关联规则的全局置信度，删除低于置信度阈值min_count的关联规则，得到最终的(全局)关联规则
5 实例分析
我们以网格环境下的两个节点(见表1所示)来说明一个多媒体关联数据挖掘的实例过程：
挖掘要求最小支持度为2（min_sup=2）、置信度为65(confidence=65%) 。
事务数据在节点中经过第一次迭代后产生网格节点候选1一项集见表2所示。表1 网格节点事务数据在完成一次频繁项集的计算后资源调度模块将获取从网格节点传回的计算中间值，并以此计算该次全局频繁项集。由此我们可以从表2中看出虽然网格节点中的候选集支持度计数都低于最小支持度2，但其合等于2，故仍保留Ⅰ5。
资源调度模块中的全局频繁项集值见表3。
网格节点将以表3中的值作为下一轮频繁项集的候选集，其值将如表4所示:
表3 资源调度模块中的全局频繁项集值表4 网格节点频繁1一项集L1重复上述步骤最后得到频繁3一项集L3，如表5所示。表5 网格节点频繁1一项集L1由于｛Ⅰ1，Ⅰ2，Ⅰ4｝支持度计数低于最小支持度2故将此项舍去，我们以频繁项｛Ⅰl，Ⅰ2，Ⅰ3｝例，计算其支持度计数如表6所示。表6 频繁项｛Ⅰl，l2，l5｝的支持度计数
Tab 6 Count of support threshold for frequent itemsets ｛Ⅰl，l2，l5｝Association ruleNode_A_support_count(A)Node_B_support_count(B)Ⅰ1∧Ⅰ2 =＞Ⅰ322Ⅰ1∧Ⅰ3 =＞Ⅰ203Ⅰ2∧Ⅰ3 =＞Ⅰ113Ⅰ1=＞Ⅰ2∧Ⅰ323Ⅰ2=＞Ⅰ1∧Ⅰ343Ⅰ3=>Ⅰ1∧Ⅰ214
计算关联规则的置信度:
Ⅰ1∧Ⅰ2 =＞Ⅰ3，confidence=2/(2+2)=50%
Ⅰ1∧Ⅰ3 =＞Ⅰ2，confidence=2/(0+3)=67%
Ⅰ2∧Ⅰ3 =＞Ⅰ1，confidence=2/(1+4)=40%
Ⅰ1=＞Ⅰ2∧Ⅰ3，confidence=2/(2+3)=40%
Ⅰ2=＞Ⅰ1∧Ⅰ3，confidence=2/(4+3)=29%
Ⅰ3=＞Ⅰ1∧Ⅰ2，confidence=2/(1+4)=40%
第2条规则是满足置信度要求。此时网格挖掘系统将向用户反馈最小支持度为2、置信度为65的强关联规则Ⅰ1∧Ⅰ3 =＞Ⅰ2。
算法结果分析：
算法结果与经典Apriori计算结果相同。算法中对数据库的水平分片挖掘不会产生不可靠的关联规则，由于算法对各节点数据进行了汇总因此也不会丢失可靠的关联规则。在数据挖掘过程中网格全局资源调度模块将负责将各网格节点中计算出的频繁K-项集进行汇总产生该次查询的全局K-项集LK，在对LK进行支持度计数，删除低于最小支持度的候选集。此时，各网格节点暂停下一轮频繁项集的查找。计算花费的时间将与频繁K-项集的K值和网格节点数成正比。由于网格节点是并行工作，因此全局统计的时间消耗将远远小于频繁项集的查找时间，因此该调度方法将适合可分解成多个网格节点的分片多媒体事务数据库。
6 结论
基于网格环境下的分布式数据挖掘是未来高性能计算的重要发展方向。本文构建了基于网格环境下的多媒体关联数据挖掘系统，并通过实例分析了一个数据挖掘的过程，从实例结果中我们可以看出系统中数据挖掘的消耗时间主要集中在网格节点的频繁项集查找中，由于网格节点是并行工作，因此全局统计的时间消耗将远远小于频繁项集的查找时间，这将确保该系统的能高效准确的进行多媒体数据的挖掘。
【参考文献】
［1］HexM，ChuQX，ZhuMY． Milionis Preemption Cost for Path Selection in Diffuser-ware MPLS Networks［J］．Computer Communications，2006，29(18)：3 825-3 832．
［2］Cho E H，Shin K S，Yoo S J．SIP-based QoS Support Architecture and Session Management in a Combined Instars,and Diffuser Networks［J］．Computer Communications，2００6，29(15)：2 996-3 009．
［3］Ahmed N U,LU X,Barbosa L O.An Efficient Parallel Optimization Algorithm for the Token Bucket Control Mechanism ［J］.Computer Communications,2006,29(12):2 281-2 293.
［4］K Krauter，R Buyya，M Maheswaran．A Taxonomy and Survey of Grid Resource Management Systems for Distributed Computing［Ｊ］．Software Practice and Experience．2002．
［5］Myllymaki J.Efective Web Data Extraction with Standard XML Technologies［C］．In：Proceedings of the l0 International Conference on World Wide Web．New York：ACM Press．2001．
［6］Jiawei Han，Micheline Kamhr．Data Mining Concepts and Techniques［M］．北京；机械工业出版社，2006．
［7］ZHA L,LI W,DAFU D,et al.System Software for China National Ｇrid［A］.IFIP International Conference on Network and Parallel Computing 2005［C］.Beijing,China,2005.14-21．
［8］Ian Foster,Carl Kesselman．网格计算［M］．北京：电子工业出版社．2004．17-18．
［9］王创新．关联规则提取中对Apriori算法的一种改进［J］．计算机工程与应用，2004，34：183．185．
［10］马盈仓．挖掘关联规则中Apriori算法的改进［J］．计算机应用与软件．2004，21(11)：82-84．
［11］冯兴杰，周谆．Apriori算法的改进［J］．计算机工程，2005，31：1 172-1 173．
［12］刘君强，孙晓莹，潘云鹤．关联规则挖掘技术研究的新进展［J］．计算机科学，2004，31(1)：110-l13．