Mining Customer Value From Association Rules to Direct Marketing

對於傳統的行銷方法而言，企業在決定行銷對象時，大多無特定目標發送廣告訊息。但事實上願意回應的消費者總是很少，造成企業在行銷資源上的浪費及顧客的反感。所以近年來，「Direct marketing for profit optimization」成為企業最想應用data mining技術解決的問題之一，它同時也是ACM在1998年所舉辦的KDD-CUP競賽問題。

一般而言，企業必須在考慮每份廣告的行銷成本之下，找出潛在傾向回應的消費者，進而只針對該消費族群行銷，並使得企業獲得的利益最大化。然而，它通常會面臨「imbalanced data」及「inverse correlation」的挑戰。在一般的狀況下，付諸回應行動的消費者佔整體行銷名單的比例非常少(在KDD-CUP-98 dataset中只佔5%)，而大部分的data mining演算法卻是偏好學習資料整體的行為規則，所以要學習在稀少類別的規則是較困難的。另一方面，愈是可能回應的消費者，通常對企業貢獻的利益則愈少，所以若只想對願意回應的消費者行銷，成效相當有限。

以往的研究工作大多先預估顧客願意回應的機率，然後在較可能回應的顧客名單之中，再找出貢獻較大的族群做為行銷對象。他們的缺失在於顧客的貢獻在先前預測回應機率的步驟被忽略，尤其是當inverse correlation現象存在的時候，潛在較大貢獻的族群更是越容易被剔除。所以本篇論文使用focus association rule一次學習顧客回應及其貢獻這兩種行為，作法分成三個步驟。

我們取50%作為learning set，50%作為validation set。再從learning set中取出70%作為building set，30%作為testing set for turning minsup, maxsup

1. Rule Generating

我們在回應名單的資料集中，尋找大於使用者自訂minimum support的frequent item(稱為focus item)，而且此focus item的出現次數必須低於在非回應名單資料集中的maximum support。然後再從回應名單資料集中找由focus item組成的frequent itemset做為"respond rule"。因為我們只從回應名單資料集中找frequent itemset，所以能解決「imbalanced data」問題。除此之外，我們可設定較低的minimum support以避免刪除profitable rules，同時也可設定maximum support來決定所要刪除的focus item數量，以控制演算法的效能及資料維度(可解決high demensionality問題)

2. Model Building

計算每條respond rule在building set中的平均獲利，並決定規則Cover record的順序: Average Profit > Generality > Simplicity > Totality of order

3. Model Pruning

預估每條respond rule在預測的testing error (pessimistic estimation)，進而計算出每條respond rule預估的期望獲利。然後把建立由respond rule組成的covering tree，以bottom-up的方式，刪除期望獲利較低且較specific的規則

本篇論文最後產生的平均獲利高於KDD-Cup-1998第一名41%，也高於2001年之前所發表的三篇論文，傳送的mail數量也是最低。檢視TOP 10的規則，我們發現高獲利的規則不一定擁有較高的support及confidence，代表這些規則不一定是經常出現或是能準確地判斷顧客是否respond。最後，作者認為結果會有這麼顯著的提升是因為association rule克服了inverse correlation，並且擁有global search及不用預測顧客回應機率的優點。

POLYPHONET : An Advanced Social Network Extraction System from the Web

本篇論文出自於WWW 2006，介紹的是一個人與人之間社群網路系統的建立，該系統是利用搜尋引擎，找出包含給定人名的網頁，並依擷取下來的網頁中人名的Co-occurrence，去計算人與人間的關聯度，進而建構出Social network。

論文當中，作者首先介紹一些在Social Network Extraction上過去常用的基本方法，並提及關於同名同姓的問題。接著，將人與人之間的關係分類成數種, 由於兩兩計算兩個人名之間的關聯度需要相當大的計算量、因此如何縮簡使用搜尋引擎query網頁的次數、也是重要的問題之一. 另外作者也提出以與人有關的word做為描述該人的metadata、以及利用metadata提供人與人間關聯度的另一種算法。

之後作者展示了POLYPHONET實際使用的介面與結果，且在最後提及Super Social Network Mining的想法，該想法與Social Network Mining最大的差異在於Super Social Network Mining具有自我修正的機制，能夠視情況適當分割或者是合併，並希望將來也能將這套機制整合至系統內。

WWW 2006 Edinburgh, Scotland. pp. 397 - 406.

Homepage live: automatic block tracing for web personalization

這篇論文觀察到personal homepage的趨勢，包括Microsoft和Google都有做personal homepage，並在homepage中讓人放置許多功能區塊。因此論文提出一個系統Homapge Live，可以讓使用者在這個網頁上建立個人首頁，並且加入小區塊。Homepage live的小區塊特色是可以讓使用者作網頁中的block tracing，也就是網頁區塊的monitering。這篇論文重點在於系統在目標網頁版本更新後，如何正確地抓取使用者所想看到的區塊。

首先將原網頁P_old和新網頁P_new表示成DOM Tree然後執行以下步驟：

1. 找出Fix Nodes：Fix Node代表在P_old及P_new中內容重複的node。
2. 產生Reduced Tree：刪除掉P_old及P_new中的Fix Nodes。
3. Mapping：此時P_old和P_new都已經成為reduced tree，將P_old和P_new作tree mapping，找出P_new中對應到的目標區塊。

Tree Mapping作者用Minimum Edit Distance Mapping來作，找出P_new中對應到P_old中使用者選取的區塊。

實驗的部分作者測試系統的accuracy和effectiveness，和Direct Path Finding(DPF)、Tag String Matching(TSM)、Tree Edit Distance(TED)三個方法比較。在accuracy部分證明系統可以超過DPF和TSM，並和TED達到一樣的效果; 在effectiveness部分證明系統時間複雜度遠低於TED，並且證明了系統的scalability。

出處：Proceedings of the 16th international conference on World Wide Web (WWW2007)

研究計畫

計畫名稱	補助或委託機構	起訖年月	計畫內擔任的工作
行動關懷社會之建構與服務(3/3)	國科會(97-2627-E-008-001-)	2008/8/1 至 2009/7/31	共同主持人
線上拍賣網站中銷售策略的研究	國科會(97-2221-E-008-088-)	2008/8/1 至 2009/7/31	主持人
Web資訊整合服務系統開發之研究	國科會(96-2221-E-008-091-MY2)	2007/8/1 至 2009/7/31	主持人
行動關懷社會之建構與服務(2/3)	國科會(96-2627-E-008-001-)	2007/8/1 至 2008/7/31	共同主持人
行動關懷社會之建構與服務(1/3)	國科會(95-2627-E-008-002-)	2006/8/1 至 2007/7/31	共同主持人
資料視覺化與群聚分析之雙向研究	國科會(95-2221-E-008-076-)	2006/8/1 至 2007/7/31	主持人
時序資料庫中跨交易關聯規則探勘之研究	國科會(94-2213-E-008-020-)	2005/8/1 至 2006/7/31	主持人
資料串流之非同步週期型樣探勘研究	國科會(93-2213-E-008-023- )	2004/8/1 至 2005/7/31	主持人
從半結構文件至自由格式文件之資訊擷取方法之研究	國科會(92-2213-E-008-028- )	2003/8/1 至 2004/7/31	主持人
IEPAD多屬性網頁資訊自動擷取系統的設計與資訊整合系統之研發(2/2)	國科會(91-2213-E-008-030- )	2002/8/1 至 2003/7/31	主持人
網際網路半結構化文件自動萃取系統之商品化研究	國科會(91-2622-E-008-018-CC3)	2002/6/1 至 2003/5/31	主持人
IEPAD多屬性網頁資訊自動擷取系統的設計與資訊整合系統之研發(1/2)	國科會(90-2213-E-008-042- )	2001/8/1 至 2002/7/31	主持人
基因體探索: 結構及生物意義－子計畫二：應用資料探採於重複序列資料庫以探索基因體調控規則(I)	國科會(90-2213-E-008-053- )	2001/8/1 至 2002/7/31	主持人
半結構性資訊擷取規則之建構與分析	國科會(89-2213-E-008-056- )	2000/8/1 至 2001/7/31	主持人

論文發表 (updated 06/05/2010)

citation by dblp

Journal Papers

1. T.-K. Fan and C.-H. Chang: Sentiment Oriented Contexture Advertising. To appear in Journal of Knowledge and Information System.
2. M. Kayed and C.-H. Chang: FiVaTech: Page-Level Web Data Extraction from Template Pages. IEEE Trans. Knowl. Data Eng. Vol. 22, No.2, pp. 249-263, 2010.
3. T.-K. Fan and C.-H. Chang: Exploring Evolutionary Technical Trends From Academic Research Papers. J. Inf. Sci. Eng. Vol. 26, No. 1, pp. 99-117, 2010.
4. K.-Y. Huang and C.-H. Chang. Efficient Mining of Frequent Episodes from Complex Sequences, Information Systems, Vol. 33. No. 1, pp. 96-114, 2008. doi:10.1016/j.is.2007.07.003
5. K.-Y. Huang, C.-H. Chang, and Kuo-Zui Lin. Efficient Discovery of Frequent Continuities by Projected Window List Technology, Journal of Information Science, Vol. 24, No. 4, pp. 1041-1064, 2008.
6. Y.C. Wu and C.-H. Chang. Efficient Text Chunking using Linear Kernel with Mask Method, Knowledge Based Systems, Vol. 20, Issue 3, pp. 209-219, 2007. doi:10.1016/j.knosys.2006.04.016
7. C.-H. Chang, M. Kayed, M. R. Girgis, K. Shaalan, A Survey of Web Information Extraction Systems, IEEE TKDE (SCI, EI), Vol. 18, No. 10, pp. 1411-1428, Oct. 2006.
8. K.-Y. Huang and C.-H. Chang, SMCA: A General Model for Mining Asynchronous Periodic Patterns in Temporal Databases, IEEE Transactions on Knowledge and Data Engineering (SCI, EI), Vol. 17, No. 6, pp. 774-785, June 2005.
9. C.-H. Chang and Z.-K. Ding, Categorical Data Visualization and Clustering Using Subjective Factors, Data and Knowledge Engineering (SCI expanded), Vol. 53, Issue 3, pp. 243-262, June 2005. doi:10.1016/datak.2004.09.001
10. C.-N. Hsu, C.-H. Chang, C.-H. Hsieh, J.-J. Lu, and C.-C. Chang, Reconfigurable Web Wrapper Agents for Biological Information Integration, JASIST (SCI expanded), Special Issue on Bioinformatics, Vol. 56, No. 5, pp. 505--517, March 2005.
11. C.-H. Chang and S.-C. Kuo, OLERA: A semi-supervised approach for Web data extraction with visual support, IEEE Intelligent Systems (SCI, EI), Vol. 19, No. 6, pp. 56--64, Dec. 2004.
12. C.-H. Chang, J.-J. Chiou, H. Siek, J.-J. Lu, and C.-N. Hsu, Reconfigurable Web Wrapper Agents, IEEE Intelligent Systems (SCI, EI), Vol. 18, No. 5, pp. 34--40, Oct. 2003.
13. C.-H. Chang, C.-N. Hsu, and S.-C. Lui, Automatic Information Extraction From Semi-Structured Web Pages By Pattern Discovery, Decision Support Systems Journal (SCI expanded), Vol. 35, Issue 1, pp. 129--147, Apr. 2003. doi:10.1016/S0167-9236(02)00100-8
14. C.-C. Hsu and C.-H. Chang, WebYacht: A Concept-based Search Tool for WWW , International Journal on Artificial Intelligence Tools, 2000.
15. C.-H. Chang and C.-C. Hsu, Enabling concept-based relevance feedback on World Wide Web, In IEEE Transactions on Knowledge and Data Engineering (SCI), Special Issue on Web Technologies, Vol.11, No.4, pp. 595-609, July/August 1999.
16. C.-H. Chang and C.-C. Hsu, Enabling Web Information Retrieval through Query Expansion via Contrast Analysis , Computer Networks and ISDN Systems, Vol. 30, pp.621-623, 1998.
17. C.-H. Chang and C.-C. Hsu, Customizable Multi-Engine Search Tool based on Clustering , In Computer Networks and ISDN Systems, Vol. 29, pp.1217-1224, 1997.

Conference Papers

