1006大班设计翻译最终版-6班以学号姓名

BessonJ,RobardetC,BoulicautJF.Constraint-basedminingofformalconceptsintransactionaldata[M]//AdvancesinKnowledgeDiscoveryandDataMining.SpringerBerlinHeidelberg,2004:615-624.IanH.Witten,EibeFrank.数据挖掘实用机器学习技术[M].:机械工业,2006GESTSInternationalTransactionsonComputerScienceandEngineering,2006,32(1):71-82.ofthe16thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2010:919-928.计算机学院（系） 毕业设计（）时间：2014年3月3日至2014年6月3答辩时间：2014年6月11日 指导教师 季书教师或答疑教师（并所负责部分系（教研室 （签字 生：李栋指导教师：季书试图分析出城市的拥堵区域，从而节约人力和资源，更加集中效率的治理D-miner算法挖掘频繁闭1-矩形的能力，挖掘出来频繁拥堵区域。但是挖掘出来的拥堵区域很多，需要提供一个量化指标来比较这些拥堵区域。紧接着创新地提出了度的概念，将数据点被挖掘出来的拥堵区域覆盖的次数作为其度。利用核心度可以量化的评比拥堵的区域与拥堵的瓶颈路段。在一块拥堵区域中可以继续划分出拥堵区域，从而实现了“类中类”的效果。：数据挖掘，模式挖掘，城市拥堵，绪 研究背 国内外研究现 智慧城市与智慧交 频繁模式挖 目前研究的不 本文的研究内容和主要创新 课题来 组织结 相关技术概 数据挖 关联规 聚 分 模式挖 数据预处 D-miner算法概 D-miner算法实 挖掘拥堵区 度与拥堵区 4.1 拥堵区 实验对 总结与展 总结及主要贡 绪不仅仅是的问题。世界各大城市都饱受堵车之苦。莫斯科的最为不幸，他们平着力建设无缝整合的交通枢纽，仅700多平方公里的上居住着500多万人，而这样虽然，对于拥堵的也取得了一定的成果，但是大多只停留于标注出拥堵路段。对于拥堵模式并没有进行进一步研究。出于建立智慧城市和优化城市状况的角势。现今，已经通过市的出租车到一定的交通数据。因此我着眼于将数据“智慧城市”(SmartCity)出现以来，国内外的学者、科研机构、企业团体纷纷似的概念还有数字城市等。2008年11月，恰逢2007年－2012年金融伊始，对智慧城市的归纳定义主要集中于三点：第一，智慧城市建设必然以应用为主线。智慧城市可以被认为是城市信息化的高级阶段，必然涉及到的创新应在IBM的《智慧的城市》白皮书中，基于科技的发展，对智慧城市的定义即智能传感设备将城市公共设施物联成网，物联网与互联网系统完全对接融合，、智慧城市定义为新一代支撑、知识社会下一代创新（创新2.0）环境下的城市征的可持续创新，塑造城市公共价值并为其中的每一位市民创造独特价 智慧城市将成为一个城市的整体发展，将作为经济、产业升级、城市提升智能交通系统(InligentTransportationSystemITS)是未来交通系统的发展方安全、提高效率，因而，日益受到各国的重视。智能交通：智能交通是一个基于现代电子面向交通的服务系统。它的频繁模式（frequentpattern）是频繁地出现在数据集的众多模式（如项集、子序列和深入，又提出了闭频繁项集和极大频繁项集的概念。如果不存在真超项集Y使得Y与XDXD中是闭的（closedX在DX是数据集D（closedfrequentitemset。如X是频繁的，并且不存在超项集Y使得𝑋⊂𝑌YD中是频繁的。[4]有效率和更加全面的管理，比如此文利用数据挖掘来研究城市堵车问题。在不断的提高。但是挖掘的结果并不太是满意。这个的首要问题是频繁模式过于杂多，数量过于庞大且有些并不是所感的。针对这个问题，紧接着提出了频繁闭城市交通问题的根源是交通需求与供给之间的不平衡。实践证路的发展远远路、消除瓶颈、人工疏堵等方法。然而要实现这些方法的首要目标是找到拥堵的区域。完善整个道路网络体系的成本非常高，而完善拥堵区域道路网络体系的成本却没那么高。知道了拥堵的区域后，对这些重点地区进行完善是可行的。加宽整消除瓶颈的主要问题是找到瓶颈，当然瓶颈就是拥堵区域。人工是有限的，面对着庞大的交通网络，有限的必须在最有效率的地方人工疏堵。自然，最有效率的地方就是拥堵区域。所以，不难理解这篇文章的目的就是研究一种定义度和挖掘出拥堵区域的方法。结合出租车GPS数据，借鉴D-miner算法挖掘出城市地点和时间的拥堵模式定义拥堵后面挖掘拥堵区域和瓶颈路段做准备。结合度挖掘出拥堵区首先，定义了一个关于“度”的全新概念。其次，提出了一整套全新的行了实验对比，证明了度的优势和其应用意义。本文的主要内容是提出一套全新的挖掘拥堵区域方法。可以利用这套方法之后，本文提出了重要的定义——度的概念，接着解释了度的合理性。然后本文利用度的概念来对拥堵区域进行量化，从而形成了拥堵区域。最后，本文进行了实验对比，展示度在应用的意义。第一章绪论最后展示了课题来源和组织结构。本章还概述了Weka这个工具。在本章首先介绍了数据预处理过程。然后介绍了D-miner算法的概要。最后展示了如何借鉴D-miner算法挖掘拥堵区域。第四章度与拥堵区度来量化拥堵区域，从而挖掘出拥堵区域。第六章总结和展望相关技术界、和研究界，“数据挖掘”通常用来表示整个知识发现过程。因此，采用广义数据集中标记的实例例如，在识别的问题中，一组手写图像learning如，一个无监督学习方法可以取一个手写数字的图像集合作为输入。假设它找100~910个不同的数字。然而，由不能告诉发现的簇的语义。标记的实例进一步改进类边界。对于两类问题，可以把属于一个类的实例Apriori算法，这个算法为布尔关联规则挖掘频繁项集的性算法[5]。Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用（强关联规则满足最小支持度和最小置信度AprioriApriori算法的变形来提高效率。包括Growthtree数据库。对于每个“模式片段”，只需要与它相关联数据集。因此，随着被很低时更是如此。所以，随着研究的深入，又提出了闭频繁项集和极大频繁项集的YYXDXD中是闭的（closedXDXD中的闭频繁项集（closedfrequentitemsetXY使得𝑋⊂𝑌YD上面的都是挖掘频繁模式。然而，有时令人感的不是频繁模式，而是聚类分析（clusterysis）简称聚类，是一个把数据对象（或观测）划分成子集的（cluster不同的聚类方法可能会产生不同的聚类。通过聚类，可能会发现数据内事先未知的nk个分区，每K-means[8]K-meds[9]算法。K-means算法通被凝聚在一起。的方法刚开始把所有的簇放在一起，然后把这个簇分为更基于网格的方法：上面的算法的复杂度都是基于对象点的数量的，当对象点很多时，算法的效率很糟糕。而基于网格的方法则首先把对象空间分割成有限个网格结构。把每一个网格结构的对象点进行统计，以这个网格来代表所有网格内的对象点。之后的聚类过程都是基于网格结构的。这使得算法的效率大据进行分类。EnvironmentforKnowledgeysis。它是一个集合了一些前沿机器学习算法Weka的使用方式之一是将一种学习方法应用于一个数据集，然后分析其输出，从而的了解这些数据。另外式则是使用已学习到的模型对新的实例做出Weka平台最有价值的部分是真实学习方案的实现。其次当属数据预处理工具，不适用。但是使用知识流界面可以使用部分用来处理大型的数据集的递增算法。Weka的第三个界面是实验者(Experimenter)视图。这个视图专门来帮助用户解答使模式息、纬度信息、速度信息、方向信息、甚至包含是否有乘客的信息（3.1一般的出租车GPS数据大多数以前的研究大多关注信息，甚至有些还关注是否有乘客的信息。以前的研究方向，但是随着研究的深入，研究发现在大多应用情况下，这个假设并息的精确度没有太大要求，这意味着不用太在意GPS经纬位置误差对结果造成的3.2出租车的位置分布与实际拥堵区域（此图自[13]实际拥堵区域的密度情况通过颜色深度来表示，红色小点表示正在载客的出租车位置，黑色小点表示未载客的出租车位置。可以清晰的看见大多数出租车3.2由于数据所限，研究目标限于市的二环路区域。因为提供的是一整地区。因此，本文的关注点暂定于市二环路区域。况且的二环路也非常典收集了多天的二环路的出租车行驶速度情况。这些数据精确到每200米一个监测点，每一个，并且这些速度数据是当时经过那个检测点的所有出租车的平3.3二环某天的出租车速度数据，每一行表示一个监测点24小时的检测数据，在二环总共有314个监测点，所以数据有314行，每一列表示在同一时间的不同路段的速度情况，5分钟一个数据，所24小时对应288个数据，即有288列。首先，对于这份数据，发现当时间位于0点至6点时，很多数据是缺少状态（-大。所以，第一部分0点至6点的数据剔除，主要研究6点至24点的数据。其624点的数据其中也有很少一部分数据是缺失的，对于这些缺失数据，经过以上步骤，基本噪声数据和缺失数据都已经被处理完毕。下面针对后面的算法操作来对数据进行格式的改造。在下一节会具体讲到使用到的D-们其实并不关心那些出租车是多大的速度，更加关心的是它处在一个什么状态，是平均速度是42km/h。因此设定拥堵的阈值为平均速度的一半，即21km/h。也就是说，对数据进行转换，将大于21的值设为0（畅通状态将小于21的值设为130公里/30公里/203.4D-minerD-miner算法是J´er´emyBessonC´elineRobardet,Jean-Fran以及coisBoulicaut在《Constraint-BasedMiningofFormalConceptsinTransactionalData》中算法[15]。D-miner算法是用来布尔型处理事务数据的。何谓事务数据呢？这种数据来源于购次事务也就包括了的东西。物品在这次购物中被就在该物品下记1，否则记0。多个事务就组成了事务数据。见表格3.1一个简单的事务数据01的布表格3.1…101001001111111APRIORI算法已经在过去十年被设计出来来都不小时，这些算法不适用了。而D-miner在数据密集时候的效果反而更加好。D-miner算法是在这样的事务数据中来基于一定的约束挖掘频繁闭合模式。何谓频模式过于繁多，以至于不能够很好的利用。所以后面研究发展了频繁闭和模式(frequentclosedpattern)M,M的超项集，但样看表格3.1事务中出现的最小次数的限制，记为𝐶𝑡。另一是最小项集长度的约束，也就是模式品的种类的最小限制，记为𝐶𝑔rectange’(t,’表格多个频繁闭合模式。他们其中的两个是({t1,t2,t3,t5},g1,g3})({t2,t3},g1,g2,g3,g4,g9,g10})。表格3.2D-minerD-miner算法是的第一步是计算出切割集。用H来表示一个0-矩形，即矩阵中（0，H必须尽可能的小来减少递归的深度和执行的时间。另一方面，不应该花太多时间D-miner算法对于一个布尔矩形，它从整个矩形开始，通H中的切割点，递归地H1-H中的元素(a,b)可以用来切割矩形（X，Y）当且仅当𝑎∩𝑋≠∅且𝑏∩𝑌≠∅。为了方便，定义（X,Y）的左切割后为（X\a，Y，右切割后为（X,Y\b。但是发现有时候切割得到的1-矩形3.5右切割得到的（t3,g3）和(t2t3,g3)并不是闭合的，因为（t1t2t3,g3为了避免有这种不闭合的模式产生，在切割的过程中还要及早剪枝。为了这种时在（从Y中移除某些元素，须检查∀(𝑎,𝑏)∈𝐻𝐿(𝑋,𝑌),𝑏∩𝑌≠∅。算法伪代1：D-miner函输入：nmr，行集O和列P，最小支持度的约束𝐶𝑡和最小项集长度输出：满足约束𝐶𝑡和𝐶𝑔的频繁闭合模式集合HL←Q←cutting((O,P),H,0,Hsize,HL);算法伪代2:cutting输入：矩阵（XY，切割集H，迭代次数i，H的大小Hsize，左切割点集合,𝐻𝐿最小输出：满足约束𝐶𝑡和𝐶𝑔的频繁闭合模式集Qa,b)←H[i]If(i≤Hsize−If((a∩X=∅)or(b∩Y=∪cutting((X,Y),H,i+If(𝐶𝑡(X\a)HL←HL∪(a,∪cutting((X\a,Y),H,i+1,Hsize,HL)HL←HL\(a,b)If(𝐶𝑔(Y\b)∧∀(a’,b’)∈HL,b’∩Y\b≠

