隨著物聯網及雲端運算科技的快速發展，串流大數據分析成為熱門的研究，其中循序行為預測、行為異常偵測與異常行為的矯正均為重要的議題。本篇論文目的在提出一個動態矯正機制，其中包含循序行為分析預測與偏異判定方法，並且提出三種規劃致動器(actuators)的演算法。本論文提出使用循序行為的回顧資料以及前瞻資料來評估其對於常態行為模式的偏異度。當評估的偏異度超過可容許範圍時，矯正機制將規劃並啟動一系列致動器，引導目標物回到正軌。對應不同的矯正方法構想，分別提出尾隨矯正演算法、跳島式矯正演算法以及平行迫近矯正演算法。
我們以加爾各答天氣資料以及模擬資料進行實驗，測試所提方法的效果、效能以及與A*演算法做比較。實驗結果顯示，本論文所提的預測式偏異分析可以有效提早偵測偏異，超前啟動矯正機制。偏異行為在動態矯正機制下，可以成功矯正回常態，並持續追蹤目標。最後三種行動規劃演算法，在規劃致動器時間以及處理高資料量上也有不錯的表現。

With the rapid development of Internet of Things and cloud computing technologies, streaming big data analysis has become a popular research, in which sequential behavior prediction, behavior anomaly detection, and anomaly correction are important issues. The purpose of this thesis is to propose a dynamic correction mechanism, which includes sequential behavior prediction and deviation detection methods, and to propose three algorithms for planning actuators that are used to correct deviation. We propose to use retrospective and prospective data of sequential behavior to evaluate the similarity and likelihood of deviation from the normative behavior pattern. When the assessed deviation exceeds a threshold, a series of actuators are planned and activated to correct the target back to the right track. The trailing correction algorithm, the island hopping correction algorithm, and the parallel progressive correction algorithm are proposed for actuators planning.
We conduct experiments with Kolkata’s weather data and simulation data to test the effectiveness and performance of the proposed method and compare it with the A* algorithm. The experimental results show that the predictive deviation detection methods can effectively detect the deviation early and activate the correction mechanism ahead of time. The deviation can be successfully corrected back to normal behaviors with the dynamic correction mechanism, and the targets can be continuously tracked. The three proposed planning algorithms also perform well in terms of the time to plan a series of correction actuators and data size.

致謝 i
摘要 ii
Abstract iii
目錄 v
圖目錄 viii
表目錄 x
公式目錄 xi
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與方法 2
1.3 研究成果 2
1.4 論文架構 3
第2章 相關研究與技術 5
2.1 串流大數據分析與預測 5
2.2 軌跡、路徑分析與預測 7
2.3 序列相似度計算 8
2.4 異常偵測與預防 10
2.5 行動規劃 12
第3章 循序行為預測式分析與動態矯正系統架構 13
3.1 系統架構 13
3.2 循序行為模式相似度分析 15
3.2.1 空間與時間最長公共子序列 15
3.2.2 STLCSS的延伸定義 16
3.3 循序行為模式的偏異偵測 18
3.3.1 行為模式回顧與前瞻預測分析 19
3.3.2 預測式偏異偵測機制 19
3.3.3 偏異度評估及回顧資料與前瞻資料的權重調整 20
3.3.3.1 線性指數權重調整 20
3.3.3.2 S型函數(sigmoid function)指數權重調整 21
3.4 動態矯正機制與預測式偏異偵測的整體流程 24
第4章 動態矯正機制之行動規劃演算法 27
4.1 偏異矯正與行動規劃問題定義 27
4.2 行動規劃矯正演算法 28
4.2.1 尾隨矯正法 28
4.2.2 跳島式矯正法 31
4.2.3 平行迫近矯正法 35
4.3 動態矯正機制與演算法 40
第5章 系統實作與效能評估 43
5.1 實驗環境 43
5.2 實驗資料 43
5.3 實驗方法 44
5.4 實驗結果 45
5.4.1 演算法矯正效果 45
5.4.2 預測式偏異偵測使用效果 47
5.4.3 預測式偏異偵測在不同序列長度不同特徵維度計算時間比較 49
5.4.4 預測式偏異偵測在不同可選擇致動器數量的比較 50
5.4.5 演算法在不同特徵維度的比較 51
5.4.6 演算法在不同使用者數量的比較 53
5.4.7 演算法與A*演算法的比較 55
5.4.8 演算法與A*演算法的未來工作 61
5.5 實驗總結 61
第6章 結論與未來工作 63
6.1 結論 63
6.2 未來工作 63
參考文獻 65