1. Chia-Hui Chang and Shu-Ying Li, MapMarker: Extraction of Postal Addresses and Associated Information for General Web Pages", To appear in IEEE/WIC/ACM Web Intelligence, 2010.
2. Teng-Kai Fan and Chia-Hui Chang: Blogger-centric contextual advertising. CIKM 2009: 1803-1806, 2009.
3. C.-H. Chang and J.-H. Lin: Decision Support and Profit Prediction for Online Auction Sellers. The First ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data (U'09), pp. 1-8, 2009.
4. T.-K. Fan and C.-H. Chang: Sentiment Oriented Contextual Advertising. Advances in Information Retrieval, 31th European Conference on IR Research, ECIR 2009, Toulouse, France, April 6-9, 2009. LNCS 5478 Springer 2009, pp. 202-215.
5. Teng-Kai Fan and Chia-Hui Chang, Exploring Evolutionary Technical Trends From Research Papers. The Eighth IAPR Workshop on Document Analysis Systems, DAS2008 (poster session). Nara, Japan. Sep 16-19, 2008.
6. C.-H. Chang, Shih-Feng Yang, Che-Min Liou, Mohammed Kayed. Gadget Creation for Personal Information Integration on Web Portals, IEEE International Conference on Information Reuse and Integration (short paper), Las Vegas, USA, 2008.
7. Mohammed Kayed, Chia-Hui Chang, Khaled Shaalan, and Moheb Ramzy Girgis. FiVaTech: Page-Level Web Data Extraction from Template Pages, ICDM 2007, Workshop on Web2.0 Environment, Omaha, NE, USA. Oct. 28-31, 2007.
8. C.-H. Chang and Kun-Chang Tsai. Aspect Summarization from Blogsphere for Social Study, ICDM 2007, Workshop on Web2.0 Environment, Omaha, NE, Oct. 28-31, 2007.
9. K.-Y. Huan, C.-H. Chang, Jiun-Hung Tung, Cheng-Tao Ho. COBRA: Closed Sequential Pattern Mining Using Bi-phase Reduction Approanch, Accepted by DaWak 2006, Krakow, Poland.
10. Y.-C. Wu, C.-H. Chang, Y.-S. Lee: A General and Multi-lingual Phrase Chunking Model Based on Masking Method. Proceedings of the 7th International Conference on Computational Linguistics and Intelligent Text Processing (CICLING 2006), Mexico City, Mexico, February 19-25, 2006. LNCS 3878, pp. 144--155.
11. K.-Y. Huang and C.-H. Chang. Efficient Mining Strategy for Frequent Serial Episodes in Temporal Database, The 8th Asia Pacific Web Conference (short paper), Harbin, China, Jan. 16-18, 2006. LNCS 3841, pp. 824--829.
12. K.-Y. Huang, C.-H. Chang, and Kuo-Zui Lin, ClosedPROWL: Efficient Mining of Closed Frequent Continuities by Projected Window List Technology, SIAM International Conference on Data Mining (short paper), CA, USA, Apr. 21-23, 2005.
13. K.-Y. Huang, C.-H. Chang, and Kuo-Zui Lin, COCOA: An Efficient Algorithm for Mining Inter-transaction Associations for Temporal Database, In the Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD04 (poster), Pisa, Italy, 2004. LNAI 3202 (SCI expanded), pp. 509--511.
14. C.-H. Chang and Z.-K. Ding, Categorical Data Visualization and Clustering using Subjective Factors, In the Proceedings of the 6th International Conference on Data Warehousing and Knowledge Discovery (DaWaK04), Zaragoza, Spain, 2004. LNCS 3181 (SCI expanded), pp. 229-238.
15. K.-Y. Huang and C.-H. Chang, Mining Periodic Patterns in Sequence Data, In the Proceedings of the 6th International Conference on Data Warehousing and Knowledge Discovery (DaWaK04), Zaragoza, Spain, 2004. LNCS 3181 (SCI expanded), pp. 401-410.
16. K.-Y. Huang, C.-H. Chang, and Kuo-Zui Lin, PROWL: An Efficient Frequent Continuity Mining Algorithm on Event Sequences, In the Proceedings of the 6th International Conference on Data Warehousing and Knowledge Discovery (DaWaK04), Zaragoza, Spain, 2004. LNCS 3181 (SCI expanded), pp. 351-360.
17. C.-H. Chang and S.C. Kuo, OLERA: On-Line Extraction Rule Analysis for Semi-structured Documents, The IASTED International Conference on ARTIFICIAL INTELLIGENCE AND APPLICATIONS (AIA 2004). Feb. 16-18, 2004, Austria.
18. K.-Y. Huang and C.-H. Chang, Asynchronous Periodic Pattern Mining from Multi-event Time Series Databases, The IASTED International Conference on DATABASES AND APPLICATIONS (DBA 2004), Feb. 17-19, 2004, Austria.
19. C.-N. Hsu, C.-H. Chang, H. Siek, J.-J. Lu, J.-J. Chiou, Reconfigurable Web Wrapper Agents for Web Information Integration, IJCAI 2003 Workshop on Information Integration on the Web, IIWeb-03, Aug. 2003, pp. 15-20.
20. C.-H. Chang and Shi-Hsan Yang, Enhancing SWF for Incremental Association Mining by Itemset Maintenance, In the Proceedings of the seventh Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD03), Korea, 2003. LNAI 2637 (SCI expanded), pp. 301-312.
21. C.-H. Chang, Sequential Pattern Mining for Web Extraction Rule Generalization, The 6th World multiconference on Systemics, Cybernetics and Informatics, July 14-18, 2002, Orlando, Florida
22. C.-H. Chang, S.-C. Kuo, K.-Y. Hwang, T.-H. Ho and C.-L. Lin, Automatic Information Extraction for Multiple Singular Web Pages, In the Proceedings of the sixth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD02), Taiwan, 2002. LNAI 2336 (SCI expanded), pp. 297-303.
23. C.-H. Chang. and S.-C. Lui. IEPAD: Information Extraction based on Pattern Discovery, In the Proceedings of the tenth International Conference on World Wide Web (WWW10), pp. 681-688, May 2-6, 2001, Hong Kong.
24. C.-H. Chang., S.-C. Lui, and Y.-C. Wu. Applying Pattern Mining to Web Information Extraction, In the Proceedings of the fifth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD01), Hong Kong, 2001. LNAI 2035 (SCI expanded), pp. 4-15.
25. C.-H. Chang, S.-C. Lui, and Y.-C. Wu. Semi-structured Information Extraction Applying Automatic Pattern Discovery , In Proc. of the fourteenth International Computer Symposium (ICS2000), Chia-Yi, Taiwan, Dec. 6-8. 2000.
26. C.-H. Chang, C.-C. Hsu and C.-L. Hou, Exploiting Hyperlinks for Automatic Information Discovery on the WWW , In Proc. of the tenth IEEE International Conference on Tools with Artificial Intelligence, (ICTAI98), Nov. 1998, Chien Tan Youth Activity Center, Taipei, Taiwan.
27. C.-H. Chang and C.-C. Hsu, Hypertext Information Retrieval for Short Queries , In Proc. of the IEEE Knowledge and Data Engineering Exchange Workshop, Nov. 1998, Chien Tan Youth Activity Center, Taipei, Taiwan.
28. C.-H. Chang and C.-C. Hsu, Enabling Web Information Retrieval through Query Expansion via Contrast Analysis , In Proc. of the seventh International Conference on World Wide Web (WWW7), Apr. 14-18, 1998, Brisbane, Queensland, Australia
29. C.-H. Chang and C.-C. Hsu, Constructing Personal Information Search Agents , In Proc. of the second Pacific Asia Conference on Knowledge Discovery and Data Mining (PAKDD98), Melbourne, Australia, 1998. LNAI 1394 (SCI expanded), pp. 374-375.
30. C.-H. Chang and C.-C. Hsu, A Multi-Engine Search Tool based on Clustering , In Proc. of the sixth international conference on World Wide Web, (WWW6), Apr.7-11, 1997, Santa Clara, CA

Domestic Conference

1. Shu-Gang Han and Chia-Hui Chang. Cleaning of Auction Data for Bidding Decision, 2007 National Computer Symposium, National Computer Symposium (全國計算機會議), Asia University, Taiwan.
2. 胡舒涵, 張嘉惠. 會議公告網站資訊擷取之研究, The 11th conference on Artiticial Intelligence and and Application (TAAI 2006).
3. 劉仁宇, 張嘉惠. 以網頁識別及清理改善資料擷取之研究, The 11th conference on Artiticial Intelligence and and Application (TAAI 2006).
4. 林千翔, 張嘉惠. 基於特製隱藏式馬可夫模型之中文斷詞研究. ROCLING XVIII: Conference on Computational Linguistics and Speech Processing, 2006.
5. 朱育德, 張嘉惠. 基於字詞內容之適應性對話系統. ROCLING XVIII: Conference on Computational Linguistics and Speech Processing, 2006.
6. 楊智宇, 吳毓傑, 張嘉惠. 問題答覆系統中使用語句分類排序方式之設計與研究. The 9th conference on Artiticial Intelligence and and Application (TAAI 2004).
7. 李泓儒, 張嘉惠. Web Cleaning: Page Segmentation and Data-rich Section Mining, The 1st Workshop on Intelligent Web Technology, IWT2004, In conjuction with the 16th ROCLING Conference.
8. C.-H. Chang, Information Extraction: A Pattern Mining Approach for Free-Form Text, 2003 The Joint Conference on AI, Fuzzy System, and Gray System, Taipei, Taiwan, Dec. 4--6, 2003.
9. C.-H. Chang, D.-S. Wu. Information Extraction and Query Model Design for Taiwan Wild Bird Database, 2003 The Joint Conference on AI, Fuzzy System, and Gray System, Taipei, Taiwan, Dec. 4--6, 2003.
10. C.-H. Chang and C.-N. Hsu, Automatic Extraction of Information Blocks Using PAT Trees , In Proc. of the National Computer Symposium, Dec. 20-21, 1999, Taipei, Taiwan
11. C.-H. Chang and C.-C. Hsu, Infomation Searching and Exploring Applying Clustering and Genetic Algorithm , In Proc. of the first Agent Technology Workshop, Dec. 4, 1997, Taipei, Taiwan

實驗室成員 (Updated 8/15/2013)

PhD
102 Oviliani
101 莊秀敏 (Hsiu-Min Chuang)
100 張淵琮 (Yuan-Chung Chang)

100 周建龍(Chien-Lung Chou)

Master