Q←(X,Y

∪cutting((X,Y\b),H,i+1,Hsize,Return挖掘的是事务数据，但是出租车数据并不是事务数据。但是可以互相借鉴。事务的数据的一行表示1次交易，此行中的1表示在该次交易中该列的物品被，此表示小支持度（min_sup）的约束，也就是模式同时在事务中出现的最小次数的限制。表示最小项集长度的约束，也就是模式品的种类的最小限制。在出租车数据中[18]所以对区域的二维也都有最小限制。𝐶𝑡表示最小同时拥堵路段数量限制，也就是同堵车的路段数必须大于𝐶𝑡。𝐶𝑔24个小时拥操作做铺垫。以一个监测地点的24小时数据为行，以同一时刻不同地点的数据列。同样是二维矩阵，要挖掘出频繁闭合的1-矩形。设置𝐶𝑡=22，𝐶𝑔=12，钟22和12的结果如图3.6，每一行代表一个1-矩形，冒号前面的为行号，冒号后面的为列号。 度与拥堵区 虽然挖掘了很多拥堵区域，但是当拥堵区域很多时，无法比较这些拥堵区勤的有限，必须把部署在最拥堵的区域或者说那些瓶颈区域去人工疏堵。需要一个量化指标来比较拥堵区域的拥堵程度。所以，提出一个度的概念。观察上一节挖掘出来的拥堵区域，发现挖掘出来的很多拥堵区域都存在一部分的覆盖情况。发现覆盖的区域基本是拥堵的中心区域，所以考虑能否用一个量图4.1，从一个4乘4的矩形（图4.1左）挖掘大于2乘2的频繁闭合模式，可以看到有一个点均被3个模式所覆盖。把每个点被频繁模式覆盖的次数显示出来，如图4.1（右）中显示，可以看出这个数值大的点也是所以这个数据集所有1的中心点。所以依据此提出了度的定义。图4.1度的提最大的点就为所有模式的点。也就是说，如果一个点在多个模式中都出现，那么它的度就高。反之，则低。同时也可以发现这个点能在多个模式中出现，其必然是在1的中心的位置。拥堵区度的提出使得获得了一种评价拥堵区域的指标。可以利用度来得到拥堵区域。对于拥堵的情况，有时更加关心拥堵的瓶颈路段。何谓瓶颈路段4.21114.3117号堵车状态图，都多次出现倒三4.21114.3117一点为瓶颈路段附近路段，比较低的为由于瓶颈路段拥堵而后续拥堵的路段。如图4.4，对于第一行的瓶颈路段，度会高一些，而后面由于瓶颈路段拥堵而后续拥堵的路段的度并不高。图4.4瓶颈路段的所以，度可以精确的表示拥堵的区域和瓶颈路段。可以按照度为红色的点是度最高的点，黄色的点度次高，浅蓝色的点度最低。但是由于度从60万到1差距过大，很多点的颜色太浅不能显著的显示出来，所以又画了图4.6将度大于3000的点均用红色表示，从而使得度较小的点也能够被直观的观察出来。从图中，可以鲜明的看到拥堵的区域度都非常高，那些瓶颈路段的度也很高。结合图4.5和图4.6对比的看，可以发现度在不同路段的差距性显著，这使得可以选择那些区域去更有效率的进行疏堵工作。图4.5拥堵点的图4.6拥堵点的度（度大于3000的点均用红色表示实验在这一章节，作对比试验来体现度的意义，更加形象的展示度的优有的处理方法应用于新的数据集。Weka还提供了一定的可视化界面，使得可以更首先，使用经典的K-means方法来对未计算度的数据和计算度的数分别使用K-means方法来对未计算度的数据和计算度的数据分别进行K105.1K-means算法，数据聚类效果并不是跟好，不能很好的分别出拥堵区域。图5.2显示了对利用加了度的数据进行聚类续划分出拥堵区域，从而实现了“类中类”的效果。图 图5.2对计算度过后数据使用K-means算看图5.3原始数据与聚类和结果对比，可以看出用本文一整套流程可以准确5.3总结与处理。优先选择速度属性用基于移动性的方法代替了传统的根据位置基于密度的方法。之后对数据进行了平滑处理和噪声数据去除，最后根据后面的操作将数值性的然后实现了D-miner算法，并利用D-miner算法挖掘频繁闭合1-矩形的能力，了度的概念，将数据点被挖掘出来的拥堵区域覆盖的次数作为其度。利用度可以量化的评比拥堵的区域与拥堵的瓶颈路段。块拥堵区域中可以继续划分出拥堵区域，从而实现了“类中类”的效果。主要贡献：定义了一个关于“度”的全新概念。用它可以量化的评比拥堵的区域与拥堵的瓶颈路段。其次，提出了一整套全新的挖掘拥堵区域方法miner算法时，需要设定两个约束𝐶𝑡和𝐶𝑔的阈值。𝐶𝑡表示最小同时拥堵路段数量制，也就是同时堵车的路段数必须大于𝐶𝑡。𝐶𝑔表示路段最小拥堵时间限制，也就是该24个小时拥堵的时间必须大于𝐶𝑔0致所能呈现。但是感谢之情却可以借此略微表达。首先感谢导师——季书帆老师。季老师不仅是我学习中的导师，而且也是我生并不，人生的得失远比想的复杂又简单。作一个有意义的人比作一个规则的接下来感谢父母。他们给了我生命，塑造了我这个人。他们是后背。他们感谢大学同学、吴煜、、姚铭、贾伟等，他们使得大学生活在最后感谢，感谢我是个健全的人，感谢我接受了良好的教育。感谢我可以参考[1]网易旅游综合. 全球最拥堵城市[OL]. [2]百科.智慧城市[OL]. [3]百科.智慧交通[OL]. JiaweiHan,MichelineKamber,JianPei.数据挖掘概念与技术[M].：机械工业AgrawalR,SrikantR.Fastalgorithmsforminingassociationrules[C]//Proc.20thint.conf.verylargedatabases,VLDB.1994,1215:487-499.KotsiantisS,KanellopoulosD.Associationrulesmining:Arecentoverview[J].GESTSInternationalTransactionsonComputerScienceandEngineering,2006,32(1):71-82.BerkhinP.Asurveyofclusteringdataminingtechniques[M]//Groumultidimensionaldata.SpringerBerlinHeidelberg,2006:25-71.HartiganJA,WongMA.AlgorithmAS136:Ak-meansclusteringalgorithm[J].Appliedstatistics,1979:100-108.ParkHS,JunCH.AsimpleandfastalgorithmforK-medsclustering[J].ExpertSystemswithApplications,2009,36(2):3336-3341.陈燕.数据挖掘技术与