跳到主要內容

臺灣博碩士論文加值系統

(44.201.97.0) 您好!臺灣時間:2024/04/19 15:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蔡宜真
研究生(外文):Yi-Chen Tsai
論文名稱:運用時空關係於漸進式移動型樣探勘
論文名稱(外文):Exploring Spatiotemporal Relationships for Incremental Movement Pattern Mining
指導教授:蔡曉萍蔡曉萍引用關係
口試委員:胡誌麟鄧維光吳國光
口試日期:2016-07-27
學位類別:碩士
校院名稱:國立中興大學
系所名稱:通訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:中文
論文頁數:56
中文關鍵詞:軌跡資料探勘時空關係漸進式移動型樣探勘
外文關鍵詞:Trajectory MiningSpatiotemporal RelationshipsIncremental Mining
相關次數:
  • 被引用被引用:0
  • 點閱點閱:158
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著無線網路、定位技術和穿戴式裝置日益普及,蒐集軌跡資料變得更加容易,現在人們可以很輕鬆地記錄自己每天的移動路徑。所以從人們日常的移動行為來做一些深入的探勘也變成現在重要的一個議題。
軌跡型樣探勘(Trajectory Pattern Mining)主要目的就是從軌跡序列資料中挖掘出隱藏在其中特殊、重要且具代表性的移動行為和特徵(feature),而Probabilistic Suffix Tree (PST)是軌跡型樣探勘常用的技術之一。許多軌跡資料探勘在探勘時經常會將軌跡所在的地理空間切割成網格,再將物件移動軌跡的經緯度座標點序列轉成網格序列,以利軌跡型樣的探勘。但這樣的方法可能面臨以下四個問題: 一、網格大小與切割位置直接影響探勘結果的有效性,不易決定;二、傳統網格的形狀多半是正方形或六邊形等,不適合表達路網中長條狀道路;三、網格數量可能很大,需要耗費大量的CPU或記憶體來進行探勘;四、累積的軌跡資料量可能很龐大,導致傳統演算法的計算時間增加,甚至無法執行;基於上述問題,本論文基Incremental Trajectory data Mining演算法,提出Exploring Spatiotemporal relationships for Incremental Movement Pattern Mining (incPST_STR)演算法框架,依據個人的移動習慣,先用縱向的合併方法,動態決定每個區域的網格大小,找出具代表性的重要網格,再找出具有時間與空間上前後有著緊密關係的網格,進一步進行橫向的合併,將人們規律行走且鮮少變化的路段合併,以節省探勘的計算成本以及記憶體空間,接著,我們採取Incremental Mining的策略,將累積的資料分批探勘,再將結果合併,來因應不斷累加的軌跡資料。
為驗證incPST_STR演算法框架的效能,我們於電腦平台實作incPST_STR演算法框架和傳統PST建置演算法,經實驗證實,incPST_STR演算法框架克服傳統PST建置演算法的限制,可以有效控制每次探勘的計算成本,因為incPST_STRSTR演算法框架可動態調整網格的顆粒粗細,使探勘所得的移動型樣更多更有效。


中文摘要 i
第1章 緒論 1
第2章 相關研究 3
2.1 序列型樣探勘( Sequence Pattern Mining ) 3
2.2 Probabilistic Suffix Tree (PST) 4
2.2.1 原始軌跡資料和序列資料(Trajectory Sequence Data)轉換 5
2.2.2 PST建置演算法 8
第3章 運用時空關係於漸進式移動型樣探勘 11
3.1 傳統PST的問題與我們提出的策略 11
3.1.1 影響PST tree建置效能的主要因素 11
3.1.2 傳統PST的問題與我們提出的策略 12
3.2 運用時空關係於漸進式移動型樣探勘之架構 15
3.3 PSTSTR 建置演算法 22
3.3.1" PSTSTR" : Vertical Merge Algorithm and Horizontal Merge Algorithm 26
3.3.2 merge2GTs algorithm 33
3.3.3 merge2Horizontal Matrix algorithm 35
3.4 PST Tree Merge 36
3.4.1 Basic Operation of PST Tree Merge 37
3.4.2 條件機率計算 39
第4章 實驗 48
4.1 實驗環境 48
4.2 實驗結果 48
4.2.1 測試有做Merge的PST與傳統PST的計算時間比較 48
4.2.2 比較只做Vertical Merge algorithm 和 PSTSTR的PST計算時間 49
4.2.3 IncPSTSTR與PSTSTR計算時間比較 50
4.2.4 測試Vertical Merge algorithm PST 和 PSTSTR的label數量比較 51
4.2.5 測試Vertical Merge algorithm PST和PSTSTR的Node數量比較 52
第5章 結論 54
參考文獻 55