103 黃鎧謙
103 林許平
103 凌杰甫
103 張弘暐
102 黃雅筠
102 許哲維
102 丁中立
102 鄭仲庭
102 高霆耀
102 胡育維

在職專班
103 湯國正
102 林奐均
101 吳佳儒
100 吳柏科
99 鍾智宇

99 蔡依達

專題生
102 楊佳靜
102 郭泰麟
101 何驊益
101 吳駿劭
101 劉至咸
101 劉季威 
100 張國斌

A New Suffix Tree Similarity Measure for Document Clustering

A New Suffix Tree Similarity Measure for Document Clustering

這篇論文想做的是關於文章的自動分群，使用的是結合Suffix Tree和Vector Space Document的方法，作者稱之為NSTC(new suffix tree document clustering algorithm)。

作者在論文中首先介紹了一個在1998年所提出的STC(suffix tree document clustering algorithm)，STC主要可分為三個步驟，第一是產生document的suffix tree，找出內部節點做為base cluster，第二步是base cluster 挑選，第三步是依據Jaccord coefficient來決定node是否具有direct link，最後各個connected graph即為分群的結果。換句話說，我們得到的是base cluster(相當於片語)的分群的結果, 任何文件若有包含這些片語，即會被歸為同一群，因此一個文件可能在不同群中出現．

而NSTC號稱欲將STC導入Vector Space Document，其做法於STC做完第二步後，以tfidf來算一個node在document的重要性，再以cosine來算document間的相似度，最後以這些相似度來做GAHC(Group-average Agglomerative Hierarchical Clustering)。因此其分群方法其實已經不同於STC所用的graph partitioning．好處是可以利用分群中的node來做為cluster的summary描述，但是這個好處在最後的實驗當中並不是很明顯。

最後的實驗裡，作者拿了STC和NSTC與傳統的GAHC做個比較，並以F-Measure做為評量的標準，發現NSTC確實相較於其他兩者有較好的表現。 但是終歸比較的是同樣的分群方法GAHC，只是表示方法一個是用node(片語)一個是用single term，似乎貢獻不大．　

WWW 2007 Banff, Alberta, Canada. pp. 121 - 130.

Supporting end-users in the creation of dependable web clips

當使用者利用 Microsoft FrontPage 等Web Authoring Tools建立自己的網頁時，常希望加入可以對網路資訊作monitoring的小區塊，例如擷取天氣預報、新聞…等等，將個人資料作information integration。有些網站有自行提供API或Mashup等工具讓使用者做資料擷取，但許多網站沒有相關工具。

Web Clip: 作者定義為end-user在自行製作網頁時，能夠即時擷取網頁資訊並顯示在網頁上的小區塊。一個Web Clip會針對某目標網站中的資料作monitoring，多個web clips可以整合到單一個人網頁。這篇論文提出Web Clipper，一個圖形化介面的Web Clip製作流程，讓使用者在 Microsoft Frontpage 中透過簡單操作就可以快速產生Web Clip並加入個人網頁中，並強調使用者不需要自行撰寫任何程式就可以完成工作。

Web Clipper主要分為四個部分：
1) Clipping 讓使用者選擇目標網頁中的區塊，記錄該區塊的HTML-Path。
2) Training 一個semi-supervised方法，為了提高區塊擷取的正確率，作者定義了數個Extraction Patterns，提供介面讓使用者選取哪些是Valid Patterns。
3) Deployment 記錄先前兩步驟的資訊並自動產生Web Clip的Ajax Script程式碼，同時在對2)中選取的Valid Patterns產生對應Filters，Filters用於評估Clip效果。
4) Filtering & Assessment 當發佈的Web Clip每次擷取資訊時，根據3)中建立的filters和2)中的patterns來計算confindence score，用來決定利用那個Filter擷取資料及檢驗Clip的Robustness。

實驗部分作者針對Web Clip的擷取效果，以及目標網站隨時間改變內容後系統正確擷取資訊的程度作評估，同時設計實驗來評估不同類型網頁區塊變化對資料擷取的影響(如block insertion, movement, deletion...等)。

出處：Proceedings of the 16th international conference on World Wide Web (WWW2007)

歷屆畢業論文 (Updated 8/15/2013)

PhD Thesis
98 范登凱 網路個人化廣告配置之研究
94 黃國瑜 交易型資料庫之跨交易關聯規則探勘之研究

Master Thesis (Graduated semester/ Name/ Thesis)
101-2 陳慶治
101-2 林伯翰
101-2 黃俞翔
101-2 鄭乃洪
101-2 陳貞伶
100-2 吳忠翰（在職專班） 行程邀約郵件的辨識與不規則時間擷取之研究
100-2 吳文斌 以聲符部件為主的漢字識字教學系統設計
100-2 趙士賢 平行化資訊理論共分群演算法
100-2 吳禹欣 改善三贏架構之行動廣告效果
100-2 陳柏志 The Design of Free Wireless Framework for Triple-win Mobile Advertising
99-2 謝承璋 Learning Transportation Modes with Two-Level Inference
99-2 劉睿哲 使用擴充資料進行共分群的協同式推薦系統
99-2 陳志銘 基於多元化部落格網頁之自動化擷取部落格主要文章
99-2 霍冠樺 手機廣告：使用者、廣告商及電信業者三贏架構
99-2 林書彥 形聲字發音規則探勘

98-2 林衍伶 非監督式網頁層次包覆程式之驗證
98-2 張志豪（在職專班） 機器學習應用於樣版網頁擷取之研究
98-2 潘立人（在職專班）資料搜尋系統視覺化與多維度分析之設計：以資訊工程研究論文檢索系統為例


97-2 李淑瑩 英文郵政地址與鄰近相關資訊擷取之研究
97-2 楊萍華 部落格意見檢索系統之設計-部落格內文之擷取與不相關部落格之過濾

97-1 楊傑程 應用樣式探勘與機器學習方法於中文未知詞擷取之研究
97-1 丁昭廷 以使用者為導向的Web資料整合系統之設計


96-2 林俊宏 線上拍賣結標價與期望獲利之預測
96-2 楊士峰 應用資料擷取於Web小工具開發之研究–多個資料源之資料整合

96-1 陳正揚 網頁意見特徵評價化之應用於旅館比較
96-1 施宗昆 使用隱藏式馬可夫模型之特定網頁資訊抓取蒐集

95-2 韓樹岡 以資料清潔為基礎的拍賣決策輔助系統
95-2 蔡坤璋 部落格理由摘要之社會科學應用
95-2 朱育德 基於字詞內容之適應性對話系統 


94-2 何承道 頻繁同構圖形探勘策略之研究
94-2 林千翔 基於特製隱藏式馬可夫模型之中文斷詞研究
94-2 童俊宏 無候選型樣產生之頻繁樹狀結構探勘
94-2 胡舒涵（在職專班） 會議公告網站資訊擷取之研究
94-2 劉仁宇（在職專班） 以網頁識別及清理改善資料擷取之研究


93-2 陳信伊 星狀座標之軸排列於群聚視覺化之應用
93-2 張立帆 由瀏覽歷程自動產生網頁抓取程式之研究
93-2 黃執強 同性質網頁資料整合之自動化研究
93-2 李季壕 動態網頁之樣版與資料分析研究

92-2 林國瑞 時序資料庫中緊密頻繁連續事件型樣之探勘
92-2 李泓儒 淨化網頁：網頁區塊化以及資料區域擷取
92-2 楊智宇 問題答覆系統中使用語句分類排序方式之設計與研究

91-2 丁智凱 非數值型資料視覺化與兼具主客觀的分群
91-2 郭釋謙 半結構化文件線上擷取規則分析之研究
91-2 何聰鑫 時序性資料庫中未知週期之非同步週期性樣板的探勘
91-2 林志龍 關聯性字組在文件摘要上成效的探討

