臺灣博碩士論文加值系統

隨著無線通訊網路、感測裝置與網際網路等相關技術的成熟，資通產業之發展已從基礎設施和理論逐漸轉移至現實世界的無所不在與人們生活息息相關的應用，例如物聯網、感測網路和智慧城市，加上大數據技術在處理與分析巨量資料的強力支援，帶來了許多新的研究機會和應用問題，特別是針對物聯網方面。本論文研究目的在於解決物聯網與感測網路上兩個根本且重要的問題。首先，如何從給定感測器所蒐集到之歷史數據，加上從外在異質性社群與環境數據，來準確推估地理空間中任意地點之感測器即時數值，特別是在城市地區極為稀疏的感測器分布條件下。其次，如果相關公司或政府機構需要部署新的感測器來提高感測器值監測與推估之品質，如何讓機器從偌大的都市空間中自動學習並決定新感測器最佳的部署地點？

此二問題是城市計算和感測網路大數據分析領域中，非常重要且具有挑戰性的問題。雖然感測器被安裝在城市物聯網中提供即時之環境監測數據，然而真實世界往往絕大多數的地點（超過99％）並沒有被安裝感測器，這使得地理空間中幾乎所有地點的環境監測數據是沒有數值的，這種資料稀疏之問題也導致我們無法有效地使用傳統機器學習訓練模型，來推估這些無感測器設置之地點的環境監測數值。在本論文中，我們以空氣品質之環境感測為例，考慮空氣品質指數(Air Quality Index)為感測器所測得之環境數據，並以空氣品質監測站為感測器，我們的目標是設計出兼具效果、效率且可拓展之演算法，來解決上述的兩個研究問題－(1)準確推估沒有監測站之地點的空氣品質指數，(2)推薦新的空氣品質監測站之佈署地點，使得空氣品質推估之準確率提升得以極大化。

在本論文研究中，我們開發了一組廣義半監督式感測器數值推估模型，它不僅能有效地學習感測器之空氣品質指數與城市中異質性空間和時間特徵 (這些特徵包括氣象資料、人群移動模式、道路網路的結構、以及不同類型的地點資訊等) 之關聯性，更能準確預測地理空間中的任意地點之空氣品質。此外，為使得新的空氣品質感測器之佈署效益能達到最大化，我們開發出一熵最小化模型，以此推薦新的感測器該被設置在哪些地點，才能使得空氣品質推估之準確率能有最大的提升。實驗上，我們使用北京市的巨量空氣品質數據來驗證我們所開發之感測器數值推估與新感測器地點推薦模型，結果顯示出我們所提出的方法在準確率、時間效率與可擴展性等各方面，均能以極為顯著之優勢勝過當前最佳的方法，證明了我們提出的模型具有極大之潛力，不僅為新世代感測器之大數據分析解決實務上感測數據稀疏之根本問題，並可作為後續各種物聯網應用的絕佳基礎。

With the gradual maturity of the persuasive techniques for networking, sensors, and Internet, the paradigm of information and communication technology has shifted from fundamental facilities and theories to real-world ubiquitous applications, such as urban computing, sensor networks, and smart cities. Along with the power of big data techniques, such advances also bring new research opportunities and practical problems, especially for Internet of Things (IoT). This thesis aims to answer two questions. First, how to infer real-time sensor value of any arbitrary location given the environmental data and the sensor data collected from monitoring stations that are extremely sparse in urban areas. Second, if the government agency needs to deploy a number of new sensors to improve the quality of sensor value inference, how to automatically learn and determine the best locations to fulfill such purpose? These two problems are very essential for urban computing and big sensor data analysis because sensors will be mounted in urban areas in the future era of Internet of Things, and are considerably challenging since for most of the locations (more than 99%) we do not have any sensor data to train a model from. In this thesis, by considering air quality indices as sensor values and treating air-quality monitoring stations as sensors, we aim to solve the two research problems in an effective, efficient, and scalable manner. We develop a general-purpose semi-supervised inference model, which is capable of not only intelligently learning to correlation between air quality values and heterogeneous spatial and temporal features of city dynamics, including meteorology, human mobility, structure of road networks, and point of interests (POIs), but also accurately predicting the air quality values of arbitrary locations without monitoring stations placed ever. In addition, to facilitate the cost-effective deployment of new sensors, we devise an entropy-minimization model to efficiently recommend the geographical locations such that new sensors established there can lead to the maximum improvement of air quality inference accuracy. We evaluate the proposed models using a huge-scale air quality data in Beijing city. Experimental results exhibit a set of clear advantages over a series of state-of-the-art and commonly used methods for both tasks, and suggest the models have superior potential for applications for current big sensor data analysis and the upcoming era of Internet of Things.

