線上拍賣蘊含龐大商機，但詐騙者也開始混雜其中，讓消費者防不勝防。面對日益猖獗的線上拍賣詐騙，除了提醒交易者小心謹慎外，學者們提出各種詐騙偵測方法。一般而言，詐騙偵測的準確性與分類屬性集的效能息息相關。然而，前人大多使用經驗法則來設計屬性集，我們認為應有更系統化、更周全的考量。有鑒於此，本研究致力於發展詐騙偵測屬性集的挑選與建構方法，以提升詐騙偵測的準確性。為達成上述目標，首先，我們提出了一套基因式的屬性挑選方法，並設計了一套完備適應函數。在演化過程中，除了偵測準確率外，也同時顧及偵測成本的多寡，期能產生一組低成本、高效能的詐騙偵測屬性集。接著，本研究發展了一套語法演化式的屬性建構方法，以BNF為基礎，配合基因演算法，以各種不同方式組合原生屬性，以產生高效能的複合屬性。為了驗證提出方法的有效性，我們使用拍賣網站真實交易資料來進行實驗。實驗結果顯示，針對不同資料集，本研究提出的方法能有效縮減屬性集的大小，並獲得較佳的準確率。此外，語法演化後產生的新屬性也具有良好的偵測成功率，有助於總體準確的提升，與資料集維度的縮減。

Because of big commercial opportunity in online auctions, there are more and more fraudulent incidents. It is also difficult to let consumers aware fraudulent transactions. In the face of fraud in online auction, many scholars have proposed some fraud detection methods instead of reminding consumers to be careful. Generally, the success rate of fraud detection has a big relationship with the fraud detection feature set. Most of scholars designed their own feature set depends on experiences. In order to improving success rate of fraud detection and generating our feature set automatically by system. In this paper, we propose a BNF-based grammatical evolution method in feature construction and a genetic algorithms in feature selection for fraud detection. The grammatical evolution technique inspired by natural evolution is explored to detect fraudsters in online auctions. Moreover, we illustrate the effectiveness of our algorithm on a real dataset collected from a large online auction site Yahoo.

第一章 緒論	1
第二章 背景知識與文獻探討	6
2.1 線上拍賣詐騙偵測屬性集	6
2.2 詐騙分類屬性之挑選	7
2.3 基因演算法	9
第三章 詐騙偵測屬性挑選方法	13
3.1 屬性集來源	13
3.2 基因式屬性挑選方法	15
3.2.1 屬性編碼	15
3.2.2 適應性函數設計及調整	15
3.3 加速演化過程方法	17
第四章 詐騙偵測屬性建構方法	18
4.1 以BNF表示新屬性	18
4.2 語法演化式的新屬性產生方法	21
第五章 實驗結果	26
5.1 實驗設定	26
5.2 實驗結果	27
5.3 屬性建構之詐騙偵測效能驗證	29
第六章 結論及未來展望	32
參考文獻	33
附錄A、屬性集資訊	39
附錄B、演化過程各代最佳偵測成功率(S-RATE)之變化	41

====================圖目錄====================

圖2 1：運算樹的交配	9
圖2 2：基因演算法流程圖 (蘇木春、張孝德 民86)	10
圖2 3：基因演算法單點交配示意圖 (蘇木春、張孝德 民86)	11
圖2 4：基因演算法單點突變示意圖 (蘇木春、張孝德 民86)	12
圖3 1：物種基因編碼及屬性選取之關係圖	15
圖4 1：以BNF法表示屬性	18
圖4 2：屬性樹範例	20
圖4 3：屬性運算樹之基因編碼	22
圖4 4：物種的複製	23
圖4 5：說明屬性單點交配之範例	23
圖4 6：交配後產生之新屬性(運算樹)	24
圖4 7：物種單點突變方式	25
圖4 8：突變後之交配池	25
圖4 9：將子代取出，進行下一代演化	25
圖5 1：將各種偵測屬性集應用於不同資料集之成功率綜合比較	28


====================表目錄====================