90-2 楊士賢 遞增資料關聯式規則探勘之改進
90-2 張毓美 應用卡方獨立性檢定於關連分類問題
90-2 吳東軒 中文資訊擷取系統之設計與研究

89-2 呂紹誠 網際網路半結構性資料擷取系統之設計與實作
89-2 吳彥欽 非簡單瀏覽路徑之探勘與應用

A Study of Statistical Models for Query Translation ：Finding a Good Unit of Translation

利用雙語字典來翻譯query，目前有兩個比較重要的課題：一是如何增強字典的覆蓋度，二是如何從字典中選出正確的字來進行翻譯。而本篇文章著重在後者。

作者在論文中結合了三種的Model，分別為Co-occurence Model、Noun Phrase Model和Dependency Translation Model來幫助翻譯。這三種Model都是使用統計的資料（如：corpus），並藉由定義特徵函數，求最大化來取得較有可能的翻譯方式，三者的差異之處在於是針對不同的translation unit來進行處理。

Noun Phrase Model針對的是名詞片語，其利用大部分名詞片語可以直譯的特性，配合由字典中來尋找翻譯的Template，以對名詞片語進行翻譯，希望最佳化Translation Template和word selection機率乘積所組成的特徵函數。
Dependency Translation Model針對的是關係triples，意指在兩個單字w1及w2之間，經常存在一種關係r，使這三者產生一組triple(w1, r, w2)，其中r在本文中只限定為以下四種：(1)subject-verb (2)verb-object (3)adjective-noun (4)adverb-verb。希望最佳化w1及w2各別單字翻譯和目標語言triple被翻譯機率的乘積再乘上relation的值，當翻譯前後的r保持不變則relation的值為1，反之則為0。
Co-occurence Model則是針對上述兩者剩餘的部分，作者推論，一個正確的翻譯，其翻譯後的句子中單字彼此間的相關度會較高，即利用這個特性，我們對該句所有翻譯後的句子做排列組合，以特徵函數來做評分，找出組合後分數最高者進行翻譯，其好處是可以不用考慮跨語言間相似度的問題。

結合以上三種模式所設計的演算法步驟如下：

1.首先利用句子剖析找出查詢問句中的名詞片語和使用關係triples
2.接著使用NP Model來翻譯名詞片語
3.第三步使用Dependency Translation Model來翻譯關係triples
4.最後使用Co-occurence Model來翻譯剩餘其他的部分

在Co-occurence Model中，作者利用了Graphic Model，讓一個query translation的問題對應到一個undirected GM上，藉解GM的最佳化來算出翻譯的最佳解。所謂的GM即是特徵函數的一種，將圖論中的node比喻為欲被翻譯的字，而edge比喻為字之間的關係，透過多層遞迴來求一個句子中，每個單字對於其他個別單字的關係度，並且期望最大化這個關係度。但在求最佳化的過程中有些算式是極耗費計算的，因此作者也有適時做一些修正的假設，不過由最後的實驗結果來看，即使是修正後仍可得到不錯的翻譯效果。



SIGIR’06, August 6–11, 2006, Seattle, Washington, USA.

Digital Content Recommender on the Internet

這篇論文的出處是從IEEE INTELLIGENT SYSTEMS 2006，目的是做數位文章的推薦。此系統分成development及online use兩個環境。development 環境做了內容跟使用者的分析並建立數個元件以供online use environment使用。
文章內容分析部分，先用貝氏分類器做文章分類，同時將information gain高的字放入word dictionary，之後一些base的建立都會參考到word dictionary。接下來用SOM做文章分群，並建立出article-keywords index跟keyword-articles index database。
使用者分析部分，依照使用者對每個之前所分群好的文章類別之RFM值用SOM做分群，並依每個群建出user preference rules。online use environment先依使用者讀過的文章將他分至某一使用者群中，接下來依使用者所看的文章，從article-keywords index找出前項，再依前項從user reference rules找出後項，最後用後項從keyword-articles index 找出推薦文章。

論文連結:Digital content recommender on the Internet

Interactive Wrapper Generation with Minimal User Effort

這篇論文出自WWW 2006，目標是提出一個半自動化的wrapper generation方法。

不同於其他semi-automatic和unsupervised wrapper，這篇論文並沒有很困難的方法，主要是提供一個使用者介面利用minimal user effort來完成wrapper工作。內容可以區分為兩個部分：

• Interactive User Interface：只需少量的training pages，讓使用者highlight頁面中的tuples，然後系統根據使用者highlight的部分做處理，將文件轉為DOM parse tree。
• Wrapper Generation System：系統定義了自己的Extraciton Language predicates，來作為產生extraction patterns的工具。
  

1. 首先透過training tuple產生dom_path和最低層的共同節點LCA(lowest common ancestor)，LCA object記錄了兩項資訊：
   1. training page中tuple的lca nodes。
   2. 萃取出這些lca nodes的patterns。
2. 利用LCA objects產生patterns, 然後萃取出tuple attributes。
3. 利用patterns去找出tuple region，產生初始的wrapper。
4. 利用predicates產生tuple validation rules，並產生新的wrapper。
5. 利用category utility function對wrapper做ranking。
   C: cluster, A: attribute, v: value
   同一群的兩個物件我們希望有較多相同的屬性，因此P(A=v|C)期望越大越好。
   不同群的兩的物件我們希望有較少相同的屬性，因此P(C|A=v)期望越小越好。
   因此CU值越大越好。
6. 由使用者做確認。
7. 將產生的wrapper使用一些verification set測試。
   

論文中提到雖然他們的方法和其他方法比較，可能需要較多的人力介入，且training examples較多，但是相信可以減少所需要的time和effort。實驗部分和WIEN, STALKER, WL^2等wrapper比較，都可以發現所需的training tuples較少，並且做了14個網站的wrapper實驗，在total user effort的部分表現也都不錯。




Proceedings of the 15th international conference on World Wide Web

Conference Call For Paper

ICDE 2008 Homepage and Submission Website Research and Industrial papers
Abstract deadline:	June 22, 2007 5pm PDT
Paper submission deadline:	June 27, 2007 5pm PDT
Notification:	October 12, 2007
Camera-ready deadline:	November 22, 2007 -

實驗室成員

Advisor

張嘉惠(Chia-Hui Chang): http://jahuichang.blogspot.com/

PhD Students

范登凱(Stanley Fan): http://stanley-fan.blogspot.com/
柯嘉穆(Mohammed Kayed):

Master Students

95 楊潔程 (Chieh-Cheng Yang) http://totti-yang.blogspot.com/
95 丁昭廷 (Chao-Ting Ting) http://dingqoo.blogspot.com/
95 蘇詠勝 (Yueng-Sheng Su) http://iyo-studio.blogspot.com/
96 廖哲民 (Che-Min Liao) http://liouville.blogspot.com/
96 楊萍華 (Ping-Hua Yang) http://blogaforschool.blogspot.com/
96 謝承璋 (Cheng-Chang Hsieh) http://vydon.blogspot.com/
97 林衍伶 (Yen-Ling Lin),xoanonlin@gmail.com
97 盧柏任 (Bo-Ren Lu), nkaf61@gmail.com
97 官直毅

Part-time Master Students

97 張志豪 (Chih-Hao Chang): nickie_chang@yahoo.com.tw.
97 林冠辰
96 胡福全 (Jason Hu): http://amtbone.blogspot.com/
94 陳斐文 (Joyce Chen):
94 林宜穎
94 潘立人
94 吳宗翰

Alumni

