柯佳伶石舒寧2019-08-292005-8-242019-08-292005http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22G0069208029%22.&%22.id.&http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/92691近來有很多實際的應用，其資料是以資料流的形式產生。本論文針對資料流探勘最近常見資料項集的問題，提出兩個近似探勘的方法，分別稱為ATS演算法(Average TimeStamp mining method)及FCP演算法(Frequency Changing Point mining method)。這兩個演算法對資料流裡每筆交易皆只需掃描處理一次，記錄下可能為最近常見資料項集的出現摘要資訊。由摘要資訊結構中的資訊，不需儲存目前視窗中的交易資料，即可更新並刪除不屬於目前視窗的過時資訊，並從中快速地近似找出最近常見資料項集。其中FCP演算法記錄資料項集在出現頻率改變點的累計次數，可用以估算出該資料項集在目前視窗中的支持度，近似探勘出目前交易視窗中的最近常見資料項集。由實驗結果顯示，採用FCP演算法來近似探勘資料流中的最近常見資料項集，可達到極高的正確率(precision)及回覆率(recall)。且相較於以往所提出的SW演算法，可有效率減少資料維護及探勘執行時間，且明顯減少所需記憶體大小。Recently, the data of many real applications are generated in the form of data streams. In this thesis, two approximately mining methods, named ATS (Average TimeStamp mining method) and FCP (Frequency Changing Point mining method), are proposed for finding recent frequent itemsets on data streams. In these two approaches, each transaction in the data stream is examined at most once and the appearing summarization of possible recent frequent itemsets is recorded. According to the data structure of appearing summarization, the outdated data which does not belong to the current window can be deleted without needing to store the transactions in the current window. Then recent frequent itemsets can be mined approximately and efficiently. Among the two approaches, FCP algorithm stores the accumulative counts for itemsets at their frequency changing points. Such information can be used to estimate the supports of itemsets in current window and then the recent frequent itemsets are mined approximately. The experimental results show that, FCP algorithm can achieve high precision and recall when used for mining recent frequent itemsets in data streams. Moreover, by comparing with the existing SW algorithm, it shows FCP algorithm improves the efficiency of data maintenance and mining process significantly and reduces the memory usage further.資料探勘資料流資料項集項目集