Chapter 1 Introduction 1
1.1. Motivation and Impacts 1
1.2. Overview and Problem Statements 4
1.3. Main Contributions 7
Chapter 2 Urban Big Data and Features 9
Chapter 3 Related work 12
3.1. Urban Computing for Environment and Planning 12
3.2. Inferring Unobserved Air Quality 14
3.3. Sensor Deployment Strategies 16
3.4. Location Recommendation and Prediction 17
Chapter 4 Inferring Arbitrary Air Quality 20
4.1. AQI Affinity Graph 21
4.2. Affinity-based AQI Inference 25
Chapter 5 Building Measurement Stations 31
5.1. Greedy-based Entropy Minimization 31
Chapter 6 Experiments 35
6.1. The Effectiveness of AQInf 35
6.2. The Effectiveness of GEM 42
Chapter 7 Conclusions 50
Bibography 51

[1]X. Chen, Y. Zheng, Y. Chen, Q. Jin, W. Sun, E. Chang, and W. Y. Ma. 2014. Indoor air quality monitoring system for smart buildings. In Proceedings of the 16th ACM International Conference on Ubiquitous Computing.
[2]T. H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.), MIT Press.
[3]S. Donald. A two-dimensional interpolation function for irregularly-spaced data. In Proc. of the National Conference. pp. 517–524. 1968.
[4]S. Devarakonda, P. Sevusu, H. Liu, R. Liu, L. Iftode, and B. Nath. 2013. Real-time air quality monitoring through mobile sensing in metropolitan areas. In Proceeding of the 2nd ACM SIGKDD International Workshop on Urban Computing.
[5]A. V. Donkelaar, R. V. Martin, and R. J. Park (2006), Estimating ground-level PM2.5 using aerosol optical depth determined from satellite remote sensing, J. Geophys. Res., 111, D21201.
[6]W. Du, Z. Xing, M. Li, B. He, L. H. C. Chua, and H. Miao. Optimal sensor placement and measurement of wind for water quality studies in urban reservoirs. In Proc. of IEEE International Symposium on Information Processing in Sensor Networks ISPN, 2014.
[7]D. Erdös, V. Ishakian, A. Lapets, E. Terzi, and A. Bestavros. The filter-placement problem and its application to minimizing information multiplicity. In Proc. VLDB 2012.
[8]J. Froehlich, J. Neumann, and N. Oliver. 2009. Sensing and predicting the pulse of the city through shared bicycling. In Proceedings of the 21st International Joint Conference on Artificial Intelligence. 1420– 1426.
[9]Y. Ge, H. Xiong, A. Tuzhilin, K. Xiao, M. Gruteser, and M. Pazzani. 2010. An energy-efficient mobile recommender system. In Proceedings of 16th SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 899–908.
[10]A. Guehnemann, R. P. Schaefer, K. U. Thiessenhusen, and P. Wagner. 2004. Monitoring Traffic and Emissions by Floating Car Data. Institute of Transport Studies, Australia.
[11]D. Hasenfratz, O. Saukh, S. Sturzenegger, and L. Thiele. Participatory Air Pollution Monitoring Using Smartphones. In the 2nd International Workshop on Mobile Sensing.
[12]H.-P. Hsieh, and C.-T. Li. Estimating Potential Customers Anywhere and Anytime on Location-based Social Networks. The 30th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases 2015.
[13]H.-P. Hsieh and C.-T. Li. Mining and Planning Time-aware Routes Using Location Check-in Data. ACM International Conference on Knowledge and Information Management (CIKM''14), 2014.
[14]H.-P. Hsieh, C.-T. Li and S.-D. Lin. Measuring and Recommending Time-Sensitive Routes from Location-based Data. ACM TIST 2014.
[15]H.-P. Hsieh and C.-T. Li. Constructing Routes with User Preference from Location Check-in Data. ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp 2013), 2013.
[16]H.-P. Hsieh, C.-T. Li and X. Gao. T-gram: a Time-aware Language Model to Predict Human Mobility. AAAI International Conference on Web and Social Media (ICWSM''15), 2015.
[17]H.-P. Hsieh, S.-D. Lin and Y. Zheng. Inferring Air Quality for Station Location Recommendation Based on Urban Big Data. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD''15). 2015.
[18]J. Hooyberghs, C. Mensink, G. Dumont, F. Fierens, O. Brasseur (2005). Aneural network forecast for daily average PM10 concentrations in Belgium. Atmospheric Environment 39 (2005) 3279-3289.
[19]Y. Jiang, K. Li, L. Tian, R. Piedrahita, X. Yun, O. Mansata, Q. Lv, R. P. Dick, M. Hannigan, and L. Shang. Maqs: A personalized mobile sensing system for indoor air quality. In Proc. of UbiComp 2011.
[20]D. Karamshuk, A. Noulas, S. Scellato, V. Nicosia, and C. Mascolo. Geo-spotting: mining online location-based services for optimal retail store placement. In Proc. of KDD 2013.
[21]A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen, and C. Faloutsos. Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks. Journal of Water Resources Planning and Management, 134(6), 2008.
[22]A. Krause, R. Rajagopal, A. Gupta, and C. Guestrin. Simultaneous Optimization of Sensor Placements and Balanced Schedules. IEEE Transactions on Automatic Control, 2011.
[23]L. N. Lamsal, R. V. Martin, A. V. Donkelaar, M. Steinbacher, E. A. Celarier, E. Bucsela, E. J. Dunlea, and J. P. Pinto (2008), Ground-level nitrogen dioxide concentrations inferred from the satellite-borne Ozone Monitoring Instrument, J. Geophys. Res., 113, D1630.
[24]Wei-Zen Lu, Wen-Jian Wang (2005). Potential assessment of the “support vector machine” method in forecasting ambient air pollutant trends. Chemosphere 59: 693-701.
[25]B. Liu, Y. Fu, Z. Yao, and H. Xiong. Learning Geographical Preferences for Point-of-Interest Recommendation. ACM KDD 2013.
[26]X. Liu, Y. Liu, K. Aberer, and C. Miao. Personalized point-of-interest rec-ommendation by mining users’ preference transition. In ACM CIKM 2013.
[27]S. Ma, Y. Zheng, and O. Wolfson. 2013. T-Share: A large-scale dynamic taxi ridesharing service. In Proceedings of IEEE International Conference on Data Engineering.
[28]R. V. Martin. Satellite remote sensing of surface air quality, Atmospheric Environment (2008), doi:10.1016.
[29]A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti. Where next: a location predictor on trajectory pattern mining. ACM KDD 2009.
[30]H. Niska, T. Hiltunen, A.Karppinen, J. Ruuskanen, and M. Kolehmainen (2004). Evolving the neural network model for forecasting air pollution time series. Engineering Applications of Artificial Intelligence 17, 159-167.
[31]A. Noulas, S. Scellato, N. Lathia, and C. Masolo. Mining User Mobility Features for Next Place Prediction in Location-based Services. In IEEE ICDM 2012.
[32]M. A. Oliver and R. Webster. Kriging: a method of interpolation for geographical information system. INT. J. Geographical Information Systems, VOL. 4, No. 3, 313-332, 1990.
[33]P. Perez, R. Palacios and A. Castillo (2004). Carbon Monoxide Concentration Forecasting in Santiage, Chile. Journal of the air and waste management association 54:908-913. ISSN 1047-3289. 2004.
[34]M. Pourali and A. Mosleh. A Functional Sensor Placement Optimization Method for Power Systems Health Monitoring, IEEE Transactions on Industrial Applications, 49(4), 2013.
[35]R. K. Rana, C. T. Chou, S. S. Kanhere, N. Bulusu, and W. Hu. 2013. Ear-phone: A context-aware noise mapping using smart phones. In eprint arXiv:1310.4270.
[36]C. Ratti, S. Sobolevsky, F. Calabrese, C. Andris, J. Reades, M. Martino, R. Claxton, and S. H. Strogatz. 2010. Redrawing the map of Great Britain from a network of humani. PLoS ONE 5, 12.
[37]S. Rinzivillo, S. Mainardi, F. Pezzoni, M. Coscia, D. Pedreschi, and F. Giannotti. 2012. Discovering the geographical borders of human mobility. K unstl Intell 26, 253–260.
[38]A. Sadilek, H. Kautz, and J. P. Bigham. Finding your friends and follow-ing them to where you are. ACM WSDM 2012.
[39]J.S. Scire, D.G. Strimaitis and R.J. Yamartino, 2000b: User’s Guide for the CALPUFF Dispersion Model, (Version 5.0), Earth Tech, Inc.
[40]S. Silvia, B. Ostermaier, and A. Vitaletti. 2008. First experiences using wireless sensor networks for noise pollution monitoring. In Proceedings of the Workshop on Real-World Wireless Sensor Networks. ACM, 61–65.
[41]K. Watkins, B. Ferris, A. Borning, S. Rutherford, and D. Layton. 2011. Where is my bus? Impact of mobile real-time information on the perceived and actual wait time of transit riders. Transportation Research Part A 45, 839–848.
[42]S. Vardoulakis, B. E. A. Fisher, K. Pericleous, N. Gonzalez-Flesca. Modelling air quality in street canyons: a review. Atmospheric Environment 37 (2003) 155-182.
[43]M. Ye, P. Yin, W.-C. Lee, and D.-L. Lee. Exploiting geographical influence for collaborative point-of-interest recommendation. ACM SIGIR 2011.
[44]J. Yuan, Y. Zheng, L. Zhang, X. Xie, and G. Sun. 2011. Where to find my next passenger? In Proceedings of 13th ACM International Conference on Ubiquitous Computing. ACM, 109–118.
[45]N. J. Yuan, Y. Zheng, L. Zhang, and X. Xie. 2014. T-Finder: A recommender system for finding passengers and vacant taxis. IEEE Transactions on Knowledge and Data Engineering.
[46]Q. Yuan, G. Cong, Z. Ma, A. Sun, and N. M. Thalmann. Time-aware point-of-interest recommendation. ACM SIGIR 2013.
[47]Y. Zheng, F. Liu, H- P. Hsieh, U-Air: When Urban Air Quality Inference Meets Big Data. In Proc. of KDD 2013.
[48]Y. Zheng, L. Capra, O. Wolfson, H. Yang. Urban Computing: concepts, methodologies, and applications. ACM Transaction on Intelligent Systems and Technology (ACM TIST). 5(3), 2014.
[49]Y. Zheng, X. Chen, Q. Jin, Y. Chen, X. Qu, X. Liu, E. Chang, W-Y. Ma, Y. Rui, W. Sun. A Cloud-Based Knowledge Discovery System for Monitoring Fine-Grained Air Quality. MSR-TR-2014-40.
[50]X. Zhu, Z. Ghahramani and J. Lafferty. Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. ICML 2003.
[51]J. Zimmerman, A. Tomasic, C. Garrod, D. Yoo, C. Hiruncharoenvate, R. Aziz, N. R. Thiruvengadam, Y. Huang, and A. Steinfeld. 2011. Field trial of Tiramisu: Crowd-sourcing bus arrival times to spur co-design. In Proceedings of the 2011 Annual Conference on Human Factors in Computing Systems. ACM, 1677–1686.