95 林俊宏 http://csieflyman.blogspot.com/
95 楊士鋒 http://tomelf.blogspot.com/
94 韓樹岡 http://my.opera.com/kenthan/
94 蔡坤璋 http://my.opera.com/FredTsai/
94 陳正揚 http://acdcpistol.blogspot.com/
94 施宗昆 http://dolcevitabm.blogspot.com/


歷屆畢業論文

Ranking Objects by Exploiting Relationships:Computing Top-K over Aggregation

這篇paper是來自於SIGMOD 2006，主要是探討給定一些關鍵字查詢時，所得到的查詢結果(文件)中的target object如何進行評分及排序，同時考慮在不需進行完整計算的可能性，因為我們只需要找出最好的前k項target object就足夠了。因此，這篇paper就是以上述為目標，並提出一個計算target object 分數，節省時間的演算法(called early termination)。

論文中首先界定document與object，以及他們之間的關係。舉例來說，在找尋領域專家的應用上，我們可以輸入代表此領域的關鍵字，從而得到相關論文paper (document)，而我們想要找尋的target object，則是paper的author。document與target object間的包含關係，我們可以用一個table來記錄，也就是我們在某個document內發現哪些target object。

假設以全文檢索來做keyword查詢，當關鍵字不只一個時。對於每個single keyword w，我們會得到一對應的ranked list，裡面包含了符合這keyword的document，並按照分數高低來排列。而計算target object分數的方式(scoring function)，即可透過加總取得，可以是row marginal或是column marginal。Row marginal class是先對每個document做所有的keyword分數之combine，再對combine後的分數作aggregation。而Column marginal class是先對每個keyword做aggregation，再對所有的document分數做combination。在此篇paper中，我們用的是column marginal class。

在這樣的模式運作下，作者提出了一個early termination的觀念，也就是說當我們確定找出了最好的k個target object，而且之後所搜尋的object都不會比這k個更好的話，我們就可以停止搜尋並回傳結果了。其中又分為generate-prune approach and generate-only approach。generate-prune approach用的是先產生一size大於k的candidate set，再做pruning得到最終 k。而generate-only則是會不斷產生candidate，直到符合某stopping criterion為止。

最後實驗證明，使用early termination的generate-prune(GP)與generate-only(GO)的執行時間皆比原本的SQL好上幾倍，而GP比GO來得更好。因此，加入early termination的觀念能成功的縮短執行時間，而且回傳top K的結果，對使用者來說也算是足夠，畢竟使用者也不見得需要那麼多卻不一定相關的答案。

Proceedings of the 2006 ACM SIGMOD international conference on Management of data (SIGMOD) 2006

Using metarules to organize and group discovered association rules

對於小型資料集來說，Association Mining Algorithm 能輕易地找出項目之間的關係，並產生關聯規則供使用者解讀。但若要處理高維的資料集時，產生的大量關聯規則通常會讓使用者無褔消受，這是因為高維的資料集容易產生許多reduntdant rule，而reduntdant rule通常起因於規則之間的overlap及containment，必須加以刪除。本篇論文針對我們所找出來的discovered rules，加以組織、分群，減少discovered rules數量，並以metarule來幫助使用者了解discovered rules彼此間的關係，以求降低使用者解讀discovered rules時的負擔。

本篇論文提出的方法包含四個步驟：
1. Finding meatrules
所謂的metarules係由兩個所找出的association rules R1, R2組合而成的規則R1→R2. 同樣使用min_sup(=0)、min_conf(=70?) 來找出metarules, 用以表達discovered rules之間的關係．
2. Finding independent subgroups of rules
以圖形表示找出的discovered rules及metarules (以discovered rules 做為 node, metarules做為 edge)，從圖形中找出獨立不與其它subgroup連接的subgroup，即每一subgroup獨自表達特定的knowledge．
3. Reorganizing equivalent rules
兩個node: ri , rj 如果滿足以下條件，則表示此兩個association rules近乎相同，因此可以合併成一個node.
a. ri ∈ OUT(rj) and ri ∈ IN(rj), i.e. r
b. OUT(ri) \ {rj} = OUT(rj) \ {ri}
c. IN(ri) \ {rj} = IN(rj) \ {ri}
4. Pruning the discovered rules using metarules
刪除規則的基本原則是找出較為複雜的規則及較為明確的規則．complex relationship定義如下：兩條已知的association rules: ri , rj ，若 ri , rj 滿足equivalent relationship且ri 的前提為 rj 前提的子集，則rj 較ri複雜，此時我們刪除較複雜的且多餘的規則 rj ，因為ri 已經包含rj 的所要含括的知識。除了complex relationship之外，若rj ∈ OUT(ri) and rj ∈ IN(ri)，則我們可以說ri 較rj 更為明確。對於這種規則，因為它不一定會導致overfitting，而且也無特定的理由須將它刪除，所以作者認為交由使用者自行決定是否刪除較為恰當。

本篇論文使用7個資料集當作實驗對象，每一個資料集都減少一定比例的discovered rules。至於減少多少數量，使用者可自行設定confidence threshold來控制。實驗結果顯示愈低的confidence會產生愈多的metarules，愈多的metarules就愈容易滿足equivelent relationship，所以我們可以合併更多的discovered rules(node)以減少更多的node及metarules。如果我們認為兩條discovered rules所重疊資料要很多才算有關係的話，我們可以把metarules 的confidence threshold設高一點，如此會保留較多的discovered rules。

Data Mining and Knowledge Discovery, 2007, volume 14, pages 409-431

實驗室簡介

Web智慧暨資料探勘實驗室

本實驗室為中央大學資訊工程系張嘉惠教授所領導的研究團隊。實驗室位於工五館A棟307(分機35327)及研究中心二館206(分機57868)。實驗室成員目前有博士生五位，碩士生十位，碩士專班七位。

實驗室的主要研究領域為全球資訊網及資料探勘兩大方向:

• Web由1.0發展到2.0，一個很大的差別在於網站從單純的提供使用者資訊的下載與閱覽，轉而提供使用者更多的上傳及分享的功能。現今的Web，每個人不僅是Web上的資訊消費者，同時也有能力藉由更方便的工具去創造資訊，我們可以說當今Web所包含的資料比過往更豐富完整。不過當我們將Web視為無所不包的資料庫，資訊的整合與利用就更為重要。近年來Mashup網站紛紛成立，正說明資訊整合的重要應用。不過再多的混搭網站也難顧到每個使用者的各別需求，因此以往被視為專業性操作的資訊整合，有必要提供更為公眾化的操作。過去我們實驗室即針對Deep Web資訊來源，發展了網頁抓取（Page Fetching）、資料擷取（Data Extraction)、及資料彙整（Data Integration）等相關技術。我們以Programming by example的概念由使用者示範網頁的來源如何取得，同時結合非監督式Web資料擷取技術取得動態網頁的URL位置；最後再透過資料間的關連彙整一個資料樹。近年來也針對Surface Web資訊擷取及整合問題，利用機器學習方法發展相關解決方法，寄望提供使用者更便利的Web資訊存取工具。



• 資料探勘（Data Mining）的目的在找出資料中未曾被發掘的知識，並利用累積的資料提供未來的決策參考。資料探勘在商業智慧（Business Intelligence)、生物資訊（Bioinformatics）、文件探勘（Text Mining）、科學計算（Scietific Computing）等等有牽涉到資料分析的應用，是相當重要的一項工具。資料探勘是結合資料庫系統（Databse system）、資料倉儲（Data warehouse）、統計（Statistics）、機器學習（Machine learning）、高效能計算（High performance computing）等多個領域的一門學科。其中資料庫系統及資料倉儲用以支援資料的淨化及快速的存取，機器學習及統計則做為資料分析預測的後盾，最後高效能的計算則保證大量資料的快速運算。常見的資料探勘技術包括有樣版探勘（Pattern Mining）、分群（Clustering）、分類（Classification）、預測（Prediction）等項目；前兩者為監督式的學習，後兩者則是非監督式的學習。本實驗室的研究包括有文件探勘、拍賣獲利預測、樣版探勘及資料視覺化等相關研究。

Lazy Associative Classification

這篇paper主要是介紹了一個新的associative classification的作法。一般來說，associative classifier會比decision tree classifier的準確率要來得高。因為decision tree classifier 是用greedy(local) search的方法，選出目前擁有最高information gain的attribute，加進tree裡面形成新的split node，對於此node的子樹來說，皆為該attribute與其他所剩下的attribute中，挑選擁有最高information gain的attribute來繼續splitting，直到所有的instance屬於同一個class或是此node已低於某特定的minimum support threshold等等。decision tree classifier的特點是快速且容易明瞭，缺點為local search的情況下容易忽略了important rules。association rule classifier可以解決此問題，透過global search的方式，可以產生large number of rules。但是該優點正也是缺點所在，產生了大規模的rule set，許多的rule在分類的過程中甚至幾乎沒有用到，整體效率不彰。
因此本篇作者提出了lazy associative classification的觀念，相比於一般的 (eager) associative classification，lazy associative classifier並不是對於所有的 training data皆產生了rule set，而是demand-driven basis，也就是只針對testing instance所擁有的feature去產生association rules，如此可以保證所產生的association rules一定至少跟testing data有若干關係，不至於發生在測試的過程中，只用到少數association rules的情形。
對於lazy associative classification，為了一開始就記錄test instance所包含的feature set，會用到比一般associative classification更多的workload，此問題在paper中也提到了可以用caching的方式解決。另一個問題是只針對test instance產生的association rule，代表的就是要犧牲部分的generalization和影響classification若干的accuracy。
最後實驗證實，lazy association classification可以降低10%的error rate，相比於一般的association classification；而若是跟decision tree classification相比，更可以減少近20%的error rate。



Proceedings of the Sixth International Conference on Data Mining 2006 (IEEE)

Movie review mining and summarization

這篇論文出自CIKM’06，目的是做movie review mining和summmarization，主要是藉由產生正面與負面的feature-opinion pairs做為此電影資訊的摘要。此篇論文提出的方法是一開始先利用WordNet、IMDB的movie casts和labeled training data去產生feature跟opinion的keyword list，利用此list找出句子中的feature words和opinion words且決定feature words是屬於哪個feature class和opinion words是正面的還負面的；訓練階段會利用pattern mining 找出dependency grammar graph中feature到opinion pair之間的常見pattern，做為測試階段feature-opinion pair找尋的依據。

實驗部分跟Hu and Liu的KDD'04的opinion extraction做法比較，以擷取feature-opinion pair 的precision 和recall做為評估原則。

連結: Proceedings of the 15th ACM international conference on knowledge management CIKM'06

A study on automatically extracted keywords in text categorization

A study on automatically extracted keywords in text categorization

本篇文章出自於ACL’2006, 其主要目的是探討 “Keyword” 對文件分類的影響力.
keyword extraction: 列舉出幾個常用的方法, 例如: n-grams, PoS, and Chunking. 在feature value 指派的方面, 描述出幾個常用的方法, 例如: tf, tf*idf, relative position of the first occurrence, PoS tag, 其中PoS tag是作者在 “Improved Automatic Keyword Extraction Given More Linguistic Knowledge”所提出來的方法, 在得到input feature and feature value之後, 採用supervised machine learning method (rule induction) 來訓練prediction models, 來判斷輸入的term, 是否為keywords, 實驗結果顯示, keyword 擷取的F-measure 可達44%.

文件分類部份所用的文件表達方式可分為keyword only 和full-text來探討, 而feature value的指派, 則採用tf*idf or boolean value, 而機器學習方法則係用linear support vector machine,來對文章做分類. 以往文件分類最基本的方式係用全文(full-text)的方式當作是input feature. 本篇針對不同的input feature 以及 feature value作了一系列的試驗, 來說明以full-text + keywords來當作是input feature, 其所得到的分類結果 (F-measure) 是最佳的, 可達到81.07%.

Link: Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL

Pollock: Automatic Generation of Virtual Web Services from Web Sites

這一篇論文是出自ACM SAC 2005，主要目的是設計一個快速產生Web Service的方法。

假設現在我們想要整合不同的網路書店，我們可能會先找100個書店，然後設法抓出網站中的拍賣資訊。此時有些書店有提供Web Service直接查詢，但有些書店則缺乏相關資訊。這篇論文的構想是為沒有Web Service的網站自動產生"Virtual Web Service"，如此一來便可以快速整合不同書店間的資訊。

對於沒有Web Service的網站，首先會利用Wrapper技術擷取該網站的回傳網頁，在這裡使用XWRAP。XWRAP是一個以XML為基礎的wrapper，可 以將wrap出來的資訊轉為XML呈現。同時論文設計了一個translator，用來轉換SOAP和Html GET/POST的資訊，讓Wrapper執行時資訊可以順利傳遞。在Wrapper工作完成後，接下來產生Web Service和WSDL的步驟在此方法中也會處理。

Slides

論文連結

Proceedings of the 2005 ACM SAC, pp. 1650 - 1655

Adaptive-Support Association Rule Mining for Recommender Systems

一般來說，我們在使用Association Rule Mining Algorithm時，例如Apriori，我們必須事先設定minimum support threshold。 但如何選擇適當的值卻不是那麼直覺，常常只能依靠暴力法來解決。此外，也因為沒有對規則有所限制，所以任何的frequent itemset都會產生規則，使得執行時間大幅增加。

上述以market basket analysis為精神的演算法不適用於推薦系統。因為推薦系統常對特定使用者進行推薦商品的動作，所以不須產生所有的frequent itemset。此外推薦系統必須考慮執行效率，特別是要online運作的規則。所以在這篇論文中，作者根據前人的CBA-RG演算法精神加以修改成適合應用於推薦系統的演算法－ASARM。ASARM不須事先指定minimum support threshold，而是指定想要產生規則數的範圍，並且自動地調整minimum support值。所以ASARM不僅省去指定minimum support的困擾，還可以透過指定產生的規則數的方式來控制執行效率。除此之外，ASARM一次只產生特定使用者或特定商品的規則，以避免產生不相關的規則。

論文中除了提出ASARM演算法之外，在進行推薦工作時，作者先產生user association及article association的規則，並把兩者合併使用，使得能提升執行效率卻又不降低準確度。而實驗部分也探討各個參數對precision、recall、accuracy的影響，並觀察到一些現象加以分析。最後再與Billsus和Pazzani在1998年所提出的方法做比較，證明作者所提出的方法在accuracy方面優於Billsus和Pazzani的方法。

PDF檔案連結

Data Mining and Knowledge Discovery, Vol. 6, No. 1 / January, pp.83-105, 2002

Social Summarization of Online Auction Feedbacks

這一篇IUI 2005的論文主要解的問題是拍賣網站上對於一個賣家評價的summarization．

一般而言，我們在拍賣網站上想要評估一個賣家時，通常我們會先看其他人對這個賣家的評價，並且以多數人的意見做為此賣家評價摘要的主要內容，換句話說，意見的頻率是文件摘要的主要採用的條件。但是通常這樣的評價都是正面居多，很難得到一個比較真實的評價．因此作者提出先對同一個寫評價的使用者，將其（對於不同賣家）所有的意見整理出來，用以過濾禮貌性敍述（也就是那些對每個賣家都寫的意見），保留比較特別的意見，做為summarization的參考．比較有趣的是如何評估這篇所提的Social Summarization比一般的Summarization 好? 本篇作者以對不同賣家摘要所得的壓縮率標準差來說明，壓縮率標準差大表示所做的摘要較有鑑別度，而實驗結果也的確顯現這樣的現象．

