臺灣博碩士論文加值系統

由於全球氣候變遷，專家學者發現海洋在氣候變遷中佔有極重要角色，海水溫度與鹽度變化研究已引起人們廣泛注意與討論。本研究將分析Argo海水溫度與鹽度資料並有效地找出其中溫度與鹽度樣式。傳統關聯法則演算法在尋找關聯法則時，僅能找出交易中項目與項目間的關係，因此若利用傳統關聯法則尋找時空樣式時，其所尋找出樣式無法顯示出時間與空間上關係。例如：若臺灣東北東部近距離地區海水鹽度上升0.15psu到0.25psu，則下個月臺灣東北東部遠距離地區海水溫度將會上升0℃到1.2℃。為了能找出前述的時空樣式，本研究提出一個可將Argo資料轉化成交易型態資料集的方法，接著再設計一個量化跨界性關聯法則探勘模型，能有效地從被轉化後的Argo資料中找出具時空變化關係之溫度與鹽度樣式。另一方面，我們結合FITI及PrefixSpan技術於量化跨界性關聯法則探勘模型中，以增進資料探勘的效率。最後則是設計模糊推論系統來預測海水溫度與鹽度變化。模糊法則庫取自於所發掘之溫度與鹽度樣式，這將使預測兼具準確性與彈性。本研究以資料探勘技術與模糊推論來分析臺灣附近海域海水溫度與鹽度資料集，實驗亦證明本研究所提之跨界性關聯法則演算法比其他研究所提之跨界性關聯法則演算法來得更有效率。

Global ocean salinity and temperature variations are attracting increasing attention, due to its influence on global climate change. This research presents an efficient technique for analyzing Argo ocean data comprising time series of salinity and temperature measurements where informative salinity and temperature patterns are extracted. Most traditional mining techniques focus on finding associations among items within one transaction and are therefore unable to discover rich contextual patterns related to location and time. In order to show the associated salinity and temperature variations among different locations and time intervals, for example, “if the salinity rose from 0.15psu to 0.25psu in the area that is in the east-northeast direction and is near Taiwan, then the temperature will rise from 0℃ to 1.2℃ in the area that is in the east-northeast direction and is far away from Taiwan next month”, the research designs a transformation method to convert Argo spatial-temporal data to market-basket type data and then a quantitative inter-transaction association rules mining algorithm is proposed to apply to the transformed data set to get salinity and temperature variation patterns. The FITI and the PrefixSpan algorithms are adopted to maximize the mining efficiency. Next, a fuzzy inference model that employs the discovered salinity and temperature patterns as its rule base is designed to predict salinity and temperature variations. The strategy is applied to ocean salinity and temperature measurements obtained from the waters surrounding Taiwan. These experimental evaluations show that the proposed algorithm achieves better performance than other inter-transaction association rule mining algorithms.

ACKNOWLEDGEMENTS i
ABSTRACT ii
ABSTRACT IN CHINESE iii
TABLE OF CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLES viii
CHAPTER 1 INTRODUCTION 1
1.1 Motivation 1
1.2 The Problem Definitions 3
1.3 Expected Contribution 5
1.4 Dissertation Organization 6
CHAPTER 2 RELATED WORK 8
2.1 The Basic Concept of Data Mining 8
2.2 Association Rules Mining 12
2.2.1 Apriori Algorithm 14
2.2.2 Increasing the Efficiency of Apriori Algorithm 17
2.3 Data Discretization 20
2.4 Temporal Sequence Pattern Mining 22
2.5 Spatial Data Mining 27
2.5.1 Spatial Association Analysis 28
2.5.2 Spatial Clustering 30
2.5.3 Spatial Co-Location Patterns 32
2.6 Inter-Transaction Association Rules 34
2.7 Fuzzy Set Theory 39
2.7.1 The Basic Concept of Fuzzy Set 39
2.7.2 Fundamental Operations of Fuzzy Set 41
2.8 Fuzzy Inference Model 42
2.8.1 Fuzzification 43
2.8.2 Rule Evaluation 44
2.8.3 Defuzzification 45
CHAPTER 3 SYSTEM FRAMEWORK 48
3.1 System Overview 48
3.2 Argo Data 50
3.3 Defining Transactions in Argo Data 53
3.4 Mining Spatial-Temporal Patterns 58
3.4.1 Quantitative Attribute Transformation 58
3.4.2 Frequent Inter-Transaction Itemsets Discovery 58
3.4.3 Inter-Transaction Association Rules Generation 63
3.5 Designing Fuzzy Inference Model 64
CHAPTER 4 EXPERIMENTAL RESULTS AND DISCUSSIONS 68
CHAPTER 5 CONCLUSIONS AND FUTURE WORK 76
REFERENCES 79

[1]R. Agrawal, T. Imielinski and A. Swami, “Mining association rules between sets of items in large database,” Proc. ACM SIGMOD Int’l Conf. on Management of Data, Washington D.C., U.S.A., pp.207-216, May 1993.
[2]R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” Proc. Int’l Conf. Very Large Data Bases, Santiago de Chile, Chile, pp.487-499, September 1994.
[3]R. Agrawal and R. Srikant, “Mining sequential patterns,” Proc. Int’l Conf. on Data Engineer, Taipei, Taiwan, pp.3-14, Mar. 1995.
[4]R.A. Angryk and F.E. Petry, “Mining multi-level associations with fuzzy hierarchies,” Proc. IEEE Int’l Conf. on Fuzzy Systems, Reno, NV, U.S.A., pp.785-790, May 2005.
[5]A. Appice, M. Ceci, A. Lanza, F.A. Lisi and D. Malerba, “Discovery of spatial association rules in geo-referenced census data: A relational mining approach,” Intelligent Data Analysis, vol. 7, no. 6, pp.541-566, Dec. 2003.
[6]S.D. Bay, “Multivariate discretization of continuous variables for set mining,” Proc. ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, Boston, U.S.A., pp.315-319, Aug. 2000.
[7]U. Bhaskar, D. Swain and M. Ravichandran, “Inferring mixed-layer depth variability from Argo observations in the western Indian Ocean,” Journal of Marine Research, vol. 64, no. 3, pp.393-406, May 2006.
[8]C. Berberidis, L. Angelis and I. Vlahavas, “Inter-transaction association rules mining for rare events prediction,” Proc. Hellenic Conf. on Artificial Intelligence, Samos, Greece, pp.308-317, May 2004.
[9]S. Brin, R. Motwani and C. Silverstein, “Beyond market basket: Generalizing association rules to correlations,” Proc. ACM SIGMOD Int’l Conf. on Management of Data, Tucson, Arizona, U.S.A., pp.265-276, May 1997.
[10]S. Brecheisen, H.-P. Kriegel and M. Pfeifle, “Multi-step density-based clustering,” Knowledge and Information Systems, vol. 9, no. 3, pp.284-308, Mar. 2006.
[11]P. Bolstad, GIS Fundamentals: A First Text on Geographic Information Systems, Eider Press, White Bear Lake, Minn., U.S.A., 2002.
[12]Q. Ding, Q. Ding and W. Perrizo, “Association rule mining on remotely sensed image using p-trees,” Proc. Pacific-Asia Conf. on Advances in Knowledge Discovery and Data Mining, Taipei, Taiwan, pp.66-79, May 2002.
[13]V. Estivill-Castro and A.T. Murray, “Mining spatial data via clustering,” Technical Report #5/97, Queensland University of Technology, Brisbane, Queensland, Australia, 1997.
[14]M. Ester, H.P. Kriegel, S. Sander and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” Proc. ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, Portland, Oregon, U.S.A., pp.226-231, Aug. 1996.
[15]L. Feng, T. Dillon and J. Liu, “Inter-transactional association rules for multi-dimensional contexts for prediction and their application to studying meteorological data,” Data & Knowledge Engineering, vol. 37, no. 1, pp.85-115, Apr. 2001.
[16]G. Forget and C. Wunsch, “Estimated global hydrographic variability,” Journal of Physical Oceanography, vol. 37, no. 8, pp.1997-2008, Aug. 2007.
[17]R.L. Grossman, C. Kamath, V. Kumar and R.R. Namburu, Data Mining for Scientific and Engineering Applications, Kluwer Academic Publishers, New York, NY, U.S.A., 2001.
[18]J. Han and J. Pei, “Mining frequent patterns by pattern-growth: Methodology and implications,” ACM SIGKDD Explorations Newsletter, vol. 2, no. 2, pp.14-20, Dec. 2000.
[19]J. Han and M. Kamber, Data Mining: Concept and Techniques, Morgan Kaufmann, San Francisco, CA, U.S.A., 2001.
[20]J. Han, K. Koperski and N. Stefanovic, “GeoMiner: A system prototype for spatial data mining,” Proc. ACM SIGMOD Int’l Conf. on Management of Data, Tucson, Arizona, U.S.A., pp.553-556, May 1997.
[21]Y. Huang, S. Shekhar and H. Xiong, “Discovering co-location patterns from spatial datasets: a general approach,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 12, pp.1472-1485, Dec. 2004.
[22]Y.-P. Huang, Teaching Materials of Fuzzy Theory, Tatung University, Taiwan.
[23]P.-S. Kam and W.-C. Fu, “Discovering temporal patterns for interval-based events,” Proc. Int’l Conf. on Data Warehousing and Knowledge Discovery, London, UK, pp.317-326, Sept. 2000.
[24]H. Kargupta, A. Joshi, K. Sivakumar and Y. Yesha, Data Mining: Next Generation Challenges and Future Directions, AAAI/MIT Press, Cambridge, MA, U.S.A., 2004.
[25]K. Koperski, J. Adhikary and J. Han, “Spatial data mining: Progress and challenges,” Proc. ACM SIGMOD Workshop on Research Issues on Mining and Knowledge Discovery, Montreal, Canada, pp.1-10, Jun. 1996.
[26]K. Koperski and J. Han, “Discovery of spatial association rules in geographic information databases,” Proc. Int’l Symposium on Large Spatial Data bases, Maine, U.S.A., pp.47-66, Aug. 1995.
[27]B. Lent, A. Swami and J. Widom, “Clustering association rules,” Proc. Int’l Conf. on Data Engineer, Birmingham, England, pp. 220-231, Apr. 1997.
[28]H. Lu, L. Feng and J. Han, “Beyond intra-transactional association analysis: Mining multi-dimensional inter-transaction association rule,” ACM Transactions on Information Systems, vol. 18, no. 4, pp.423-454, Oct. 2000.
[29]S. Ma, T.J. Wang and S.W. Tang, “A new fast clustering algorithm based on reference and density, Lectures Notes in Computer Science, vol. 2762, pp.214-225, Aug. 2003.
[30]H. Mannila and H. Toivonen, “Discovering generalized episodes using minimal occurrences,” Proc. Int'l ACM SIGKDD Conf. on Knowledge Discovery and Data Mining, Portland, Oregon, U.S.A., pp.146-151, Aug. 1996.
[31]R. Meo, G. Psaila and S. Ceri, “A new SQL-like operator for mining association rules,” Proc. Int’l Conf. Very Large Data Bases, Bombay, India, pp.122-133, Sept. 1996.
[32]R.J. Miller and Y. Yang, “Association rules over interval data,” Proc. ACM SIGMOD Int’l Conf. on Management of Data, Tucson, Arizona, U.S.A., pp.452-461, May 1997.
[33]T. Morzy, M. Wojciechowski and M. Zakrzewicz, “Scalable hierarchical clustering method for sequences of categorical values,” Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, Hong Kong, pp.282-293, Apr. 2001.
[34]P. Nardiello, F. Sebastiani and A. Sperduti, “Discretizing continuous attributes in AdaBoost for text categorization,” Proc. European Conf. on Information Retrieval, Pisa, Italy, pp.320-334, Apr. 2003.
[35]A. Ng and W.-C. Fu, “Mining frequent episodes for relating financial events and stock trends,” Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining, Seoul, Korea, pp.27-39, Apr. 2003.
[36]R.T. Ng and J. Han, “CLARANS: A method for clustering objects for spatial data mining,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5, pp.1003-1016, Sept./Oct. 2002.
[37]E. Oka, L.D. Talley and T. Suga, “Temporal variability of winter mixed layer in the mid- to high-latitude North Pacific,” Journal of Oceanography, vol. 63, no. 2, pp.293-307, 2007.
[38]J.S. Park, M.S. Chen and P.S. Yu, “An effective hash-based algorithm for mining association rules,” Proc. ACM SIGMOD Int’l Conf. on Management of Data, San Jose, CA, U.S.A., pp.175-186, May 1995.
[39]J. Pei, J.W. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M. C. Hsu, “PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth,” Proc. IEEE Int’l Conf. on Data Engineering, Heidelberg, Germany, pp.215-224, Apr. 2001.
[40]V. Popovici and J.-Ph. Thiran, “Pattern recognition using higher-order local autocorrelation coefficients,” Pattern Recognition Letters, vol. 25, no. 10, pp.1107-1113, Oct. 2004.
[41]J.F. Roddick and M. Spiliopoulou, “A survey of temporal knowledge discovery paradigms and methods,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 4, pp.750-767, Jul./Aug. 2002.
[42]S. Shekhar, C.T. Lu and P. Zhang, “A unified approach to spatial outliers detection,” GeoInformatica, vol. 7, no. 2, pp.139-166, Jun. 2003.
[43]S. Shekhar and S. Chawla, Spatial Databases: Issues, Implementation and Trends, Prentice Hall, New Jersey, U.S.A., 2001.
[44]S. Shekhar and S. Chawla, Spatial Databases: A Tour, Prentice Hall, New Jersey, U.S.A., 2002.
[45]R. Srikant and R. Agrawal, “Mining quantitative association rules in large relation tables,” Proc. ACM SIGMOD Int’l Conf. on Management of Data, Montreal, Canada, pp.1-12, Jun. 1996.
[46]R. Srikant and R. Agrawal, “Mining sequential patterns: Generalizations and performance improvements,” Proc. Int'l Conf. on Extending Database Technology, Avignon, France, pp.3-17, Mar. 1996.
[47]R. Srikant, Q. Vu and R. Agrawal, “Mining association rules with item constraints,” Proc. ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, Newport Beach, CA, U.S.A., pp.67-73, Aug. 1997.
[48]S. Shekhar, S. Chawla, S. Ravada, A. Fetterer, X. Liu and C.T. Lu, “Spatial databases: Accomplishments and research needs,” IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 1, pp.45-55, Jan./Feb. 1999.
[49]P. Tan, M. Steinbach, V. Kumar, C. Potter, S. Klooster and A. Torregrosa, “Finding spatio-temporal patterns in earth science data,” Proc. ACM SIGMOD KDD Workshop on Temporal Data Mining, San Francisco, CA, U.S.A., pp.1-12, Aug. 2001.
[50]A.K.H. Tung, H. Lu, J. Han and L. Feng, “Efficient mining of intertransaction association rules,” IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 1, pp.43-56, Jan./Feb. 2003.
[51]T.D. Wade, P.J. Byrns, J.F. Steiner and J. Bondy, “Finding temporal patterns – a set based approach,” Artificial Intelligence in Medicine, vol. 6, no. 3, pp.263-271, Jun. 1994.
[52]J. Wang and J. Han, “BIDE: Efficient mining of frequent closed sequences,” Proc. Int’l Conf. on Data Engineering, Boston, U.S.A, pp.79-90, Mar. 2004.
[53]X. Wu, “Fuzzy interpretation of discretized intervals,” IEEE Transactions on Fuzzy Systems, vol. 7, no. 6, pp.753-759, Dec. 1999.
[54]D.-L. Yang, J. Chou and D. Chen, "A hierarchical spatial clustering algorithm based on Delaunay triangulation," Proc. Conf. on Artificial Intelligence and Applications, Kaohsiung, Taiwan, pp.150-156, Dec. 2005.
[55]Y. Yasui and S.R. Lele, “A regression method for spatial disease rates: an estimating function approach,” Journal of the American Statistical Association, vol. 92, no. 437, pp.21-32, Mar. 1997.
[56]J.S. Yoo and S. Shekhar, “A join-less approach for mining spatial colocation patterns,” IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 10, pp.1323-1337, Oct. 2006.
[57]C.C. Yu and Y.L. Chen, “Mining sequential patterns from multidimensional sequence data,” IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 1, pp.136-140, Jan. 2005.