(3.236.222.124) 您好!臺灣時間:2021/05/13 20:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:陳建國
論文名稱:利用基因演算法於KNN近似查詢之種類型資料對映演算法
論文名稱(外文):Mapping categorical data with genetic algorithm for KNN approximate search
指導教授:郭煌政郭煌政引用關係
學位類別:碩士
校院名稱:國立嘉義大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:57
中文關鍵詞:記憶基礎推理順序路徑基因演算法對映演算法
外文關鍵詞:Memory-based ReasoningOrdering PathGenetic AlgorithmsMapping Algorithms
相關次數:
  • 被引用被引用:3
  • 點閱點閱:258
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:79
  • 收藏至我的研究室書目清單書目收藏:0
記憶基礎推理能廣泛的運用在不同的資料型態,推理時新資料必須與訓練資料集內的每一筆資料比較相似度,以找出新資料之k筆鄰近資料,這是需花費很高的時間成本的,若能將所有資料建構在索引結構上,便可加速推理以找出新資料之k筆鄰近資料,但是必須將種類型欄位資料轉換成數值型欄位資料,方能將數值型欄位資料存入索引結構中,以便後續之查詢,而種類型欄位資料的轉換可透過順序路徑來達成,尋找出順序路徑也是需要花費相當高的時間成本,因此本文提出運用基因演算法來找出順序路徑。
我們用染色體來表示路徑,經由基因演算法的基因操作後,產生出新的世代族群。但是,當染色體經過交配後,可能產生不合法的染色體,也就是說,在經過交配之後的路徑,在該路徑上會有頂點重複的情形,所以我們在演算法中添加了染色體修補的功能,使得該路徑上不會有頂點重複的情形。
由實驗結果可以看出,當我們將基因演算法運用在真實資料時,從所有案例中所求出的k筆鄰近資料為標準,相對於利用索引機制從少數案例中所求出的k筆鄰近資料來說,有很高的準確性。
Memory-Based Reasoning (MBR) can be applies to applications in various data types. MBR predicts the target value of a new instance based on a training dataset. The target value of the new instance can be predicted by the k nearest neighbors (KNN) in the training dataset. In order to retrieve the KNN instances, the instance between the new instance and each instance in the training dataset is computed. It is time consuming when the training dataset is very large. We can use an indexing mechanism to filter instances for distance computing. It is difficult to index categories. Therefore, we map categories of an attribute to numbers. The distances among the categories form a weighted complete graph. We then order the categories on a simple path, called ordering path. Categories are mapped to numbers according to their position orders.
In this paper we propose genetic algorithms to find the ordering path. We use a chromosome to encode a path and use score of an ordering path as fitness value. We develop a method to repair illegal chromosomes, due to crossover operation. Experiments are performed on a real-life dataset. Using the index to filter a small fraction of the dataset for approximate KNN searching. The result shows high percentage of true KNN instances have been filtered.
中文摘要 i
英文摘要 ii
誌謝 iii
論文目錄 iv
圖表目錄 vi
表格目錄 viii
第一章 概論 1
1.1 研究背景 1
1.2 研究動機 3
1.3 研究目的 8
1.4 論文架構 9
第二章 相關研究 11
2.1 索引結構之相關研究 13
2.1.1 R-tree 索引結構 13
2.1.2 葉節點和內部節點的表示方式 14
2.2 對映演算法之相關研究 15
2.2.1 FarthestPairFirst演算法 16
2.2.2 NearestNeighborFirst演算法 17
2.2.3 Expanding演算法 18
2.3 基因演算法之相關研究 19
2.3.1 基因演算法的相關名詞 20
2.3.2 基因演算法的演算流程 20
第三章 順序路徑之評估 27
第四章 用基因演算法解決排順位問題 31
4.1 修補式基因演算法 31
4.2 舉例說明 33
第五章 實驗結果 42
5.1 人造資料實驗 42
5.2 UCI真實資料實驗 50
第六章 結論與未來研究方向 54
6.1 結論 54
6.2 未來研究方向 55
參考文獻 56
[1] Thomas Bäck, Ulrich Hammel, Hans-Paul Schwefel, “Evolutionary Computation: Comments on the History and Current State,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, 1997, pp. 3-17.
[2] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger, “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” ACM SIGMOD, 1990, pp. 322-331.
[3] Michael J.A. Berry, Gordon Linoff, Data Mining Techniques: for Marketing, Sales, and Customer Support, Wiley, 1997.
[4] Venkatesh Ganti, Johannes Gehrke, Raghu Ramakrishnan, “CACTUS-Clustering Categorical Data Using Summaries,” ACM KDD, 1999, pp. 73-83.
[5] Antomn Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” ACM SIGMOD, 1984, pp. 47-57.
[6] Jiawei Han, Micheline Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, 2000.
[7] John H. Holland, Adaptation In Natural and Artificial Systems, The University of Michigan Press, 1975.
[8] Huang-Cheng Kuo, Yi-Sen Lin, Jen-Peng Huang, “Distance Preserving Mapping from Categories to Numbers for Indexing,” 8th International Conference on Knowledge-Based Intelligent Information & Engineering Systems, New Zealand, September 2004.
[9] Zne-Jung Lee, Shun-Feng Su, Chou-Yuan Lee, Yao-Shan Hung, “A Heuristic Genetic Algorithm for Solving Resource Allocation Problems,” Knowledge and Information Systems, Vol. 5, No. 4, November 2003, pp. 503-511.
[10] Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, third edition, 1999.
[11] Timos Sellis, Nick Roussopoulos, Christos Faloutsos, “The R+-Tree: A Dynamic Index for Multi-Dimensional Objects,” VLDB Conference, 1987, pp. 507-518.
[12] Chuan-Kang Ting, Sheng-Tun Li, Chungnan Lee, “TGA: A New Integrated Approach to Evolutionary Algorithms,” Congress on Evolutionary Computation, 2001, pp. 917-924.
[13] C. L. Blake and C. J. Merz, UCI Repository of machine learning databases [http://www.ics.uci.edu/~mlearn/MLRepository.html]. Irvine, CA: University of California, Department of Information and Computer Science, 1998.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