EBSCAN: An Entanglement-based Algorithm for Discovering Dense Regions in Large Geo-social Data Streams with Noise
EBSCAN: An Entanglement-based Algorithm for Discovering Dense Regions in Large Geo-social Data Streams with Noise
复制标题
DOI：
10.1145/2830657.2830661
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Shohei Yokoyama;Ágnes Bogárdi-Mészöly;H. Ishikawa
中科院分区：
文献类型：
--
作者：
Shohei Yokoyama;Ágnes Bogárdi-Mészöly;H. Ishikawa
社交网络服务在全球定位系统（GPS）启用的手持设备上的显着增长产生了大量的地理参考大数据。给定一个大型空间数据集，挑战是从数据集中有效发现密集区域。茂密的地区可能是城市中最吸引人的地区或城镇最危险的地区。解决此问题的解决方案在许多应用程序中可能很有用，包括营销，旅游业和社会研究。基于密度的聚类方法（例如DBSCAN）通常用于此目的。然而，当前的空间聚类方法强调了密度，同时忽略了从地理特征获得的人类行为。在本文中，我们提出了EBSCAN，它基于基于纠缠方法的新思想。我们的方法不仅考虑了空间信息，还考虑了从地理特征得出的人类行为。另一个问题是，诸如DBSCAN之类的竞争方法具有两个输入参数。因此，很难确定最佳值。 EBSCAN仅需要一个直观的参数TOFAR才能发现密集的区域。最后，我们使用玩具示例和实际数据集评估了所提出方法的有效性。我们的实验获得的结果揭示了EBSCAN的特性，并表明它比竞争对手快10倍。
The remarkable growth of social networking services on global positioning system (GPS)-enabled handheld devices has produced enormous amounts of georeferenced big data. Given a large spatial dataset, the challenge is to effectively discover dense regions from the dataset. Dense regions might be the most attractive area in a city or the most dangerous zone of a town. A solution to this problem can be useful in many applications, including marketing, tourism, and social research. Density-based clustering methods, such as DBSCAN, are often used for this purpose. Nevertheless, current spatial clustering methods emphasize density while neglecting human behavior derived from geographical features. In this paper, we propose EBSCAN, which is based on the novel idea of an entanglement-based approach. Our method considers not only spatial information but also human behavior derived from geographical features. Another problem is that competing methods such as DBSCAN have two input parameters. Thus, it is difficult to determine optimal values. EBSCAN requires only a single intuitive parameter, tooFar, to discover dense regions. Finally, we evaluate the effectiveness of the proposed method using both toy examples and real datasets. Our experimentally obtained results reveal the properties of EBSCAN and show that it is >10 times faster than the competitor.