表3–1：不同大小屬性集與其準確率關係	14
表4–1：原生屬性集	19
表4–2：屬性樹節點定義	20
表4–3：物種複製個數設定範例	22
表5–1：不同資料來源與不同屬性集之準確率	27
表5–2：將各種偵測屬性集應用於不同資料集之成功率綜合比較	28
表5–3 : 資料來源及屬性集綜合比較(S-Rate)	29
表5–4：原生屬性集各屬性之成功率(S-Rate)	30
表5–5：語法演化產生之新屬性之成功率(S-Rate)前五名	31
表5–6：各屬性集成功率(S-Rate)比較	31

1.	劉祐宏. 線上拍賣詐騙偵測之屬性挑選與流程設計 - Construction for the Classification Feature Selection and the Fraud Detection Flow in Online Auctions. 淡江大學資訊管理學系碩士班, 2012.
2.	蘇木春、張孝德. 機器學習 類神經網路、模糊系統以及基因演算法則. 台北市: 全華科技圖書股份有限公司, 1997.
3.	財團法人資訊工業策進會. 10 18, 2010. http://www.iii.org.tw/Default.aspx.
4.	鄭孝儒. 線上拍賣潛伏期詐騙者之有效偵測 - Effective detection for latent fraudsters in online auctions. 淡江大學資訊管理學系碩士班, 2011.
5.	eBay 交易安全 網上拍賣自保招數 ─ 詐騙賣家的特徵 . 2013. http://pages.ebay.com.hk/securitycenter/education/fraud_traits.html.
6.	Ian H. Witten , Eibe Frank , Mark A. Hall. DATA MINING : Practical Machine Learning Tools and Techniques. Morgan Kaufmann Publishers, 2011.
7.	Quinlan, J. R. "Programs for machine learning." San Mateo CA: Morgan Kaufmann, 1993.
8.	Tomasz Kaszuba , Albert Hupa , Adam Wierzbicki. "Advanced Feedback Management for Internet Auction Reputation Systems." IEEE Computer Society, 2010.
9.	Aha, D. K.:Instance-based learning algorithms. Machine Learning. 6:37-66, 1991.
10.	Bay, Stephen D., "Nearest Neighbor Classification from Multiple Feature Subsets", Machine Learning, 1998.
11.	Bhattacharjee, R., and Goel, A. Avoiding Ballot Stuffing in eBay-like Reputation Systems. ACM SIGCOMM'05 workshops, Aug. 22-26, 2005, pp. 133-137.
12.	Brandt, F., "Fundamental Aspects of Privacy and Deception in Electronic Auctions", Ph.D. Thesis, 2003.
13.	Brodley, Carla E. and Friedl, Mark A., "Identifying and Eliminating Mislabeled Training Instances, Proceedings of Thirteenth National Conference on Artificial Intelligence August 4-8, 1996, Portland, OR, pp. 799-805.
14.	Chandola, V., Banerjee, A., and Kumar, V. (2009), "Anomaly detection: A survey," ACM Comput. Surv. 41, 3 (Jul. 2009), 1-58.
15.	Chang W.H. and Chang, J.S.: A Multiple-Phased Modeling Method to Identify Potential Fraudsters in Online Auctions. The 2nd International Conference on Computer Research and Development (ICCRD 2010), May 7 - 10, 2010, Kuala Lumpur, Malaysia.　http://www.iccrd.org/ , 2010.
16.	Chang, E., T. Dillon, F.K. Hussain ,"Trust and Reputation for Service-Oriented Environments: Technologies for Building Business intelligence, " Wiley, May 2007.
17.	Chang, W.H. and Chang, J.S. "An Online Auction Fraud Screening Mechanism for Choosing Trading Partners"　2010 The 2nd International Conference on Education Technology and Computer (ICIEE 2010), June 22-24, 2010, Shanghai, China
18.	Chang, W.H. and Chang, J.S., An Early Fraud Detection Mechanism for Online Auctions Based on Phased Modeling. The IEEE International Workshop on Mobile Systems E-commerce and Agent Technology (MSEAT 2009), Dec 3-5, 2009, Tamkang University, Taipei, Taiwan.
19.	Chang, W.H. and Chang, J.S., Using Clustering Techniques to Analyze Fraudulent Behavior Changes in Online Auctions. 2010 International Conference On Networking and Information Technology (ICNIT 2010), June 11-13, 2010, Manila, Philippine, http://www.icnit.org/ , 2010.
20.	Chang, W.-H. and Chang, J.-S. , “An Effective Early Fraud Detection Method for Online Auctions,” summated to Electronic Commerce Research and Applications, 2011. (accepted for publication subject to minor revision)
21.	Chang, W.-H. and Chang, J.-S. , “Analysis on the Strategies of Fraudulent Behavior Flipping in Online Auctions,” 2011 (Working Paper)
22.	Chau, D.H., and Faloutsos, C. (2005). Fraud detection in electronic auction. European Web Mining Forum at ECML/PKDD,
23.	Chau,D.H., Pandit,S., and Faloutsos,C.:Detecting fraudulent personalities in networks of online auctioneers. Proceedings of PKDD 2006, pp.103-114, 2006.
24.	Chau,D.H., Pandit,S., Faloutsos,C., and Wang,S..: NetProbe: A fast and scalable system for fraud detection in online auction networks. Proceedings of the 16th International Conference on World Wide Web, pp. 201-210, 2007.
25.	Chouchoulas A. and Q. Shen, “Rough set-aided keyword reduction for text categorisation,” Appl. Artif. Intell., vol. 15, no. 9, pp. 843–873, 2001.
26.	Dellarocas, C. and Wood, C. A. The Sound of Silence in Online Feedback: Estimating Trading Risks in the Presence of Reporting Bias, Management Science 54(3), March 2008, 460-476.
27.	Dellarocas, C. Immunizing online reputation reporting systems against unfair ratings and discrimatory behavior. Proceedings of the second ACM Conference on Electronic Commerce, October 2000.
28.	Dellarocas, C. Mechanisms for coping with unfair ratings and discriminatory behaviour in online reputation reporting systems. International conference on Information Systems, December 2000.
29.	Dellarocas, C., "Analyzing the Economic Efficiency of eBay-like Online Reputation Reporting Mechanisms," ACM EC'01, Oct. 14-17, 2001, pp. 171-179.
30.	ebay Inc. :eBay 2009 annual report, http://files.shareholder.com/downloads/ebay/923940436x0x361552/b45137ee-aa41-4c2c-94ca-d72d5b0844be/eBay_77655_BANNERLESS.pdf , 2010.
31.	eBay Inc., EBAY 2008 Annual Report. http://investor.ebay.com/annuals.cfm, 2009
32.	eBay Inc., How Feedbacks Works. http://pages.ebay.com/help/feedback/howitworks.html, 2009.
33.	Eng, C., Chua H., and Wareham J., Fighting Internet Auction Fraud: An Assessment and Proposal, IEEE Computer, Oct. 2004, pp. 31-37. 
34.	Espejo et al., “SURVEY ON THE APPLICATION OF GENETIC PROGRAMMING TO CLASSIFICATION,” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 40, NO. 2, MARCH 2010.
35.	Frank, E. and Witten, I. H. Generating Accurate Rule Sets Without Global Optimization. In Proceedings of the Fifteenth international Conference on Machine Learning (July 24 - 27, 1998). J. W. Shavlik, Ed. Morgan Kaufmann Publishers, San Francisco, CA, 144-151.
36.	Gavish B. and Tucci, C.L., "Reducing Internet Auction Fraud," communication of the ACM, May 2008, vol. 51. No.5, pp89-97
37.	Gilad-Bachrach, R., Navot, A., and Tishby, N. 2004. Margin based feature selection - theory and algorithms. In Proceedings of the Twenty-First international Conference on Machine Learning (Banff, Alberta, Canada, July 04 - 08, 2004).
38.	Goes, P., Tu, Y. and Tung, A.,:Onine Auctions Hidden Metrics", Communications of the ACM, vol. 52, No.4, pp. 147-149, 2009. 
39.	Peng, H., Fuhui Long and Chris Ding, "Feature Selection Based on Mutual Information: Criteria of Max-Dependecy, Max-Relevance, and Min-redundancy," IEEE Transactions on Pattern Anaylsis and Machine Intelligence, vol.27, No.8, August 2005, pp1226-1238.
40.	Harmon, P., Genetic Algorithms and Evolutionary Programming, Intelligent Software Strategies, 1994 June, Vol.5, No 6
41.	Igor Kononenko: Estimating Attributes: Analysis and Extensions of RELIEF. In: European Conference on Machine Learning, 171-182, 1994.
42.	JENSEN AND SHEN, “FUZZY-ROUGH SETS ASSISTED ATTRIBUTE SELECTION,” IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 15, NO. 1, FEBRUARY 2007. 
43.	Jensen, R. and Shen, Q., “Are More Features Better? A Response to Attributes Reduction Using Fuzzy Rough Sets, “ IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 17, NO. 6, DECEMBER 2009.
44.	Kauffman, R. J. and Wood, C. A., The effects of shilling on final bid prices in online auctions. Electronic Commerce Research and Applications vol. 4 (2005) pp. 21-34.
45.	Kazem, H., Hasan, Q. and Khan R. Z., Fraud/Privacy Protection in anonymous Auction. The second international conference on Internet monitoring and Protection, 2007 (ICIMP 2007).
46.	Kenji Kira, Larry A. Rendell: A Practical Approach to Feature Selection. In: Ninth International Workshop on Machine Learning, 249-256, 1992.
47.	Kohavi, Ron and John, H.George, "Wrappers for feature subset selection", Artificial Intelligence 97 (1997), pp. 273-324
48.	K. Krawiec, “Genetic programming-based construction of features for machine learning and knowledge discovery tasks,” Genet. Program. Evol. Mach., vol. 3, no. 4, pp. 329–343, Dec. 2002.
49.	Liang H. S, Chang J.-S., Chang W. S.，”AntiFraud: a real time fraud detection system for online auctions”，2011 (Working Paper)
50.	Liu, H. and Setiono, R. 1997. Feature Selection via Discretization. IEEE Trans. on Knowl. and Data Eng. 9, 4 (Jul. 1997), 642-645. 
51.	Marko Robnik-Sikonja, Igor Kononenko: An adaptation of Relief for attribute estimation in regression. In: Fourteenth International Conference on Machine Learning, 296-304, 1997.
52.	National White Collar Crime and the Federal Bureau Investigation: 2009 Internet Crime Report - January 1- December 31, 3 http://www.ic3.gov/media/annualreport/2009_IC3Report.pdf , 2010
53.	Pandit, S., Chau, D.-H., Wang, S., and Faloutsos, C. NetProbe: A Fast and Scalable System for Fraud Detection in Online Auction Networks. WWW 2007, May 8-12, 2007, Banff, Alberta, Canada, pp. 201-210.
54.	Pawlak , Zdzisław, “Rouugh sets: Theoretical Aspects of Reasoning about Data,” Springer, 2001.
55.	Pelleg, D. and Moore, A. W.:X-means: Extending K-means with Efficient Estimation of the Number of Clusters," In Proceedings of the Seventeenth international Conference on Machine Learning (June 29 - July 02, 2000). P. Langley, Ed. Morgan Kaufmann Publishers, San Francisco, CA, 727-73, 2000.
56.	Quinlan, J. R..:C4.5:Programs for machine learning. San Mateo CA: Morgan Kaufmann, 1993.
57.	Ryan, C., J. Colline, and M. O’Neill. Grammatical evolution: Evolving programs for an arbitrary language. In 1st European Workshop on Genetic Programming Proceedings, LNCS 1391, pages 83–95. Springer, 1998.
58.	Sen and Clark, “A Grammatical Evolution Approach to Intrusion Detection on Mobile Ad Hoc Networks,” WiSec’09, March 16–18, 2009, Zurich, Switzerland, pp. 95-102.
59.	Sherrah, J. R. E. Bogner, and A. Bouzerdoum, “Automatic selection of features for classification using genetic programming,” in Proc. Australian New Zealand Conf. Intell. Inf. Syst., Piscataway, NJ: IEEE, Nov.1996, pp. 284–287.
60.	Smith, M. G. and L. Bull, “Genetic programming with a genetic algorithm for feature construction and selection,” Genet. Program. Evol. Mach., vol. 6, no. 3, pp. 265–281, Sep. 2005.
61.	Michelle, T. M., "Machine Learning", McGrow Hill 1997.
62.	Witten, I. H. and Frank, E., Data mining: Practical machine learning tools and techniques. San Francisco: Morgan Kaufmann, 2005.
63.	Yahoo-Kimo, On the display and calculation of feedbacks,  http://help.cc.tw.yahoo.com/cp_info.html?id=2402, 2009.
64.	Yu, B., and M. P. Singh, "Detecting Deception in Reputation Management," AAMAS'03, July 14-18, 2003, pp.73-80.