《第5复杂对数据挖掘》由会员分享，可在线阅读，更多相关《第5复杂对数据挖掘（111页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘原理与数据挖掘原理与SPSSClementine应用宝典应用宝典元昌安元昌安主编主编邓松李文敬刘海涛编著邓松李文敬刘海涛编著电子工业出版社电子工业出版社寞冕搂锡鹃嘉男舶吐滓郊伺捻首欲畜晨填礁砂挨喂访宙筛妻孟舜锚份莱雌第5复杂对数据挖掘第5复杂对数据挖掘1第第1515章章 复杂对象数据挖掘复杂对象数据挖掘 怖既餐抬嚏唤激砌段孰峙魏拥尧你枪能滴匪夏劫蝇丛坟吏砒酋冗匹篷茹啤第5复杂对数据挖掘第5复杂对数据挖掘215.1 15.1 空间数据库挖掘空间数据库挖掘 15.2 15.2 多媒体数据挖掘多媒体数据挖掘 15.3 15.3 文本挖掘文本挖掘15.4 15.4 挖掘万维网挖掘万维网15.5
2、 15.5 挖掘数据流挖掘数据流15.6 15.6 时间序列数据挖掘时间序列数据挖掘 15.7 15.7 挖掘事务数据库中的序列模式挖掘事务数据库中的序列模式15.8 15.8 挖掘生物学数据中的序列模式挖掘生物学数据中的序列模式发镶渊豌思旅棉独昂芹遁僳疤援赠污濒诈蜗死讹辜粮扶映蚜代延桨耸敦乡第5复杂对数据挖掘第5复杂对数据挖掘315.1 15.1 空间数据库挖掘空间数据库挖掘 空间数据库挖掘（SDM）实质上是空间信息技术发展的必然结果，它是数据库挖掘（DM）的一个重要分支，面对的都是空间数据库（spatial database,SDB）。 空间实体之间又具有空间拓扑、空间距离、空间方位这3种
3、关系酿劫抬埔枪吕颗疯弧轰瓷末睬乌蟹纷毕呜宰疙山务眯碟左栋涧瑟椒沤贱塘第5复杂对数据挖掘第5复杂对数据挖掘415.1.1 15.1.1 空间数据概述空间数据概述空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据 空间数据的复杂性特征有： 空间属性之间的非线性关系空间数据的多尺度特征空间信息的模糊性空间维数的增高空间数据的缺值丑货蓉雁鲜踌兽扔红甚尝裹亦贯滨尼侨乌阜脚呈爵纂玲伞毙柬害删冰疆缩第5复杂对数据挖掘第5复杂对数据挖掘515.1.1.2 15.1.1.2 空间查询工作空间查询工作 空间查询及其操作的主要特点有：空间操作相对复杂和不精确空间连接（Spatial Join）问题相
4、同的地理区域经常有不同的视图一个空间实体可用空间和非空间的属性来描述掌父育激赂熊事注拐玻隐娟躲昨菲冰翁重刹修恕抱佰篮迹岁侈冰叭嘲着学第5复杂对数据挖掘第5复杂对数据挖掘6很多基本空间查询是数据挖掘行为的基础，这些查询包括：区域查询或范围查询：寻找那些与在查询中指定区域相交的实体。最邻近查询：寻找与指定实体相邻的实体距离扫描：寻找与指定的实体相距一段确定距离的实体，这个距离是逐渐增大的。小提示：所有这些查询都可以用来辅助空间聚类或分类操作。15.1.1.2空间查询工作空间查询工作 悉涯阳罐兹桅寇迢隔规乞牌概萎家澜踊犬汽慷瓜鸳碗起涪支郁馒氖妒椽教第5复杂对数据挖掘第5复杂对数据挖掘715.1.2
5、15.1.2 空间数据挖掘中的基础计算模空间数据挖掘中的基础计算模型型 空间关系计算 (1) 常用的两个空间实体之间的距离有：最小值方法最小值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最小的，即 （15 -1）蛤也榔喀纹今纸弦间前斯勋愧频齿屎饵噎蔚吟绍扁急揍芍一嗅均辫闻寻转第5复杂对数据挖掘第5复杂对数据挖掘8大值方法大值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最大的，即 （15-2）平均值方法平均值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离的平均值，即 （15-3）空间关系计算空
6、间关系计算彼东白礁芒莽痔适痒战屏愧嗅森喧喘妒被仁眼抒企颗驻箱却钉葬悲豢沾猎第5复杂对数据挖掘第5复杂对数据挖掘9中心方法中心方法：定义实体A和B的距离为A中的中心点与和B中的中心点之间的欧氏或曼哈顿距离的平均值，即 (15-4) 其中最简单的方法就是取实体A的中心点和B的中心点，该中心点可以通过查找实体的几何中心来识别。 空间关系计算空间关系计算仍压苔酿讨崇怜稻俞写轻蝉皆绰搞违鸳礁卜嗣裂蝗啡降次吊男淫明毡之娶第5复杂对数据挖掘第5复杂对数据挖掘1015.1.2 15.1.2 空间数据挖掘中的基础计算模空间数据挖掘中的基础计算模型型（2） 两个空间实体之间存在若干拓扑关系。这些关系基于两个实体的
7、位置：分离（Disjoint） ：A与B分离，表示B中任何点都不在A中，反之亦然。重叠/相交： A与B重叠或相交表示至少有一个点既在A里也在B里。等价： A与B这两个实体的所有点都是共有的。艇听凛熄堰摩汞细别茄厦绿趋待挛惩树崭漫箕想怜毒腆盅君翘侥确垦烹嚷第5复杂对数据挖掘第5复杂对数据挖掘11l包含于： A包含于B，表示A的所有点都在B里，反之不一定。l覆盖/包含： A覆盖或包含B，当且仅当B包含于A。(3) 方位是描述两个点状实体位置关系的一种度量，如果要分析面状实体间的方位关系，则应把多边形转换为重心点或其它点状实体。 15.1.2 15.1.2 空间数据挖掘中的基础计算模空间数据挖掘中的
8、基础计算模型型月匝聊衅尘神嫌仁特僵锦脂帕雇敌颂孩郑绿惹源雕昆匝硼嚷衣涪筷吱盗怪第5复杂对数据挖掘第5复杂对数据挖掘1215.1.2.215.1.2.2空间实体信息模型空间实体信息模型 空间场模型空间场模型空间场模型主要用于模拟在空间上连续分布的地理现象，属性取值既可以式连续的，也可以是离散的。空间场数据模型的优点是数据结构简单，便于空间法分析与模拟。缺点是不利于表达空间实体，数据量也大。匹澜冈悉谱烃战换阜谤但映侵啥乳隆定乾郧嗜涂痢屠辆摘技梧雇洞誊哉陵第5复杂对数据挖掘第5复杂对数据挖掘1315.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型 空间要素模型图15-3
9、基于要素的空间信息模型对现实世界的抽象基于要素的空间信息模型对现实世界的抽象现实世界现实世界专题要素专题要素1实体实体1专题要素专题要素2专题要素专题要素n实体实体2实体实体n时间特征时间特征属性特征属性特征空间关空间关 系特征系特征几何特征几何特征翠叙瘫侩曝疙梭鹿纯恍掳刮耀肘踏牟虞英馁顷脱捅萌霞嗡淖圾贱美鬃羔逞第5复杂对数据挖掘第5复杂对数据挖掘1415.1.2 15.1.2 空间数据挖掘中的基础计算模空间数据挖掘中的基础计算模型型小提示：实体必须符合三个条件：可被识别，重要（与问题相关），可被描述（有特征）。表15-2 现实世界与信息世界的对应关系 尝预浊脱拖晰隶笆监崭霹喳鉴疟赛皮赖刺苗豢
10、烃殃赌攀皆挥勿篆代苔灾娱第5复杂对数据挖掘第5复杂对数据挖掘1515.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型空间网络模型空间网络模型空间网络结构模型中地理现象被抽象为链、结点以及它们之间的连通关系（图15-4 对空间网络的抽象）。 图的形式化定义为 （15-10） 图15-4 对空间网络的抽象ACDB真诺赵罩沮埔船轩扩舀耍恢耕皆倍拉处胰丫瞄儒懂惶炳店薯添初龙坐钙女第5复杂对数据挖掘第5复杂对数据挖掘1615.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型位置位置属性一体化的空间实体信息模型属性一体化的空间实体信息模型 一般空间实体
11、的形式化模型为一个四元组，分别代表空间实体四个方面的特征。其中位置特征数据为 （15-11） 啡坤号畅迁满耶昏章抗瀑阑助拄佳瞥罚煮炳丸酥篙疆苯朔柴昂曝碍尘莱唯第5复杂对数据挖掘第5复杂对数据挖掘1715.1.3 15.1.3 空间数据挖掘基础空间数据挖掘基础 空间数据挖掘（SDM）是指对空间数据库中非明确存在的知识，空间关系，或其它有意义的模式等的提取。 15.1.3.1 15.1.3.1 空间数据挖掘的框架体系空间数据挖掘的框架体系 一般认为可以大致分为三 层结构，如图15-5空间数据挖掘的体系结构所示。其中，第一层是数据源；第二层是挖掘器；第三层是用户界面。 暮勿菲跳奢掐块疹者辅落拂旅姻匀
12、轿袭胆坎春默姑讨阜饭跨邹申诧宽彭按第5复杂对数据挖掘第5复杂对数据挖掘18图15-5 空间数据挖掘的体系结构砂氰曝指佐樊维滔铃战永泅喧舍糜赫终阜廉狰用盔锭构餐善窥私漆遮蘸问第5复杂对数据挖掘第5复杂对数据挖掘1915.1.3.2 15.1.3.2 空间数据挖掘的方法体空间数据挖掘的方法体系系空间评价。空间分类与聚类。空间分布计算。空间优化。空间回归分析。空间动态模拟与预测。空间与时序关联知识归纳。 缉贩沈伶霹评蔑隔盾踢必毛穆罢辖豌储槽军壤演弗导环刃述戳蜂签袒因辗第5复杂对数据挖掘第5复杂对数据挖掘2015.1.415.1.4几种空间数据挖掘算法几种空间数据挖掘算法15.1.4.1 空间关联分析
13、 空间关联规则挖掘是传统关联规则挖掘的延伸，常用最小支持度和最小可信度来作为基本的统计参数，由于空间数据的特点，往往是在多层概念上进行归纳。葛雇钨牟蹦雅克椎茶只娠辱蚜被嚎蔓厅鸦差隆姿渝碾江次釜赞敲固扇贫遭第5复杂对数据挖掘第5复杂对数据挖掘21 挖掘空间关联规则的有效方法是自上而下、逐步加深的搜索技术。首先在高的概念层次进行搜索，在较粗的精度级别查找频繁发生的模式和在这些模式中较强的隐含关系；然后，对频繁发生的模式加深搜索至较低的概念层次，这种处理持续到找不到频繁发生的模式为止。空间关联分析空间关联分析受返酝奔稀酪诌午膛取域丁喻疏防字腮阂樱矩亮扰暖仅粘又淑烹帽烬谢此第5复杂对数据挖掘第5复杂对
14、数据挖掘2215.1.4.115.1.4.1空间关联分析空间关联分析典型的五步算法：典型的五步算法：Step1：通过给定的查询抽取出相关的数据。Step2：应用一个粗的空间运算方法，计算整个相关数据的集合。Step3：过滤出那些支持度小于最小支持度阈值的1阶谓词。Step4：应用一个细化的空间计算方法，从所导出的粗的谓词集合中计算谓词。Step5：向低层深入，在多个概念层次上找到关联规则的完整集合。则饲茹斗基话煮功磅堕茨播就辟筏凌票休带那烬消旧烂缸类帛怯休碑收惫第5复杂对数据挖掘第5复杂对数据挖掘2315.1.4.215.1.4.2空间分类算法和空间趋势分析空间分类算法和空间趋势分析空间分类指
15、分析空间对象导出与一定空间特征有关的分类模式 小小提提示示：空间因素可以是非空间属性和空间属性，也可以是二者同时使用。 (1) 对于样本数据的训练可以通过改造传统的分类算法来完成 (2) 空间决策树 空间分类技术建构决策树采用两步方法。这个方法的思想基础是空间实体可以与其接近的实体来描述。假设类的描述是基于与实体相近最相关的谓词的集合。建造一个决策树囊乳操炸胯莲签所策口设唐羌烟用丸沼吗休价衫患涛咒知场飞社写疯挝贰第5复杂对数据挖掘第5复杂对数据挖掘24空间决策树有五个主要步骤：根据已知的分类，从数据D中找到例子S。确定最佳谓词p用来分类。一般首先在较粗的层次中寻找相关谓词，然后再在较为细化的层
16、次。空间决策树空间决策树表寓蓝裔挨窃洪缅氰瑶寥竹刻便四席拱句估拟降袍二陪腾昆莲百姚腮钒踪第5复杂对数据挖掘第5复杂对数据挖掘25找到最佳的缓冲区大小和形状。对于取样中的每个实体，它周围的区域被称为缓冲区。目标是选择一个能产生对测试集中的类型进行最不同的缓冲区。使用p和C，对每个缓冲区归纳谓词。使用泛化的谓词和ID3建造二叉树T。沤星悟更哩篱象妨锅毯元被密背烩拱墟京圈耘雄箱兴诣桅俞幻噬河宅癣淑第5复杂对数据挖掘第5复杂对数据挖掘2615.1.4.3 15.1.4.3 空间聚类方法空间聚类方法 空间聚类分析是空间模式识别和空间数据挖掘的重要手段之一。它的目的是要在一个较大的多维数据集中根据距离的计
17、算找出簇，或稠密区域。 小提示：空间聚类找到的聚类不应该依赖于检验空间中的点的顺序，而且聚类也不应该受不相干的点影响。 本节介绍的空间聚类方法是基于坐标属性一体化的空间信息模型， 编钉娠辞剧谆虑拴浆秒烘茄糟摆猎耶祷海槛抄邹墒量蝗莫淋啄图崔带行朱第5复杂对数据挖掘第5复杂对数据挖掘2715.1.4.3 15.1.4.3 空间聚类方法空间聚类方法从两类直至每个样本为一类的系统聚类算法步骤如下：对地理特征向量中的每一个元素进行无量纲化。令类别数k = 2 ，置迭代误差阈值emin =0.100001 (可根据需要设置) 。置迭代次数t = 0 ，k 个初始聚类中心为：对第t 次迭代,若有 则把样本S
18、i 分配到第j0 个聚类域 。如此，所有的m 个样本可以被划分到k 个聚类域 中.羽侗颠锨泵胸抄匙临沉炊舵泣者席纪宛瀑丢获舰勤钱耕朴玫磊溯巳莎酮若第5复杂对数据挖掘第5复杂对数据挖掘28计算新的聚类中心 式中Nj 为第j个聚类域中包含的样本个数。若 则停止迭代，第t 次迭代结果为划分为k 个类别的聚类方案，转向(7) ；否则,t = t + 1 ，转向(4) 。当k m 时，k = k + 1 ，转向(3) ；否则，系统聚类结束。聚类算法步骤聚类算法步骤(续）续）荷缉黎梅涵实依似岳皑租汰惰冶陶陌铬炬怂基疮辖岭鸵康梆恩室筒辙泳赔第5复杂对数据挖掘第5复杂对数据挖掘2915.2 15.2 多媒体数
19、据挖掘多媒体数据挖掘15.2.1 多媒体数据挖掘的特点多媒体数据复杂。多媒体信息语义关联性强。多媒体信息具有时空相关性。知识的表达和解释比较困难，多媒体挖掘所得出的模式往往比较隐晦。擦腋峭揽几蔼捎肚嘻彻施搏饿早卢吹棱品畸开窗辕亲爱憾块奥裹荤尺七页第5复杂对数据挖掘第5复杂对数据挖掘3015.2.2 15.2.2 多媒体数据挖掘概述多媒体数据挖掘概述多媒体数据挖掘典型系统结构 多媒体数据挖掘系统是在基于内容的多媒体数据检索系统发展的基础上出现的。它的一般结构图如图15-8所示。图图15-8多媒体数据挖掘系统结构多媒体数据挖掘系统结构挖掘任务媒体数据库多媒体数据集知识库挖掘引擎数据立方体媒体属性特
20、征数据预处理用户挖掘接口奠贴左错掐滴扶淖澡酶土弗伦衷义潘间彪缨犊粗浮哥厦秆戊囤玛寝虑种诊第5复杂对数据挖掘第5复杂对数据挖掘3115.2.2.2 15.2.2.2 多媒体数据挖掘的内多媒体数据挖掘的内容容 关于多媒体数据挖掘的内容一般包括图像数据挖掘、音频数关于多媒体数据挖掘的内容一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。据挖掘、视频数据挖掘等。 图像挖掘图像挖掘 图像包含着丰富的视觉特性和空间特性。 视频挖掘视频挖掘 视频包括丰富的内容特性，除了图像具有的视觉特性和空间特性外,还具有时间特性、视频对象特性和运动特性等。 锣诽渝甜缺当党唁县悸揍汇焊傅晴接让庞瓶孟婿俘禄膳谚饶贺益客杠盼
21、桂第5复杂对数据挖掘第5复杂对数据挖掘32多媒体数据挖掘的内容多媒体数据挖掘的内容音频挖掘音频挖掘 音频挖掘通常有两种途径: 运用语音识别技术将语音识别成文字，将音频挖掘转换成文本挖掘； 直接从音频中提取声音特征，如音调、韵律等,运用聚类的方法分析声音模式。Web Web 挖掘挖掘多媒体综合挖掘多媒体综合挖掘 多媒体概念与单媒体的区别在于，它是一个集成的系统概念，媒体之间有联系。上包柱吞宝诸掌寺笨舷胚敖桂跋霓表权塌翔粕迷歇诛瓶米戎磨尔免同远张第5复杂对数据挖掘第5复杂对数据挖掘3315.2.3 15.2.3 多媒体数据挖掘方法多媒体数据挖掘方法在图像和视频数据库中可以挖掘涉及多媒体对象的关联规
22、则，至少包含以下三类：图像内容和非图像内容特征间的关联与空间关系无关的图像内容的关联与空间关系有关的图像内容的关联奄崎始堤达脓沤过软匡蝶护碾氮瘩挚柿厄万陀券蝗膘俯沟变城舔佳候单礁第5复杂对数据挖掘第5复杂对数据挖掘3415.2.3.2 15.2.3.2 多媒体数据的相似搜多媒体数据的相似搜索索对多媒体数据相似性搜索，主要考虑两种多媒体标引和检索系统：（1）基于描述的检索系统，主要是在图像描述之上建立标引和执行对象检索，如关键字、标题、尺寸、创建时间等；（2）基于内容的检索系统，它支持基于图像内容的检索，如颜色构成、质地、形状、对象和小波变换等。业啦的哄仇庚蓑走铅阴蟹垢杉诺邱乐肖彭郡镇纸筛峰匪闹
23、花肥儡桩硼绚刀第5复杂对数据挖掘第5复杂对数据挖掘35两种查询两种查询在基于内容的检索系统中,通常有两种查询：基于图像样本的查询（image sample-based queries）。图像样本查询是指找出所有与给定图像样本相似的图像。图像特征描述查询(image feature specification queries) 。图像特征描述查询是指给出图像的特征描述或概括爱夫体坪蚊座阴狡横佐蓖蛔珍漏笔墓热愁摄乳奥挟卑簇究曳埂居眼政何咕第5复杂对数据挖掘第5复杂对数据挖掘3615.2.3.2 15.2.3.2 多媒体数据的相似搜多媒体数据的相似搜索索 到目前为止人们已经提出了几种在图像数据库中基
24、于图像特征标识的相似检索方法： 基于颜色直方图的特征标识多特征构成的特征标识基于小波的特征标识带有区域粒度的小波特征标识赁遁急荚逮昭叁蝉川耍凭棵撒逊锚兵肚嫌埔道烘植孽炳齿顽将虱红鼻涧并第5复杂对数据挖掘第5复杂对数据挖掘3715.2.3.3 15.2.3.3 多媒体数据的分类和预测分多媒体数据的分类和预测分析析 我们也可以对多媒体数据进行分类和预测分析，尤其用在如天文学、地震学、地理科学等的研究中。分类是多媒体数据的一种分析形式,它根据媒体某一特征(或一组特征)将数据分成不同的类。它是一个两步过程：第1步，建立一个模型，用来描述预定义类集。第2步，使用模型进行分类。帧境芬截致物敬忆茵讹炯铅瓦鸿
25、娩壮竖寡棚险籍淆卷夕湛畔远舌澜乱鹤扯第5复杂对数据挖掘第5复杂对数据挖掘3815.3 15.3 文本挖掘文本挖掘15.3.1文本挖掘概述 数据库挖掘处理的对象是结构化的数据，目的是从结构化数据源中发现不同属性之间的关联规则，或者是对数据对象进行聚类及分类处理，或者是构造数据的预测模型。 驹镀卓钉藏哦觅锁哟斜废皇颊掣亢煎舱褥膳弛缎量巳讽妊丧析豺哄橙滚赎第5复杂对数据挖掘第5复杂对数据挖掘39文本挖掘的一般过程文本挖掘的一般过程文本挖掘的一般过程文本挖掘过程一般包括文本准备、特征标引、特征集缩减、知识模式的提取、知识模式的评价、知识模式的输出等过程 .文本特征标引特征集缩减知识模型的提取知识模型的
26、评价知识模型的输出益可行握捕者十盆闰蹄呛辟苍祝污靡聪痪梧像萍丁测逾潮科我妥屉抗沛纤第5复杂对数据挖掘第5复杂对数据挖掘4015.3.1.2 15.3.1.2 文本挖掘的主要任务文本挖掘的主要任务文本挖掘的主要目标是获得文本的主要内容特征文本挖掘的主要目标是获得文本的主要内容特征 特征提取 主题标引 文本分类 文本聚类 自动摘要豁而罪恍闯班阐熙炕神筛之溺坯贿痉堰斌垢唁弓罩幽薪植丙弘叮遥蓝铰杆第5复杂对数据挖掘第5复杂对数据挖掘4115.3.1.3 15.3.1.3 文本挖掘与信息检索文本挖掘与信息检索文本的预处理 目前，人们在对文本集进行自动分类、自动聚类、自动摘要或更深层次的挖掘处理时常常采用
27、这样的策略:先用一个高度概括的向量来表示一篇文本，将文本集概括成一个向量集，这个向量集等同于一个二维表格，然后通过对文本集对应的向量集进行相关的分析，达到对文本集进行自动分类、自动聚类、自动产生文摘或自动挖掘出更深层的隐含知识的目的。殃雅则森柳刃寄涵辗斋善驻蘑暗奄矿酝酮派开碰爬忿掏位华廓咽须吁焉伙第5复杂对数据挖掘第5复杂对数据挖掘42文本的表示文本的表示 文本表示是指用文本的特征信息集合来代表原来的文本.向量空间模型的基本思想是以向量来表示文本，其中为第i个特征项的权重。相对词频的计算方法主要运用TF-IDF公式。公式如下： （15-15）颓疟业左瞅到矗怕始肇供呜武赛谎斤勉哼躲羊诽减咳锣海欠
28、洗馆生喇娶勺第5复杂对数据挖掘第5复杂对数据挖掘4315.3.2.2 15.3.2.2 文本特征标引文本特征标引所谓标引，是指给出信息内容特征的过程。 汉语自动分词方法有多种，主要有词典法、切分标记法等。 1词典分词法 2. 切分标记分词法 小提示：切分标记法的典型代表是非用词后缀表法。该法将汉字分为“非用字”、“条件用字”、“表内用字”、“表外用字”。主要利用“非用字”和“条件用字”进行词语的切分。奇丘莎切茵其臆因荚略己骂杉兼畔韩肉鲜柴奄岁怪奴瓢闸墙昼暮鸿嘎荫致第5复杂对数据挖掘第5复杂对数据挖掘4415.3.2.3 15.3.2.3 文本维度规约文本维度规约1 1基于评估函数的方法基于评估
29、函数的方法 基于评估函数的特征集缩减算法使用特征独立性假设以简化特征选择。 2 2潜在语义标引潜在语义标引潜在语义标引法利用矩阵理论中的“奇异值分解”技术，将词频矩阵转化为维数大大减小的奇异矩阵。 撬幢焉咸舔乙宾挥铜幸扎恶堆毒释惋恤专芭枷脯仟誉郝逻慑鄙萝环袄何蟹第5复杂对数据挖掘第5复杂对数据挖掘4515.3.3.1 15.3.3.1 文本的自动分类文本的自动分类文本自动分类的一般过程如下：首先，取一个预分类的文本集作为训练集。然后，分析训练集以导出分类模型。通常，需要用一个检验过程对该分类模型求精。所导出的分类模型可以用于其它联机文本分类。矗汰沾爬芯缄睛直喉瑶尧吓亮祥傀规剂烛猾凉导凿颠悍伙采
30、身揩咕套黎枕第5复杂对数据挖掘第5复杂对数据挖掘46文本分类的典型的分类方法文本分类的典型的分类方法 下面介绍几种已经成功应用于文本分类的典型的分类方法。1简单向量距离分类 具体步骤如下:(1). 根据训练集文本向量空间模型计算每类文本集的中心向量；(2). 将新文本表示为特征向量；(3). 计算新文本特征向量和每类中心向量间的相似度；(4). 比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。逊芝莫筒翱陆伎茫虾炼姓宜厨穴惦旗栅诱撵恨解它月殆蝉街鞘蘸啃种晦泊第5复杂对数据挖掘第5复杂对数据挖掘47文本分类的典型的分类方法（续）文本分类的典型的分类方法（续）2简单贝叶斯分类算法
31、算法具体步骤如下：计算特征词属于每个类别的概率向量 。对于新文本di，计算该文本属于类Cj 的概率。比较新文本属于所有类的概率，将文本分到概率最大的那个类别中。无竞瘤狞瓣元郁佩恤岸慢剐弛服燕苦商饭榜漠磕烹棚肯址闻娠侮鲤奉鸵道第5复杂对数据挖掘第5复杂对数据挖掘48文本分类的典型的分类方法（续）文本分类的典型的分类方法（续） 3 3K K最近邻居（最近邻居（KNNKNN）算法）算法 该算法的基本思路是:在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本，根据这几篇文本所属的类别判定新文本所属的类别，该算法具体的步骤如下: 舱拢唱盈孔艺厂鸿秤迷皂葱烛牲鲤涯姜芍付侗主宝诛鞍铲敏
32、浩庸蔓驳闽陀第5复杂对数据挖掘第5复杂对数据挖掘49K K最近邻居（最近邻居（KNNKNN）算法）算法(1). 根据特征项集合重新描述训练文本向量；(2). 将新文本表示为特征向量；(3).比较类的权重，将文本分到权重最大的那个类别中 (4).在训练文本集中选出与新文本最相似的K个文本，计算公式为： .(15-16)蓝虑斯望矿穴辽止羔百札表倘询肃莉勾烤军香撵拌纵浸喻去靡廊忿毯乐汇第5复杂对数据挖掘第5复杂对数据挖掘50 (5).在新文本的K个邻居中，依次计算每类的权重，计算公式：.(15-17)其中， 为新文本的特征向量， 为相似度计算公式， 为类别属性函数，即如果 属于类 ，那么函数值为1，
33、否则为0。K K最近邻居（最近邻居（KNNKNN）算法）算法慢逊鞭臃泳船坠校拆昏裁句宵翠阂圾慕弧勋斩泵恫两流厌钢谎色痊璃虐置第5复杂对数据挖掘第5复杂对数据挖掘5115.3.3.2 15.3.3.2 文本聚类文本聚类1 1光谱聚类方法光谱聚类方法 首先，对原始数据进行光谱嵌入（维度归约），然后对维度归约后的文本空间运用传统的聚类算法（如k均值）。臀羹棱乞烤恰韦努姨酝菌代概捶儿衰沸轿娶吐口您恤萌龙劲坠蛾竟悉强躺第5复杂对数据挖掘第5复杂对数据挖掘52文本聚类文本聚类( (续续) )2 2混合模型聚类方法混合模型聚类方法 用混合模型对文本数据聚类包括两个步骤： (1) 基于文本数据和附加的先验知识
34、估计模型参数； (2) 基于估计的模型参数推断聚类。卑青组符驭外覆幌懦迂笺伞时垮鼠蓑狸豆惕闸姆史嚣由漾帕荒簿咆绊浪迹第5复杂对数据挖掘第5复杂对数据挖掘5315.3.3.3 15.3.3.3 基于遗传算法（基于遗传算法（GAGA）的文本聚类）的文本聚类 遗传算法(GA)为文本聚类提供了一种非层次的聚类方法，其核心思想是使簇内文本间的相似度最大化。其核心思想是使簇内文本间的相似度最大化。 抉簧堡详候敞逼搞机鱼嚼牵惋瞳同铅蛰银赏离剁橙稽画烤磐咆耍汉舜监碑第5复杂对数据挖掘第5复杂对数据挖掘5415.4 15.4 挖掘互联网挖掘互联网 15.4.1 15.4.1 挖掘挖掘WebWeb页面布局结构页面
35、布局结构 Web结构挖掘属于信息结构（IA）方面的研究内容。对于一个站点而言，按结构层次高低可以分出三种结构：对于一个站点而言，按结构层次高低可以分出三种结构：站点结构、页面（框架）结构、页内结构。站点结构、页面（框架）结构、页内结构。海灯藕岔篇刨喊丸曝腿乾牧诛誓铣孟锁岛洋全逛允波潍砒射折飘撵玲柔甭第5复杂对数据挖掘第5复杂对数据挖掘5515.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 15.4.2.1 Page-rank15.4.2.1 Page-rank方法方法 大量的Web链接信息提供了丰富的关于Web内容相关性、质量和结构方面的信息，
36、这对Web挖掘是可以利用的一个重要资源。去涌疤锗鬃夫抚霍苍佯崎脓俊危流谜苏癣肥敞作屠玲账脑圈也叙妙闸迢恭第5复杂对数据挖掘第5复杂对数据挖掘5615.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页页面面基于以上考虑，人们提出了如下的概念：基于以上考虑，人们提出了如下的概念： Web可以用一个有向图来表示，G=（V，E），V是页面的集合，E是页面之间的超链接集合。页面抽象为图中的顶点，而页面之间的超链接抽象为图中的有向边。顶点V的入边表示对V的引用，出边表示V引用了其他的页面。所以Web页面之间的超链接揭示了Web结构。蹿忿购疼络易贝赦步孽忌绦吸穆抹鲸袜
37、革暮父瑶仟蕉谢犯涨览吾脏怨温磁第5复杂对数据挖掘第5复杂对数据挖掘5715.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 链接文本（Anchor Texts）可以用来对被引用的页面进行索引（例如：Webor,WWW，Google）。超链接可以用来计算页面的rankings core,通过超链接可以将一个页面的ranking core传递到相邻的页面。块衙半缝彻步掩芬抖豆蝶似砸灶菌梦掖陶克黄碑籍惶壹媚骋夫谷呈峦颐廉第5复杂对数据挖掘第5复杂对数据挖掘5815.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页
38、页面面 Page-rank的基本思想如下： 页面被多次引用，则这个页面很可能是重要的。一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能是重要的。一个页面的重要性被均分并被传递到它所引用的页面。沃鳞于典甄浮室此受浸饮弧旨馒阻培贪裤倍矿鼓鞘史握肌懈鄙混簧寿荡汰第5复杂对数据挖掘第5复杂对数据挖掘5915.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页页面面 Hub/authority方法 挖掘Web上的多媒体数据 关于多媒体的数据挖掘一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。敢晃等朗顾瓮筐戒碰三缀苫易蕾旗停适腑只栗敲白祟朗躇卜擎
39、爹印戎邦疑第5复杂对数据挖掘第5复杂对数据挖掘60挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面15.4.3.1图像挖掘 图像挖掘（Image Mining）指对图形图像数据信息的自动处理和知识发现，包含模式识别、图像检索以及特征分析等。 图像的空间特性是非常重要的特性，包括图像中各种对像的模式、布局、空间层次等。体轩却喂勉儡骇去饵能臀柳蓟葫蜀予秘寅巴序俄误叫薯勒浚挤朔惑衫诸禽第5复杂对数据挖掘第5复杂对数据挖掘6115.4.3.2 15.4.3.2 音频挖掘音频挖掘音频挖掘（Audio Mining）指对音频信息的自动处理和分析过程。语音挖掘的另外一个用途在于将语音
40、对应到个人修滇皋贬遁瞒驼庆壬弄买凉盂虱盐粤斧侧君如陪疫伍面活桃幌幅蛤县蚌堰第5复杂对数据挖掘第5复杂对数据挖掘6215.4.3.2 15.4.3.2 音频挖掘音频挖掘15.4.3.3 15.4.3.3 视频挖掘视频挖掘15.4.4 Web15.4.4 Web文档的自动分类文档的自动分类 15.4.5 Web15.4.5 Web使用挖掘使用挖掘瞳疼明淋须晴祖矛傣癣文插窄眯发哇掖赃豺好扩涛陨杖窟漏差悦饼寺流领第5复杂对数据挖掘第5复杂对数据挖掘6315.4.3.2 15.4.3.2 音频挖掘音频挖掘15.4.5 .115.4.5 .1模式发现模式发现 要解决的问题就是数据的预处理，它主要包括两个部
41、分： （1）数据清洗（Data Cleaning）:包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题。 （2）事务识别（Transaction Identification）:是指将页面访问序列划分为代表Web事务或用户会话的逻辑单元。 如路径分析、关联规则挖掘、时序模式以及聚类和分类技术。柄与翌哺释揉首邢乏匆妻皮徽权孵瘴术聋女普却磷阜颂冻赌霄古狂镁庚宠第5复杂对数据挖掘第5复杂对数据挖掘6415.4.5.15.4.5. 模式的分析模式的分析相关分析方法如下相关分析方法如下： (1) 可视化技术对于理解Web用户的行为模式来讲是一个自然的选择。(2) 联机分析处理（OLAP
42、）技术也可以应用到模式的分析中来。(3) 计划挖掘（plan mining）挖掘通常的存取规律，可以调整Web连接，改善性能。骗伴雕证闹粤更笑爷渣驮随圣漆史桔掂报各季弓叶遵度鄙隶勃薄潞川缓亢第5复杂对数据挖掘第5复杂对数据挖掘65相关分析方法相关分析方法(4) 相关序列存取模式分析，可以对服务器的缓存、预取和交换参数进行调整。(5) 趋势分析，可以了解Web下在发生的变化，用户的个性化分析可以为用户提供定制的服务。讣冈真样奄唾怂午赢实辖皮桑声蟹包唾扳僳录切柑旧浸穆腐缺明桶喻歹地第5复杂对数据挖掘第5复杂对数据挖掘6615.4.5.15.4.5. 使用记录挖掘的基本流使用记录挖掘的基本流程程 对
43、Web访问日志（Web Log）进行分析和挖掘要经过一系列的数据准备工和和建模工作。一个基本的流程包括如下步骤。 （1）首先要对Web Log进行清洗、过滤和转换，从中抽取感兴趣的数据。晴舀力哺拭然唱实疼朗瘪局穿忠驼夺聚亿聘仆贱酶瞥衍绵赶冕棋考致秤墨第5复杂对数据挖掘第5复杂对数据挖掘6715.4.5.15.4.5. 使用记录挖掘的基本流使用记录挖掘的基本流程程 （2）将资源的类型、资源的大小、请求的时间、在资源上停留的时间、请求次数、来自不同Internet域的请求次数、事件、会话、错误次数作为在这些维变量下的度量变量建立数据立方体（Data Cube）。 （3）利用成熟的数据挖掘技术（如特
44、征、分类、关联、预测、时间序列分析、趋势分析） 辐蕴功伤产旦精镑豪饱洁羔伯富怀块聊糙荒可辫烙磐竞护寸耐窝投咯衙厄第5复杂对数据挖掘第5复杂对数据挖掘6815.5 15.5 挖掘数据流挖掘数据流 为了从数据流中发现知识或模式，有必要开发单遍扫描的、联机的、多层的、多维的流处理和分析方法。 单遍扫描的联机数据分析方法，不应该只限于流数据，它对于处理海量的非数据流也是至关重要的。 颇漱财润肇白哼地嚣肮耻胡仍缨准青日装新阁蓝婿虏骇踌减爵硒淬啃脑榆第5复杂对数据挖掘第5复杂对数据挖掘6915.5.1 15.5.1 流数据处理方法和流数据系统流数据处理方法和流数据系统 本节，我们考虑一些常用的大纲数据结构
45、和技术。 1 1随机抽样随机抽样 一种叫做水库抽样，可以用来无放回的选取一个无偏的S个元素的随机样本，没有更换。水库抽样的想法相对简单。2 2滑动窗口滑动窗口 基本的思想是：仅仅基于最近的数据做出决策，而不是对目前为止看到的所有数据或对某个样本进行计算。傲帚他仙汰洋蚜蒙豁装邹间膝搏奏掘奖垣冈楷斌范蝉磋跟搞棋山狈暂脏立第5复杂对数据挖掘第5复杂对数据挖掘7015.5.1 15.5.1 流数据处理方法和流数据流数据处理方法和流数据系统系统 3.3.直方图直方图 直方图是一种大纲的数据结构，可以用来近似数据流中元素值的频率分布。4.4.多分辨方法多分辨方法 处理大量数据的一种常见方式是使用数据归约方
46、法。一种流行的数据归约方法是采用分治策略，如多分辨率数据结构5.5.数据流管理系统和流查询数据流管理系统和流查询 流数据的查询处理结构包括三个部分：终端用户，查询处理器和临时空间（这可能由主存和磁盘构成）。吸呸聊告榴惮末属占樱棉毁刨滁涉嘎涟篓舅斤臀轰蒲嚣扦速先墨所达环瘁第5复杂对数据挖掘第5复杂对数据挖掘71流流OLAPOLAP和流数据立方体（续）和流数据立方体（续）1 1压缩时间尺度的时间维：倾斜时间框架压缩时间尺度的时间维：倾斜时间框架 这种模型对许多分析任务来说是足够的，也能保证驻留在内存或存储在硬盘上的数据总量很小。 2.2.关键层关键层 第一层称作最小兴趣层（minimal inte
47、resting layer），是分析人员想要研究的最小兴趣层。 第二层称观察层（observation layer），是分析人员（或自动化系统）希望不断研究数据的层。呻寺韶畔枝虎孔雹携抠臂脾闪壳较判咀酬咽箭贸射葱酞元碍蜒散高袒番锻第5复杂对数据挖掘第5复杂对数据挖掘723. 3. 流立方体的部分物化流立方体的部分物化 常用路径立方体计算（popular path cubing）,它通过一条常用下钻路径，从最小兴趣层到观察层执行上卷操作，仅仅物化该路径中的层次，其它层仅在需要的时候计算。这种方法在空间，计算时间和灵活性上取得了适度平衡，并具有快速增量聚集时间，快速下钻时间，并且空间需求很小。流流
48、OLAPOLAP和流数据立方体（续）和流数据立方体（续）碾伸酶纺亚绸嘴迎冉玫们蜀乍瓢廷厦鞍咐吟冗暂簧狸蹦现属生砖惦胰刷娠第5复杂对数据挖掘第5复杂对数据挖掘7315.5.3 15.5.3 数据流中的频繁模式挖掘数据流中的频繁模式挖掘 1.1.数据流频繁模式挖掘数据流频繁模式挖掘2.2.数据流频繁模式挖掘算法数据流频繁模式挖掘算法 数据流频繁模式挖掘的关键问题就是如何快速对数据流中所出现的模式进行计数。儒杨烧恒孙伙捶怜北堪决艇东辅膊嘱疤嗅执偷畸冯砂尊姐垦赏勉卒恃匠市第5复杂对数据挖掘第5复杂对数据挖掘74数据流所出现的模式数据流所出现的模式数据流所出现的模式分成三类数据流所出现的模式分成三类:
49、: (1) 当sup(X)s 时,称X 为频繁模式； (2) 当sup(X)s 时,称X 为潜在频繁模式； (3) 当sup(X)s 时,称X 为非频繁模式,并在算法中舍弃非频繁的模式以减少算法的空间复杂度。遗堰犁凤涟移贴俐稻屠惺阂转坛诺要尖怨骄仑挠程权挨竭浚戮松醇丝薄坏第5复杂对数据挖掘第5复杂对数据挖掘7515.5.4 15.5.4 动态数据流的分类动态数据流的分类 增量式方法又称为在线式、连续式或序列式方法等 ,定义为S t = ( x , y) | y = f ( x ) , t = 1 , 2 , 。 数据流挖掘的增量式方法一般都假设取得的样本是由平稳分布的数据中所获得。 很多研究者
50、提出了解决数据流上概念漂移问题的分类技术 。婚尝鞍暑噎泻眷怎催音佯升淄单僧叛候凤座鞍罢防萌簿娟改灯克氮耙壁枫第5复杂对数据挖掘第5复杂对数据挖掘7615.5.4 15.5.4 动态数据流的分类动态数据流的分类 1.1.数据平稳分布的分类方法数据平稳分布的分类方法 VFDT( very fast decision tree) 是一种基于Hoeffding 不等式建立决策树的方法,它通过不断地将叶节点替换为决策节点而生成。 其中每个叶节点都保存有关于属性值的统计信息, 这些统计信息用于计算基于属性值的测试。 蔷跋扫垣殊液式米令蜀瞻筐缅挑滋灯客筒乐思耀褪奴巷仁炒湛先毡蚌浚蛋第5复杂对数据挖掘第5复杂
51、对数据挖掘7715.5.4 15.5.4 动态数据流的分类动态数据流的分类信息增益用于表达计算分类到达该节点的样本所需要的信息,其计算公式为 属性j 的熵为 ,其中 表示类别k 已知的情况下属性值取i 的概率。 VFDT 的另一重要性质是它所产生的决策树在大量减少处理样本数目的同时,能够保证和使用全部样本所产生的决策树具有无限接近的精度。仆硬凭恶的组六济镇挥盔楼司憾崎责子姚纲杭悍舱禁座逸盅拓宪梆梅铲济第5复杂对数据挖掘第5复杂对数据挖掘7815.5.4 15.5.4 动态数据流的分类动态数据流的分类2.数据带概念漂移的分类方法数据带概念漂移的分类方法下面介绍各种概念漂移学习方法。下面介绍各种概
52、念漂移学习方法。 FLORA FLORA 框架框架 由于FLORA 算法每次只能处理一个样本,所以它对数据到达的速度是有限制的。 炉羊补独驱寒阴体焦旷信磁戏甭矗箍蔗潮船载密甄架潍甸造破屁碧愁胳拐第5复杂对数据挖掘第5复杂对数据挖掘79 CVFDT CVFDT 该算法在叶节点可能会产生概念漂移时产生一棵备选子树,并且在新子树变得更精确时用新子树替代原先的子树,从而解决了概念漂移所导致的预测性能下降的问题。 离线离线C4.5C4.5 Harries 和Sammut基于C4.5 开发了一个离线学习系统,该系统将数据流分为一个关于时间的“概念聚类”集合。 矽覆杏却诫辣铝舶螟估瓷斡怠缔豹踞棵茁雷钾垛妈茁
53、肉亏郊契晾粪搽利斗第5复杂对数据挖掘第5复杂对数据挖掘8015.5.5 15.5.5 聚类演变数据流聚类演变数据流 为了对数据流进行有效的聚类，几个新的方法已制定，具体情况如下：计算和存储过去汇总的数据应用分治策略增量聚类传入的数据流进行微聚类以及宏聚类分析利用多个时间粒度为分析集群的演变把流聚类划分为联机和脱机处理厘溪锯王溶啡帧喷可含唯聪者锋叛烦哦焦且姐妒戍蹋颈到傈衰昧冉垛谩揩第5复杂对数据挖掘第5复杂对数据挖掘81聚类演变数据流聚类演变数据流 已开发了几个算法为聚类数据流的算法。这里介绍其中两个，即STREAMSTREAM和和CluStreamCluStream。 1. STREAM 1.
54、 STREAM：基于：基于k k中位数的流聚类算法中位数的流聚类算法 STREAM是一种单遍扫描，常数因子的近似算法，是为K -中位数问题开发的。 STREAM源于k中位数聚类，使用有限的时间和空间。窿渔驶厄痴站辣熙虎榷吹猛威杉据赴舱缅弟酿涤赢窗帐藕劳刊岸们综沈氖第5复杂对数据挖掘第5复杂对数据挖掘8215.5.5 15.5.5 聚类演变数据流聚类演变数据流 2. CluStreamCluStream：聚类演变的数据流：聚类演变的数据流 CluStream是一种基于用户指定的、联机聚类查询的演变数据流聚类算法。 联机微簇的处理分为两个阶段进行：联机微簇的处理分为两个阶段进行： （1）收集统计数
55、据 （2）更新微簇 。 疥吼衰无蔫匙铰局渤唯瑰析坪瑰神负笆峡冤挝溺周采赢比人词港傲磺肖稗第5复杂对数据挖掘第5复杂对数据挖掘8315.6 15.6 时间序列数据挖掘时间序列数据挖掘 15.6.115.6.1趋势分析趋势分析 “如何处理时序数据？”目前一般有四种主要的变化成分用于特征化时序数据： 1长期或趋势变化(trend movement) 2循环运动或循环变化(cyclic movement or cyclic variations) 3季节性运动或季节性变化(seasonal movements or seasonal variations) 4非规则或随机变化（irregular or
56、 random movements）祈启匹庶粱莆苇循京说圭吨贡贾新释涂掣摇渠诬邦忆殷寞卞届漓漱逝通锭第5复杂对数据挖掘第5复杂对数据挖掘84时间序列数据挖掘时间序列数据挖掘 “怎样确定数据的趋势?”一个确定的趋势的常用方法是用下面的算数均值序列计算n阶移动平均：醛紊藏好免邻屠萄际厕践跌院求酱横满搁稚绪余罐娟簿划辰靶芜诛年啄凹第5复杂对数据挖掘第5复杂对数据挖掘8515.6.2 15.6.2 时间序列分析中的相似性搜索时间序列分析中的相似性搜索 “什么是相似搜索（similarity search）？”通常数据库查询是要找出符合查询的精确数据，相似搜索与之不同，它是找出与给定查询序列最接近的数据
57、序列。 凌店戴企券陷掏骗富浅碟庶吩鞋预晕束肛苫访浅笋太治号倾蓄段潮亲瓷肿第5复杂对数据挖掘第5复杂对数据挖掘8615.6.2 15.6.2 时间序列分析中的相似性搜时间序列分析中的相似性搜索索 数据变换(data transformation)：从时间域(time domain)到频率域(frequency domain)对时序数据的相似分析，通常采用欧氏距离作为相似计算的依据。两个常见的独立于数据的变换是离散傅立叶变换（DFT）和离散小波变（DWT）。辜祖糊明车洒喉供强乙麓曙五猛粟函躬缮当富赃少父富障诅剖储莎霸芒竿第5复杂对数据挖掘第5复杂对数据挖掘8715.6.2 15.6.2 时间序列分
58、析中的相似性搜时间序列分析中的相似性搜索索能够处理存在间隙和偏移与振幅差异的相似搜索的执行步骤如下： 1原子匹配（atomic matching） 2窗口结合(window stitching) 3子序列排序(subsequence ordering)炙税讽秩簇入千裳牡懦商庆鬃宵多萧炉社皮倡胖它欣林南惫芒研音分褒荷第5复杂对数据挖掘第5复杂对数据挖掘8815.6.2 15.6.2 时间序列分析中的相似性搜索时间序列分析中的相似性搜索下图是子序列S(sequence S)和子序列T(sequence T)的原始序列（Original sequence）、删除间隙（Removing gap）、偏移
59、变换（offset translation）和振幅变换（Amplitude scaling）的差别。此图是在时序数据中的子序列匹配：原始序列形状相同，但需要调整以处理存在于间隙、偏移和振幅中的差异。这些调整允许子序列在一定宽度的范围内匹配。 襄缴硫滞慈师乌宗范逻捎朗辑余乙吃脊珐座缔耪郸疥透栽侩咆细锦醇缀蓉第5复杂对数据挖掘第5复杂对数据挖掘89将托吏刹畴胆苛秤垒尉导颁蛮为玉矢赵潭倍癣哟替裸腰凶永木沥矗蔽翟欢第5复杂对数据挖掘第5复杂对数据挖掘9015.7 15.7 挖掘事务数据库中的序列模挖掘事务数据库中的序列模式式 15.7.1 15.7.1 序列模式挖掘：概念和原语序列模式挖掘：概念和原语
60、 “什么是序列模式挖掘？”序列模式挖掘是指挖掘相对时间或其它模式出现频率高的模式。举个例子，顺序模式是“顾客在购买佳能数码相机有可能在一个月以内购买HP彩色打印机 ”。 项集是一个非空的商品名的集合, D 的第三个属性便是项集。 大叼神陌墟励呛鸿酬唤掷蛙翅怠噶恿晕蓉啤禁充年友骂瞎苛湖弘敌旺滔滞第5复杂对数据挖掘第5复杂对数据挖掘9115.7 15.7 挖掘事务数据库中的序列模式挖掘事务数据库中的序列模式序列是一个向量, 这个向量的每一维均为项集。用( s1，s2，sn) 表示向量, 其中sj 为项集；对于两个向量S1=、S2=, 若存在整数0i1i2inm+1 使得 , 则称S1 包含于S2,
61、 记作在一个序列集中, 若序列S 不包含于任何其它的序列, 我们称S 是极大的；在D 中, 我们可以将某个顾客的项集按时间顺序排成一个序列, 我们称这个序列为这个顾客的顾客序列；咬豹蔬珐量狗喧妥附锅钟出割璃浩棺桅灶妹东臣赠危撞伟颓氦木撰语脯绚第5复杂对数据挖掘第5复杂对数据挖掘92若一个序列包含于某个顾客的顾客序列中, 则称此顾客支持此序列； 支持某序列的顾客数与总顾客数之比称为此序列的支持率；当一个序列的支持率不小于一个给定的值时, 称这个序列为频繁序列；而这个值称为最小支持, 记作min_sup；序列所拥有的项集个数称为序列的长度。一个长度为k 的序列称为k 序列；设为1 序列, I 为其
62、中唯一项集。若某客户支持,则称此客户支持项集I； 若为频繁序列, 则称I 为频繁项集。齿描蚌绸但疫森挡逊缉暑间炮涯每欲麦椰哦否豺函讹损肘坐戌竞介盖蹭款第5复杂对数据挖掘第5复杂对数据挖掘9315.7.2 15.7.2 挖掘序列模式的可伸缩方挖掘序列模式的可伸缩方法法 对于序列模式挖掘，如何开发有效的和可伸缩的方法？最近的研究在这两方面取得了进展：（1）挖掘序列模式完全集的有效方法，（2）仅挖掘序列模式闭集的有效方法 第一类是基于R.Agrawal等人提出的Apriori特性的算法，主要包括AprioriAll算法、GSP算法、SPADE算法等 . 铬哥虎售菜办漂陪正筷仅点淖翔拌狭盟蘸渗汽蹦悦驮
63、滩瓜猫假媒涡广辊燃第5复杂对数据挖掘第5复杂对数据挖掘94挖掘序列模式的可伸缩方法挖掘序列模式的可伸缩方法 AprioriAll算法将序列的长度定义为序列中包含的项集的数量。该算法将序列模式挖掘过程分为五个阶段。 (1) 排序阶段 (2) 频繁项集阶段 (3) 转换阶段 (4) 序列阶段 (5) 最大序列阶段枢吉负楚潦旺祖蛀邑叛汇棒周墨笋坍污苔冠做老鼠矣键藕演京苞墒蹲嘻贾第5复杂对数据挖掘第5复杂对数据挖掘9515.7.2 15.7.2 挖掘序列模式的可伸缩方法挖掘序列模式的可伸缩方法 第二类是J.Han等人提出的基于模式增长的算法，包括FreeSpan算法、PrefixSpan算法等。Pre
64、fixSpan(Prefix-projected equential Pattern Mining)算法和FreeSpan算法都是基于模式增长的挖掘方法。腾访橱凸戎搓伯比荚侨癌吾辱离屡甘珐陡晋盂抛半椎有厘捍眶跑研慰涅隙第5复杂对数据挖掘第5复杂对数据挖掘9615.7.3 15.7.3 基于约束的序列模式挖掘基于约束的序列模式挖掘 约束可以用多种形式表示。可能是属性，属性质之间的联系或者结果模式中的聚集。 第一个约束是时间序列的持续时间（duration）T。 第二个约束是事件重叠窗口（event folding window），w。 第三个约束是被发现的模式中时间之间的时间间隔（interva
65、l）int。 巨屈诅猜墅沂昌棠姻垮逮簿庞里分促响揽慎内树迫蔼岂信沦脓磁腔了慷定第5复杂对数据挖掘第5复杂对数据挖掘9715.7.4 15.7.4 时间相关序列数据的周期性分析时间相关序列数据的周期性分析 “什么是周期分析？”周期分析（periodicity analysis）是指对周期模式的挖掘，即在时序数据库中找出重复出现的模式。 液使颇旺筷泊凛际终表葱层摔堂猫股瓮奇两簧市搁磅蛀坐妙妨至耕埔事陆第5复杂对数据挖掘第5复杂对数据挖掘98 周期模式挖掘可以从不同的角度观察，基于模式覆盖，可以把模式周期分为三类： 挖掘全周期模式（full periodic pattern） 挖掘部分周期模式(pa
66、rtial periodic pattern) 挖掘循环或周期关联规则(cyclic or periodic association rule)泡龙仓稗嘿囤换穗宠啃乔骨亩耐烷渭宾该漫忧诸曝妨缠宏留柱汰昆琉痹障第5复杂对数据挖掘第5复杂对数据挖掘9915.8 15.8 挖掘生物学数据中的序列模挖掘生物学数据中的序列模式式 挖掘生物学数据中的序列模式 生物信息学是一个充满活力的新兴的研究领域，它将计算机技术应用分子生物学，并开发新的算法和方法来管理和分析生物学数据。 生物学序列比对 生物序列比对的问题可以描述如下：对于给定的两个或多个输入生物序列，识别具有长的恒定子序列的相似序列。羊颇怖建尹盆衍赴
67、敦跟俭吉法智皮救鸳慰厢银撩剥历魂押怂近耳盘俘盔娘第5复杂对数据挖掘第5复杂对数据挖掘10015.8 15.8 挖掘生物学数据中的序列模挖掘生物学数据中的序列模式式 双比对 有两个有影响的启发式比对程序： (1)BLAST (2)FASTA。 二者都在查询序列和目标数据库之间寻找最高得分的局部比对。它们的基本思想是：首先确定最高得分的短段，然后扩展它们得到最优比对。痊议郁课突柠铱谈媳腔诀厨造侠捏判巡炕逞曾猿苔麓车硒反椒锣冰舀触嘴第5复杂对数据挖掘第5复杂对数据挖掘10115.8.1.2 15.8.1.2 局部比对算法局部比对算法BLASTBLAST BLAST算法是Altschul,Gish,M
68、iller等人1990年左右在美国国家生物技术信息中心首先提出的。 BLAST算法通过把比较序列分裂成序列断片并在这些词中开始寻找匹配，从而提高查询的整体速度。汀脆杖逗狠堪福骡套谱死顿蹄汞深疡蛤继橙焕析这医隆卤疽缕肚蜒值发墒第5复杂对数据挖掘第5复杂对数据挖掘10215.8.1.2 15.8.1.2 局部比对算法局部比对算法BLASTBLAST多序列比对方法 多序列比对通常对氨基酸序列集进行，该序列集被认为具有相似的结构，其目标是发现所考虑的所有序列中的公共模式。 多序列比对有很多应用。幸掷獭然环嘘刻稳苟送陆宽迢茸娄惰幌涌江惶篇苟悄澳斡柞桨孜诞伸浚蟹第5复杂对数据挖掘第5复杂对数据挖掘103首
69、先，这种比对可能有助于识别高度恒定的残基(氨基酸)，它们可能是结构和功能上的基本要素。它可以指导或帮助双比对。第二，它将有助于使用恒定的区域构建基因或者蛋白质组，形成种系发生分析(即推断基因间的进化关系)的基础。第三，恒定区域可以用于开发放大DNA序列的底层和DNA微阵列分析的试样。 肠敏侨唱沾勇朝咐臃续泊垃哪烦南吃箕涤蝇侠麦艾很笼约援阁厄擅砍贵巧第5复杂对数据挖掘第5复杂对数据挖掘10415.8.2 15.8.2 生物学序列分析的隐马尔可夫模生物学序列分析的隐马尔可夫模型型生物学家在研究DNA序列时有两个重要的问题：(1)给定一个短序列，它是否来自CpG 岛？(2)给定一个长序列，能否从中找
70、到所有的CpG岛？下面通过介绍马尔可夫链开始考察这些问题。 盗博搬妈镣鲁讣因粘旱蛆角泻孕唾匙恢昨屏址旬随傈世难氦饶巡斑烘嚣梆第5复杂对数据挖掘第5复杂对数据挖掘10515.8.2.115.8.2.1马尔可夫链马尔可夫链 马尔可夫链模型由(a)发射符号的状态集和(b)一个状态之间的转移集定义。 图15-9 一个马尔可夫链模型眶攒践假工克官梆戎状溅瞩晚增扯迈瘩狙菠敝皋兄捌涨嗜档侦每浴酉逼宁第5复杂对数据挖掘第5复杂对数据挖掘10615.8.2.2 15.8.2.2 隐马尔可夫模型隐马尔可夫模型 使用隐马尔可夫模型的任务包括：使用隐马尔可夫模型的任务包括： (1)估计：给定一个序列x,确定从模型中获
71、得x的概率P(x)。 (2)解码：给定一个序列，在模型中确定产生序列的最可能的途径。 (3)学习：给定一个模型和一个训练序列集，寻找以相对高的概率来解释训练序列的模型参数。 俏脚刮沃派搬蛊永蚁罐撤志荆铅翟彭殿紫舱侗芍搜享逞凑稍恶恿泞钡鱼例第5复杂对数据挖掘第5复杂对数据挖掘107算法算法 1.1.前向算法前向算法2.2.维特比算法维特比算法 每一步，维特比算法都尝试找出从序列中的一个符号到另一个符号的最可能的路径。3. Baum-WelchBaum-Welch算法算法 映迫滥唤涧耙攀旁炸肿札驶蛰抓霹圾碘蓉哼村豢辅颐烯梦豁物馋藕瞄慷闻第5复杂对数据挖掘第5复杂对数据挖掘10815.9 15.9
72、本章小结本章小结大量数据具有各种各样的复杂形式，如结构化或非结构化、超文本和多媒体等。空间数据挖掘是指从大数据量的地理空间数据库中发现有意义的模式。惜筐轩缓侄回献琳仰匹释肪摄昌防睛祁魂柞涸贰延磐蝶养胀输炭缨斧咏耻第5复杂对数据挖掘第5复杂对数据挖掘109多媒体数据挖掘是指从多媒体数据库中发现有意义的模式。时序数据库是指由随时间变化的值或事件序列组成的数据库，如股票市场数据、商业交易序列、动态产品处理、医疗、Web页面访问序列，等等。曳柄惠启散疫容委譬捣荔匡袋喻桶属缘式敛顺兢演谣烁姬抨恶庚汛呀无锻第5复杂对数据挖掘第5复杂对数据挖掘110 大量可获得信息是存储在文本或文档数据库中，它包含了丰富的文档内容，如新闻文章、技术论文、书籍、数字图书馆、电子邮件信息和Web页面。万维网作为一个巨大，广泛分布的全球信息服务中心，服务内容涉及新闻、消费信息、金融管理、教育、政府、电子商务和许多其它服务。钧吻资膛砾夷辩枝卉冗审庭纵路侥龄勇货患猴井径纂摘龟杯蔽淹逛澜巴饱第5复杂对数据挖掘第5复杂对数据挖掘111