而處理這些feedback的前置作業則是要先將text做意見的擷取，這樣我們才能有效的計算每個意見的頻率．以拍賣網站的意見來說，作者一共歸納了13種feature，共37個feature-value pair．擷取方法是屬於監督式學習，先由標記意見所在的句子，在經過POS Tagging之後，找出frequent patterns，即可做為意見擷取的規則．因此實際應用上是利用一個事先定義的字典，將要擷取的同義字均加入其中．當測試文章有出現這些字時，我們即可應用以上找出的規則做為feature value擷取的方法．實驗結果真正意見的擷取precision為70.8%，recall則為89.5%，而禮貌性敍述擷取precision為93.8%，recall則為80.8%，效果看起來不錯，但是前提是訓練和測試資料筆為100比10．

Systems and Computers in Japan, Vol. 37, Iss. 8, (July 2006), Pages: 38 - 55.

Opinion Extraction and Polarity Identification

這篇論文出自 2003年 ACM Empirical methods in natural language processing，原始的動機跟目的其實是為了應用在QA 系統上，希望藉由正確分辨opinion跟fact的句子來幫助回答一些更複雜的問題，像是"為什麼會發生伊拉克戰爭?" 等．

這裡主要的問題是判斷一個文件(或是一個句子)是一個事實的報導或是一個意見的表逹，次要的問題則是判斷一個句子是一個正向意見或是一個反向意見． 本篇採用的方法則包括相似度, Naive Bayes及Boosting三種方式，使用的特性(features)則包括字本身,Bigram,Trigram, 詞性,以及oritented words當作feature，使得判斷一個句子是否為意見表達的有相當高的準確率0.70及招回率0.92，但是判斷一個句子是否為事實陳述則準確率 0.13及招回率0.42相對較差．

這篇有個特點是他們的訓練資料為了避免大量人工標示，而利用了華爾街日報的文章的種類標示,例如:文章有分"新聞","社論","信件"等，來作為 文章是否為opinion或fact．基本上這篇論文的目標與坤璋原先設想的題目幾乎相疊，表示這個方向是對的，而且有個方法做比較，實驗上也比較好做．

ACM Proceedings of the 2003 conference on Empirical methods in natural language processing, Pages: 129-136

Mining Risk Patterns in Medical Data

Association Rule 傳統上是為了所謂Basket Data所創造出來的規則，每筆資料並無所謂的類別。 因為有規則產生，很自然的可以應用在資料分類上，但是如何處理不同類別所找出的規則？過去有研究試過利用統計檢定（如Chi-square）來篩選這些規則，通常最後則以分類的結果來評估篩選方法的好壞。這篇選自KDD2005的論文，則是利用統計上常用的Relative Risk來篩選optimal risk patterns。Relative Risk本身沒有anti-monotone 的特性，但是在特殊情況下是有anti-monotone的特性，這也是這篇論文最主要的貢獻，但是篇幅關係，作者並未詳列在論文。本篇論文是Industry/Education Track所以較Research Track的內容較淺顯易懂。

Knowing a Web Page By the Company It keeps

這篇取自於 CIKM'2006的論文，內容主要是講如何透過neighboring page的資訊將target page 做分類。 Web page classification可以使用的資訊，包括網頁的內容及鏈結資訊等，這一篇論文則著重在相鄰網頁可以提供的分類效果。作者將相鄰網頁分成Parent，Child，Sibling及Sprouse四種類別，同時依據相鄰網頁是否經過label與否給予權重，再依相鄰網頁與target Page是否係出同門（網站）給予不同權重，最後對所有的參數如何影響分類的表現做了很完整的實驗。整篇的idea不是很困難，不過作者做了深入的研究以及實驗。 結論與直觀想法差距不大：

1. 有label的網頁提供的分類效果總是比沒有label的網頁好(η Eta)。

2. 四種鄰近網頁中屬Sibling的效最佳(β Beta)。

3. 來自同一網站的相鄰網頁提供的資訊比其他網站的相鄰資訊有益於分類(θ Theta)。

4. 鄰近網頁與target page的權重比於0.2與0.8是效果最佳(α Alpha)。

對ODP(Open Directory Project)等品質高的網頁分類效果可達90%，但是對一般網頁效果則降至56%，顯示還有相當的改善空間。

Gimme' the context: context-driven automatic semantic annotation with C-PANKOW

P. Cimiano等人先前在WWW 2004發表了一篇有關自動文件註解 (automatic document annotation) 的論文。所謂文件註解，是輸入一份文件，將文件中的特定字彙標上類別(concept)，再輸出一份註解後的文件。作者提出的方法，是將文件中需要標記的proper nouns (NP)，套用linguistic patterns，產生例如 「Hotel ( concept) such as Hilton (proper noun)」等語句，再利用Google API搜尋到的頁面總數。去衡量不同concepts和NP間的關係，決定NP所屬的concept。這個方法最大的好處，是不需很多的訓練資料，就可以達到50%以上的precision。然而該方法仍有幾個問題，例如recall過低，時間複雜度隨著concepts數量成長。

　　本篇論文作者於WWW 2005發表了一個改進方法。與先前不同之處，作者利用正規表示式定義了「instance」做為文件中要註解的目標，降低計算複雜度。將instances套用linguistic patterns上Google去搜尋，抓取abstract。然後考慮了註解文件和abstracts間的相似度，來過濾掉與註記文件不相干的內容，藉以提高recall。

　　這個idea很直觀，並沒有套用很難的理論，但是作者在實驗還有相關研究比較上花了不少功夫，且把方法實作成公開的web service。根據實驗的結果，此方法的確提高了recall，並因時間複雜度的降低可以套用更大的ontology。

論文寫作

這兩天有關論文抄襲的問題，再度登上報紙頭板，很自然的兩位掛名教授也遭受到相當的質疑．我想正好趁這機會談談論文寫作這件事．

科技論文基本原則是為了闡述自己的觀點，同時要配合起承轉合讓文章讀來如行雲流水．觀點不是無中生有，要麻是自己推論出來的，要麻是參考別人的，這時當然要有適當的引用．至於起承轉合則多屬於一般性的描述，平舖直敍雖可達到目的卻欠缺文字的吸引力，因此若是別的文章有好的描述，我通常會參考一兩句，但不可能三句話一字不漏的抄襲，一定要加以改寫配合自己的主軸．

跨入Web2.0的時代

一直斷斷續續聽到有關Web2.0的成功的故事，卻一直把Web2.0當成分享文章，照片，書籤等的功能，不太覺得自己可以直接應用Web2.0來改善自己手邊的工作．一直到看到阿孝札記對於Web2.0實現其創造個人媒體的夢想，才真正去思考Web2.0背後的成因．　　

原來架網站這事對於資工系的人來說雖非難事，但非人人可為，就算是人人可為，也因為繁複的動作，阻礙了生產力，更何況還有網路流量，系統安全維護等等問題，才讓網站代管成為一個風潮．　　

一直以來實驗室的討論群組似乎很難維持的很好，雖說用phpbb架了討論群組，但是也遭駭客入侵，更別說永續經營．有了生命力新聞的經驗，或許可以嘗試著用部落格的方式讓研究生們多多練習作文，對於論文的撰寫或許有所幫助．　　

除此之外，這也讓我想到Wrapper的技術，原本就是以無須寫程式為目標，而大眾也愈來愈多使用Web搜尋的需求，或許把這樣的技術直接行銷到大眾面前是一種可行的方案．