實驗室成員

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）等項目；前兩者為監督式的學習，後兩者則是非監督式的學習。本實驗室的研究包括有文件探勘、拍賣獲利預測、樣版探勘及資料視覺化等相關研究。