一种基于加权欧氏距离的移动轨迹相似度匹配方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106339716A(43)申请公布日2017.01.18(21)申请号201610677693.7(22)申请日2016.08.16(71)申请人浙江工业大学地址310014浙江省杭州市下城区潮王路18号(72)发明人王卫红杨洁陈小柱(74)专利代理机构杭州天正专利事务所有限公司33201代理人王兵黄美娟(51)Int.Cl.G06K9/62(2006.01)权利要求书2页说明书4页附图3页(54)发明名称一种基于加权欧氏距离的移动轨迹相似度匹配方法(57)摘要一种改进的基于欧式距离的相似度匹配方法，方法包括：获取移动数据，保留包括IMSI、StartTime、LocLng以及LocLat等移动信息；根据IMSI查询得到若干个移动数据，即轨迹点，以采集时的即时时间排序获取原始轨迹；将特定的时间段分为若干个时间区间，轨迹点放置到相应的时间区间内，根据轨迹点停留时间给予权重，加权计算时间区间特征点位置；根据筛选条件不同，赋予相应时间区间以较高权值，进行加权欧式距离相似度计算；将计算得到的欧氏距离排序，取距离最小的5条轨迹，即为相似度最高的行为轨迹。CN106339716ACN106339716A权利要求书1/2页1.一种改进的基于欧式距离的相似度匹配方法，将所提取的轨迹点进行时间维度上的划分，每个时间段内的特征点进行特征提取，在考虑时间维度以及保留数据特征的情况下，降低相似度比较过程中的数据量；所述的方法包括：步骤1，获取移动数据；利用现有移动数据，每条数据均为主基站接收的信号数据，保留包括IMSI、StartTime、LocLng以及LocLat字段作为移动定位过程中的必要信息，其中，IMSI表示个体携带的移动设备的唯一标识符，StartTime为基站接收到移动信号的即时时间，LocLng以及LocLat为接收基站的经纬度，即基站的地理位置；步骤2，获取原始轨迹；根据IMSI查询，即可获得特定时间段内该IMSI对应移动设备的若干条移动数据，每条移动数据即为该移动设备移动轨迹的一个轨迹点，其中，轨迹点信息包括该点的位置坐标以及采样时间t；按照轨迹点的即时时间排序，即可构成个体的运动轨迹；步骤3，分时段特征点采样；以一定的时间区间为单位，将特定时间段划分为若干个时间区间，将采集得到的移动轨迹的轨迹点按照其即时时间，放入每个区间，这样每个时间区间内会有若干按时间排序的轨迹点；在单个时间区间内，通过这些轨迹点的位置坐标可得轨迹经过的位置点(Lngj,Latj)，即时时间差可得到个体在某位置点停留的时间Δtj，将位置停留时间作为计算特征点位置的权重条件，按照如下公式计算；注：wtj表示位置j在计算特征点时该轨迹点位置的权重，Δtj表示在位置j停留的时间，tTotal表示单个时间区间的总时间；由每个位置点的权重wtj，得到可以代表该个体在该时间区间的综合位置，如以下公式所示；注：rix以及riy表示在该时间区间i内特征点的总位置经纬度，该时间区间内的总轨迹点数为m，Lngj以及Latj在该时间区间内经过位置点j的经纬度；经过以上计算，即可得到特定时间段内轨迹的运动位置情况；步骤4，相似度计算；根据不同的筛选对象，给这些时间区间赋予不同的权值wpi，权值取值范围：1≤wpi≤2；例如，需要筛选家庭成员，则给予夜间时间区间以较高的权值；需要筛选一起工作学习的团体，则给予日间时间区间以较高的权值；选取某个IMSI，作为待匹配对象，得到轨迹R，与库中的各轨迹S进行加权的欧氏距离计算，如下公式所示；注：R,S分别为两条轨迹，两条轨迹的轨迹点数分别为n，E(R,S)为轨迹R与S间的欧式距离，ri,si分别表示轨迹R与S上第i个轨迹点，rix与riy表示ri的位置坐标，six与siy表示si的位2CN106339716A权利要求书2/2页置坐标，wpi为相应时间区间的权值，distance(ri,si)表示ri,si间的欧式距离；步骤5，给出相似度排序表；根据计算得到的欧氏距离，取出距离最小的5条轨迹，作为与之相似度最高的轨迹集。3CN106339716A说明书1/4页一种基于加权欧氏距离的移动轨迹相似度匹配方法技术领域[0001]本发明涉及移动数据分析领域，尤其是针对移动大数据平台下基于移动轨迹数据的相似度匹配方法。背景技术[0002]近年来，随着移动通信技术以及传感器技术的发展，移动设备的持有率不断攀升。由附近基站接收到的移动数据可大致标定移动设备的位置以及即时时间。进而，通过查询移动设备的唯一标示符，得到其某段时间内的轨迹数据。[0003]由于人类移动轨迹显示出高度的时间以及空间规律性，在大多数情况下，个体会在生活原点附近徘徊，大幅度偏离仅为小概率事件。因其规律性，使得