[1] Amazon Web Services (AWS) 什麼是串流資料? https://aws.amazon.com/tw/streaming-data/ (參照日期 2022/1/03)
[2] 什麼是串流數據分析. https://cloud.google.com/learn/what-is-streaming-analytics?hl=zh-tw (參照日期 2022/1/03)
[3] Amazon Kinesis Analytics. https://aws.amazon.com/tw/kinesis/analytics/ (參照日期 2022/1/03)
[4] P. Domingos and G. Hulten. “Mining high-speed data streams”. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '00), 2000, pp. 71–80. https://doi.org/10.1145/347090.347107.
[5] L. Chen, W. Wang, and Y. Yang, “An efficient dynamic neural network for predicting time series data stream,” 2020 IEEE Intl Conf. on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), pp. 625-632, 2020.
[6] A. Ed-daoudy and K. Maalmi, “Application of Machine Learning Model on Streaming Health Data Event in Real-Time to Predict Health Status Using Spark,” 2018 International Symposium on Advanced Electrical and Communication Technologies (ISAECT), ,pp. 1-4, 2018.
[7] 王宜倫(2015) 資料流(Streaming Data)技術於大數據(Big Data)之應用淺析. https://www.syscom.com.tw/ePaper_New_Content.aspx?id=456&EPID=209&TableName=sgEPArticle (參照日期 2022/1/03)
[8] X. Kong et al., “Big Trajectory Data: A Survey of Applications and Services,” in IEEE Access, vol. 6, pp. 58295-58306, 2018.
[9] H. Jeung, H. Lu, S. Sathe, and M. L. Yiu, "Managing Evolving Uncertainty in Trajectory Databases," in IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 7, pp. 1692-1705, July 2014.
[10] M. Riyadh, N. Mustapha and D. Riyadh, “Review of Trajectories Similarity Measures in Mining Algorithms,” 2018 Al-Mansour International Conference on New Trends in Computing, Communication, and Information Technology (NTCCIT), pp. 36-40, 2018.
[11] 陳昱衡(2020)，以整合式形狀與符號聚合近似法為基礎之時間序列資料分析與行為辨識。國立東華大學資訊工程學系碩士論文，花蓮市.
[12] Z. Feng and Y. Zhu, “A Survey on Trajectory Data Mining: Techniques and Applications,” in IEEE Access, vol. 4, pp. 2056-2067, 2016.
[13] X. Li, V. Ceikute, C. S. Jensen, and K. Tan, "Effective Online Group Discovery in Trajectory Databases," in IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 12, pp. 2752-2766, Dec. 2013.
[14] S. Liu, S. Wang, K. Jayarajah, A. Misra & R. Krishnan, “TODMIS: Mining communities from trajectories.” Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, pp. 2109-2118, Oct. 2013.
[15] D. Patel, C. Sheng, W. Hsu, and M. L. Lee, “Incorporating Duration Information for Trajectory Classification,” 2012 IEEE 28th International Conference on Data Engineering, pp. 1132-1143, 2012.
[16] Q. Lin, D. Zhang, K. Connelly, H. Ni, Z. Yu, and X. Zhou, “Disorientation detection by mining GPS trajectories for cognitively-impaired elders,” Pervasive and Mobile Computing, Volume 19, pp. 71-85, 2015.
[17] A. Brilingaitė, & C.S. Jensen, “Online Route Prediction for Automotive Applications,” World Congress and Exhibition on Intelligent Transport Systems and Services, Oct 2006
[18] A. D. Alowayr, L. A. Alsalooli, A. M. Alshahrani, and J. Akaichi, “A Review of Trajectory Data Mining Applications,” 2021 International Conference of Women in Data Science at Taif University (WiDSTaif ), pp. 1-6, 2021.
[19] Y. Li, K. Fu, Z. Wang, C. Shahabi, J. Ye, and Y. Liu.. “Multi-task Representation Learning for Travel Time Estimation.” In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '18). Association for Computing Machinery, New York, NY, USA, pp. 1695–1704. 2018.
[20] Y. Wang, N.J. Yuan, D. Lian, L. Xu, X. Xie, E. Chen, and Y. Rui. “Regularity and Conformity: Location Prediction Using Heterogeneous Mobility Data.” In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15). Association for Computing Machinery, New York, NY, USA, pp. 1275–1284. 2015.
[21] X. Song, Q. Zhang, Y. Sekimoto, R. Shibasaki, N.J. Yuan, and X. Xie, “Prediction and Simulation of Human Mobility Following Natural Disasters,” ACM Trans. Intell. Syst. Technol. vol 8, issue 2, Article 29, pp 1-23, Mar. 2017.
[22] T.M.T. Do and D. Gatica-Perez. “Contextual conditional models for smartphone-based human mobility prediction”. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing (UbiComp '12). Association for Computing Machinery, New York, NY, USA, pp 163–172, 2012.
[23] D.J. Berndt and J.Clifford. “Using dynamic time warping to find patterns in time series.” In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (AAAIWS'94). AAAI Press, pp 359–370. 1994.
[24] L. Chen and R. Ng, “On the marriage of Lp-norms and edit distance,” In Proceedings of the Thirtieth international conference on Very large databases (VLDB '04) Volume 30. pp792–803, 2004.
[25] L. Chen, M.T. Özsu, and V. Oria. “Robust and fast similarity search for moving object trajectories.” In Proceedings of the 2005 ACM SIGMOD international conference on Management of data (SIGMOD '05). Association for Computing Machinery, New York, NY, USA, pp. 491–502, 2005.
[26] M. Vlachos, G. Kollios, and D. Gunopulos, “Discovering similar multidimensional trajectories,” Proceedings 18th International Conference on Data Engineering, pp. 673-684, 2002.
[27] 最長公共子序列-維基百科. https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90 %E5%BA%8F%E5%88%97 (參照日期 2022/09/20)
[28] G. Soleimani, & M. Abessi, “DLCSS: A new similarity measure for time series data mining.” Engineering Applications of Artificial Intelligence. 92. vol 14. 2020.
[29] L.J. Latecki, & A. Lazarevic, & D. Pokrajac, “Outlier Detection with Kernel Density Functions”, Machine Learning and Data Mining in Pattern Recognition, 5th International Conference, pp. 61-75, 2007..
[30] Hao, W. U., et al. “Statistical outlier processing and dosimetric effect in Varian Rapid Plan model verification.” Chinese Journal of Medical Physics, 2016.
[31] W. Dai, C. Zhang, X. Su, and S. Cao, “Trajectory Outlier Detection Based on DBSCAN and Velocity Entropy,” 2020 International Conferences on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) and IEEE Congress on Cybermatics (Cybermatics), pp. 550-557, 2020.
[32] C. Wang, Z. Zhao, L. Gong, L. Zhu, Z. Liu, and X. Cheng, “A Distributed Anomaly Detection System for In-Vehicle Network Using HTM,” in IEEE Access, vol. 6, pp. 9091-9098, 2018.
[33] M. Solaimani, M. Iftekhar, L. Khan, B. Thuraisingham, and J. B. Ingram, “Spark-based anomaly detection over multi-source VMware performance data in real-time,” 2014 IEEE Symposium on Computational Intelligence in Cyber Security (CICS), Orlando, FL, pp. 1-8, 2014.
[34] J. Zhang, X. Zhu, Y. Yue, and P. W. H. Wong, “A real-time anomaly detection algorithm/or water quality data using dual time-moving windows,” 2017 Seventh International Conference on Innovative Computing Technology (INTECH), Luton, pp. 36-41,2017.
[35] J. Wang, C. Liu, M. Zhu, P. Guo, and Y. Hu, “Sensor Data Based System-Level Anomaly Prediction for Smart Manufacturing,” 2018 IEEE International Congress on Big Data (BigData Congress), San Francisco, CA, pp. 158-165, 2018.
[36] Y. Kitagawa, T. Ishigoka, and T. Azumi, “Anomaly Prediction Based on k-Means Clustering for Memory-Constrained Embedded Devices,” 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA), Cancun, pp. 26-33, 2017.
[37] K. Raghuraman, M. Senthurpandian, M. Shanmugasundaram, Bhargavi, and V. Vaidehi, “Online Incremental Learning Algorithm for anomaly detection and prediction in health care,” 2014 International Conference on Recent Trends in Information Technology, Chennai, pp. 1-6, 2014.
[38] wayback machine. https://web.archive.org/web/20191003035423/http://www.businessdiction ary.com/definition/action-plan.html (參照日期 2022/09/20)
[39] M. Hintzche and E. Heinrichs, “Traffic Noise and Noise Action Planning in Germany,” 2018 Joint Conference - Acoustics, pp. 1-5, 2018.
[40] L. Chen et al., “Effects of Transcutaneous Vagus Nerve Stimulation (tVNS) on Action Planning: A Behavioural and EEG study,” in IEEE Transactions on Neural Systems and Rehabilitation Engineering, pp. 625-632, 2020.
[41] Paul Masson, Rotations in Higher Dimensions. https://analyticphysics.com/Higher%20Dimensions/Rotations%20in%20Higher%20Dimensions.htm (參照日期 2022/09/20)
[42] Suman Dey, Kaggle Temperature and Humidity of Kolkata from 2015-2020. https://www.kaggle.com/datasets/sumandey/temperature-and-humidity-of-kolkata-from-20152020 (參照日期 2022/09/20)