7/23/2008

MA Reading Memo 7/23

Tag-based Social Interest Discovery (paper)
->證明user-generated tag比keyword 好用

目前在social network中 discover interests的方法:
 (1) user-centric: 從user的relation上找到common的object,如:facebook

 (2) object-centric: 從global的network中找到所有有common object,如:del.icio.us
 在object-centric中,relation的關係可能很弱或不明顯

資料來源:del.icio.us,430萬筆tag,20萬個user,140萬筆URL(過濾掉非英語及非HTML file的object)
分析發現:
1. [figure 1]大部份的url只會被少數人bookmark,只有少部份的URL比較popular
2. [figure 2]大部份的user很不主動(一般人僅有少於30個的bookmark)
3. [figure 3]user會選擇的tag有高度集中性(i.e.有Popular Tag)
4. [figure 4, 5] Tag 在過濾掉一些noise(ex. idf 太高的值)之後,可以的cover大部份的keyword
5. [figure 6] tag數量雖然會隨著bookmark此URL數量的增加而增加,但過一定數字後就會趨向一個穩定的數字
6. [figure 7] tag 可以cover document的比率,40%的網頁內容可以被tag完全cover(顯示大部份user還是傾向於從文章中取出相關字來做tag)
7. ISID(Internet social interest discovery) clustering:
對所有Post,找出裡面含有同樣topic(tag set)的user set 跟url set
8. [figure 9,10] 分別用tag 及keyword 來跑ISID clustering後的結果發現,用數量比較少的tag仍然可以有接近keyword的效果,所以顯示用tag來代替keyword search應該是make sense的!

Some Questions Dicussed Today
1. for figure 1,2,3 : the definition of the x-axis and y-axis is confused.
2. the definition of support in this paper is wrong. correct definition list belowed(referenced: wiki)

Association rule learning (link on wiki)
ex. 去超市買東西時:買了{洋蔥,馬鈴薯}→也會買{牛肉}

基本名詞定義:
Definition: X => Y , where X,Y包含於I and X∩Y = Φ
(Assume I = collection of n items, D = collection of m transactions)

SUPP(X) = X/m ,在m次transaction中,出現X狀況的機率
Conf(X=>Y) = SUPP(X∪Y)/SUPP(X) : Confidence, 在 X發生時,發生X∪Y的機率
lift(X=>Y) = SUPP(X∪Y) / [SUPP(X) * SUPP(Y)]
Conv(X=>Y) = [1-SUPP(Y)]/ [1-Conf(X=>Y)]

0 comments: