應用粒子群最佳化演算法於關聯法則探勘之研究

Applying Particle Swarm Optimization algorithm in Association Rule Mining

邱宇婷(Yu-Ting Chiu)

指導教授 ： 郭人介

國立臺北科技大學/管理學院/工業工程與管理系所/碩士(2006年)

摘要

由於資訊科技的進步日新月異，且要在龐大的資料中整理並擷取出有意義的資訊，是一個很重要的課題，而近年來資料探勘技術已成功的應用在不同領域，因為資料探勘能將各種龐大的資料中的隱藏事實與資訊探勘出來，並在這些資料中歸納出有結構的模式，其中關聯法則為使用最廣泛且最實用的一種模式，主要用於找尋資料中屬性之間的關係，而最典型是應用於購物籃分析上。
在過去的文獻中，發現在關聯法則演算法上的改良研究，大多都是以提高搜尋效率為目的，也有些研究是針對關聯法則設定的最小支持度與最小信心度門檻值，因為客觀的設定最小門檻值得到的關聯規則是相當重要的。因此本研究將提出改善關聯法則整體效率與客觀設定門檻值的新演算法，其先透過二元資料型態轉換，再應用啟發式方法-粒子群最佳化演算法，搜尋最佳粒子之適應値，作為最小門檻值設定之建議；且利用Microsoft SQL Server 2000之內建資料庫做為此方法的模式驗證，並與基因演算法比較其探勘效率，其結果可得知，藉由粒子群最佳化演化應用確實能快速且客觀的提供最適的最小門檻值設定建議，來提升探勘關聯法則的品質與效率；另外也應用在實際證卷公司資料分析上，可以藉由本研究提出的關聯法則，探勘出投資者之行為對於購買股票之類股間的關聯性。

關鍵字

資料探勘 ； 關聯法則 ； 粒子群最佳化演算法

並列摘要

With the development of information technology (IT), how to find useful information existed in vast data has become an important issue. The most broadly discussed technique is Data-mining, which has been successfully applied to many fields as analytic tool. Data mining extracts implicit, previously unknown, and potentially useful information from data. Association rule is one of the most important and useful technologies in data mining methods. Association rule summarizes meaningful relations among items, and this technology is typically applied to basket analysis in supermarkets.
Most of previous researches focus on improving computational efficiency. However, there are also some other researches which emphasize on how to decide the threshold values of support and confidence parameters. The reason is that deciding suitable threshold values is critical to the quality of association rule mining. In this study, we propose a new algorithm for association rule mining in order to improve the whole efficiency and determine suitable threshold values. At first, transaction data are transformed into binary formats and then we apply Particle Swarm Optimization (PSO) algorithm to search the optimum fitness value of particle and find its corresponding support and confidence as minimum threshold. The proposed method is verified by applying FoodMart2000 database of Microsoft SQL Server 2000 and compared with genetic algorithm in efficiency. According to the results, it is found that particle swarm optimization algorithms can really suggest suitable threshold values and obtain the quality rules. We also apply real-world stock market database in order to mine association rule among investment behavior and stock category purchasing. The computational result is also very promising.

並列關鍵字

Data mining ； Association rule ； PSO

參考文獻

[1]G.H.Grupe and M.M. Owrang, “Database Mining Discovering New Knowledge and Cooperative Advantage,” Information System Management, Vol 12,No. 4, 1995, pp.26-31.

[2]U. Fayyad, G. Piatetsky-shapiro and P. Smyth, “From data mining to knowledge discovery in databases,” AI Magazine, 1996, pp.37-54.

[3]M.J.A. Berry and G.S. Linoff, Data Mining Technique： For Marketing, Sales, and Customer Relationship Management, New York：Wiley Computer Publishing, 1997.

[5]U. Fayyad, G. Piatetsky-shapiro and P. Smyth, “From data mining to knowledge discovery in databases,” AI Magazine, pp.37-54, 1996.

[6]M. J. Shaw, C. Subramaniam, G.W. Tan and M.E. Welge, “Knowledge management and data mining for marketing,” Decision Support Systems, Vol. 31, pp.127-137, 2001.