[1] Paul Bieganski, John Ned1, John V. Cadis, Ernest E Retzel, “Generalized Suffix Trees for Biological Sequence Data: Applications and Implementation, ” System Sciences, 1994. Proceedings of the Twenty-Seventh Hawaii International Conference on , vol.5, no., pp.35-44, 4-7 Jan. 1994.
[2]Zhong, W.; Altum, G.; Harrison, R.; Tai, P.C.; Pan, Y.; , "Mining protein sequence motifs representing common 3D structures," Computational Systems Bioinformatics Conference, 2005. Workshops and Poster Abstracts. IEEE , vol., no., pp. 215- 216, 8-11 Aug. 2005.
[3] Demiriz, A.; , "webSPADE: a parallel sequence mining algorithm to analyze web log data," Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on , vol., no., pp. 755- 758, 2002.
[4]Man Yat Lo; Lucas, S.M.; , "Evolving Musical Sequences with N-Gram Based Trainable Fitness Functions," Evolutionary Computation, 2006. CEC 2006. IEEE Congress on , vol., no., pp.601-608, 0-0 0.
[5]Greenspan, H.; Goldberger, J.; Mayer, A.; , "Probabilistic space-time video modeling via piecewise GMM," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.26, no.3, pp.384-396, March 2004.
[6]Wang, Chong; Wang, Yanqing; , "Discovering consumer''s behavior changes based on purchase sequences," Fuzzy Systems and Knowledge Discovery (FSKD), 2012 9th International Conference on , vol., no., pp.642-645, 29-31 May 2012.
[7] Ming-Syan Chen; Jong Soo Park; Yu, P.S.; , "Efficient data mining for path traversal patterns," Knowledge and Data Engineering, IEEE Transactions on , vol.10, no.2, pp.209-221, Mar/Apr 1998.
[8] Dianhui Wang; Nung Kion Lee; Dillon, T.S.; , "Data mining for building neural protein sequence classification systems with improved performance," Neural Networks, 2003. Proceedings of the International Joint Conference on , vol.3, no., pp. 1746- 1751 vol.3, 20-24 July 2003.
[9] de Souza Rodrigues, T.; Cardoso, F.C.; Ribeiro Teixeira, S.M.; Oliveira, S.C.; Braga, A.P.; , "Protein Classification with Extended-Sequence Coding by Sliding Window," Computational Biology and Bioinformatics, IEEE/ACM Transactions on , vol.8, no.6, pp.1721-1726, Nov.-Dec. 2011.
[10]Jingke Xi; , "Outlier Detection Algorithms in Data Mining," Intelligent Information Technology Application, 2008. IITA ''08. Second International Symposium on , vol.1, no., pp.94-97, 20-22 Dec. 2008.
[11] Koufakou, A.; Secretan, J.; Reeder, J.; Cardona, K.; Georgiopoulos, M.; , "Fast parallel outlier detection for categorical datasets using MapReduce," Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on , vol., no., pp.3298-3304, 1-8 June 2008.
[12] Zhipeng Cai; Lizhe Xu; Yi Shi; Salavatipour, M.R.; Goebel, R.; Guohui Lin; , "Using Gene Clustering to Identify Discriminatory Genes with Higher Classification Accuracy," BioInformatics and BioEngineering, 2006. BIBE 2006. Sixth IEEE Symposium on , vol., no., pp.235-242, 16-18 Oct. 2006.
[13] Nagar, A.; Al-Mubaid, H.; , "Using path length measure for gene clustering based on similarity of annotation terms," Computers and Communications, 2008. ISCC 2008. IEEE Symposium on , vol., no., pp.637-642, 6-9 July 2008.
[14]Chen, X.; Murphy, R.F.; , "Location proteomics: determining the optimal grouping of proteins according to their subcellular location patterns as determined from fluorescence microscope images," Signals, Systems and Computers, 2004. Conference Record of the Thirty-Eighth Asilomar Conference on , vol.1, no., pp. 50- 54 Vol.1, 7-10 Nov. 2004.
[15] Chih-Chieh Hung; Wen-Chih Peng; , "A Storage Management for Mining Object Moving Patterns in Object Tracking Sensor Networks," Web Intelligence and Intelligent Agent Technology Workshops, 2006. WI-IAT 2006 Workshops. 2006 IEEE/WIC/ACM International Conference on , vol., no., pp.252-258, Dec. 2006.
[16] Gaol, F.L., "Exploring the Pattern of Habits of Users Using Web log Squential Pattern," Advances in Computing, Control and Telecommunication Technologies (ACT), 2010 Second International Conference on , vol., no., pp.161-163, 2-3 Dec. 2010.
[17] Chih-Chin Liu; Jia-Lien Hsu; Chen, A.L.P.; , "Efficient theme and non-trivial repeating pattern discovering in music databases," Data Engineering, 1999. Proceedings., 15th International Conference on , vol., no., pp.14-21, 23-26 Mar 1999.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top