隨著環保意識的抬頭，節能減碳目標的追求，電力公司對於電力資料探勘需求日益增加，再加上智慧電表的逐漸普及，電力時間序列資料正在快速的成長，使得相關人員面臨了巨量資料分析與複雜運算之困難。而巨量資料中的目前最普及的解決方案就是使用開放式原始碼巨量資料處理平台Hadoop，透過其分散式編程架構MapReduce、分散式檔案系統HDFS 來處理巨量資料。
在時間序列探勘中有個重要的研究議題就是基序(motif)探勘，基序是指在一個時間序列中重複出現的片段序列，藉由基序探勘，我們將能找出有意義的片段，並讓他代表一個事件，接著就能將一個時間序列轉換為一個事件序列並使用傳統的關聯法則找出用戶其隱藏的用電行為規則，而用電行為規則將對於節能減碳相關政策上的決定提供了相當大的參考價值。
因此為了能解決傳統基序演算法對於巨量資料處理上的限制，本研究將基於Hadoop提出新的基序(motif)探勘演算法-「PrefixMotif」以及「MR_PrefixMotif」，PrefixMotif是由知名循序樣式探勘演算法PrefixSpan所改良。實驗結果顯示，在資料規模相當大的時候PrefixMotif比基序探勘研究中的常用方法Time Serise Project還要快上80倍以上且使用的記憶體空間更小，而做分散化處理後的「MR_PrefixMotif」在hadoop平台上執行，更隨著節點增加讓效能更是進一步的提昇，讓「MR_PrefixMotif」比起傳統的方法在執行效能上具有壓倒性的優勢。
最後本研究也實作了知名循序樣式探勘演算法I-PrefixSapn的分散化處理，提出基於Hadoop上執行的「MR_I-PrefixSpan」演算法並處理樣式探勘的部分，讓整體電力時間序列資料探勘的過程完整，而其探勘流程、基序結果、樣式結果等可供後續相關用電探勘研究之參考。

With the rise of environmental awareness, power companies increasing demand for electric data mining. In addition, the increasing popularity of Smart Meters generate big electric time series data. Big data make researchers confronted analysis of large-scale data sets and heavy computation. It is a good choice to solve this problem that Hadoop which provide fault-tolerant parallelized analysis based on a Programming style named MapReduce.
In order to achieve the goal of electric data mining. Motif mining is important research topic in time series mining. In time series, a motif is a subsequence fragment of a recurring. By motif mining, we can discovery a significant event.
Traditional single-processor motif algorithm is inadequate to mining motif from that large-scale time series datasets. Therefore, this study provides two novel motif mining algorithm「PrefixMotif」 and 「MR_PrefixMotif」 based on Hadoop platform.
Experiments show that when facing big data, 「PrefixMotif」 performance is better than traditional motif mining algorithm 「Time Series Projection」. Further, a distributed algorithm「MR_PrefixMotif」performance is better than single-processor algorithm「PrefixMotif」.
MR_PrefixMotif is a novel parallel and distributed algorithm optimized for motif mining of large-scale time series datasets and provided superior performance of motif mining for electric data mining researchers.

第一章 緒論 1
第一節 研究動機 1
第二節 研究目的 4
第三節 研究步驟與流程 5
第四節 論文架構 8
第二章 文獻探討 10
第一節 資料探勘 10
2.1.1 資料探勘之定義 10
2.1.2 資料探勘之步驟 13
2.1.3 資料探勘技術分類 16
第二節 時間序列探勘 17
2.2.1 規則發現 17
2.2.2 基序(Motif)探勘 18
第三節 循序樣式探勘 18
2.3.1 循序樣式探勘之定義 19
2.3.2 循序樣式探勘之演算法發展 20
第四節 巨量資料 23
2.4.1 巨量資料處理技術的發展 23
2.4.2 Hadoop簡介 25
2.4.3 Hadoop分散式文件系統 27
2.4.4 Hadoop的運算模型 29
第三章 問題定義 33
第一節 用電行為的時間區間循序樣式探勘 33
第二節 時間序列中的基序(motif) 34
第四章 研究方法 37
第一節 資料分析流程 37
第二節 時間序列表示法 38
4.2.1 離散化 39
4.2.2 距離測量 41
第三節 時間序列的基序(motif)探勘 42
4.3.1 Time Series Projection 42
4.3.2 PrefixMotif 45
4.3.3 MapReduce_PrefixMotif 50
第四節 時間區間循序樣式探勘 52
4.4.1 I-PrefixSpan 52
4.4.2 MapReduce_I_PrefixSpan 54
第五章 實驗結果 57
第一節 參數討論 57
5.1.1 最小支持度(minSup)的影響 58
5.1.2 容許差異(d)的影響 61
5.1.3 距離(R)的影響 65
5.1.4 小結 68
第二節 演算法的效率 68
5.2.1 基序探勘演算法的效率 69
5.2.2 MapReduce架構演算法的效率 73
第三節 用電需求序列資料的基序結果 74
第四節 用電需求序列資料的時間區間樣式結果 80
第六章 結論與建議 81
第一節 結論 81
第二節 建議 82
6.2.1 研究限制 82
6.2.2 未來研究方向 83
參考文獻 85

一、英文部分
【1】Han, J &; Kamber, M.(2001). Data Mining Concepts and Techniques. San Francisco: Morgan Kaufmann Publishers.
【2】Fayyad, U., Piatetsky-Shapiro, G. &; Smyth, P. (1996). The KDD Process for Extracting Useful Knowledge from Volumes of Data. Communication of the ACM, 39, 27-34.
【3】Fayyad, U. &; Stolorz, P. (1997). Data mining and KDD: Promise and Challenges. Future Generation Computer Systems, 13, 99-115.
【4】Cabena, P., Hadjinian, P. O., R. Stadler, DR. J. Verhees, and. Zanasi, A. (1997). Discovering Data Mining from Concept to Implementation. Prentice Hall.
【5】Kagami., Iwamoto. &; Tani (2008). Application of datamining method (ID3) to data analysis for ultra deep hydrodesulfurization of straight-run light gas oil—determination of effective factor of the feed properties to reaction rate of HDS. Fuel, Vol84 no.2-3, 279-285.
【6】Berry, M.J.A. and G. Linoff (1997) . Data Mining Techniques：For Marketing, Sales, and Customer Support, New York：John Wiley &; Sons
【7】Hirst, E. (1996). The future of DSM in a restructured US electricity industry. Energy Policy, 24, 303-315.
【8】Nadel, S. &; Geller, H. (1996). Utility DSM. What hava we learned? Where are we going? Energy Policy, 24, 289-302.
【9】Dean, J. &; Ghemawat, S. (2004). MapReduce: Simplified Data Processing on Large Clusters. Google Research Publications.
【10】Ghemawat, S. &; Gobioff, H. (2003). The Google File System. Google Research Publications.
【11】White, T. (2012). Hadoop: the definitive guide. O’REILLY.
【12】Agrawal, R. &; Srikant, R. (1994). Fast Algorithms for Mining Association Rules. Proceedings of 1994 International Conference on Very Large Data Bases, 487-499.
【13】Agrawal, R. &; Srikant, R. (1995). Mining Sequential Patterns. Proceedings of 1995 International Conference on Data Engineering, 3-14.
【14】Srikant, R. &; Agrawal, R. (1996) Mining Sequential Patterns: Generalizations and Performance Improvements. EDBT, 3-14.
【15】Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U. &; Hsu, M. C. (2000). FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining. Proc. 2000 Int. Conf. on Knowledge Discovery and Data Mining, 355-359.
【16】Pei, J., Han, J., Printo, H., Chen, Q., Dayal, U. &; Hsu, M. C., (2001) PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. Proc. 2001 Int. Conf. on Data Engineering (ICDE’01).
【17】Chen, Y. L., Chiang, M. C., &; Ko, M. T. (2003). Discovering time-interval sequential patterns in sequence databases. Expert Systems with Applications,25(3), 343-354.
【18】Das, G., Lin, K. I., Mannila, H., Renganathan, G., &; Smyth, P. (1998, August). Rule Discovery from Time Series. In KDD (Vol. 98, pp. 16-22).
【19】Lonardi, J. L. E. K. S., &; Patel, P. (2002). Finding motifs in time series. InProc. of the 2nd Workshop on Temporal Data Mining (pp. 53-68).
【20】Lin, J., Keogh, E., Lonardi, S., &; Chiu, B. (2003). A symbolic representation of time series, with implications for streaming algorithms. In Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery (pp. 2-11). ACM.
【21】Chiu, B., Keogh, E., &; Lonardi, S. (2003, August). Probabilistic discovery of time series motifs. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 493-498). ACM.
【22】Keogh, E., &; Lin, J. (2005). Clustering of time-series subsequences is meaningless: implications for previous and future research. Knowledge and information systems, 8(2), 154-177.
【23】Tanaka, Y., Iwamoto, K., &; Uehara, K. (2005). Discovery of time-series motif from multi-dimensional data based on MDL principle. Machine Learning, 58(2-3), 269-300.
【24】Yankov, D., Keogh, E., Medina, J., Chiu, B., &; Zordan, V. (2007, August). Detecting time series motifs under uniform scaling. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 844-853). ACM.
【25】Minnen, D., Isbell, C., Essa, I., &; Starner, T. (2007, October). Detecting subdimensional motifs: An efficient algorithm for generalized multivariate pattern discovery. In Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on (pp. 601-606). IEEE.
【26】Tang, H., &; Liao, S. S. (2008). Discovering original motifs with different lengths from time series. Knowledge-Based Systems, 21(7), 666-671.
【27】Mueen, A., Keogh, E., &; Bigdely-Shamlo, N. (2009, December). Finding time series motifs in disk-resident data. In Data Mining, 2009. ICDM''09. Ninth IEEE International Conference on (pp. 367-376). IEEE..
【28】Yi, B. K., Jagadish, H. V., &; Faloutsos, C. (1998, February). Efficient retrieval of similar time sequences under time warping. In Data Engineering, 1998. Proceedings., 14th International Conference on (pp. 201-208). IEEE
二、中文部分
【29】台灣電力公司業務處 (1993) ，「表燈用電負載管理策略之研究」，台 灣電力公司八十二年度研究發展專題報告。
【30】台灣電力公司綜合研究所 (1991)，「負載管理價格需求彈性對用電特性之影響」，台灣電力公司八十年度研究報告。
【31】台灣電力公司綜合研究所 (2008) ，「97年度家用電器普及狀況調查」，台灣電力公司九十八年度研究報告。
【32】台灣電力公司綜合研究所 (2010) ，「99年度家用電器普及狀況調查」，台灣電力公司一百年度研究報告。
【33】台灣電力公司綜合研究所 (2007) ，「可停電力潛在用戶探勘分析決策支援系統之建構」，台灣電力公司九十六年度研究報告。
【34】台灣電力公司綜合研究所 (2010) ，「智慧電網下住宅時間電價研訂策略之研究」，台灣電力公司一百年度研究報告。
【35】王派洲譯 (2008)，「資料探勘：概念與方法2/e」，滄海書局
【36】王耀聰、辜文元、周天穎、衷嵐焜譯(2013)，TomWhite著，「Hadoop技術手冊-第三版」，歐萊禮(O’REILLY)。