2008年11月17日
Learning Social Networks from Web Documents Using Support Vector Classifiers
Learning Social Networks from Web Documents Using Support Vector Classifiers出自於IEEE Web Intelligence 2006, 本篇論文主要係透過機器學習的方式自動地去建立social network, 本研究首先假設已經存有不完整關聯 (incomplete relationship), 再透過SVM建立出完整的social network, 其中屬性的建立則是藉由網路文章 (web documents)來產生文件向量. 不難發現作者將判斷social network relationships的問題轉化成傳統的文件分類問題 (text classification problem), 所採用的判斷方法 (亦可視為分類方法) 則是SVM.
此外由於relationships在social network中呈現出不均衡的資料型態 (imbalance data), 此類型資料對於機器學習具有很大的挑戰 (亦即容易傾向將資料判斷成某一特定類別), 作者也採用一般常見的 up-sampling 及 down-sampling 方法來舒緩此議題. 實驗部份採用真實資料集 FOAF (Friend Of A Friend), 評估機制則以Precision, Recall 及 F-measure為主.
以下為投影片:
此外由於relationships在social network中呈現出不均衡的資料型態 (imbalance data), 此類型資料對於機器學習具有很大的挑戰 (亦即容易傾向將資料判斷成某一特定類別), 作者也採用一般常見的 up-sampling 及 down-sampling 方法來舒緩此議題. 實驗部份採用真實資料集 FOAF (Friend Of A Friend), 評估機制則以Precision, Recall 及 F-measure為主.
以下為投影片:
Learning Social Networks From Web Documents Using Support
View SlideShare presentation or Upload your own.
2008年8月4日
Tag-based Social Interest Discovery
對於社群網站中常見的元素─標籤，我總覺得應該可以有更多利用的方法。我也曾經思考過標籤可以有哪些用途，甚至也想過可能可以代表使用者的興趣取向。可是不知道怎樣去分析，也不知道資料該如何取得。剛好WWW 2008有這一篇題為"Tag-based Social Interest Discovery"的paper，所以我就研讀了一下，學習別人的思考方式。這篇paper是由Yahoo公司的研究員所發表的，由於剛好收購del.icio.us網站，所以不難想像完全採用該網站的資料作分析與研究。底下是摘要部份：
在Web 2.0的概念下，許多社群網站開始發展且越來越受到歡迎。其中主要區分成兩類，一類是以人為核心，如Facebook、MySpace等等；一類是以物件為核心，如YouTube、Flickr與del.icio.us等等。對於社群網站來說，發現使用者群體中的共同喜好是很有用的。一來可以有助於加強使用者間的關係(有共通興趣)，二來可以刺激使用者貢獻與分享更多內容。然而目前已經提出的相關解決方法中，都是基於利用使用者在網站上的互動關係來分析，這對於像del.icio.us這類網站來說是不合適的。因此本篇paper提出一個利用使用者自定標籤(tag)的新方法來找出像這類網站中的社群興趣(Social Interest)，它的好處是不需要透過使用者間的互動關係來作分析。
分析所需的資料來自del.icio.us資料庫中的一部份(公開的書籤)，總共有140萬個URL被20萬個使用者儲存到430萬個書籤上。這些URL對應的網頁利用英文中廣泛使用的stopword list來對文字內容與標籤作過濾，接著將過濾出來的關鍵字與標籤利用Porter stemming algorithm作正規化。結果顯示，平均來說一個URL的註解標籤數量遠小於對應網頁內容的關鍵字數量(大約是100個量)。所以如果能夠以標籤來取代關鍵字作為社群興趣發現的元素，將可以讓工作得到非常大的簡化。
首先，作者們利用實例展示URL中top-10 tf、tfidf 關鍵字和註解標籤的比較，說明標籤比關鍵字更能表達出內容的高階概念。其次，觀察top-10、top-20及top-40的tf、tfidf關鍵字被標籤字彙函蓋的程度，顯示標籤對最重要關鍵字集的函蓋程度是很高的。第三，分析標籤的發散性，其中標籤隨著URL數量的增加不會無限制的成長，而是會趨向穩定的數量。最後，檢視標籤與關鍵字的匹配率，大部份URL中較常被使用的標籤被關鍵字匹配的程度是不錯的。經由以上分析，使用標籤來找出社群興趣是可行的。
此外，作者們還根據分析結果實作了一個稱為ISID(Internet Social Interest Discovery)的系統，可以用來發現共同的使用者興趣以及依據興趣主題對使用者或URL作分群的功能。其原理是對URL中註解標籤運用關連規則(association rule)的方式找出熱門興趣主題，在此將每個張貼書籤(由user、url和tags組合而成)看成傳統上的交易資料，而user+url的組合可以當成唯一key，tags則代表item。
最後，將此系統產生的結果對資料作評估顯示：
1.相同主題群組內的URL間資料的相似度遠高於不同主題群組的URL
2.ISID系統找出的興趣主題函蓋極大多數使用者最常使用的標籤集
3.經人類編輯審查，群組中URL與該主題的相關性是夠高的
因此採用以標籤來代表興趣的方法在效果上是不錯的，同時也不需要使用者間必需有網站上的互動關係或是真實世界中額外的關係資訊。
底下是投影片部份：
在Web 2.0的概念下，許多社群網站開始發展且越來越受到歡迎。其中主要區分成兩類，一類是以人為核心，如Facebook、MySpace等等；一類是以物件為核心，如YouTube、Flickr與del.icio.us等等。對於社群網站來說，發現使用者群體中的共同喜好是很有用的。一來可以有助於加強使用者間的關係(有共通興趣)，二來可以刺激使用者貢獻與分享更多內容。然而目前已經提出的相關解決方法中，都是基於利用使用者在網站上的互動關係來分析，這對於像del.icio.us這類網站來說是不合適的。因此本篇paper提出一個利用使用者自定標籤(tag)的新方法來找出像這類網站中的社群興趣(Social Interest)，它的好處是不需要透過使用者間的互動關係來作分析。
分析所需的資料來自del.icio.us資料庫中的一部份(公開的書籤)，總共有140萬個URL被20萬個使用者儲存到430萬個書籤上。這些URL對應的網頁利用英文中廣泛使用的stopword list來對文字內容與標籤作過濾，接著將過濾出來的關鍵字與標籤利用Porter stemming algorithm作正規化。結果顯示，平均來說一個URL的註解標籤數量遠小於對應網頁內容的關鍵字數量(大約是100個量)。所以如果能夠以標籤來取代關鍵字作為社群興趣發現的元素，將可以讓工作得到非常大的簡化。
首先，作者們利用實例展示URL中top-10 tf、tfidf 關鍵字和註解標籤的比較，說明標籤比關鍵字更能表達出內容的高階概念。其次，觀察top-10、top-20及top-40的tf、tfidf關鍵字被標籤字彙函蓋的程度，顯示標籤對最重要關鍵字集的函蓋程度是很高的。第三，分析標籤的發散性，其中標籤隨著URL數量的增加不會無限制的成長，而是會趨向穩定的數量。最後，檢視標籤與關鍵字的匹配率，大部份URL中較常被使用的標籤被關鍵字匹配的程度是不錯的。經由以上分析，使用標籤來找出社群興趣是可行的。
此外，作者們還根據分析結果實作了一個稱為ISID(Internet Social Interest Discovery)的系統，可以用來發現共同的使用者興趣以及依據興趣主題對使用者或URL作分群的功能。其原理是對URL中註解標籤運用關連規則(association rule)的方式找出熱門興趣主題，在此將每個張貼書籤(由user、url和tags組合而成)看成傳統上的交易資料，而user+url的組合可以當成唯一key，tags則代表item。
最後，將此系統產生的結果對資料作評估顯示：
1.相同主題群組內的URL間資料的相似度遠高於不同主題群組的URL
2.ISID系統找出的興趣主題函蓋極大多數使用者最常使用的標籤集
3.經人類編輯審查，群組中URL與該主題的相關性是夠高的
因此採用以標籤來代表興趣的方法在效果上是不錯的，同時也不需要使用者間必需有網站上的互動關係或是真實世界中額外的關係資訊。
底下是投影片部份：
2008年1月3日
Mining Social Networks for Targeted Advertising
本篇paper的題目是"Mining Social Networks for Targeted Advertising"，出處是："Proceedings of the 39th Annual Hawaii International Conference on System Sciences (HICSS'06)"。以下是本篇paper的摘要內容：
在商業中，針對部份客戶作目標性的廣告推薦是很有用的。傳統上都是靠手動方式分析先前的歷史交易資料或是客戶的相關特徵，但是近年來隨著技術的進展，這部份已經開始利用自動化的工具來處理了。目前推薦系統產生目標廣告的技術主要有兩大類，一類是content-based，另一類則是social-based。前者主要是比對個人特徵與產品內容分類的匹配性，缺點是沒有利用到有影響力的其它人。後者則是利用客戶對產品的評等關係之間的關連來作推薦，但是對於沒有被評等過的新產品或是尚未有評等產品的新客戶來說，這種方法並沒有用處。
為了修正上面所提方法的缺失，因此本篇paper提出一種基於social network概念的data mining framework for targeted advertising system。這種方法的原理是利用social network中的概念─如果兩個不認識的人間有另一個共同彼此認識的人，那麼他們之間的連結程度比任意兩個不認識的人之間還要強的許多。以此為基礎，找出客戶關係網路中的cohesive subgroups。接著將產品作分類，然後計算每個產品類別在對應的subgroup中交易的次數作為整個subgroup對該產品類別的愛好程度。透過這種方式，找出在某個固定的客戶數量下最有可能購買某項產品的客戶群 。對於新客戶來說，廣告推薦是根據新客戶屬於哪一個subgroup而定；對於新產品而言，則是根據新產品屬於哪一個分類。
最後作者們以彰化師範大學的教職員email logs與library-circulation data作為資料針對以下四種方法來實驗：
1. Group-based, 本篇paper所提出的方法
2. Single-based,將每個人視為一個subgroup
3. Neighbor-based,將有直接關係的人視為一個subgroup
4. Random,隨機選擇
結果顯示本篇paper所提出的group-based方法的performance是最佳的，並且在數量100-300之間具有明顯的統計顯著性。
最後是這次報告的投影片內容：
在商業中，針對部份客戶作目標性的廣告推薦是很有用的。傳統上都是靠手動方式分析先前的歷史交易資料或是客戶的相關特徵，但是近年來隨著技術的進展，這部份已經開始利用自動化的工具來處理了。目前推薦系統產生目標廣告的技術主要有兩大類，一類是content-based，另一類則是social-based。前者主要是比對個人特徵與產品內容分類的匹配性，缺點是沒有利用到有影響力的其它人。後者則是利用客戶對產品的評等關係之間的關連來作推薦，但是對於沒有被評等過的新產品或是尚未有評等產品的新客戶來說，這種方法並沒有用處。
為了修正上面所提方法的缺失，因此本篇paper提出一種基於social network概念的data mining framework for targeted advertising system。這種方法的原理是利用social network中的概念─如果兩個不認識的人間有另一個共同彼此認識的人，那麼他們之間的連結程度比任意兩個不認識的人之間還要強的許多。以此為基礎，找出客戶關係網路中的cohesive subgroups。接著將產品作分類，然後計算每個產品類別在對應的subgroup中交易的次數作為整個subgroup對該產品類別的愛好程度。透過這種方式，找出在某個固定的客戶數量下最有可能購買某項產品的客戶群 。對於新客戶來說，廣告推薦是根據新客戶屬於哪一個subgroup而定；對於新產品而言，則是根據新產品屬於哪一個分類。
最後作者們以彰化師範大學的教職員email logs與library-circulation data作為資料針對以下四種方法來實驗：
1. Group-based, 本篇paper所提出的方法
2. Single-based,將每個人視為一個subgroup
3. Neighbor-based,將有直接關係的人視為一個subgroup
4. Random,隨機選擇
結果顯示本篇paper所提出的group-based方法的performance是最佳的，並且在數量100-300之間具有明顯的統計顯著性。
最後是這次報告的投影片內容：
2007年8月14日
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.
論文當中，作者首先介紹一些在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.
訂閱：
文章 (Atom)
