（教育技术学专业论文）基于关联规则和粗糙集的智能交通改进算法研究与实验.pdf

天津师范大学硕士学位论文 摘要 随着经济技术的不断发展和城市现代化的建设，智能交通已经成为了热点问 题。而道路最优路径的快速查找和分析处理又成为了目前智能交通中的研究前 沿，数据预处理、加权函数、算法分析则是其中最重要的部分。本文主要研究了 智能交通中的寻求最优路径问题，提出了基于关联规则和粗糙集的改进算法，阐 述了其基本理论及算法原理，并通过仿真实验验证了算法的假设。 本文主要研究内容是：首先，概述了智能交通的发展现状，及目前所使用的 算法，并扼要地介绍了本文所涉及的数据挖掘算法；其次，分析了目前道路信息 的研究现状，特别是针对道路断交问题，提出了基于关联规则的a 水算法，描述 了算法的基本思路、算法分析及其流程图；第三，针对大量的道路信息数据，提 出了基于粗糙集的聚类算法，其以约简道路属性为基础寻找最优路径，阐述了算 法的基本原理、步骤及其流程图；第四，结合实际道路数据，对基于关联规则的 a 木算法与基于粗糙集的聚类算法分别进行仿真实验，分析实验结果，并验证了算 法的有效性。本文对获取道路最优路径做了一些有益的探讨。 关键词：智能交通，关联规则，a 幸算法，粗糙集，聚类分析 天津师范大学硕士学位论文 a b s tr a c t w i mt l l e d e v e l o p m e i l to fe c o n o m i c 觚dt 1 1 em o d e n lp r o g 阳s s i v eo fu i b a n c o i l s 删i o 玛n e l l i g e n tt r 觚s p o r t a t i o nh a v eb e c o m eah o ti s s u e hm ci t ，骶q u i d d y 丘l l d i n 岛a n a l y z i n 吕姐dp r o c e s s i n go n0 p t i l i l a lp a t ho fr o a da r et h er e s 翩托“m g f o r e 董m ，t o o d a t ap r e 骶a 恤e m ，w e i 咖e d 向n c t i o n ，柚da l g o r i t l l ma n a l y s i si st h e i 1 i l p c n 锄tp a r t t l l i s 吐l 船i sm a i l l l yd i s c u s s 鹤也e 邮b l e mo fs e 删n go 埘m a lp a n li i l t l l e 劬f j i ci n t e l l i g 钮t ，p u t sf o 刑a r dt h ei m p r o v e da l 鲥i mb a s e do n 弱s o c i a t i o nm l e 锄dr o u 曲s e t ，e x p o u n d si t s 如n d 锄e n t a lt l l e o f y 卸d 研n c i p l eo fa l g o r i m m m o r e o v s i m u l a t i o ne x p e d m e n t sa r ei m p l e m e i l t e dt 0v 甜母m ev a l i d i 锣 t h em a i l lc o n t e n t so f 也es t u d y 舔旬l l o w s ：f i f s t l y ，l ed e v e l o p m e n ts t a t 吣o f i n t e l l i g 僦咖l s p o r t a ：t i o na n dc l 硼r e n tu s i n go ft l l ea l g o r i l ma r e 蛐【i i 】m 撕z e d t h e i l ，i t h 弱s o m eb r i e fd e s c d p t i o n so fd a l am i l l i n ga l g o r i t l l m so ft l l i sp a p e r ；s e c o i l d l y ， a o c o 础n gt o 锄a l y s i s i n gt h ec 1 1 e n tr e s e a r c l l i n gs t a h 塔o fr o a dm f o n l l a t i o 玛i t p r o p o s e sn l ea 搴a l g o r i n l mo n 勰s o c i a t i o nr i l l e st os o l v cp r o b l e mw h f a c i i 培吐l e i s s l l eo nc l o s e dr o a di i l 舰f i c a n di td e s c r i b en l eb a s i ci d e 弱o f 坞a l g o r i u n ，i t s a l g o r i 廿u n s 觚a 1 ) r s i sa n di t sn o wc h a r t ；t l l i r d l y a c c o r d i i l gt o 吐l el o t so f a d i n 内咖a t i o n ，i n 衄sp a p e ri tp r o p o s e st l l ed u s t e r i r 培a l g o d 廿l mo nr o u g hs e t s ，0 b 妇 m eo p t i m a lp a 吐lb 弱e d r o d u c i n ga t t r i b u 慨i n f o m a t i o no fr o a d ，觚de x p o u n d st l l e a l g o r i t l l 】ma 1 1 a l y s i s ，s t e pa i l df l o w c h a n ；l 嬲t l y ，c o m b i l l i n gw i t l lt l l ea c t u a ld a t ai nr o a d ， r e s p e c t i v e l ya 宰a l g o d t l l mo na s s o d a t i o nr u l e s ，锄dc l u s t e r i n ga l g o r i 也mo nr o u g h s e t sd os 妣l a t i o ne x p 甜m e n t s ，a i l a l y s i sr e s u l t sa n d p r o v et h ev a l i d i t yo fm ea 1 9 0 r i t l l i n w e c a 订了o u ts o m e b e l l e f i c i a ld i s c u s s i o nt 0o b t a i nt l l eo p t i m a lp a t h k e y w o r d s ：i n t e l l i g e ：n tt 姗s p o r t a t i o n ，a s s o c i a t i o nr u l e ，a 幸a l g o r i t l l m ，i b u 曲s e t ， c 1 u s t e r i n ga l g o r i t h m i l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得丞洼垭堇太堂或其它教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 签名：璺咝日 学位论文版权使用授权书 期： 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权 将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫 描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交 论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：錾丛聊签名：壶歪盟苎日 期： 天津师范大学硕士学位论文 第一章绪论 随着我国经济发展和城市现代化建设，道路的信息量也呈现了快速增长的模 式，在这种情况下，为了更好的实现智能交通的理论思想，我们需要对寻求最优 路径问题进行更深层次的研究。 1 1 智能交通概述 随着全球经济的发展和城市化的不断进程，道路交通拥堵严重、交通事故率 上升、交通营运效率下降、道路车辆的指数增长引起的资源浪费成为全球各个城 市发展面临的共同问题。面对道路交通的发展，人们对于现代交通的需求也发生 了改变，安全、舒适、便捷和信息化成为了追求的目标，智能交通( i n t e l l i g 饥t t r 锄s p d n a t i o n ，i d 便应运而生，其研究和应用也得到了快速的发展【1 1 【2 】。 智能交通( i t ) 是将先进的信息技术、数据通讯传输技术、电子传感技术、电 子控制技术以及计算机处理技术等有效地集成运用于整个地面运输管理体系，而 p 建立起的一种在大范围内、全方位发挥作用的，实时、准确、高效的综合运输和 管理体系【3 1 。其本质是将人、车、道路、设施、管理、环境等许多子系统有机组 成了复杂的综合性系统最大限度地实现道路信息的采集、预处理、加工和共享等， 实现整个交通系统的优化运行【4 】。 1 2 目前智能交通使用的算法 在智能交通中，路径的选择是系统其中的一个核心部分，在寻径过程中，采 用的路径选取算法是至关重要的，它可以帮助在出行前或在出行中更快更好地确 定路线。目前常用的算法包括：数据挖掘相关算法、启发式搜索算法、f l o y d 算 法、动态规划算法、增长图算法、域阀算法等，分别介绍一下这些算法的概念、 基本理论及分类，并且分析算法的功能特点。 1 2 1 启发式搜索算法 启发式搜索算法是人工智能和各种网络搜索中的一种基本搜索算法，启发式 搜索算法相对于没有利用任何知识的盲目搜索算法，在搜索过程中其搜索的目的 性更强，能够朝着目标节点的方向搜索，从而减少无关节点的搜索数量。反过来 也就是，知识越多越完全，其搜索量就越少。这种搜索针对性强，因而原则上只 需要搜索问题的部分状态空间，效率高【5 1 。 尤其启发式搜索算法中著名的蚁群算法在智能交通方面更是体现了这一特 天津师范大学硕士学位论文 点，其基本原理及创新点是，蚁群算法( a n tc o l o n y 越g o r i t h m ，a c a ) 作为一种新 兴的模拟进化算法，是意大利学者d 嘶g o 等人于1 9 9 1 年创立的，可用来求解当 前的动态交通最优路径问题。蚁群算法与其它模拟进化算法一样，可以通过多个 可行解组成的种群不断进化，并以最大概率逼近甚至达到问题的最优解。一般这 个过程需要两个基本阶段，即适应阶段和协作阶段。在第一个阶段，每个可行解 可依据积累的信息不断调整自身结构；在最后阶段，可以通过交流信息，以等待 产生性能更优的解。该算法是一类基于多主体的智能算法，各主体之间通过相互 协作能够根据实时的信息调整自己的搜索行为，规避障碍，从而迅速地找到最优 路径【6 1 。 1 2 2 穷举法 顾名思义，穷举法就是通过把需要解决问题的所有可能情况逐一试验来找出 符合条件的解的方法，对于许多毫无规律的问题而言，穷举法用时间上的牺牲换 来了解的全面性保证，尤其是随着计算机运算速度的飞速发展，穷举法的形象已 经不再是最低等和原始的无奈之举，比如f 1 0 y d 算法就算是一种穷举型算法。 比如，当需要求解图中所有顶点对之间的最短路径时，可以轮流以图中的每 个顶点为源点，重复执行算法n 次，f l o y d 算法则可以直接求出图中所有的顶点 对之间的最短路径和路径的长度。算法的基本思想是：设置一个nxn 方阵a ( k ) ， 其中除对角线的矩阵元素均为0 以外，其他元素表示顶点，到v j 的有向路径 的长度，k 表示运算步骤。初始时，以任意两顶点之间的弧的权值作为路径长度， 以后逐步的在源路径中加入其他顶点作为中间顶点( 可以按照顶点序号进行) 。若 增加中间顶点后，得到的路径长度比原来的路径长度小，则以此新路径代替原路 径，修改矩阵元素，代入新的更短的路径长度【7 】。 1 2 3 动态规划算法 动态规划是运筹学的一个分支，是解决多阶段决策过程最优化的一种通用数 学算法。动态规划在各个领域都有着广泛的应用，许多问题用动态规划方法去处 理，常比线性规划或非线性规划更有成效。特别对于离散性的问题，由于解析数 学无法施展其术，而动态规划的方法就成为非常有用的工具。它不像线性规划那 样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体 分析处理。动态规划模型的分类，根据多阶段决策过程的时间参量是离散的合适 连续的变量，过程分为离散决策过程和连续决策过程。根据决策过程的延边是确 2 天津师范大学硕士学位论文 定性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程。组合起 来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型【8 】。 动态规划的基本思想是： ( 1 ) 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界 条件( 简称为基本方程) 。要做到这一点，必须先将问题的过程分成几个相互联系 的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题 化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优， 在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行， 最后一个子问题所得的最优解，就是整个问题的最优解。 ( 2 ) 在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开， 又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选 取是从全局来考虑的，与该段的最优选择答案一般是不同的。 ( 3 ) 在求整个问题的最优策略时，由于初始状态是已知的，而每段盼决策 都是该段状态的函数，故最优策略所经过的各段状态便可主词变换得到，从而确 定了最优路线【9 1 。 1 2 4 遗传算法 遗传算法( g e t i ca l g o d t h j n g a ) ，是模拟达尔文的遗传选择和自然淘汰 的生物进化过程的计算模型。由于遗传算法在机器学习、过程控制、经济预测、 工程优化等领域取得的成功，同时，研究内容也十分广泛，包括数学、物理学、 化学、计算机科学、社会科学、经济学及工程应用等各个领域的应用。 遗传算法是模拟前述生物进化过程的计算模型。遗传算法作为一种新的全局 优化搜索算法，以其简单通用、鲁棒性强、适于并行处理以及应用范围广等显著 特点，奠定了它作为2 1 世纪关键智能计算之一的地位【1 0 1 。 1 2 5 支持向量机 支持向量机( s u p p o r tv e c t o rm a c l l i n e ，s v m ) 是基于统计学习理论和结构风险 最小化( s 1 w ) 原则的学习机器。其基本思想是把输入空间的样本通过非线性变 换映射到高维特征空间，然后再特征空间中求取把样本线性分开的最优分类面， 算法使用分类间隔控制线性学习机器的容量，从而使结构风险最小，也使其在有 限样本下具有较强的泛化能力。不同的核函数即变换到不同的特征空间，使用核 函数也避免了在高维的特征空间中直接计算。因此，在模式识别、数据分类和预 天津师范大学硕士学位论文 测中表现出了很多优于已有方法的性斛1 1 【12 1 。 1 3 现有算法不足的分析与问题的提出 总体来看，智能交通的研究和应用大多是通过各种算法的有机结合对路径进 行寻求，对特殊路况的分析稍少。当遇到如道路维修、断交施工等特殊问题时， 采用已有的方法往往不能达到预期的效果。通过不断地分析发现，关联规则算法 可以帮助发现大量数据库中项集之间的关联关系。通过该算法可以逐级探查，找 到项集间的关联，并进行进一步研究。其最重要的特点是，关联规则可以预先对 断交道路属性等方面进行规则分析，找到合适的考察点，从而使得在搜索过程中 便于寻求到替代道路。针对这一特点，本文将用于路径寻求的启发式搜索算法 一a 算法与其相结合，提出了基于关联规则的a 木算法，来解决道路选择时遇到 的特殊问题，通过回退迅速寻求到最优路径，从而提高查找效率。 同时，有些算法理论上可以保证最优路径，但是在实际计算过程中总会存在 一些困难，因为实际中的信息量是相当庞大的；往往不能快速解决问题，因此计 算过程需要耗费大量的时间，体现不出高效性，为了更有效地寻求路径，针对大 量的道路信息，本文通过分析其不同的限制属性，提出了一种新的算法，即利用 粗糙集与聚类算法结合道路信息数据，对信息数据进行预处理，分层递减从而达 到高效。 1 4 本文相关的数据挖掘算法 随着计算机技术，特别是数据库技术的快速发展和广泛应用，各行各业积累 的数据量越来越大。有数据表明，进入2 0 世纪9 0 年代，人类积累的数据量每月 高于1 5 的速度增加。如果不借助强有力的挖掘工具，仅依靠人的能力来理解这 些数据时不可能的。人们已经评估出世界上信息的数量每2 0 个月翻一番，并且 数据库的数量与大小正在以更快的速度增长【1 3 】。 数据挖掘( d a t am i n i n g ) 概念最早是由u s 锄af a y a a d 在1 9 9 5 年加拿大蒙 特利尔的第一届知识发现和数据挖掘国际会议上提出的，它的提出是与计算机科 学、人工智能相关的机器学习等发展分不开的。 同时，数据挖掘又被称为数据库中的知识发现( 1 0 0 w l e d g ed i s c o v e r yi i l d a t a b a s e ，k d d ) ，就是从大量的、不完全的、有噪声的、模糊的、随机的数据 库中提取隐含潜在有用的信息和知识的过程。它是一门涉及面很广的交叉学科， 4 天津师范大学硕士学位论文 包括机器学习、数理统计、人工智能、神经网络、数据库、模式识别、粗糙集和 模糊数学等相关技术。针对各种算法的理论，下面简单介绍3 种本文用到的经典 算法的基本思想及特点。 1 4 1 聚类分析 聚类分析又称群分析，它是研究( 样品或指标) 分类问题的一种统计分析方 法。聚类分析起源于分类学，但与分类不同的是，它要划分的类是未知的。聚类 就是将数据对象分组成为多个有意义或有用簇，在同一个簇中的对象之间具有较 高的相似度，而不同簇中的对象差别较大。相异度是基于描述对象的属性值来计 算的。距离是经常采用的度量方式。在某种意义下，聚类分析是其他目的( 如数 据汇总) 的起点。聚类分析源于许多研究领域，包括心理学和其他社会科学、数 据挖掘、统计学、生物学以及机器学习。 1 4 2 关联规则的挖掘算法 关联规则挖掘( a s c i 撕0 nr u l em i n i n g ) 是帮助发现大量数据库中项集之间 的关联关系。关联规则模式属于描述型模式，其形式简洁、易于解释和理解并可 以有效的捕捉数据间的重要关系，发现关联规则的算法属于无监督学习的方法。 关联规则问题由a 蹦1 w a l 等人于1 9 9 3 年首先提出，以后诸多的研究对关联规则 进行了大量的研究，包括对原有算法进行优化，如引入随机采样、并行的思想等， 以提高算法挖掘规则的效率；对关联规则的应用进行推广，已经取得了数据库、 人工智能、统计学、信息检索、可视化及信息科学等诸多领域的研究成果。 1 4 3 粗糙集 粗糙集理论是由波兰华沙理工大学p a w l a k 教授于2 0 世纪8 0 年代初提出的 一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，它是一种 刻画不完整性和不确定性的数学工具，能有效的分析不精确、不一致、不完整等 各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示 潜在的规律。因此，粗糙集在机器学习、决策支持系统、机器发现、归纳推理、 数据库中的知识发现、模式识别等领域都得到了广泛的应用【1 4 1 。 1 5 本文研究的内容和组织结构 本文在深入研究智能交通、数据挖掘、启发式搜索算法以及寻求最优路径问 题研究的基础上，提出了对于常用的粗糙集、聚类方法和a 木算法的改进算法， 天津师范大学硕士学位论文 阐述了其算法原理与步骤流程，并使用实际数据集进行仿真实验。同时，在完成 实验后，进一步分析基于关联规则和粗糙集的智能交通改进算法的实验结果。 全文共分为五章。 论文第一章为绪论，主要包括智能交通的概述、目前智能交通所采用的方法、 本文相关的数据挖掘算法以及论文的主要研究内容和章节安排； 第二章提出了一种基于关联规则的a 幸算法，用于道路断交时期的路径选择； 首先介绍了目前道路断交寻求最优路径的研究现状，然后介绍了利用关联规则的 原理和利用a 算法寻求路径最优解的方法，重点介绍了利用关联规则的a 宰算法 描述了寻求最优路径的流程、算法分析和流程图； 第三章提出了一种基于粗糙集的聚类方法，首先阐述了粗糙集以及聚类方法 的基本理论，由于聚类算法很多分类，并对其进行了对比，然后重点介绍了基于 粗糙 集的聚类方法的内容以及应用方向，给出了算法分析及流程图； 第四章是利用道路交通数据进行仿真实验，首先是对基于关联规则的a 奉算 法进行了实验并分析算法效果；然后是进行及研究分析了基于粗糙集的聚类方法 的仿真实验与结果，显示了算法的可行性； 第五章是结论与展望，对论文所做的工作进行了总结，分析了其中的优缺点， 并对相关问题进行了展望。 1 6 本章小结 本章首先介绍了智能交通的产生和发展。寻求最优路径是智能交通的主要研 究内容，因此我们将利用先进的数据挖掘算法分析智能交通中的道路数据信息， 挖掘大量信息中隐含的规律和知识。本章具体讨论的是目前智能交通中使用的算 法，并对这些分析算法进行了分析。其中，第五节总结了论文的主要研究内容成 果和本文的组织结构。 6 天津师范大学硕士学位论文 第二章基于关联规则的a 改进算法 2 1 问题描述及研究意义 近年来，国内外学者对于智能交通中的寻径算法进行了许多研究，但是面对 道桥的修复断交等特殊交通问题往往有些忽视。同时，由于相关断交信息的延迟 性，经常会影响日常出行。因此，面对这样的特殊问题，我们应该特别加以重视。 由于目前大多数研究还没有涉及类似特殊问题的讨论，因此，通过分析这类 道路断交问题的现实道路状况，本文提出了一种新的基于关联规则的a 宰算法， 专门为解决道路断交问题而设计，通过实验，可以发现面对断交的道路，该算法 比一般的路径寻求算法的选取时间短，相对使用到的方法要简单的多，并得到了 最优路径。 2 2 关联规则 2 2 1 关联规则定义 定义2 1 设i - i l ，i 2 ，i m ) 为所有项目的集合，d 为事务数据库，事务t 是一个项目子集( t 互d 。每一个事务具有唯一的事务标识t i d 。设a 是一个由项 目构成的集合，称为项集。事务t 包含项集a ，当且仅当a t 。 定义2 2 关联规则是形如x 专y 的逻辑蕴含式，其中x i ，y i 且 x ny = a 。如果事务数据库d 中有s 的事务包含x uy ，则称关联规则x y 的 支持度为s 。 如果不考虑关联规则的支持度和置信度，那么在事务数据库中存在数量庞大 的关联规则。事实上，人们一般只对满足一定支持度和置信度的关联规则感兴趣。 一般称满足一定要求的规则为强规则。因此，为了发现有意义的关联规则必须满 足的最小支持度，它表示了一组物品集在统计意义上需要满足的最低程度；后者 即用户规定的关联规则必须满足的最小置信度，它反应了关联规则的最低可靠 度。 关联规则的挖掘就是在事务数据库d 中找出具有用户给定的最小支持度 m i n s u p 和最小置信度m i n c o n f 的关联规则。同时满足最小支持度阈值和最小置 信度阈值的规则称为强规则。 定义2 3 如果项集a 中包含k 个项目，则称其为k 项集。项集a 在事务数 据库d 中出现的次数占d 中总事务的百分比叫做项集的支持度。如果项集的支持 7 天津师范大学硕士学位论文 度超过用户给定的最小支持度阈值( m i n s u p ) ，就称该项集是频繁项集或大项集。 关联规则挖掘的基本模型( 如图2 1 所示) ：其中算法1 为频繁项目集的搜索算 法，算法2 为关联规则的产生算法。用户通过指定最小支持度阈值和最小置信度 阈值分别与算法l 和算法2 交互，并通过与规则结果集的交互对挖掘结果进行解 释和评价【1 5 1 。 图2 1 关联规则挖掘的基本模型 2 2 2 关联规则分类 ， 事实上，有许多不同类型的关联规则，可以根据以下标准对这些关联规则进 行分类。 ( 1 ) 布尔型和数值型关联规则 基于规则中处理的变量类别，可以分为布尔型和数值型关联规则。布尔型关 联规则处理的值都是离散的、种类化的，它显示了这些变量之间关系；而数值型 关联规则处理的是定量数据项( 或属性) 之间的关系，在这些规则中，可以将数 据项( 或属性) 的定量值划分为区间范围，当然数值型关联规则中也可以包含种 类变量。 ( 2 ) 单层关联规则和多层关联规则 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。若一 个关联规则的内容仅涉及单一层次的概念，这样的关联规则就称为单层关联规 则。倘在关联规则内容描述中涉及多个不同抽象层次概念，这样的关联规则就称 为多层关联规则。 ( 3 ) 单维关联规则和多维关联规则 基于规则中涉及的数据维数，可以分为单维关联规则和多维关联规则。若一 个关联规则中的项或属性仅涉及一个维，那它就是一个单维关联规则；若关联规 则中的项( 或属性) 涉及二维或更多维，则它就是一个多维关联规则。换句话说， 天津师范大学硕士学位论文 单维关联规则处理的是单个属性中的一些关系；而多维关联规则处理的是各个属 性之间的某些关系。 2 2 3 关联规则挖掘算法讨论 随着不断深入研究关联规则的挖掘问题，对原有的算法进行了优化，如引入 随机采样、并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化 的关联规则、周期关联规则等，对关联规则的应用进行推广。通过分析总结，根 据处理数据的不同方式，现有的各种关联规则挖掘算法大致可分为搜索算法、层 次算法、数据集划分算法、抽样算法等。 ( 1 ) 搜索算法 搜索算法在读入数据集中的每条事务时，对该事务中包含的所有项集进行处 理，因此搜索算法需计算数据集d 中所有项集的支持数。a t s 算法、s e l m 算 法，以及以建格算法为主体的关联规则挖掘算法都是这种挖掘算法。 ( 2 ) 宽度优先算法 宽度优先算法也叫分层算法。分层算法的思想是按包含项目数自小至大的顺 序寻找频繁项目集( 数据集中含项目数最大的频繁项集称为最大频繁项目集) 。 此类算法包括：ra 髓1 w a l 等人提出的：a p r i o r i 、a p r i 砥t i d 和a 面o m y b 五d 算 法，j s p a r k 等人提出的d h p 算法等。 a p 五耐算法是这类算法的典型代表，该算法需扫描数据集的次数等于最大 频繁项目集的项目数。a p r i o r i 算法在第k 次扫描数据集时找出所有的频繁k 项 集，第k + 1 次扫描数据集时的候选项集由所有的频繁k 项集通过连接运算产生。 其他算法都是在a p r i 耐算法的基础上进行改进融合，或是对候选集修剪，来减 少扫描数据库的时间等等。总之，以a 研o r i 算法为代表的层次算法可以产生相 对较小的候选项集，扫描数据库的次数由最大频繁项集的项数来决定。 ( 3 ) 深度优先算法 f p g r o 、加算法使用一种紧缩的数据结构来存储查找频繁项目集所需要的全 部信息。将提供频繁项目集的数据库压缩到一颗频繁模式树( 或f p 树) ，但保 留项集关联信息：然后将压缩后的数据库分成一组条件数据库，每个关联一个频 繁项目集。 设p 为一个频繁项目集，s 为所有包含p 的事务的集合，x 是个单个项目。 如果x 在s 中是个频繁的项目，那么 x ) up 定也是个频繁项目集。 9 天津师范大学硕士学位论文 f p g r o w m 算法利用上述原理，不生成任何的候选项目集，而是一个递归挖掘所 有频繁项目集的算法。f p 舯、砌算法挖掘频繁项目集的过程如下：找到所有的 频繁l 项集，并建立频繁模式树；对所有l 项集，找到其条件模式并构造条件模 式树；在条件模式树中挖掘新的频繁l 项集。如此不断循环下去，直到构造的条 件模式树为空。 对每一个频繁l 项集x ，算法扫描一次频繁模式树，然后构建一个较小的条 件模式树，对包含该项目x 的频繁的挖掘在条件模式树上递归进行。频繁模式 树的规模通常比原有的数据库要小得多。因此后面的挖掘过程通常在小得多的条 件模式树上进行。 ( 4 ) 划分算法 划分算法的基本思想是将整个数据集划分成可以存放在内存中进行处理的 数据块，以节省访问外存的i ，o 开销。此类算法包括a s a v 弱e r e 等人的p 砒i t i o n 算法、s b 血等人的d i c 算法等。p 枷t i o n 算法只需要对整个数据集进行两次扫 描，d i c 算法在数据块划分恰当时可以通过两次扫描数据集找出所有的频繁项目 集。数据集划分算法的候选项集的数量一般比a p r i 耐算法的候选项集的数量大， 增加各数据块的数据扭曲性可以减少候选项集数量。 ( 5 ) 抽样算法 抽样算法是通过对数据集d 抽样产生抽样数据集d ，找出抽样数据集d 中的频繁项集作为候选项集，然后扫描数据集d 确定其中的频繁项集。如何计 算负边界已找回部分遗漏的频繁项集是抽样算法的关键。此类算法包含j s p a r k 等人提出的可调精度的挖掘算法和h t o i v o n 饥的s 锄1 p l i n g 算法。 t o i v o n e i l 利用抽样方式从原始数据库中抽取样本，以便直接存储在内存中， 再针对样本数据库挖掘频繁项集，以减少挖掘时间。这是因为样本体积比原始数 据库小许多，所以能够快速挖掘出频繁项目集。采取抽样技术产生的样本数据必 定含有抽样误差，所以t o i v o n e l l 提出利用降低最小支持度以避免遗漏频繁项目 集。 并且，t o i v o n 锄提出的抽样算法是利用单纯随机抽样法来进行抽样的动作， 由于样本数据库所含的数据量较少，所以能借此针对样本数据进行挖掘以减少原 来所需要耗费的时间，提高挖掘效率。 通过对关联规则各算法的分析研究，我们发现：搜索算法只需对数据集扫描 l o 天津师范大学硕士学位论文 一次就可以找出所有的频繁项集，不过条包含n 个项目的事务就将产生2 n 1 个项集，因此该算法只适合于项目集数量相对较小的数据集中的关联规则挖掘； 分层算法适合于最大频繁项目集相对较小的数据集中的关联规则挖掘； f p 。印、砒算法无须生成候选项目集，显著地缩小了搜索空间；划分算法是各种 并行关联规则挖掘算法和分布式关联规则挖掘算法的基础；抽样算法适合于要求 挖掘效率较高，而挖掘准确性不太高环境下的关联规则挖掘。 2 2 4 分层搜索经典算法一a pr i o r 算法 一般情况下，关联规则都可以分解为两个重点问题，一个是寻找频繁项目集； 另一个是利用频繁项目集产生所需的强关联规则。其中如何寻找到频繁项目集是 关联规则挖掘的核心问题。 a p r i 嘶算法是由a 莎a w a l 等人于1 9 9 3 年提出的，随后的很多算法都是根据 a 1 m o r i 算法而进行的改进或是扩展，因此，a p r i 谢算法是最为经典的关联规则 挖掘算法。a 研嘶算法是挖掘单维布尔型关联规则频繁项目集的有效算法。此 算法通过使用频繁项目集性质中的一些特性即先验知识( p r i o rk n o w l e d g e ) 来进 行挖掘，这也正是该算法名称的由来。 ( 1 ) 频繁项目集的产生 a p r i o r i 算法使用层次顺序搜索的循环方法( 又称做逐层搜索的迭代方法) 产生频繁项目集，即用频繁k 项集探索产生( k + 1 ) 项集。首先，找出长度为l 的频繁项集，记为l l ，l l 用于产生频繁2 项集的集合k ，而k 用于产生频繁3 项集的l 3 ，如此循环下去，直到不能找到新的频繁k 项集。找每个l k 需要扫描 数据库一次。 ( 2 ) 产生关联规则 在从数据库中挖掘出所有的频繁项目集后，就可以较为容易的获得相应的关 联规则了。也就是要产生满足最小支持度和最小置信度的强关联规则，可以利用 如下公式( 2 1 ) 来计算所获关联规则的置信度。这里的条件概率是利用项集的 支持频度来计算的。 彻叫耻州旧= 鼍蓑篙 ( 2 - 1 ) 其中，s u p p o n c o u n t ( aub ) 是包含项集a ub 的交易记录数目， s u p p o n - c o u n t ( a ) 是包含项集a 的交易记录数目。 天津师范大学硕士学位论文 ( 3 ) 性能分析 a p r i o f i 算法采用这样的启发式思想：频繁项目集的所有非空子集必须也是 频繁的；若一个项集是非频繁的，则其任何超集都是非频繁的。通过频繁模式连 接生成中的剪枝步大大减少了候选项集的产生，从而大大提高了频繁模式的挖 掘。然而，对于存在大量频繁模式、长模式或者最小支持度阈值较小的时候，这 类a 1 证嘶算法会面对以下问题： 算法将花费很多的开销来处理数目特别巨大的候选项集。 多次扫描事务数据库，需要很大的i o 负载。每生成一个新的候选项集， 就要进行数据库扫描，来确定其对应的支持度。因此，对于数据库中大量的候选 项集，需要不断地访问数据库，通过模式匹配来计算项集的支持度，需要大量的 i o 开销【16 】【m 。 2 3 启发式搜索_ a 算法 在实际生活中，一些寻求路径的问题难以求解，通常造成这些问题的原因包 括很多情况，如在搜索空间中所产生的可能解的数目过多，导致不能通过穷举搜 索法找到相关问题的最优解；问题对应的可能解的评价函数是会不断变化的，引 起解不唯一，甚至是一个解集，一系列的解难以选择；当然还有一些特殊情况， 若对于特定的问题，会设置一些约束限制，导致在构造解的过程中就遇到困难， 根本不能得到最优解；同时，在求解的过程中，还会有这样那样的人为原因或是 客观不可变的限制和影响等等很多因素，都会对找到最优解造成一定程度的影 响。 根据上述列举的这些原因，虽然不够全面，有的地方有些片面，不能反映出 大家在路径搜索问题中的全部，不过，总体上来说，解释了绝大多数问题在解决 过程中遇到的困难。通过问题的分析与研究，要想找到最优的解，而且在求解的 过程中更加的有效率，一定要利用具体问题领域的有关信息，这样才能简化搜索。 2 3 1 启发式搜索 在搜索过程中，一般情况下，都是通过使用搜索方法去找到一个满足要求的 解，那么所选择的方法就显得尤为重要。具体的来说，盲目搜索方法都要消耗很 多的时间或者空间，主要的原因可能是由于要扩展的节点数目大，或是节点扩展 的次序是完全随意的，没有顺序；或者是对于要解决的问题的特性或一些比较有 1 2 天津师范大学硕士学位论文 用的信息没有赋权值加以利用，都可能造成很多麻烦。 而启发式搜索的思想是在搜索过程中加入与其问题相关的启发性信息，进行 估价来指导相应的搜索沿着最有效果、有希望的方向前进，以此加快问题的求解 过程并且找到最优解。这种搜索针对性较强，因此在原则上只需要搜索到问题的 部分状态空间就可以解决问题了，效率较高【1 9 1 。 上面提到的启发中的估价就是用估价函数表示的，如公式( 2 2 ) 所示： f 【n ) = 颤n ) + h ( n ) ( 2 2 ) 其中，f 【n ) 为节点n 的估价函数，g ( n ) 为现实状态空间中从初始点到n 节点 的实际代价值，h ( n ) 是从n 到目标节点的最佳路径的估计代价值。h ( n ) 在这里体 现出搜索的启发信息，因为g ( n ) 其实是已知的条件。值得注意的是，当h ( n ) g ( n ) 时，可以省略甙n ) ，从而提高效率。 所以，启发式搜索与盲目搜索是有很大区别的，其在原则上只需要知道求解 问题状态空间的一部分就能求解该问题，搜索效率特别高。通过对启发信息加以 利用，来决定哪个节点是下一步进行要扩展的，这种搜索方法总是选择最有希望 的节点作为被扩展的下一个节点，所以把这种搜索方法也称之为有序搜索。a 幸 算法就是启发式搜索中应用及其广泛的一个，许多研究者采用该算法进行路径规 划，已经有了很深入的探讨与研究【2 0 】【2 n 。 2 3 2 ”算法 其实，启发式搜索有很多种算法，比如：局部择优搜索算法、最好优先搜索 算法等等。当然a 宰也是其中之一。这些算法在使用过程中都用到了启发函数， 但不同算法，在具体的选取最优搜索节点时候的策略也不尽相同。 ( 1 ) 局部择优搜索算法，其搜索过程就是在选取“最佳节点后便舍弃其 他兄弟节点，等于父节点则一直搜索到最后。这样的搜索结果很明显，由于最初 就舍弃了其他子节点，很可能也把最好的节点在最开始就舍弃了，因为求到的最 佳节点只是在最开始那个阶段是最佳，但并不能保证它是全局的最佳。 ( 2 ) 最好优先算法，与局部择优搜索算法相比，在选择节点方面就改进了 很多，其在搜索过程时，没有舍弃任何一个节点( 除非该节点是死节点) ，在每 步进行的估价中都把当前的节点和以前未选的节点的估价值进行进一步比较，这 时选取一个“最佳的节点”。这样就能够有效防止“最佳节点”在最初阶段的丢失。 其实，理论上讲a 木算法也是最好优先算法的一种。只不过在其基础上加了 天津师范大学硕士学位论文 一些约束条件。因为在一些问题求解时，希望可以搜索出在状态空问中的最短路 径，也就是能用最快的方法求解出问题的解，a 宰就是通过改进估价函数完成了 这样一个工作。a 算法的估价函数可表示为公式( 2 3 ) ： f ( n ) = g ( n ) + h ( n ) ( 2 3 ) 其中，p ( n ) 为估价函数，g ( n ) 为起始点到终结点的最短路径值，”( n ) 是n 节 点到目标点的最短路径的估价值。由于f ( n ) 其实是无法预知的，一般都是用前面 的估价函数删做近似代替，还有在大部分情况下g ( n ) 也是代替g ( n ) ，不过只有 当h ( n ：l 通行状况( 2 ) 主干( 1 ) a n d 单向导通( 2 ) a n d 限速( 1 ) = 通行状况( 2 ) 主干( 1 ) a n d 单向导通( 1 ) a n d 限速( 1 ) = 通行状况( 2 ) 经过约筒后得到的核集为注于、禁行路、单向导通、限速 。 423 聚类分析 根据相糙集的属性约简结果，对于起始点与结束点的聚类应泼分两步进行。 首先是根据起始点及日标点的经纬度距离聚类出在其范围3 0 0 米内的所有u r 通 行的道路段，然后再根据道路属性约简的结果得出的权值选取出更加合适的路 天津师范大学硕士学位论文 径。 假设之前实验的数据即为目标地点通过经纬度的计算距离函数d 所求得的 有效数据，在此基础上，通过分析核集，为了更好的对权值进行区分，参照了二 元变量的推广分类变量，来对对象之间的权值进行简单计算： d ( f ) = 尘塑( 4 - 1 ) p 这里m = q + 什s + t ，是对应的属性值之和，即用于衡量道路属性的状况：q ，r ， s ，t 分别代表主干、禁行路、单向导通、限速四个属性值；p 是全部变量的数目； 而旯是针对m 的影响而赋于的权重值，可取( o ，1 】区间的任意数值。下面分别对名 的取值进行讨论。当a 分别取0 1 、o 5 、1 时，通过公式可以得到属性d 的计算 结果，( 如图4 1 9 所示) 。 abcdefgh l道路主干 禁行路 单向导通限速 五= 0 1 时d 一五= 0 5 时d ：五j l 时d 2r 111210 8 7 50 3 7 50 2 5 3r 2012 ：20 8 7 5 ：0 3 7 50 2 5 4r 30011o 9 5 ：0 7 50 5 5r 400220 9 ：0 50 6r 511 1 ： 30 8 50 2 50 5 7r 601220 8 7 50 3 7 50 2 5 8r 7 1 11 10 9 。0 50 9r 811239 8 2 5 ：0 1 2 5_ 0 7 5 1 0r 9112 ：10 8 7 50 3 7 5- 0 2 5 1 1r 1 001220 8 7 50 3 7 50 2 5 图4 1 9 不同名取值的权重值d 通过计算公式，当五取不同的数值时，可以得到对应的属性权值d ，不论正 负都能衡量道路的属性，当d 越小时，说明道路的通行状况更好；反之说明道路 的通行状况一般。本实验取力= 0 5 时的属性值，将其附加在聚类结果之上，即对 聚类结果选取出的道路增加通过公式( 4 1 ) 计算得到的属性权值d ，来对道路进 行最终的选择。 通过上面得到的结果，下面进行具体分析。当从a 地出发，途中分别可以 经过c ，d ，e ，f ，g 等很多道路到达b 地( 如图4 2 0 所示) 。经过聚类，得 到下面标注的1 0 条道路，每条道路加起来的总路径和都不超过5 0 0 米，也就是 说都是通过距离聚类得到的结果，或者说是候选最优路径。 同时，在每条道路上也标注了属性权值d ，经过对道路属性权值d 求和，可 以对道路进行排序，即d ( g ) = 0 5 ；d ( c ) = 0 7 5 ；d ( d ) = o 7 5 ；d ( e ) ；o 8 7 5 ；d ( f ) = 1 1 2 5 。 4 s 天津师范大学硕士学位论文 这样就可以发现，通过对道路属性权值d 的和排序，就能够较清晰地推出在目前 状况下，通行路况最好的道路是g ，即使g 的路径比其他道路的距离要远些。 但是由于这5 条道路已经通过距离聚类，那么就说明它们之间的总路径距离相差 不远，在这个基础之上，又利用属性权值d 对其进行追加分析，从而更快更方便 地得到路况最好的道路，即最优路径。 图4 2 0a 地出发到b 地的地形图 因此，在一定距离范围内的通行道路中，可以将属性权值d 进行求