本发明涉及利用移动终端的位置数据准确定位IP地址地理位置的方法，属于计算机系统技术领域，该方法包括：收集用户使用移动终端的位置数据，组成地理位置数据集，去除可靠性低的数据：筛选出该用户晚上、白天的移动终端地理位置数据全部记录，进行聚类，得到的若干聚合的重心作为该用户对应的第一、第二候选位置；收集用户使用固定终端上网的IP地址数据，将每一条记录的IP地址转化为一个IP段；对于预处理后的IP地址数据集中，筛选出使用过该IP段的所有用户，找出这些用户对应的第一候选位置和第二候选位置；得到一系列聚合，将从聚类得到的包含候选位置最多的聚合的重心作为该IP段对应的地理位置。该方法不仅能够实现街道级的定位精度，同时也具备响应快和部署简单等优点。
1.一种利用用户使用移动终端的位置数据来定位IP位置的方法，其特征在于，包括以下步骤：步骤(1)：收集一段时间内用户使用移动终端的位置数据，组成地理位置数据集，每一条地理位置数据记录包括用户标识、时间和地理位置；
步骤(2)：预处理收集到的用户使用移动终端的地理位置数据集；
步骤(3)：对于地理位置数据集中的每个用户：筛选出该用户在每天第一时间段内的移动终端地理位置数据全部记录，对这些记录的地理位置使用经纬度进行聚类，将聚类得到的若干聚合的重心作为该用户对应的第一候选位置；筛选出该用户在每个工作日第二时间段内的移动终端地理位置数据全部记录，对这些记录的地理位置进行聚类，将聚类得到的若干聚合的重心作为该用户对应的第二候选位置；
步骤(4)：收集一段时间内用户使用固定终端上网的IP地址数据，组成IP地址数据集，每一条IP地址数据记录包括用户标识、时间和IP地址；
步骤(5)：预处理收集到的IP地址数据集：将每一条记录的IP地址转化为一个IP段；
如果一个用户使用某个IP段的记录数目低于预先设定的阈值，则从IP地址数据集中去除该用户使用这一IP段的IP地址数据记录；
步骤(6)：对于预处理后的IP地址数据集中的每一个IP段，筛选出使用过该IP段的所有用户，根据步骤(3)获得的结果，找出所有这些用户对应的第一候选位置和第二候选位置，作为该IP段所对应的候选地理位置；对这些候选地理位置进行聚类，得到一系列聚合，从这一系列聚合中选出包含候选地理位置最多的聚合，将该聚合的重心作为该IP段所对应的地理位置。
2.如权利要求1所述方法，其特征在于，所述步骤(2)具体包括以下步骤：步骤(2.1)：从地理位置数据集中取一个尚未处理的用户；
步骤(2.2)：从地理位置数据集中筛选出该用户的所有记录；
步骤(2.3)：如果该用户总的地理位置数据记录条数低于设定的一个阈值或高于某设定的另一个阈值，则从地理位置数据集中去除该用户所有的地理位置数据记录；
步骤(2.4)：如果地理位置数据集中还有尚未处理的用户，则转回步骤(2.1)，否则结束，转步骤（3）。
3.如权利要求1所述方法，其特征在于，所述步骤(3)具体包括以下步骤：步骤(3.1)：从地理位置数据集中取一个尚未处理的用户；
步骤(3.2)：从地理位置数据集中筛选出该用户在每天第一时间段内的地理位置数据记录，计算任每两条记录的地理位置的距离；基于距离的远近对这些地理位置进行聚类，得到一系列聚合，将这一系列聚合中一个或多个聚合的重心作为该用户对应的第一候选位置；
步骤(3.3)：从地理位置数据集中筛选出该用户在每个工作日第二时间段内的地理位置数据记录，计算任每两条记录的地理位置的距离；基于距离的远近对这些地理位置进行聚类，得到一系列聚合，将这一系列聚合中的一个或多个聚合的重心作为该用户对应的第二候选位置；
步骤(3.4)：如果地理位置数据集中还有尚未处理的用户，转回步骤(3.1)，否则结束；
4.如权利要求3所述方法，其特征在于，所述的步骤(3.2)中，计算任每两条记录的地理位置的距离，具体计算如下：如果这两条记录的地理位置不是经纬度，则将它们转换为经纬度[lat1,lng1]和[lat2,lng2]，将经纬度[lat1,lng1]和[lat2,lng2]分别转换为对应的弧度[α1,β1]和[α2,β2]；
[lat1,lng1]和[lat2,lng2]之间的距离为S=arccos(sin(α1)*sin(α2)+cos(α1)*co*s(α2)*cos(β1-β2))R；其中，arccos,sin,cos分别为反余弦，正弦，余弦符号，R为地球赤道半径；
上述的步骤(3.2)中，聚合的重心通过如下方法计算：假设一个聚合为{[lat1,lng1],[lat2,lng2],…,[latn,lngn]}，则该聚合的重心为[(lat1+lat2+…+latn)/n,(lng1+lng2+…+lngn)/n]。
5.如权利要求3所述方法，其特征在于，所述的步骤(3.2)中，基于距离的远近对这些地理位置进行聚类，具体步骤如下：步骤(3.21)：将每一个地理位置转化为只包含一个经纬度的聚合{[lati,lngi]}；
步骤(3.22)：计算每两个聚合之间的距离，两个聚合之间的距离定义为从两个聚合各任意取一个经纬度的最大距离；
步骤(3.23)：找出距离最近的两个聚合，如果该距离小于指定阈值，则将这两个聚合合并成一个新的聚合，新聚合中包括原来两个聚合的所有的经纬度，转到步骤(3.22)；如果该距离大于或者等于指定阈值，则聚类结束。
6.如权利要求1所述方法，其特征在于，所述步骤(5)中，将一个IP地址转化为一个IP段的步骤如下：步骤(5.1)：选定一个数值M作为IP地址转换后对应IP段所需要保留的IP地址长度，M的取值范围为大于8小于32的整数；
步骤(5.2)：将该IP地址的前面M位保留不变，后面的32-M位设置为零，得到的结果作为该IP地址所对应的IP段；
7.如权利要求1所述方法，其特征在于，所述步骤(6)具体包括以下步骤：步骤(6.1)：从预处理后的IP地址数据集中取一个尚未处理的IP段；
步骤(6.2)：从IP地址数据集中找出使用过该IP段的所有用户，根据步骤(3)的结果找出所有这些用户对应的第一候选位置和第二候选位置，作为该IP段所对应的候选地理位置，计算每两个候选地理位置之间的距离，基于距离的远近进行聚类，聚类结束后将得到一系列聚合；
步骤(6.3)：选择一个聚合的重心作为该IP段对应的地理位置。
8.如权利要求7所述方法，其特征在于，所述步骤(6.2)中，基于所有计算的距离进行聚类的步骤如下：步骤(6.21)：将每一个候选地理位置对应的经纬度[lati,lngi]转化为只包含一个经纬度的聚合{[lati,lngi]}；
步骤(6.22)：计算每两个聚合之间的距离；其中，两个聚合之间的距离定义为从两个聚合各任意取一个经纬度的最小距离；
步骤(6.23)：找出距离最近的两个聚合，如果该距离小于指定阈值，则将这两个聚合合并成一个新的聚合，新聚合中包括原来两个聚合的所有的经纬度，转到步骤(6.22)；如果该距离大于或者等于指定阈值，则聚类结束；转步骤(6.3)。
9.如权利要求7所述方法，其特征在于，所述步骤(6.3)：选择一个聚合的重心作为该IP段对应的地理位置：具体包括以下步骤：步骤(6.31)：将所有聚合依据包含的候选位置的个数从多到少进行排序，分别记为C1,C2,…Ci…,Cn；n为聚合的个数；
步骤(6.32)：如果C1包含的候选位置个数比C2多，将选择C1进行下一步处理，转步骤(6.34)，否则转步骤(6.33)；
步骤(6.33)：如果C1包含的候选位置个数与Ci一样多，则从C1,...,Ci中选出包含用户数最多的聚合，转到步骤(6.34)；如果多个聚合包含的用户数并列第一时，则随机选择一个聚合，转到步骤(6.34)；
步骤(6.34)：计算所选择的聚合的重心作为该IP段对应的地理位置。
利用移动终端的位置数据来定位IP位置的方法
技术领域
[0001] 本发明属于计算机系统技术领域，特别涉及一种利用用户使用手机等移动终端的位置数据，来确定固定终端，如个人计算机及其使用的IP地址所对应的地理位置的方法。
背景技术
[0002] 通过用户计算机的IP地址来推测该计算机的地理位置（IP定位）具有广泛的应用，包括在线广告、电子商务、应用监控、网络诊断等。以在线广告为例，如果网站能够通过用户的计算机IP地址准确推测用户所在的地理位置，则可以在网站上显示用户附近的广告信息（比如用户所在小区附近的电影院），而不是随机显示与位置无关的广告信息。
[0003] 现有的IP定位方法主要包括基于延时测量的IP定位方法和基于数据库的IP定位方法两种。基于延时测量的IP定位方法通过在不同的地区部署服务器，利用这些服务器测量它们到目标IP的网络延时，然后基于网络延时的大小来推测这些服务器距离目标IP的实际距离。这种方法通常能够达到10公里到40公里的精确度。由于需要在各地大规模部署服务器，这种方法的成本比较高；同时，大规模的网络延时测量使得这类方法通常需要几十秒到几分钟的响应时间来确定一个IP地址的地理位置。基于数据库的IP定位方法将收集到的IP注册信息、域名登记信息、用户贡献的位置信息等存储在数据库中，然后利用这些数据来确定给定IP地址的位置。这种方法的优点是响应时间很快，确定一个IP地址的位置时直接从数据库查询即可。但是由于数据来源本身的精度比较差，这种方法往往只能得到70公里以上的精确度，只能满足城市级精度的应用需求。
[0004] 具体说来，基于延时测量的IP定位方法包括GeoPing、CBG、TBG、Octant、WangGeo等。GeoPing是其中最简单的一种方法。它直接将到目标IP的网络延时最小的服务器所在的位置推测为目标IP的位置，定位精度在300公里以上。CBG则利用所有服务器到目标IP的网络延时来推测相应的距离，根据每一个距离确定一个目标IP可能的区域，然后将所有可能区域的交集作为目标IP的位置。CBG的定位精度在200公里左右。TBG和Octant在CBG的基础上，考虑了网络的拓扑结构，从而将目标IP限定在了更小的范围。它们分别能够达到60公里和35公里的定位精度。WangGeo除了考虑网络延时和网络拓扑结构，还结合了网页上的邮编地址，能够达到7到10公里的定位精度。
[0005] 基于数据库的IP定位方法通过IP注册信息、DNS信息、用户贡献的位置信息等来确定IP地址的位置。比如可以从IP注册的管理机构（IANA）查到北京的某公司注册了某个IP地址，则一般可以确定这个IP在北京。如果查到一个IP地址对应的域名是router-1.haidian.chinanet.cn，则可以推测该IP地址在海淀区。国内知名的IP定位网站（IP138、IP.cn等）大多采用这类方法。另一种方法是用户自己贡献位置信息，比如腾讯的位置分享网站（ip.qq.com）允许用户提交自己的IP地址及其对应的位置信息。
[0006] 现有IP定位方法及其比较如表1所示。归纳如下：
[0007] 1)基于延时测量的方法响应时间长、部署成本高，最高定位精度能达到7到10公里；
[0008] 2)基于数据库的方法响应快、部署成本低，但是定位精度低；
[0009] 3)对在线广告等应用所要求的街道级（比如2公里以内）定位精度，上述两类方法均不能满足要求。
[0010] 表1现有IP定位方法及其比较
[0011]
发明内容
[0012] 本发明的目的是为克服已有IP定位技术的不足，提出一种利用移动终端位置数据准确定位用户计算机IP地址所对应地理位置的方法。该方法不仅能够实现街道级的定位精度，同时也具备响应快和部署简单等优点。
[0013] 本发明提出的利用用户使用移动终端的位置数据来定位IP位置的方法，包括以下步骤：
[0014] 步骤(1)：收集一段时间内用户使用移动终端的位置数据，组成地理位置数据集，每一条地理位置数据记录包括用户标识、时间和地理位置；
[0015] 步骤(2)：预处理收集到的用户使用移动终端的地理位置数据集；
[0016] 本步骤(2)具体包括以下步骤：
[0017] 步骤(2.1)：从地理位置数据集中取一个尚未处理的用户；
[0018] 步骤(2.2)：从地理位置数据集中筛选出该用户的所有记录；
[0019] 步骤(2.3)：如果该用户总的地理位置数据记录条数低于设定的一个阈值或高于某设定的另一个阈值，则从地理位置数据集中去除该用户的所有条地理位置数据记录；
[0020] 步骤(2.4)：如果地理位置数据集中还有尚未处理的用户，则转回步骤(2.1)，否则结束，转步骤（3）；
[0021] 步骤(3)：对于地理位置数据集中的每个用户：筛选出该用户在每天第一时间段内的移动终端地理位置数据全部记录，对这些记录的地理位置进行聚类，将聚类得到的若干聚合的重心作为该用户对应的第一候选位置；筛选出该用户在每个工作日第二时间段内的移动终端地理位置数据全部记录，对这些记录的地理位置进行聚类，将聚类得到的若干聚合的重心作为该用户对应的第二候选位置；
[0022] 本步骤(3)包括以下步骤：
[0023] 步骤(3.1)：从地理位置数据集中取一个尚未处理的用户；
[0024] 步骤(3.2)：从地理位置数据集中筛选出该用户在每天第一时间段内的地理位置数据记录，计算任每两条记录的地理位置的距离；基于距离的远近对这些地理位置进行聚类，得到一系列聚合，将这一系列聚合中一个或多个聚合的重心作为该用户对应的第一候选位置；
[0025] 上述的步骤(3.2)中，计算任每两条记录的地理位置的距离,具体计算如下：
[0026] 如果这两条记录的地理位置不是经纬度，则将它们转换为经纬度[lat1,lng1]和[lat2,lng2]，将经纬度[lat1,lng1]和[lat2,lng2]分别转换为对应的弧度[α1,β1]和[α2,β2]；
[0027] [lat1,lng1]和[lat2,lng2]之间的距离为S=arccos(sin(α1)*sin(α2)+cos(α1)*cos(α2)*cos(β1-β2))*R；其中，arccos,sin,cos分别为反余弦，正弦，余弦符号，R为地球赤道半径；
[0028] 上述的步骤(3.2)中，基于距离的远近对这些地理位置进行聚类，具体步骤如下：
[0029] 步骤(3.21)：将每一个地理位置转化为只包含一个经纬度的聚合{[lati,lngi]}；
[0030] 步骤(3.22)：计算每两个聚合之间的距离，两个聚合之间的距离定义为从两个聚合各任意取一个经纬度的最大距离；
[0031] 步骤(3.23)：找出距离最近的两个聚合，如果该距离小于指定阈值，则将这两个聚合合并成一个新的聚合，新聚合中包括原来两个聚合的所有的经纬度，转到步骤(3.22)；如果该距离大于或者等于指定阈值，则聚类结束；转步骤（3.2）。
[0032] 上述的步骤(3.2)中，聚合的重心通过如下方法计算：假设一个聚合为{[lat1,lng1],[lat2,lng2],…,[latn,lngn]}，则该聚合的重心为[(lat1+lat2+…+latn)/n,(lng1+lng2+…+lngn)/n]；
[0033] 步骤(3.3)：从地理位置数据集中筛选出该用户在每个工作日第二时间段内的地理位置数据记录，计算任每两条记录的地理位置的距离；基于距离的远近对这些地理位置进行聚类，得到一系列聚合，将这一系列聚合中的一个或多个聚合的重心作为该用户对应的第二候选位置，具体方法与步骤(3.2)中完全相同；
[0034] 步骤(3.4)：如果地理位置数据集中还有尚未处理的用户，转回步骤(3.1)，否则结束；转步骤（4）；
[0035] 步骤(4)：收集一段时间内用户使用固定终端（如PC算机）上网的IP地址数据，组成IP地址数据集，每一条IP地址数据记录包括用户标识、时间和IP地址；
[0036] 步骤(5)：预处理收集到的IP地址数据集：将每一条记录的IP地址转化为一个IP段；如果一个用户使用某个IP段的记录数目低于预先设定的阈值，则从IP地址数据集中去除该用户使用这一IP段的IP地址数据记录。
[0037] 上述步骤(5)中，将一个IP地址转化为一个IP段的步骤如下：
[0038] 步骤(5.1)：选定一个数值M作为IP地址转换后对应IP段所需要保留的IP地址长度，M的取值范围为大于8小于32的整数；
[0039] 步骤(5.2)：将该IP地址的前面M位保留不变，后面的32-M位设置为零，得到的结果作为该IP地址所对应的IP段；
[0040] 步骤(6)：对于预处理后的IP地址数据集中每一个IP段，筛选出使用过该IP段的所有用户，根据步骤(3)获得的结果，找出所有这些用户对应的第一候选位置和第二候选位置，作为该IP段所对应的候选地理位置；对这些候选地理位置进行聚类，得到一系列聚合，从这一系列聚合中选出包含候选地理位置最多的聚合，将该聚合的重心作为该IP段（即该IP段所涵盖的IP地址）所对应的地理位置。
[0041] 步骤(6)具体包括以下步骤：
[0042] 步骤(6.1)：从预处理后的IP地址数据集中取一个尚未处理的IP段；
[0043] 步骤(6.2)：从IP地址数据集中找出使用过该IP段的所有用户，根据步骤(3)的结果找出所有这些用户对应的第一候选位置和第二候选位置，作为该IP段所对应的候选地理位置，计算每两个候选地理位置之间的距离，基于距离的远近进行聚类，聚类结束后将得到一系列聚合。上述的步骤(6.2)中，基于所有计算的距离进行聚类的步骤如下：
[0044] 步骤(6.21)将每一个候选地理位置对应的经纬度[lati,lngi]转化为只包含一个经纬度的聚合{[lati,lngi]}；
[0045] 步骤(6.22)计算每两个聚合之间的距离；其中，两个聚合之间的距离定义为从两个聚合各任意取一个经纬度的最小距离；
[0046] 步骤(6.23)找出距离最近的两个聚合，如果该距离小于指定阈值，则将这两个聚合合并成一个新的聚合，新聚合中包括原来两个聚合的所有的经纬度，转到步骤(6.22)；如果该距离大于或者等于指定阈值，则聚类结束；转步骤(6.3)；
[0047] 步骤(6.3)：通过以下步骤选择一个聚合的重心作为该IP段对应的地理位置：
[0048] 步骤(6.31)将所有聚合依据包含的候选位置的个数从多到少进行排序，分别记为C1,C2,…Ci…,Cn；n为聚合的个数；
[0049] 步骤(6.32)如果C1包含的候选位置个数比C2多，将选择C1进行下一步处理，转步骤(6.34)，否则转步骤(6.33)；
[0050] 步骤(6.33)如果C1包含的候选位置个数与Ci一样多，则从C1,...,Ci中选出包含用户数最多的聚合，转到步骤(6.34)；如果多个聚合包含的用户数并列第一时，则随机选择一个聚合，转到步骤(6.34)；
[0051] 步骤(6.34)计算所选择的聚合的重心作为该IP段对应的地理位置。
[0052] 本发明中提到的一段时间，可以为任意长的一段时间，例如一个月或一年。本发明提到的阈值或个数选择，可以设定为任何值，这些值的设定只会影响结果精度，不会对方法本身造成影响。
[0053] 本发明方法主要基于以下原理：大部分人每天的活动都具备很强的规律性，通常第一时间段内（晚上）在家，工作日第二时间段内（白天）则在办公地点；如果能够收集用户使用的移动终端（比如手机）的位置数据（通常通过GPS获知），则用户晚上的位置数据记录将会集中在家附近，而工作日白天的位置数据记录则会集中在办公地点附近；于是可以据此推测某用户可能的家庭位置和办公位置。同时，可以收集到用户使用的固定终端的IP使用记录。如果收集到的IP使用记录数据显示某个IP/24段被多个用户的固定终端使用，则这个IP/24段很可能在这几个用户的家庭和办公地点集中的位置。
[0054] 本发明的特点及有益效果：
[0055] 本发明利用用户使用的移动终端（比如带有GPS定位功能的手机）时所产生的位置数据信息来间接推测该用户使用的固定终端(如家用PC机，办公室PC机)，服务器等及其使用的IP地址所对应的位置；
[0056] 本发明由于间接使用了移动终端上提供的高精度的位置信息，能够实现街道级的IP定位精度，同时具备部署简单和响应速度快等优点。
附图说明
[0057] 图1是本实施例的总体流程图。
[0058] 图2是本实施例中预处理移动位置数据集（步骤2）的流程图。
[0059] 图3是本实施例聚类移动位置数据记录得到候选家庭位置和候选办公位置（步骤3）的流程图。
具体实施方式
[0060] 本发明提出的一种利用移动终端位置数据来精确定位IP位置的方法，结合附图及实施例详细说明如下。
[0061] 本方法以用户使用IM工具或者社交应用，例如腾讯公司的手机版QQ、手机微博等应用为例说明用户使用终端的地理位置数据的收集途径；以用户使用腾讯公司的桌面版QQ为例说明用户使用固定终端的IP地址数据收集途径。当用户使用腾讯的手机QQ、手机微博等应用时，可以使用“足迹”、“说说”等功能提交自己的地理位置信息，这些位置信息包括用户的登录ID（即本发明方法所指的用户标识），提交的时间，以及地理位置信息（通过GPS采集的经纬度数据）。当用户每次登陆桌面版腾讯QQ软件时，服务器都会记录其相应的登录信息，这些登录信息包括用户的登录ID（用户标识），登录时间，以及登录的IP地址。利用上述用户自己提交的地理位置信息和桌面版QQ登录信息，可以收集到本发明实施例中所需要的地理位置数据集和IP地址数据集。
[0062] 本方法的实施例包括以下步骤：
[0063] 步骤(1)：收集一段时间（时间可长可短，如1个月）内用户使用移动终端的位置数据，组成地理位置数据集，每一条地理位置数据记录包括用户标识、时间和地理位置。在本实施例中，地理位置为经纬度（[lat,lng]），采集到的地理位置数据集存储到MySQL数据库。数据记录的格式如表2所示。
[0064] 表2移动终端的地理位置数据的存储格式
[0065]字段 描述 类型 长度 举例
UID 用户标识 字符串 20字节 liming1982
Time 时间 字符串 19字节 2012-12-12 11:12:12
Latitude 纬度 浮点数 8字节 46.339202
Longitude 经度 浮点数 8字节 121.393833
[0066] 步骤(2)：预处理收集到的用户使用移动终端的地理位置数据集，本步骤具体包括步骤如图2所示：
[0067] 步骤(2.1)：从地理位置数据集中取一个尚未处理的用户（用户标识）；
[0068] 步骤(2.2)：从地理位置数据集中筛选出该用户的所有记录；
[0069] 步骤(2.3)：如果该用户总的地理位置数据记录条数低于设定的一个阈值（可根据实际情况需要取值，本实施例设置为10条）或者高于设定的另一个阈值（本实施例设置为1000条），则从地理位置数据集中去除该用户对应的所有条地理位置数据记录；
[0070] 步骤(2.4)：如果地理位置数据集中还有尚未处理的用户，则转回步骤(2.1)，否则结束；转步骤（3）；
[0071] 步骤(3)：对于地理位置数据集中的每个用户：筛选出该用户在每天第一时间段内（晚上）的移动终端地理位置数据全部记录，对这些记录的地理位置进行聚类，将聚类得到的若干聚合的重心作为该用户对应的第一候选位置；筛选出该用户在每个工作日第二时间段内（白天）的移动终端地理位置数据全部记录，对这些记录的地理位置进行聚类，将聚类得到的若干聚合的重心作为该用户对应的第二候选位置；将该用户的第一候选位置和第二候选位置存储到MySQL数据库中，用户的第一候选位置和第二候选位置数据的存储格式如表3所示。
[0072] 表3用户第一候选位置和第二候选位置数据的存储格式
[0073]字段 描述 类型 长度 举例
UID 用户标识 字符串 20字节 liming1982
Latitude 候选位置纬度 浮点数 8字节 45.219393
Longitude 候选位置经度 浮点数 8字节 120.293933
Type 位置类型（1为第一，0为第二） 布尔 1位 1
[0074] 本步骤的具体过程如图3所示，如下：
[0075] 步骤(3.1)：从地理位置数据集中取一个尚未处理的用户；
[0076] 步骤(3.2)：从地理位置数据集中筛选出该用户在每天第一时间段内（本实施例为每天晚上8:00到早上7:00之间）的记录，计算任每两条记录的地理位置的距离；基于距离的远近对这些地理位置进行聚类，得到一系列聚合的重心，将这一系列聚合中一个或多个聚合（本实施例设置为全部聚合）的重心作为该用户对应的第一候选位置：
[0077] 上述的步骤(3.2)中，计算任每两条记录的地理位置的距离,具体计算如下：
[0078] 将经纬度[lat1,lng1]和[lat2,lng2]分别转换为对应的弧度[α1,β1]和[α2,β2]；
[0079] [lat1,lng1]和[lat2,lng2]之间的距离为S=arccos(sin(α1)*sin(α2)+cos(α1)*cos(α2)*cos(β1-β2))*R；其中，arccos,sin,cos分别为反余弦，正弦，余弦符号，R为地球赤道半径（默认值为6378137.0米）。
[0080] 上述的步骤(3.2)中，基于距离的远近对这些地理位置进行聚类，具体步骤如下：
[0081] 步骤(3.21)：将每一个地理位置转化为只包含一个经纬度的聚合{[lati,lngi]}；
[0082] 步骤(3.22)：计算每两个聚合之间的距离，两个聚合之间的距离定义为从两个聚合各任意取一个经纬度的最大距离；
[0083] 步骤(3.23)：找出距离最近的两个聚合，如果该距离小于指定阈值（本实施例设置为200米），则将这两个聚合合并成一个新的聚合，新聚合中包括原来两个聚合的所有的经纬度，转到步骤步骤(3.22)；如果该距离大于或者等于指定阈值（本实施例设置为200米），则聚类结束；转步骤（3.2）。
[0084] 上述的步骤(3.2)中，聚合的重心通过如下方法计算：假设一个聚合为{[lat1,lng1],[lat2,lng2],…,[latn,lngn]}，则该聚合的重心为[(lat1+lat2+…+latn)/n,(lng1+lng2+…+lngn)/n]；
[0085] 步骤(3.3)：从地理位置数据集中筛选出该用户在每个工作日第二时间段内（本实施例为周一到周五的上午9:00到下午6:00之间）的记录，计算任每两条记录的地理位置的距离；基于距离的远近对这些地理位置进行聚类，得到一系列聚合，将这一系列聚合中的一个或多个聚合（本实施例设置为全部聚合）的重心作为该用户的第二候选位置，具体方法与步骤(3.2)中完全相同；
[0086] 步骤(3.4)：如果地理位置数据集中还有尚未处理的用户，转回步骤(3.1)，否则结束；转步骤（4）；
[0087] 步骤(4)：收集一段时间（本实施例为一个月）内用户使用PC上网的IP地址数据，组成IP地址数据集，每一条IP地址数据记录包括用户标识、时间和IP地址；将数据存储到MySQL数据库；本实施例数据记录的格式如表4所示。
[0088] 表4IP地址数据的存储格式
[0089]字段 描述 类型 长度 举例
UID 用户标识 字符串 20字节 liming1982
Time 时间 字符串 19字节 2012-12-12 11:12:12
IP IP地址 字符串 15字节 166.111.193.233
[0090] 步骤(5)：预处理收集到的IP地址数据集：将每一条记录的IP地址转化为一个IP段。转换后的存储格式如表5所示。如果一个用户使用某个IP段的记录数目预先设定的阈值（如低于10），则从IP地址数据集中去除该用户使用这一IP段的IP地址数据记录。上述步骤(5)中，将一个IP地址（本实施例以IP地址166.111.120.13为例说明）转化为一个IP段的步骤如下：
[0091] 步骤(5.1)：选定一个数值M（本实施例设置为24）作为IP地址转换后对应IP段所需要保留的IP地址长度；
[0092] 步骤(5.2)：将该IP地址的前面24保留不变，后面的8位设置为零，得到的结果(166.111.120.0）作为该IP地址所对应的IP段；
[0093] 表5IP地址转换为IP/24段后的IP地址数据存储格式
[0094]字段 描述 类型 长度 举例
UID 用户标识 字符串 20字节 liming1982
Time 时间 字符串 19字节 2012-12-12 11:12:12
IP/24段 IP地址对应的/24段 字符串 13字节 166.111.193.0
[0095] 步骤(6)：对于预处理后的IP地址数据集中每一个IP/24段，筛选出使用过该IP/24段的所有用户，根据步骤(3)获得的结果，找出所有这些用户对应的第一候选位置和第二候选位置，作为该IP段所对应的候选地理位置；对这些候选地理位置进行聚类，得到一系列聚合，从这一系列聚合中选出包含候选地理位置最多的聚合的重心作为该IP/24段（即该IP段所涵盖的IP地址）所对应的地理位置。
[0096] 本步骤的具体过程如下：
[0097] 步骤(6.1)：从预处理后的IP地址数据集中取一个尚未处理的IP/24段；
[0098] 步骤(6.2)：从IP地址数据集找出使用过该IP/24段的所有用户，根据步骤(3)的结果找出所有这些用户对应的第一候选位置和第二候选位置，作为该IP段所对应的候选地理位置，计算每两个候选地理位置之间的距离，基于距离的远近进行聚类，聚类结束后将得到一系列聚合；
[0099] 上述的步骤(6.2)中，基于所有计算出的距离进行聚类的步骤如下：
[0100] 步骤(6.21)将每一个候选地理位置对应的经纬度[lati,lngi]转化为只包含一个经纬度的聚合{[lati,lngi]}；
[0101] 步骤(6.22)计算每两个聚合之间的距离；其中，两个聚合之间的距离定义为从两个聚合各任意取一个经纬度的最小距离；
[0102] 步骤(6.23)找出距离最近的两个聚合，如果该距离小于指定阈值（设置为500米），则将这两个聚合合并成一个新的聚合，新聚合中包括原来两个聚合的所有的经纬度，转到步骤(6.22)；如果该距离大于或者等于指定阈值（设置为500米），则聚类结束；转步骤(6.3)；
[0103] 步骤(6.3)：通过以下步骤选择一个聚合的重心作为该IP/24段对应的地理位置：
[0104] 步骤(6.31)将所有聚合依据包含的候选位置的个数从多到少进行排序，分别记为C1,C2,…,Cn；n为聚合的个数；
[0105] 步骤(6.32)如果C1包含的候选位置个数比C2多，将选择C1进行下一步处理，转(6.34)，否则转(6.33)；
[0106] 步骤(6.33)如果C1包含的候选位置个数与Ci一样多，则从C1,...,Ci中选出包含用户数最多的聚合，转到(6.34)；如果多个聚合包含的用户数并列第一时，则随机选择一个聚合，转到(6.34)；
[0107] 步骤(6.34)计算所选择的聚合的重心作为该IP/24段对应的地理位置。
[0108] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体（Read-Only Memory，ROM）或随机存储记忆体（Random Access Memory，RAM）等。
[0109] 以上所揭露的仅为本发明较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。
