CN111160385B - 海量位置点聚合的方法、装置、设备及存储介质 - Google Patents
海量位置点聚合的方法、装置、设备及存储介质 Download PDFInfo
- Publication number
- CN111160385B CN111160385B CN201911185717.7A CN201911185717A CN111160385B CN 111160385 B CN111160385 B CN 111160385B CN 201911185717 A CN201911185717 A CN 201911185717A CN 111160385 B CN111160385 B CN 111160385B
- Authority
- CN
- China
- Prior art keywords
- model
- modified
- clustering
- sample set
- point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 67
- 230000004931 aggregating effect Effects 0.000 title claims abstract description 15
- 230000002776 aggregation Effects 0.000 claims abstract description 45
- 238000004220 aggregation Methods 0.000 claims abstract description 45
- 238000003064 k means clustering Methods 0.000 claims abstract description 7
- 238000004364 calculation method Methods 0.000 claims description 38
- 230000015572 biosynthetic process Effects 0.000 claims description 11
- 238000003786 synthesis reaction Methods 0.000 claims description 11
- 238000004422 calculation algorithm Methods 0.000 description 24
- 239000013598 vector Substances 0.000 description 14
- 230000000694 effects Effects 0.000 description 12
- 238000010586 diagram Methods 0.000 description 9
- 230000008569 process Effects 0.000 description 8
- 230000006870 function Effects 0.000 description 7
- 238000004891 communication Methods 0.000 description 5
- 238000012545 processing Methods 0.000 description 4
- 238000000926 separation method Methods 0.000 description 4
- 230000008878 coupling Effects 0.000 description 3
- 238000010168 coupling process Methods 0.000 description 3
- 238000005859 coupling reaction Methods 0.000 description 3
- 230000015556 catabolic process Effects 0.000 description 2
- 238000006731 degradation reaction Methods 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 230000001788 irregular Effects 0.000 description 2
- 238000010801 machine learning Methods 0.000 description 2
- 238000005259 measurement Methods 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000002194 synthesizing effect Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000008901 benefit Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000004590 computer program Methods 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000006116 polymerization reaction Methods 0.000 description 1
- 238000000638 solvent extraction Methods 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F18/00—Pattern recognition
- G06F18/20—Analysing
- G06F18/23—Clustering techniques
- G06F18/232—Non-hierarchical techniques
- G06F18/2321—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions
- G06F18/23213—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions with fixed number of clusters, e.g. K-means clustering
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/29—Geographical information databases
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- Databases & Information Systems (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Remote Sensing (AREA)
- Life Sciences & Earth Sciences (AREA)
- Artificial Intelligence (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Evolutionary Biology (AREA)
- Evolutionary Computation (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
本发明公开了一种海量位置点聚合的方法，包括：获取第一样本集合；将第一样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第二样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设上限值，将第二样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第三样本集合，记录第三样本集合中的类别个数，其中，预先修改的DBSCAN模型中的密度参数为预设下限值，将第三样本集合输入至预先修改的K‑means模型进行聚类运算，进行K‑means聚类运算的次数为类别个数，得到聚类结果，将聚类结果输入至预先修改的轮廓系数模型，获取聚合点。通过上述方法，可以从海量的位置点中快速找到最优的聚合结果。本发明还公开了一种海量位置点聚合的装置、设备及存储介质。
Description
技术领域
本发明涉及地理信息处理技术领域，特别涉及一种海量位置点聚合的方法、装置、设备及存储介质。
背景技术
随着计算机技术的飞速发展，对海量位置点进行监控和管理已经成为公共交通、智能地图等领域的核心应用，如何高效地从海量位置点中找到POI(兴趣点，Point ofInterest)是本领域技术人员一直努力解决的技术问题。
目前，常见的对位置点进行聚合的方法，主要包括利用K-means、DBSCAN等经典的机器学习聚类方法，但是经典的机器学习聚类方法，在数据点的数量很庞大的时候，性能下降非常严重，耗费的时间长，甚至不能在需求许可的时间内完成，而且不同的参数会产生不同的聚合结果。因此，急需一种可以从海量位置点中高效快速的找到最优聚合结果的方法。
发明内容
本公开实施例提供了一种海量位置点聚合的方法、装置、设备及存储介质。为了对披露的实施例的一些方面有一个基本的理解，下面给出了简单的概括。该概括部分不是泛泛评述，也不是要确定关键/重要组成元素或描绘这些实施例的保护范围。其唯一目的是用简单的形式呈现一些概念，以此作为后面的详细说明的序言。
在一些实施例中，一种海量位置点聚合的方法，包括：
获取第一样本集合；
将第一样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第二样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设上限值；
将第二样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第三样本集合，记录第三样本集合中的类别个数，其中，预先修改的DBSCAN模型中的密度参数为预设下限值；
将第三样本集合输入至预先修改的K-means模型进行聚类运算，进行K-means聚类运算的次数为类别个数，得到聚类结果；
将聚类结果输入至预先修改的轮廓系数模型，获取聚合点。
可选地，将聚类结果输入至预先修改的轮廓系数模型，获取聚合点，包括：
根据预先修改的轮廓系数模型对聚类结果分别计算轮廓系数，将轮廓系数值最大的聚类结果所对应的位置点作为聚合点。
可选地，获取第一样本集合包括：
根据经纬度划分不同的网格，将位置点根据经纬度划分到不同的网格中；
将网格中距离小于预设值的位置点合成一个点，作为合成位置点，将距离小于预设值的位置点的个数作为合成位置点的重复数，以合成位置点的经度、纬度、重复数生成第一样本集合。
可选地，预先修改的DBSCAN模型包括：
在DBSCAN模型中增加一个数量参数，数量参数为合成位置点的重复数，将DBSCAN模型中在距离条件内累加样本数量的操作，由每次加1改为每次加上重复数。
可选地，预先修改的K-means模型包括：
在K-means模型中增加一个数量参数，数量参数为合成位置点的重复数，将K-means模型中计算质心时，每个样本参与一次计算修改为每个样本重复参与计算，重复参与计算的次数为重复数。
可选地，预先修改的轮廓系数模型包括:
在轮廓系数模型中增加一个数量参数，数量参数为合成位置点的重复数，将计算样本距离的方法修改为将原有的距离乘以重复数。
在一些实施例中，一种海量位置点聚合的装置，包括：
第一获取模块，用于获取第一样本集合；
第一分类模块，用于将第一样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第二样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设上限值；
第二分类模块，用于将第二样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第三样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设下限值；
聚类模块，用于将第三样本集合输入至预先修改的K-means模型进行聚类运算，得到聚类结果；
第二获取模块，用于将聚类结果输入至预先修改的轮廓系数模型，获取聚合点。
在一些实施例中，一种海量位置点聚合的装置，包括处理器和存储有程序指令的存储器，处理器被配置为在执行程序指令时，执行上述实施例提供的海量位置点聚合的方法。
在一些实施例中，一种海量位置点聚合的设备，包括上述实施例提供的海量位置点聚合的装置。
在一些实施例中，一种计算机可读介质，其上存储有计算机可读指令，计算机可读指令可被处理器执行以实现上述实施例提供的一种海量位置点聚合的方法。
本公开实施例提供的技术方案可以包括以下有益效果：
本发明通过修改原有的DBSCAN模型、K-means模型、轮廓系数模型，在模型原有的参数中增加一个重复数参数，以及将位置点根据经纬度划分到不同的网格中，将网格中距离小于预设值的位置点合成一个点，并将合成后的点的经纬度信息和重复数信息作为一个样本集合，将上述样本集合输入到预先修改的DBSCAN模型、K-means模型、轮廓系数模型中。通过上述方法，可以使计算时的样本量大大较少，计算时间也相应的大大减少，而且通过将样本集合依次输入DBSCAN模型、K-means模型进行聚类，再输入轮廓系数模型进行聚类结果评估，可以快速得到最优的聚合结果。
应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本发明。
附图说明
此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本发明的实施例，并与说明书一起用于解释本发明的原理。
图1是根据一示例性实施例示出的一种海量位置点聚合方法的流程示意图；
图2是根据一示例性实施例示出的一种海量位置点聚合方法的流程示意图；
图3是根据一示例性实施例示出的一种海量位置点聚合方法的流程示意图；
图4是根据一示例性实施例示出的一种海量位置点聚合的装置示意图；
图5是根据一示例性实施例示出的一种海量位置点聚合的装置示意图。
具体实施方式
以下描述和附图充分地示出本发明的具体实施方案，以使本领域的技术人员能够实践它们。
图1是根据一示例性实施例示出的一种海量位置点聚合方法的流程示意图。
如图1所示，本公开实施例提供了一种海量位置点聚合方法，包括：
步骤S101、获取第一样本集合。
具体地，第一样本集合指的是合成位置点的经度、纬度、重复数，首先，根据经纬度划分出不同的网格，将海量位置点根据经纬度划分到不同的网格中；将网格中距离小于预设值的点合成一个点，作为合成位置点，将距离小于预设值的位置点的个数作为合成位置点的重复数，以合成位置点的经度、纬度、重复数生成第一样本集合。
例如，将网格中距离小于5米的点合成一个点，作为合成位置点，具体距离可以根据实际情况确定，在一些示例性场景中，网格中距离小于5米的点有8个，则合成位置点的重复数为8，合成位置点的经度经测量为东经116度23分，纬度为北纬39度54分，则第一样本集合包括“东经116度23分、北纬39度54分、8”。
通过上述方法，将海量位置点根据经纬度划分到不同的网格中，将网格中距离较近的点合成一个点，可以大大减少计算时的样本量，提升运算速度。
步骤S102、将第一样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第二样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设上限值。
DBSCAN是一个比较有代表性的基于密度的聚类算法，与划分和层次聚类算法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。
DBSCAN聚类算法和传统的K-means算法相比，DBSCAN聚类算法的最大的不同是不需要事先知道要形成的簇类的数量，因此不需要输入类别个数K，它最大的优势是可以发现任意形状的聚类簇，而不像K-means算法，一般只适用凸的样本集，同时，DBSCAN聚类算法能识别出噪声点，但是如果样本集的密度不均匀，聚类间距差相差很大时，聚类效果较差。
DBSCAN聚类算法的描述如下：
a、输入：包含n个对象的样本集合，半径eps，密度参数Minpts；
b、输出：生成的所有达到密度要求的簇；
c、从样本中抽出一个未被访问的点，找出与该点在距离eps内的所有附近点；
d、将在距离eps内的所有附近点累加；
e、如果累加得到的数值≥密度参数Minpts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问，然后递归，以相同的方法处理该簇内所有未被标记为已访问点，从而对簇进行扩展；
f、如果累加得到的数值＜密度参数Minpts，则该点暂时被标记为噪声点；
g、用同样的算法去处理未被访问的点，直到所有的点被访问完。
在本公开实施例中，首先修改经典DBSCAN模型，在DBSCAN模型中增加一个数量参数，数量参数为合成位置点的重复数，将DBSCAN模型中在距离条件内累加样本数量的操作，由每次加1改为每次加上重复数。
具体地，修改经典DBSCAN模型的第4步，将在距离eps内的所有附近点累加的操作，由每次加1，改为每次加上该点的重复数，因为该点是由多个距离相近的点合成的，例如，在距离eps内的某点的重复数为8，则在步骤4中的累加操作时，累加上8。
通过上述步骤，得到修改过的DBSCAN模型，通过修改DBSCAN模型，可以大大提升运算速度。
将第一样本集合输入修改过的DBSCAN模型进行分类，此时密度参数Minpts为预设上限值，就是将密度参数Minpts定义为一个较大值，DBSCAN模型对用户定义的参数很敏感，细微的不同都会导致差别很大的结果，参数的选择无规律可循，只能靠经验确定，本公开实施例中的预设上限值是根据大量数据统计得到的。
在一些实施例中，将第一样本集合输入修改过的DBSCAN模型进行分类，得到噪声数据和分类后生成的簇，将噪声数据去除，将分类后生成的簇合成一个新样本，作为第二样本集合。
通过将密度参数定义为一个较大值，可以把大量不满足条件的位置点先过滤掉，得到较小范围的类别，提升聚合速度和准确度。
步骤S103、将第二样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第三样本集合，记录第三样本集合中的类别个数，其中，预先修改的DBSCAN模型中的密度参数为预设下限值。
将第二样本集合输入修改过的DBSCAN模型进行分类，此时密度参数Minpts为预设下限值，就是将密度参数Minpts定义为一个较小值，DBSCAN模型对用户定义的参数很敏感，细微的不同都会导致差别很大的结果，参数的选择无规律可循，只能靠经验确定，本公开实施例中的预设下限值也是根据大量数据统计得到的。
通过将密度参数定义为一个较小的值，再执行一次DBSCAN聚类算法，是为了确定下一步K-means模型进行聚类操作的次数。
在一些实施例中，将第二样本集合输入修改过的DBSCAN模型进行分类，得到噪声数据和分类后生成的簇，将噪声数据去除，将分类后生成的簇合成一个新样本，作为第三样本集合。并且记录第三样本集合中的类别个数。
通过上述方法，将样本集合输入修改过的DBSCAN模型进行基于密度的聚类运算，得到不同类别的聚类结果。
步骤S104、将第三样本集合输入至预先修改的K-means模型进行聚类运算，进行K-means聚类运算的次数为类别个数，得到聚类结果。
K-means模型是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。此方法以K为参数，把N个对象分为K个簇，以使簇内具有较高的相似度，而且簇间的相似度较低，相似度的计算根据一个簇中对象的平均值来进行。K-means算法首先随机选择k个对象，每个对象代表一个聚类的质心，对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中，然后，计算每个聚类的新质心。重复上述过程，直到标准测度函数收敛，k-means算法是一种较典型的逐点修改迭代的动态聚类算法。
k-means算法理解容易，聚类效果不错，当处理大数据集的时候，该算法具有良好的伸缩性和高效率，当簇近似高斯分布的时候，处理效果不错，但是不适合发现非凸形状的簇或者大小差别很大的簇，也不适合簇与簇距离相近的聚类。
k-means算法的描述如下：
a、输入：参数K，包含n个对象的样本集合；
b、输出：满足方差最小标准的K个聚类；
c、随机选择K个对象，每个对象代表一个聚类的质心；
d、依据欧氏距离最小的原则将其余对象分配至最邻近的类别；
e、重新计算每个聚类的新质心；
f、重复上述过程，直到标准测度函数收敛；
g、结束，得到K个聚类结果。
在本公开实施例中，首先修改经典k-means模型，在经典k-means模型中增加一个重复数参数，将K-means模型中计算质心时，每个样本参与一次计算修改为每个样本重复参与计算，重复参与计算的次数为重复数。
具体地，修改经典k-means模型的第5步，重新计算每个聚类的新质心，类别中的每个样本参与一次计算修改为类别中的每个样本重复参与计算，重复参与计算的次数为重复数，例如，当前样本中的重复数为8，则该样本重复参与8次计算，因为该样本中的位置点是由距离较近的8个点合成的，所以修改为重复参与8次计算。
通过上述方法，得到修改过的k-means模型，通过修改过的k-means模型，可以大大提高运算速度。
具体地，将第三样本集合输入修改过的k-means模型进行聚类运算，例如，第三样本集合中的类别个数为M，将K值由1到M分别运行k-means聚类运算，首先，令参数K＝1进行聚类运算，得到1组聚类结果，令参数K＝2进行聚类运算，得到2组聚类结果，令参数K＝3进行聚类运算，得到3组聚类结果，令参数K＝M进行聚类运算，得到M组聚类结果。
在一些示例性场景中，第三样本集合中的类别个数为5，将K值由1到5分别运行k-means聚类运算，首先，令参数K＝1进行聚类运算，得到1组聚类结果，令参数K＝2进行聚类运算，得到2组聚类结果，令参数K＝3进行聚类运算，得到3组聚类结果，令参数K＝4进行聚类运算，得到4组聚类结果，令参数K＝5进行聚类运算，得到5组聚类结果，总共得到15组聚类结果。
通过上述方法，将样本集合输入修改过的k-means模型进行基于样本间相似性度量的间接聚类运算，得到若干组聚类结果。
步骤S105、将聚类结果输入至预先修改的轮廓系数模型，获取聚合点。
轮廓系数是聚类效果好坏的一种检查方式，它结合内聚度和分离度两种因素，在相同原始数据的基础上用来检查不同的算法，或者算法不同的运行方式对聚类结果产生的影响。
轮廓系数的计算过程描述：
假设我们已经通过一定算法，将待分类数据进行了聚类。得到若干组聚类结果，对于每组聚类结果中的每个向量，分别计算它们的轮廓系数。
对于其中一个向量i来说：
计算a(i)＝average(i向量到所有它属于的簇中的点的平均距离)，a(i)越小，说明样本i越应该被聚类到该簇；
计算b(i)＝min(i向量到所有它不属于的簇中的点的平均距离)，b(i)越大，说明样本i越不属于其他簇。
向量i的轮廓系数为：
所有样本的轮廓系数均值称为该聚类结果的轮廓系数，从轮廓系数公式可以看出，轮廓系数的值是介于[-1,1]。
si接近1，则说明样本i聚类合理；
si接近-1，则说明样本i更应该分类到另外的簇；
若si近似为0，则说明样本i在两个簇的边界上。
在本公开实施例中，首先修改经典轮廓系数模型，在轮廓系数模型中增加一个重复数参数，将计算样本距离的方法修改为将原有的距离乘以重复数。例如，样本中合成位置点的重复数为8，在计算a(i)和b(i)时，向量i到其他点的距离乘以重复数8。
通过上述方法，得到修改过的轮廓系数模型。
将k-means模型聚类得到的若干组聚类结果分别进行轮廓系数计算，将轮廓系数值最大的聚类结果所对应的位置点作为聚合点。例如，经k-means模型聚类得到5组聚类结果，分别计算上述5组聚类结果的轮廓系数，例如，第一组聚类结果的轮廓系数为0.5，第二组聚类结果的轮廓系数为0.9，第三组聚类结果的轮廓系数为0.1，第四组聚类结果的轮廓系数为-0.6，第五组聚类结果的轮廓系数为-0.3，选取轮廓系数值最大的聚类结果所对应的位置点作为聚合点，也就是将第二组聚类结果所对应的位置点作为聚合点。因为轮廓系数越接近1，表明该聚类结果的内聚度和分离度都相对较优。
通过上述方法，利用轮廓系数检查聚类结果的聚类效果好坏，可以适配到最优的聚合点。
可选地，将聚类结果输入至预先修改的轮廓系数模型，获取聚合点，包括：
根据预先修改的轮廓系数模型对聚类结果分别计算轮廓系数，将轮廓系数值最大的聚类结果所对应的位置点作为聚合点。
具体地，k-means模型进行聚类运算会得到若干组聚类结果，每组聚类结果的效果好坏不等，计算得到的若干组聚类结果的轮廓系数，可以检查聚类结果的内聚度和分离度，从而检查聚类结果的聚类效果。
轮廓系数公式：
从轮廓系数公式可以看出，轮廓系数的值是介于[-1,1]，其中，a(i)＝average(i向量到所有它属于的簇中的点的平均距离)，a(i)越小，说明样本i越应该被聚类到该簇，b(i)＝min(i向量到所有它不属于的簇中的点的平均距离)，b(i)越大，说明样本i越不属于其他簇。因此，轮廓系数值最大的聚类结果的聚类效果越好，也就是轮廓系数值越接近1，聚类效果越好。
在一些示例性场景中，经k-means模型聚类得到5组聚类结果，分别计算上述5组聚类结果的轮廓系数，例如，第一组聚类结果的轮廓系数为0.5，第二组聚类结果的轮廓系数为0.9，第三组聚类结果的轮廓系数为0.1，第四组聚类结果的轮廓系数为-0.6，第五组聚类结果的轮廓系数为-0.3，选取轮廓系数值最大的聚类结果所对应的位置点作为聚合点，也就是将第二组聚类结果所对应的位置点作为聚合点。
通过上述方法，利用轮廓系数检查聚类结果的聚类效果好坏，可以适配到最优的聚合点。
图2是根据一示例性实施例示出的一种海量位置点聚合方法的流程示意图。
如图2所示，获取第一样本集合包括：
步骤S201、根据经纬度划分不同的网格，将位置点根据经纬度划分到不同的网格中。
具体地，第一样本集合指的是合成位置点的经度、纬度、重复数，首先，根据经纬度划分出不同的网格，将海量位置点根据经纬度划分到不同的网格中。例如，将北纬37度、北纬39度、东经114度、东经116度划分为一个网格，只要位置点的经纬度位于该网格中，就将位置点划分到该网格中。
步骤S201、将网格中距离小于预设值的位置点合成一个点，作为合成位置点，将距离小于预设值的位置点的个数作为合成位置点的重复数，以合成位置点的经度、纬度、重复数生成第一样本集合。
将网格中距离小于预设值的点合成一个点，作为合成位置点，将距离小于预设值的位置点的个数作为合成位置点的重复数，以合成位置点的经度、纬度、重复数生成第一样本集合。
例如，将网格中距离小于5米的点合成一个点，作为合成位置点，具体距离可以根据实际情况确定，在一些示例性场景中，网格中距离小于5米的点有8个，则合成位置点的重复数为8，合成位置点的经度经测量为东经116度23分，纬度为北纬39度54分，则第一样本集合包括“东经116度23分、北纬39度54分、8”。
通过上述方法，将海量位置点根据经纬度划分到不同的网格中，将网格中距离较近的点合成一个点，可以大大减少计算时的样本量，提升运算速度。
可选地，预先修改的DBSCAN模型包括：
在DBSCAN模型中增加一个数量参数，数量参数为合成位置点的重复数，将DBSCAN模型中在距离条件内累加样本数量的操作，由每次加1改为每次加上重复数。
具体地，DBSCAN聚类算法的描述如下：
a、输入：包含n个对象的样本集合，半径eps，密度参数Minpts；
b、输出：生成的所有达到密度要求的簇；
c、从样本中抽出一个未被访问的点，找出与该点在距离eps内的所有附近点；
d、将在距离eps内的所有附近点累加；
e、如果累加得到的数值≥密度参数Minpts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问，然后递归，以相同的方法处理该簇内所有未被标记为已访问点，从而对簇进行扩展；
f、如果累加得到的数值＜密度参数Minpts，则该点暂时被标记为噪声点；
g、用同样的算法去处理未被访问的点，直到所有的点被访问完。
在本公开实施例中，修改经典DBSCAN模型，在DBSCAN模型中增加一个数量参数，数量参数为合成位置点的重复数，将DBSCAN模型中在距离条件内累加样本数量的操作，由每次加1改为每次加上重复数。
具体地，修改经典DBSCAN模型的第4步，将在距离eps内的所有附近点累加的操作，由每次加1，改为每次加上该点的重复数，因为该点是由多个距离相近的点合成的，例如，在距离eps内的某点的重复数为6，则在步骤4中的累加操作时，累加上6。
通过上述步骤，得到修改过的DBSCAN模型，通过修改DBSCAN模型，可以大大提升运算速度。
可选地，预先修改的K-means模型包括：
在K-means模型中增加一个数量参数，数量参数为合成位置点的重复数，将K-means模型中计算质心时，每个样本参与一次计算修改为每个样本重复参与计算，重复参与计算的次数为重复数。
具体地，k-means算法的描述如下：
a、输入：参数K，包含n个对象的样本集合；
b、输出：满足方差最小标准的K个聚类；
c、随机选择K个对象，每个对象代表一个聚类的质心；
d、依据欧氏距离最小的原则将其余对象分配至最邻近的类别；
e、重新计算每个聚类的新质心；
f、重复上述过程，直到标准测度函数收敛；
g、结束，得到K个聚类结果。
在本公开实施例中，修改经典k-means模型，在经典k-means模型中增加一个重复数参数，将K-means模型中计算质心时，每个样本参与一次计算修改为每个样本重复参与计算，重复参与计算的次数为重复数。
具体地，修改经典k-means模型的第5步，重新计算每个聚类的新质心，类别中的每个样本参与一次计算修改为类别中的每个样本重复参与计算，重复参与计算的次数为重复数，例如，当前样本中的重复数为6，则该样本重复参与6次计算，因为该样本中的位置点是由距离较近的8个点合成的，所以修改为重复参与6次计算。
通过上述方法，得到修改过的k-means模型，通过修改过的k-means模型，可以大大提高运算速度。
可选地，预先修改的轮廓系数模型包括:
在轮廓系数模型中增加一个数量参数，数量参数为合成位置点的重复数，将计算样本距离的方法修改为将原有的距离乘以重复数。
具体地，例如我们已经通过一定算法，将待分类数据进行了聚类。得到K组聚类结果，对于每组聚类结果中的每个向量，分别计算它们的轮廓系数。
对于其中一个向量i来说：
计算a(i)＝average(i向量到所有它属于的簇中的点的平均距离)，a(i)越小，说明样本i越应该被聚类到该簇；
计算b(i)＝min(i向量到所有它不属于的簇中的点的平均距离)，b(i)越大，说明样本i越不属于其他簇。
向量i的轮廓系数为：
在本公开实施例中，修改经典轮廓系数模型，在轮廓系数模型中增加一个重复数参数，将计算样本距离的方法修改为将原有的距离乘以重复数。例如，样本中合成位置点的重复数为8，在计算a(i)和b(i)时，向量i到其他点的距离乘以重复数8。
通过上述方法，得到修改过的轮廓系数模型。
图3是根据一示例性实施例示出的一种海量位置点聚合方法的流程示意图。
步骤S301、修改经典DBSCAN模型、K-means模型、轮廓系数模型。在上述三种模型中，加入重复数参数，将DBSCAN模型中在距离条件内累加样本数量的操作，由每次加1改为每次加上重复数，将K-means模型中计算质心时，每个样本参与一次计算修改为每个样本重复参与计算，重复参与计算的次数为重复数，将轮廓系数模型中计算样本距离的方法修改为将原有的距离乘以重复数。
步骤S302、根据经纬度划分不同的网格，将位置点根据经纬度划分到不同的网格中。
步骤S303、将网格中距离小于预设值的位置点合成一个点，作为合成位置点，将距离小于预设值的位置点的个数作为合成位置点的重复数，以合成位置点的经度、纬度、重复数生成第一样本集合，将网格中距离较近的点合成一个点，可以大大减少计算时的样本量，提升运算速度。
步骤S304、将第一样本集合输入至预先修改的DBSCAN模型进行分类，得到噪声数据和分类后生成的簇，将噪声数据去除，将分类后生成的簇合成一个新样本，作为第二样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设上限值。
步骤S305、将第二样本集合输入至预先修改的DBSCAN模型进行分类，得到噪声数据和分类后生成的簇，将噪声数据去除，将分类后生成的簇合成一个新样本，作为第三样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设下限值。
步骤S306、将第三样本集合输入至预先修改的K-means模型进行聚类运算，得到聚类结果，例如，第三样本集合中的类别个数为M，将K值由1到M分别运行k-means聚类运算，首先，令参数K＝1进行聚类运算，得到1组聚类结果，令参数K＝2进行聚类运算，得到2组聚类结果，令参数K＝3进行聚类运算，得到3组聚类结果，令参数K＝M进行聚类运算，得到M组聚类结果，总共得到1+2+3+…M组聚类结果。
步骤S307、将聚类结果输入至预先修改的轮廓系数模型，获取聚合点，计算得到的若干组聚类结果的轮廓系数，可以检查聚类结果的内聚度和分离度，从而检查聚类结果的聚类效果，轮廓系数值最大的聚类结果的聚类效果越好，将轮廓系数值最大的聚类结果对应的位置点作为聚合点。
图4是根据一示例性实施例示出的一种海量位置点聚合装置的示意图。
在一些实施例中，一种海量位置点聚合装置包括：
S401、第一获取模块，用于获取第一样本集合。
S402、第一分类模块，用于将第一样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第二样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设上限值。
S403、第二分类模块，用于将第二样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第三样本集合，其中，预先修改的DBSCAN模型中的密度参数为预设下限值。
S404、聚类模块，用于将第三样本集合输入至预先修改的K-means模型进行聚类运算，得到聚类结果。
S405、第二获取模块，用于将聚类结果输入至预先修改的轮廓系数模型，获取聚合点。
图5是根据一示例性实施例示出的一种海量位置点聚合装置的示意图。
在一些实施例中，一种海量位置点聚合装置，包括处理器51和存储有程序指令的存储器52，还可以包括通信接口53和总线54。其中，处理器51、通信接口53、存储器52可以通过总线54完成相互间的通信。通信接口53可以用于信息传输。处理器51可以调用存储器52中的逻辑指令，以执行上述实施例提供的海量位置点聚合方法。
此外，上述的存储器52中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。
存储器52作为一种计算机可读存储介质，可用于存储软件程序、计算机可执行程序，如本公开实施例中的方法对应的程序指令/模块。处理器51通过运行存储在存储器52中的软件程序、指令以及模块，从而执行功能应用以及数据处理，即实现上述方法实施例中的方法。
存储器52可包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序；存储数据区可存储根据终端设备的使用所创建的数据等。此外，存储器52可以包括高速随机存取存储器，还可以包括非易失性存储器。
本公开实施例提供了一种海量位置点聚合设备，包括上述实施例提供的海量位置点聚合的装置，包括存储器52及处理器51；
存储器52中存储有可执行程序代码；
处理器51读取可执行程序代码，运行与可执行程序代码对应的程序，以实现上述实施例提供的海量位置点聚合方法。
本公开实施例提供了一种计算机可读介质，其上存储有计算机可读指令，计算机可读指令可被处理器执行以实现上述实施例提供的海量位置点聚合方法。
上述的计算机可读存储介质可以是暂态计算机可读存储介质，也可以是非暂态计算机可读存储介质。
本领域技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，可以取决于技术方案的特定应用和设计约束条件。技术人员可以对每个特定的应用来使用不同方法以实现所描述的功能，但是这种实现不应认为超出本公开实施例的范围。技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统、装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。
本文所披露的实施例中，所揭露的方法、产品(包括但不限于装置、设备等)，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，单元的划分，可以仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另外，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例。另外，在本公开实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。
附图中的流程图和框图显示了根据本公开实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，模块、程序段或代码的一部分包含一个或一个以上用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这可以依所涉及的功能而定。框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
以上，仅为本申请较佳的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应以权利要求的保护范围为准。
Claims (4)
1.一种海量位置点聚合的方法，其特征在于，包括：
获取第一样本集合，包括：根据经纬度划分不同的网格，将位置点根据经纬度划分到不同的网格中；将网格中距离小于预设值的位置点合成一个点，作为合成位置点，将距离小于预设值的位置点的个数作为所述合成位置点的重复数，以所述合成位置点的经度、纬度、重复数生成所述第一样本集合；
将所述第一样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第二样本集合，其中，所述预先修改的DBSCAN模型中的密度参数为预设上限值，所述预先修改的DBSCAN模型包括：在DBSCAN模型中增加一个数量参数，所述数量参数为所述合成位置点的重复数，将DBSCAN模型中在距离条件内累加样本数量的操作，由每次加1改为每次加上重复数；
将所述第二样本集合输入至预先修改的DBSCAN模型进行分类，生成分类后的第三样本集合，记录所述第三样本集合中的类别个数，其中，所述预先修改的DBSCAN模型中的密度参数为预设下限值；
将所述第三样本集合输入至预先修改的K-means模型进行聚类运算，进行K-means聚类运算的次数为所述类别个数，得到聚类结果；所述预先修改的K-means模型包括：在K-means模型中增加一个数量参数，所述数量参数为所述合成位置点的重复数，将K-means模型中计算质心时，每个样本参与一次计算修改为每个样本重复参与计算，重复参与计算的次数为所述重复数；
将所述聚类结果输入至预先修改的轮廓系数模型，获取聚合点，所述预先修改的轮廓系数模型包括:在轮廓系数模型中增加一个数量参数，所述数量参数为所述合成位置点的重复数，将轮廓系数模型中计算样本距离的方法修改为将原有的距离乘以所述重复数。
2.根据权利要求1所述的方法，其特征在于，所述将所述聚类结果输入至预先修改的轮廓系数模型，获取聚合点，包括：
根据所述预先修改的轮廓系数模型对所述聚类结果分别计算轮廓系数，将轮廓系数值最大的聚类结果所对应的位置点作为聚合点。
3.一种海量位置点聚合的装置，其特征在于，包括处理器和存储有程序指令的存储器，其特征在于，所述处理器被配置为在执行所述程序指令时，执行如权利要求1至2任一项所述的海量位置点聚合的方法。
4.一种计算机可读介质，其特征在于，其上存储有计算机可读指令，所述计算机可读指令可被处理器执行以实现如权利要求1至2任一项所述的一种海量位置点聚合的方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911185717.7A CN111160385B (zh) | 2019-11-27 | 2019-11-27 | 海量位置点聚合的方法、装置、设备及存储介质 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911185717.7A CN111160385B (zh) | 2019-11-27 | 2019-11-27 | 海量位置点聚合的方法、装置、设备及存储介质 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111160385A CN111160385A (zh) | 2020-05-15 |
| CN111160385B true CN111160385B (zh) | 2023-04-18 |
Family
ID=70556163
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201911185717.7A Active CN111160385B (zh) | 2019-11-27 | 2019-11-27 | 海量位置点聚合的方法、装置、设备及存储介质 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111160385B (zh) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111881939B (zh) * | 2020-06-24 | 2021-03-09 | 东南大学 | 一种基于聚类算法的共享单车停车区布设方法 |
| CN114037854B (zh) * | 2021-11-25 | 2024-08-02 | 武汉中海庭数据技术有限公司 | 一种众包高精度地图中地面要素聚类融合方法及装置 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106709503A (zh) * | 2016-11-23 | 2017-05-24 | 广西中烟工业有限责任公司 | 一种基于密度的大型空间数据聚类算法k‑dbscan |
| CN110493221A (zh) * | 2019-08-19 | 2019-11-22 | 四川大学 | 一种基于聚簇轮廓的网络异常检测方法 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR101700340B1 (ko) * | 2012-04-06 | 2017-01-26 | 에스케이플래닛 주식회사 | 대용량 데이터의 클러스터 결과 분석 시스템 및 방법 |
| CN107103329A (zh) * | 2016-02-22 | 2017-08-29 | 阿里巴巴集团控股有限公司 | 一种数据聚类方法及装置 |
| CN108520023B (zh) * | 2018-03-22 | 2021-07-20 | 合肥佳讯科技有限公司 | 一种基于混合聚类算法的雷暴核识别及追踪方法 |
| CN109086323A (zh) * | 2018-06-28 | 2018-12-25 | 上海中通吉网络技术有限公司 | 用户家庭和工作地址的确定方法和系统 |
| CN109002858B (zh) * | 2018-07-23 | 2022-01-28 | 合肥工业大学 | 一种用于用户行为分析的基于证据推理的集成聚类方法 |
| CN110208793B (zh) * | 2019-04-26 | 2022-03-11 | 纵目科技（上海）股份有限公司 | 基于毫米波雷达的辅助驾驶系统、方法、终端和介质 |
| CN110457315A (zh) * | 2019-07-19 | 2019-11-15 | 国家计算机网络与信息安全管理中心 | 一种基于用户轨迹数据的群体聚集模式分析方法和系统 |
-
2019
- 2019-11-27 CN CN201911185717.7A patent/CN111160385B/zh active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106709503A (zh) * | 2016-11-23 | 2017-05-24 | 广西中烟工业有限责任公司 | 一种基于密度的大型空间数据聚类算法k‑dbscan |
| CN110493221A (zh) * | 2019-08-19 | 2019-11-22 | 四川大学 | 一种基于聚簇轮廓的网络异常检测方法 |
Non-Patent Citations (1)
| Title |
|---|
| 李杨等.基于DBSCAN聚类的关联函数区间参数训练算法.《第三十一届中国控制会议论文集D卷》.2012,1946-1949. * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111160385A (zh) | 2020-05-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US9390556B2 (en) | Systems and methods for generating a large scale polygonal mesh | |
| KR20160019897A (ko) | 시계열의 고속 그룹화 기법 | |
| CN109189876B (zh) | 一种数据处理方法及装置 | |
| CN110298687B (zh) | 一种区域吸引力评估方法及设备 | |
| CN111867049A (zh) | 定位方法、装置及存储介质 | |
| Raimbault et al. | Space matters: Extending sensitivity analysis to initial spatial conditions in geosimulation models | |
| CN111160385B (zh) | 海量位置点聚合的方法、装置、设备及存储介质 | |
| CN111479321B (zh) | 一种网格构建方法、装置、电子设备和存储介质 | |
| CN110795978B (zh) | 路面点云数据提取方法、装置、存储介质及电子设备 | |
| CN114386466B (zh) | 一种用于脉冲星搜寻中候选体信号挖掘的并行的混合聚类方法 | |
| CN114511679A (zh) | 点云数据处理方法、装置、设备及存储介质 | |
| CN104484600A (zh) | 一种基于改进密度聚类的入侵检测方法及装置 | |
| CN111144612B (zh) | 一种加油站位置点预测方法、装置、存储介质及终端 | |
| CN117495891B (zh) | 点云边缘检测方法、装置和电子设备 | |
| CN108055638A (zh) | 获取目标位置的方法、装置、计算机可读介质及设备 | |
| CN113486134A (zh) | 降雨量异常检测方法、装置、计算机设备及存储介质 | |
| CN111949530A (zh) | 测试结果的预测方法、装置、计算机设备及存储介质 | |
| CN112686996B (zh) | 游戏山脉地形创建方法、模型训练方法及相关装置 | |
| Purnawansyah et al. | K-Means clustering implementation in network traffic activities | |
| CN114565031B (zh) | 基于经纬度的车队识别方法、装置及计算机设备 | |
| CN116611678A (zh) | 数据处理方法、装置、计算机设备和存储介质 | |
| Carbone et al. | Relative cluster entropy for power-law correlated sequences | |
| CN116523640A (zh) | 一种基于调度反馈算法的金融信息管理系统 | |
| WO2017193554A1 (zh) | 区域聚合的方法及装置 | |
| CN115662514A (zh) | 基于融合定位的scRNA-seq数据缺失值填充方法及装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |