在都會城市之中，有許多設施需要建設新設站點來輔助現有的不足。在本研究中以處理犯罪案件為主軸，目的為以建立新設警局為案例當作研究對象。本研究會使用道路網結構，犯罪資料以及現有警局站點，目標推薦使用者可以減少交通距離成本的新設警局站點位置。此論文的實驗模型主要可以分成四個主軸：(a)DBSCAN尋找潛在的可能犯罪熱點(b)透過網路偵測將浩大的路網分割成許多較小的網路去作探討(c) 設計一個新的緊密度的指標，去尋找距離犯罪案件近的網路節點(d)設計一個貪婪距離最小化的演算法去依序建立所需的警局。找出最佳的建設地點是一個NP-hard的問題。實驗結果顯示出我們的方法可以在可接受時間內得到近似最佳地點的解，且與其他比較方法在減少交通成本上提高至少15%以上的效率。本方法可用於各種需考慮交通成本的城市應用如救護站點建立或消防栓地點設置。

In urban area, there are a lot of services and stations need to be deployed. In our research we consider establishing new police stations as a case study. Given the number of stations we plan to construct, our goal is recommending locations as the deploy placements so that the transportation cost could be efficiently reduced. We consider and combine road network, existing stations, and crime event data to develop our data-driven approach. Our model can be divided four components. First, we adopt the DBSCAN clustering method to find the hot spots of crime events. Second, we do community detection for road network to split the huge road network to several smaller communities. Third, we propose a refined closeness centrality to identify a good candidate location in each community. Finally, we develop a greed-based distance minimization to establish stations. Finding the best set of deployed locations is a NP-hard problem. The experimental results verify that our solution is not too far away from the optimal result in small dataset and show the efficiency and effectiveness of our proposed method in large crime dataset.

[1] Albert, R., & Barabási, A.-L. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1), 47-97, 2002.
[2] Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008.
[3] Chen, L., Zhang, D., Pan, G., Ma, X., Yang, D., Kushlev, K., . . . Li, S. Bike sharing station placement leveraging heterogeneous urban open data. Paper presented at the Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Osaka, Japan, 2015.
[4] Deng, K., Sadiq, S., Zhou, X., Xu, H., Fung, G. P. C., & Lu, Y. On Group Nearest Group Query Processing. IEEE Transactions on Knowledge and Data Engineering, 24(2), 295-308, 2012.
[5] Ester, M., Kriegel, H.-P., #246, Sander, r., & Xu, X. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. Paper presented at the Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, Portland, Oregon, 1996.
[6] Freeman, L. C. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(1), 35-41, 1977.
[7] Freeman, L. C. Centrality in social networks conceptual clarification. Social Networks, 1(3), 215-239, 1978.
[8] Hailong, C., & Chunli, L. Research and application of cluster analysis algorithm. Paper presented at the Proceedings of 2013 2nd International Conference on Measurement, Information and Control, 2013.
[9] Hsieh, H.-P., Li, C.-T., & Lin, S.-D. Estimating Potential Customers Anywhere and Anytime Based on Location-Based Social Networks, Cham, 2015.
[10] Hsieh, H.-P., Lin, S.-D., & Zheng, Y. Inferring Air Quality for Station Location Recommendation Based on Urban Big Data. Paper presented at the Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 2015.
[11] Johnson, D. B. A Note on Dijkstra's Shortest Path Algorithm. J. ACM, 20(3), 385-388, 1973.
[12] L. H, U., Zhao, H. J., Yiu, M. L., Li, Y., & Gong, Z. Towards Online Shortest Path Computation. IEEE Transactions on Knowledge and Data Engineering, 26(4), 1012-1025, 2014
[13] Lam, A. Y. S., Yiu-Wing, L., & Xiaowen, C. Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions. IEEE Transactions on Smart Grid, 5(6), 2846-2856, 2014.
[14] Li, Y., Zheng, Y., Ji, S., Wang, W., U, L. H., & Gong, Z. Location selection for ambulance stations: a data-driven approach. Paper presented at the Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, Washington, 2015.
[15] Lin, K., Wang, J., Zhang, Z., Chen, Y., & Xu, Z. Adaptive location recommendation algorithm based on location-based social networks. Paper presented at the 2015 10th International Conference on Computer Science & Education (ICCSE), 2015, 22-24 July 2015.