Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/91836
DC FieldValueLanguage
dc.contributor蔡曉萍zh_TW
dc.contributor.authorYi-Chen Luen_US
dc.contributor.author盧釔辰zh_TW
dc.contributor.other通訊工程研究所zh_TW
dc.date2014zh_TW
dc.date.accessioned2015-12-11T07:30:50Z-
dc.identifier.citation參考文獻 [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.zh_TW
dc.identifier.urihttp://hdl.handle.net/11455/91836-
dc.description.abstract軌跡型樣探勘(Trajectory Pattern Mining) 主要目的就是從軌跡序列資料中挖掘出隱藏其中的特殊、重要且具代表性的移動行為和特徵(feature),是資料探勘非常熱門的領域之一。探勘所得的移動型樣(Movement Pattern)應用性很廣,可以用於移動軌跡的預測或相似度的比對,或進一步發展許多有趣的應用。 許多軌跡資料探勘的方法會將監控區域切割成網格,藉以將物件移動軌跡的經緯度座標點序列,轉成一連串的網格序列,以利軌跡型樣的探勘。但這樣的方法可能面臨的問題包括下列五方面: 一、不容易找出一個最佳的網格大小與切割位置。二、網格數量可能很大,致使探勘耗費大量的CPU或記憶體。三、採用client-server架構,將軌跡資料上傳到server端做探勘再回傳結果的策略有隱私洩漏的疑慮,不利相關應用的發展。四、大量的軌跡資料導致傳統演算法的計算時間增加,甚至無法執行。五、傳統的型樣定義和演算法無法快速反應移動行為的變化。基於上述五大問題和挑戰,本論文提出Incremental PST with Dynamic Granularity and Auto-labeling (incPSTDGAL )演算法,其根據個人的移動習慣,動態決定每個區域的網格大小,找出具代表性的網格,並分配重要網格label,以減少總label的總數,再採取incremental mining的策略,來因應不斷累積增加的軌跡資料;也就是將累積的資料分批探勘,再將每次探勘的結果合併,如此可以避免一次探勘很大量的資料,此外,我們設計Aging的調整機制,在合併探勘結果時,給予新的探勘結果較大的weighting,以利快速反應使用者行為的劇烈變動。這一系列的改進使單次軌跡資料探勘的計算時間大幅下降,有助於直接在客戶端直接進行個人軌跡資料的探勘,無形中也加強了使用者隱私保護。 為驗證incPSTDGAL演算法的效能,我們於Android手機平台實作演算法,並設計多個實驗來比較演算法的效率和探勘結果的有效性。經實驗證實,incPSTDGAL演算法克服傳統PST的限制,可以有效控制每次探勘的計算成本,因此,我們可以在client端做軌跡資料探勘而不需將資料上傳到server端,且因為動態調整有效網格的顆粒粗細,使探勘所得的移動型樣更多更有效。zh_TW
dc.description.tableofcontents目錄 誌謝辭 i 中文摘要 ii 第1章 緒論 1 第2章 相關研究 4 2.1 序列型樣探勘( Sequence Pattern Mining ) 4 2.2 Variables Length Markov Models(VMMs) 5 2.3 PST ( Probabilistic Suffix Tree ) 6 2.3.1 軌跡序列資料(Trajectory Sequence Data) 6 2.3.2 PST樹的介紹與型樣定義 9 2.3.3 PST建置 12 第3章 具動態顆粒與自動標籤的漸進式軌跡資料探勘 14 3.1 傳統PST所面臨的限制和挑戰與我們提出的解決策略 14 3.1.1 影響PST tree建置效能的幾個主要因素 14 3.1.2 傳統PST所面臨的限制和挑戰與我們提出的解決策略 15 3.2 具動態顆粒與自動標籤的漸進式軌跡資料探勘之架構 20 3.3 DGAL Algorithm 26 3.3.1 DGAL : newGT algorithm and gtMerge algorithm 31 3.3.2 DGAL : merge2GTs algorithm 40 3.4 Incremental mining and periodic merge 42 3.4.1 Basic Operation of PST Tree Merge 44 3.4.2 近似公式估計 50 第4章 實驗 68 4.1 實驗環境 68 4.2 實驗結果 69 4.2.1 測試做Auto-labeling之後的效率提升幅度 69 4.2.2 Inc'PSTDGAL' 計算時間比較 70 4.2.3 Information Loss 76 第5章 結論 88 參考文獻 89 圖目次 圖 2 1 (左) Raw Trajectories (右) Grid-based Method 7 圖 2 2物件的移動軌跡 8 圖 2 3 (上) PST的資料結構 (左下) 監控區域以及物件移動軌跡 9 圖 2 4 (上) 單一物件的移動軌跡記錄 (下) 經探勘圖2.5 (上)所得之PST 11 圖 2 5 PST的建置演算法 13 圖 3 1 監控範圍內不同|Σ|對PST建置影響 15 圖 3 2學校台中一中分屬不同網格(圖中綠色區塊),導致軌跡序列S1和 S2被判定為兩種不同移動方式 18 圖 3 3台中市市區面積為54km*55km 18 圖 3 4 此實驗圖旨說明當輸入軌跡資料每次增加1MByte,其資料量多寡對運算時間的影響。其資料來源是實驗室同學所記錄的真時移動軌跡,PST基本參數設定為 Pmin=0.001, Lmax=5,|Σ| = 100 19 圖 3 5具動態顆粒與自動標籤的漸進式軌跡資料探勘之架構 20 圖 3 6 (上) 傳統PST,將監控區域內所有網格都拿來建tree (下) 使用DGAL演算法所建置的PSTDGAL 22 圖 3 7 使用者在Period i 所累積的經緯度序列資料集以及軌跡點所對應地理位置 23 圖 3 8 Example of newGT和其輸入與輸出 24 圖 3 9 Example of Build PSTDGAL 25 圖 3 10 Example of Phase 2 26 圖 3 11 DGAL演算法中,我們以階層式的網格切割方式 28 圖 3 12 各種level 的網格大小(grid size)示意圖 29 圖 3 13 (a)以level 0的網格大小對監控區域做分割,以gid 0~8將網格編碼;圖 3 2 (b)改以level 1的網格大小對同一監控區域做分割,並以gid 0~35將網格編碼 29 圖 3 14 (左) 監控區域以不同level的網格大小做分割 (右)Grid Tree 資料結構示意圖 30 圖 3 15 DGAL Phase 1: newGT algorithm 31 圖 3 16 DGAL Phase 1: gtMerge algorithm 33 圖 3 17 (右上) 為該監控區域在不同level下gid的對應關係 34 圖 3 18 Period 0的Grid Tree及mapping table和location sequences 36 圖 3 19(上) Period i-1的Grid Tree (下) Period i, i>0的Grid Tree參考前一週期的網格切割方式往下延伸j層計算所有leaf node的no.of spots 38 圖 3 20 Period 0的Grid Tree及mapping table和location sequences 39 圖 3 21 DGAL Phase 2 : merge2GTs algorithm 40 圖 3 22 前兩個週期所建的Grid Tree 1和 Grid Tree2經由merge2GTs algorithm合併成新Grid Tree : Grid Tree1 + Grid Tree2 41 圖 3 23 Problem of PST Tree Merge 43 圖 3 24將'PSTDGAL ' 1 和'PSTDGAL' 2合併得Inc'PSTDGAL' 44 圖 3 25 Inc'PSTDGAL' 的條件機率值為'PSTDGAL 1 ' & 'PSTDGAL 2' 取其地理位置相同的數個節點乘轉換參數Wi而得,其中W1=wσ1wσ1wσ2 ,W2=wσ1wσ1wσ2_1 ,W3=wσ1wσ1wσ2-2 46 圖 3 26 'PSTDGAL' 的節點 c對應到Inc'PSTDGAL' 的c&d&f是屬於split(One-to-Many mapping) 47 圖 3 27 'PSTDGAL' 的節點 g&f對應到 Inc'PSTDGAL' 是屬於merge(Many-to-One mapping) 48 圖 3 28 'PSTDGAL' 的node bcf &bcg對應到Inc'PSTDGAL' 的bdh & bch是屬於merge(Many-to-One mapping)和split(One-to-Many mapping)都有 49 圖 3 29 σ split to σ1、σ2、σ3 、 σ4 51 圖 3 30 σ1、σ2、σ3 、 σ4 merge to σ 51 圖 3 31 'One-to-One mapping' 52 圖 3 32 估計權重W的計算 53 圖 3 33推導目標找出作incremental merge時的weighting factor W 54 圖 3 34 incremental merge的運算概念 54 圖 3 35移動型樣S3內含所有網格全屬split – 而σ 屬split 56 圖 3 36移動型樣S3內含所有網格全屬split – 而σ 屬merge 59 圖 3 37 移動型樣S3內含網格split和merge都有 – 而σ 屬split 61 圖 3 38移動型樣S3內含網格有split和merge–而σ屬merge 64 圖 3 39 PSTDGAL algorithm 66 圖 3 40 IncPSTDGAL algorithm 67 圖 4 1在不同網格數量下執行時間比較 69 圖 4 2比較每次在處理不斷增加的資料時,有沒有使用incremental在計算時間上的差異 71 圖 4 3累計計算時間比較 72 圖 4 4比較每次在處理不斷增加的資料時,有沒有使用incremental在計算時間上的差異 73 圖 4 5累計計算時間比較 74 圖 4 6比較每次在處理不斷增加的資料時,有沒有使用incremental在計算時間上的差異 75 圖 4 7累計計算時間比較 75 圖 4 8 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' ,平均每個節點內含條件機率距離的總和 77 圖 4 9 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' 的整體條件機率距離 78 圖 4 10 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' ,平均每個節點內含條件機率距離的總和 79 圖 4 11 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' 的整體條件機率距離 80 圖 4 12 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' ,平均每個節點內含條件機率距離的總和 81 圖 4 13 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' 的整體條件機率距離 81 圖 4 14 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' ,平均每個節點內含條件機率距離的總和 82 圖 4 15 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' 的整體條件機率距離 83 圖 4 16 incremental建出來的Inc'PSTDGAL' 的總節點數變化 83 圖 4 17 user 於2008.10一整個月的軌跡移動資料 84 圖 4 18 user 於2008.11一整個月的軌跡移動資料 84 圖 4 19 user 於2008.12一整個月的軌跡移動資料 85 圖 4 20 user 於2009.01一整個月的軌跡移動資料 85 圖 4 21 user 於2009.02一整個月的軌跡移動資料 86 圖 4 22 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' ,平均每個節點內含條件機率距離的總和 87 圖 4 23 incremental建出來的Inc'PSTDGAL' 和重掃資料庫建出來的'PSTDGAL' 的整體條件機率距離差 87 表目次 表格 2 1 PST建置演算法的參數和說明 12 表格 3 1 incremental merge的近似公式之基本符號定義 50 表格 4 1實驗環境 68zh_TW
dc.language.isozh_TWzh_TW
dc.rights不同意授權瀏覽/列印電子全文服務zh_TW
dc.subjectTrajectory miningen_US
dc.subjectAuto-labelingen_US
dc.subjectDynamic granularityen_US
dc.subjectIncremental miningen_US
dc.subject軌跡資料探勘zh_TW
dc.subject自動標籤zh_TW
dc.subject動態顆粒zh_TW
dc.subject漸進式資料探勘zh_TW
dc.title具動態顆粒與自動標籤之漸進式軌跡資料探勘zh_TW
dc.titleIncremental Trajectory Data Mining with Dynamic Granularity and Auto-labelingen_US
dc.typeThesis and Dissertationen_US
dc.date.paperformatopenaccess2017-08-31zh_TW
dc.date.openaccess10000-01-01-
Appears in Collections:通訊工程研究所
文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.