位置大数据的价值提取与协同挖掘方法

软件学报ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],2014,25(4):713−730[doi:10.13328/j.cnki.jos.004570]©中国科学院软件研究所版权所有.Tel/Fax:[phone]位置大数据的价值提取与协同挖掘方法∗郭迟1,刘经南1,方媛1,罗梦2,崔竞松2,31(武汉大学卫星定位导航技术研究中心,湖北武汉430079)2(武汉大学计算机学院,湖北武汉430072)3(软件工程国家重点实验室(武汉大学计算机学院),湖北武汉430072)通讯作者:郭迟,崔竞松,E-mail:{guochi,jscui}@whu.edu.cn摘要:随着位置服务和车联网应用的不断普及,由地理数据、车辆轨迹和应用记录等所构成的位置大数据已成为当前用来感知人类社群活动规律、分析地理国情和构建智慧城市的重要战略性资源,是大数据科学研究极其重要的一部分.与传统小样统计不同,大规模位置数据存在明显的混杂性、复杂性和稀疏性,需要对其进行价值提取和协同挖掘,才能获得更为准确的移动行为模式和区域局部特征,从而还原和生成满足关联应用分析的整体数据模型.因此,着重从以下3个方面系统综述了针对位置大数据的分析方法,包括:(1)针对数据混杂性,如何先从局部提取出移动对象的二阶行为模式和区域交通动力学特征;(2)针对数据复杂性,如何从时间和空间尺度上分别对位置复杂网络进行降维分析,从而建立有关社群整体移动性的学习和推测方法;(3)针对数据的稀疏性,如何通过协同过滤、概率图分析等方法构建位置大数据全局模型.最后,从软件工程角度提出了位置大数据分析的整体框架.在这一框架下,位置数据将不仅被用来进行交通问题的分析,还能够提升人们对更为广泛的人类社会经济活动和自然环境的认识,从而体现位置大数据的真正价值.关键词:大数据;轨迹移动模式;位置服务;泛在测绘;数据挖掘中图法分类号:TP311文献标识码:A中文引用格式:郭迟,刘经南,方媛,罗梦,崔竞松.位置大数据的价值提取与协同挖掘方法.软件学报,2014,25(4):713−730.英文引用格式:GuoC,LiuJN,FangY,LuoM,CuiJS.Valueextractionandcollaborativeminingmethodsforlocationbigdata.RuanJianXueBao/JournalofSoftware,2014,25(4):713−730(inChinese).(GlobalNavigationSatelliteSystemResearchCenter,WuhanUniversity,Wuhan430079,China)2(ComputerSchool,WuhanUniversity,Wuhan430072,China)3(StateKeyLaboratoryofSoftwareEngineering(ComputerSchool,WuhanUniversity),Wuhan430072,China)Correspondingauthor:GUOChi,CUIJing-Song,E-mail:{guochi,jscui}@whu.edu.cnAbstract:Uncountablegeographicallocationinformation,vehicletrajectoriesandusers’applicationlocationrecordshavebeenrecordedfromdifferentlocation-basedservice(LBS)applications.Theserecordsareformingtoalocationbigdataresourcewhichfacilitatesmininghumanmigratingpatterns,analyzinggeographicconditionsandbuildingsmartcities.Comparingwithtraditionaldatamining,locationbigdatahasitsowncharacteristics,includingthevarietyofresources,thecomplexityofdataandthesparsityinitsdataspace.Torestoreandrecreatedataanalysisnetworkmodelfromlocationbigdata,thisstudyappliesdatavalueextractionandcooperativeminingonlocationbigdatatocreatetrajectoriesbehaviorpatternandlocalgeographicalfeature.Inthispaper,threemajoraspectsof∗基金项目:国家自然科学基金(41104010);国家高技术研究发展计划(863)(2013AA12A206,2013AA12A204);国家自然科学重大研究计划(9112002);高等学校学科创新引智计划(B07037)收稿时间:2013-10-14;修改时间:2013-12-18;定稿时间:2014-01-27714JournalofSoftware软件学报Vol.25,No.4,April2014analysismethodsonlocationbigdataaresystematicallyexplainedfollows:(1)Forthevarietyofresources,howtoextractpotentialcontents,generatebehaviorpatternsanddiscovertransferringfeaturesofmovingobjectsinapartialregion;(2)Forcomplexityofdata,howtoconductdimensionreductionanalysisoncomplexlocationnetworksintemporalandspatialscale,andthustoconstructlearningandinferentialmethodsformobilitybehaviorofindividualsincommunities;(3)Forsparsity,howtoconstructtheglobalmodeloflocationbigdatabyusingcollaborativefilteringandprobabilisticgraphicalmodel.Finally,anintegralframeworkisprovidedtoanalyzelocationbigdatausingsoftwareengineeringapproach.Underthisframework,locationdataisusednotonlyforanalyzingtrafficproblems,butalsoforpromotingcognitiononamuchwider-rangeofhumansocialeconomicactivitiesandmasteringabetterknowledgeofnature.Thisstudyincarnatesthepracticalvalueoflocationbigdata.Keywords:bigdata;trajectoriesmobilitypattern;locationbasedservice;ubiquitousmapping;datamining位置服务(locationbasedservice,简称LBS)是近年来新兴的移动计算服务.发展位置服务主要需重视其两个方面的能力:提供位置的能力和理解位置的能力.在提供位置方面,随着室内外无缝定位技术和增强系统技术的发展,定位精度不断提高[1],在大众应用层面已经基本满足人们生产、生活的需要;然而在理解位置的能力方面,目前尚有很多挑战,是学术界和产业界关注的热点.理解位置其实就是理解位置背后所反映出来的人的活动、人的情感和人的环境,因此也被称为泛在测绘(ubiquitousmapping)或位置社会感知(location-basedsocialawareness)[2].位置大数据(locationbigdata)是构成泛在测绘和位置社会感知的重要资源,具有相当大的体量.近几年,位置服务、数据挖掘和机器学习领域,已经涌现出一批针对位置大数据的优秀研究.其所使用的数据集在体量和复杂性上均已达到了“大”数据的层次,代表性实例见表1.Table1Instancesoflocationbigdata表1位置大数据实例移动目标目标数量|O|持续时间|T|(天)记录数量|P|研究目的出租车12000110577000000寻找乘客和空闲出租车[3];推断交通异常[4]74753853000000000土地规划分类[5]移动电话500009010000000研究人们移动行为的可预测性[6]1500000450/研究人们移动行为的独一性[7]1600000365/模拟灾后人们大规模移动行为[8]社交网站6326113015944084模拟疾病传播[9]位置大数据主要来源于车联网(Internetofvehicles,简称IOV)、移动社交网络、微博等新兴互联网应用,更新速度快且具有很大的混杂性(inaccurate).同时,往往受到数据采集技术等方面的客观制约,使得这些数据不能全面和正确地反映观察对象的整体全貌,因而具有“复杂但稀疏(complexyetsparse)”的特点.如何从位置大数据中获得价值,进而发现人类社群活动规律,是非常值得探讨的问题.本文将着重归纳和阐述这其中有关局部特征提取、数据降维、整体特征建模以及整体数据协同挖掘的方法.本文的另一个贡献是从关联应用角度阐述了位置大数据的意义和价值.传统的诸如轨迹数据等往往仅被用以分析城市交通等直接且特定的问题.大量经典的大数据科学研究表明,通过价值提取和协同挖掘后的数据结果能够将一些看似无关的事件很好地联系在一起,从而从数据层面“直接”反映一些原本需要复杂因果建模才能得到的结果,且更加直观和准确[10−13].这些案例对位置大数据研究同样具有启发性.因此,我们在探讨位置大数据分析方法时,本身就应将其置于关联应用的大背景下,着重探讨如何将模型参与到社会经济活动、政治活动、自然环境、人类情感以及人口卫生等一系列社会学、人类学、经济学的研究中.这样的位置大数据才更有助于地理国情的分析和智慧城市的建设.1基本定义和预处理方法首先,我们给出本文所面对的位置大数据的基本结构.前文已述,当前的位置大数据主要来源于IOV、移动社交网络新兴互联网应用,有如下描述:郭迟等:位置大数据的价值提取与协同挖掘方法715定义1.位置数据集记为LBD={O,T,P},其中,O={o1,o2,…}表示数据集中的移动对象集合,包括了|O|个产生位置的移动目标;T为观察数据集的时间;|T|天内总共获得|P|个位置记录.定义2.单个位置数据记录p主要包含移动目标o和位置的地理坐标〈x,y〉和记录时刻t,可以用一个四元或五元组表示.如果是车辆轨迹数据,一般还包含车辆的速度v以及一组状态信息S=〈S1,S2,…〉