基於重複式交叉分群的廣告使用者資料分析
巫孟倫
國立中央大學資訊
工程學系
張嘉惠
國立中央大學資訊
工程學系
劉睿哲
國立中央大學資訊
工程學系
范 凱
國立中央大學資訊
工程學系
摘要
分群 (clustering) 於分析工作中扮演著重要基 礎的角色，可用以將相似的資料進行分組，目前 被廣泛地應用於市場資料分析 除常見的單向對資 料矩陣中的列分群之外，共分群則同時對列及行進 行雙向分群(dyadic co-clustering) 本研究主要係透 過共分群機制 (co-clustering) 將廣告及使用者資料 進行分群，進而得到有利於分析的資訊 透過交替 使用相關性質的資料對應變表中的行列進行 運 算，使分群的表現更好 本研究提出基於重複式交 叉分群 (Iterative clustering) 的方法來實現共分群 的目的；問題本質在於如何利用廣告資料 使用者 資料及廣告使用者鏈結資料等三個矩陣，讓廣告及 使用者分群的結果能反應資料的群聚現象 為了有 效地的評估本研究所提出的方法，我們蒐集來自於 Morgenstern 社群網站中的使用者及廣告資料，並 採用決策樹 (Decision Tree) 分類器的準確率做為 驗證分群的可解讀性；此外並以 KL divergence 評估 群組間的變異性 實驗結果顯示本研究提出的重複 式交叉分群法可達到較佳的效能
關鍵詞：共分群(Co-clustering) KL divergence 決 策樹(Decision tree) 分群評估
1. 前言
網路廣告是一種廣告行銷的形式，主要係透過 網際網路來刊 廣告 Ad$Mart 則是 Umatch 社群 網站所推出的一個網路廣告服務，Umatch 是標榜 奠基在經營自我的 Web3.0 基礎上的社群網路平 台，以金融理財為主的內容提供者 一方面透過如 財經奧林匹亞 全球動態資產配置 創意履歷等專 業競賽聚集眾多的人才；另一方面配合 Ad$Mart 社 群廣告經濟平台，讓使用者主動挑選廣告放置於個 人自畫像中(Self-Portrait)，做為廣告的代言人 有 別於 Google Adsense 所提供的 contextual advertising 行銷方式 Umatch 服務包含社群入口 Lohas 生活 模 式 解 析 Ad$Mart 廣 告 連 線 大 樂 透 Self-Portrait 討論區等內容
Ad$Mart 與 Google Adsense 一樣對廣告主有低 簾的廣告成本，以及打破 80/20 定律的長尾經濟效 益優點 最大不同之處在於，透過 Ad$Mart 使用者
可以分享利潤為自 帶來收益 因此在個人自畫像 中同時成為廣告的代言人的同時，系統會提撥總廣 告一定比例金額，由代言人依社群活躍點數共同分 潤 由於 Ad$Mart 採取與使用者分享利潤，並且由 使用者挑選廣告的方式經營，在商業模式上與目前 網路的廣告收費方法 有區隔，但是如何提供廣告 主更具體的流量，以及提供使用者最適合的廣告， 則是創造廣告主 使用者與平台三贏的關鍵
本篇論文的主軸主要專注在分群實驗，一方面 要將不同廣告做適當的分群，一方面也要了解使用 者是否有不同族群的現象 藉以針對不同廣告主提 供合適的建議以吸引適當的使用者 讓廣告主能夠 利用最低的成本以獲得最大的廣告效益 傳統的分 群架構，主要針對資料矩陣中的列做單向分群，並 將每行的資料視為資料屬性 以廣告與使用者矩陣 來說，可以對廣告做分群，或是將矩陣轉置，對使 用者做分群 然而這樣分別進行分群結果，無法讓 我們了解相同類型廣告和相同類型使用者之間的 關係，我們希望知道的是甚麼樣類型的廣告會被什 麼樣類型的使用者點選，而不是僅侷限於個別使用 者的點選廣告模式分析
本篇論文著重在利用分群演算法對廣告及使 用者進行觀察 其中資料集包括廣告特性資料 (ad main) 廣告與使用者鏈結資料 (ad-user link) 以及 使 用 者 的 lohas 生 活 模 式 解 析 資 料 (user lohas
game) 我們藉由交替使用應變表中的行列進行運
算，加以廣告資料矩陣與使用者 lohas 資料矩陣， 為 廣 告 和 使 用 者 分 別 進 行 分 群 ， 希 望 共 分 群 (Co-clustering)效果能較單獨分群的結果呈現更好 更容易解讀的結果
我們主要提出兩種不同的共分群方法：3-staged clustering 及 Iterative cross co-clustering，運用於使 用者相關資料集來評估效能 為有效地評估本研究 所提出的方法，我們藉由分類的方法來產生分群的 依據，並以 Precision, Recall 及 F-Measure 為評估 度量衡 此外，為使驗證方式更佳完整，我們透過 KL divergence 來評估群體之間的變異性 換言之， 當變異性越大，代表各群之間的差異性也就越大， 表示分群出來的效果較佳 我們 現當依廣告資料 特性分群，群的分佈主要和廣告金額的設定以及鏈 結廣告的總人數相關；如果採用使用者每天鏈結廣 告的資料做分群，群的分佈主要係和使用者鏈結廣 告次數的多寡有關 另外，使用者的個人特徵於
lohas 問卷表現出來的結果也可應用於鑑別使用者 的族群
2. 相關研究
傳統的分群議題，大部分著重於單向的資料分 群 近 幾 年 來 ， 陸 續 有 一 些 學 者 提 出 共 分 群 (Co-clustering)的概念，因為單向的資料分群，無法 觀察雙維的資料關係 共分群的主要議題，是可以 雙向對行與列的資料同時進行分群 有許多研究利 用了簡單的數學模型以及最佳化的技巧，來解決共 分群的問題
Dhillon[4]利用共分群來解決文件和辭彙之間 的關係，透過共分群，我們可以觀察哪些類型的文 件，會出現哪些辭彙，這樣的技術，有助於我們在 設計搜尋系統時，為文件和關鍵字標註索引有非常 大的幫助；而 Hanisch D 等人[3]，想了解什麼樣的 基因分佈會對應到怎樣的資料描述，於是它們利用 共分群的方式，來解決了這樣的問題
在這篇論文中，我們想透過共分群的方式，了 解使用者與廣告類型的分佈，並透過分類的方式來 預測我們的分群準確度
目前有許多共分群的研究[2,4]，其中以 2003 年由 Dhillon 等人提出的以資訊理論為基礎的共分 群方法”Information-theoretic co-clustering”[5]，最為 熱門，他們將文件和詞彙之間的關係視為一種聯合 機率(joint probability distribution)的問題，並利用最 小化分群前後行列兩個變數的 Mutual Information Loss，來達到共分群；隔年，他們提出利用 Bregman divergence 來取代 K-L divergence[1]，以解決資料矩 陣中值為負的共分群問題，並用最佳化演算法達到 共分群
本報告第三章將描述實驗所採用的資料集；第 四章介紹應用的共分群演算法 第五章為實驗結 果，第六章則為最後的總結與未來研究方向
3. 資料描述及前處理
本研究主要涉及的資料包含 2009/05~2009/9 區間，刊 於 Ad$Mart 平台上的廣告特性資料 ad main 廣告鏈結資料 ad-user link 及使用者的生 活模式解析資料 (user lohas game)，我們首先針對 各資料進行簡單介紹，接著描述資料前處理 1. 廣告特性資料(Ad feature matrix)
每個廣告主對於廣告的播放方式可以設定廣 告播放日期(play_date) 廣告標題(ad_title) 廣告金 額(M) 以及使用者活躍點數的最高與最低限制 (K_high) 活躍點數的最低限制(K_low) 廣告鏈結 限制人數(L) 其中廣告金額會影響到廣告在使用者 瀏覽畫面中排列的 序(Order) 另外系統針對每個 廣告刊 之結果記錄了播放鏈結當日廣告總人數 (N) 鏈結當日廣告的總活躍點數(select_score)
由於每支廣告刊 日期長短不一，每天的廣告
金額也不盡相同，因此針對廣告金額 當日選擇廣 告總人數以及廣告排序三種屬性，我們分別取資料 的最大值(max) 最小值(min) 中位數(median) 一 分位數(q1) 和三分位數(q3)，利用這些數值代表整 個刊 區間的指標性數值；針對排列 序另外取其 除以 10 的餘數加 1 來表示 廣告在頁面中出現的 位置
K-high 和 K-low 因為都是代表活躍點數的限 制，所以我們僅需知道是否有設定即可，因此可透 過 Boolean 值來描述 我們同樣的將每一天的 K-high 列舉出來之後，設定只要在此時間區間當中 有設定 K-high，即判斷有設定，K-low 值亦是如此 接 著 我 們 再 判 斷 這 兩 個 數 值 是 否 有 設 定 (K = K-high ∪ K-low)，如果有設定則 K 值為 1，反之為 0
L 則是判斷限制人數，我們同樣以 Boolean 值 來描述 最後彙整後一共有 463 個廣告與 22 廣告 特性，構成我們的廣告資料矩陣
2. 使用者資料矩陣(User matrix)
針對使用者，我們建立個別資料矩陣，包含 的屬性主要依據使用者回答生活模式解析(LOHAS Game)的問卷所產生，其中問卷主要涉及 24 個生活 模式解析問題，每個屬性均為類別型資料 系統註 冊的使用者雖有二萬多人，但同時有做過 LOHAS Game 及參與廣告鏈結的使用者有 1685 人
3. 廣告-使用者鏈結資料(Ad-user link matrix) 原始廣告與使用者鏈結資料包含了廣告播放日期 (play_date) 廣 告 代 號 (ad_id) 鏈 結使 用 者 代 號 (uid) 鏈結使用者活躍積分(active_score) 使用者 創建廣告鏈結的時間(create_time) 我們將原始資料 整理成使用者×廣告矩陣，稱為使用者-廣告鏈結矩 陣 (user–ad matrix)，矩陣中的值代表使用者鏈結特 定廣告的總次數 其轉置矩陣則為廣告-使用者矩 陣
圖 1 資料矩陣：(a)廣告資料矩陣 (b)使用者-廣告 鏈結矩陣 (c)使用者資料矩陣
4. 共分群方法
Ad_feature Ad_id Lohas
Ad A
User UxA User U
(a) (b) (c)
本篇論文主要針對廣告資料的分析為主，使用 者的資料分析為輔，主要是因為廣告資料有了廣告 特性的描述，以及廣告與使用者之間的鏈結關係 (Ad-user link)，這部分資料比較齊全；而使用者的 部分，雖有 LOHAS 生活模式解析資料和風險承受 度解析資料(RISK GAME) 然而並不是所有使用鏈 結廣告的使用者皆會填寫這兩份解析問卷，而這兩 份問卷，又以生活模式解析資料最多使用者填寫， 風險承受度解析的使用者數量又更少了
我們希望從這些資料中，去分析哪些廣告的特 性是相同的，會去被鏈結的；哪些廣告特性的設定 會令鏈結這隻廣告的使用者變少 同樣的針對使用 者部分，我們希望藉由資料，找到是否具有相同特 性的使用者，均會去鏈結相同特性的廣告，舉例來 說，會去鏈結廣告金額較高的使用者，使否也會鏈 結其他高金額的廣告
我們分析廣告資料的工具，是利用分群的方 式，來找出相似特性的廣告和使用者 傳統的分群 方式主要是單向的將資料矩陣中的列或行資料進 行分群，而這樣的分群方式，僅能看出其中一 分 群的特性，如果我們同時需要對行與列兩種資料進 行分群，則為所謂的共分群
我們首先使用傳統的分群方式，分別對廣告資料矩 陣 使用者資料矩陣進行列資料的分群，觀察廣告 資料的分群的結果以及使用者資料的分群結果 接 著結合使用者-廣告鏈結矩陣調整分群群結果 我們 提 出 兩 種 分 群 方 式 ， 第 一 種 是 三 階 段 式 分 群 (Three-staged clustering)，第二種是重複式交叉分群 (Iterative Cross Co-clustering)，透過這兩種分群方 式，我們可以同時對廣告與使用者做分群
4.1 三階段式的分群
關於三階段式的分群，我們分為兩個部分，一 個 為 根 據 廣 告 資 料 的 三 階 段 式 分 群 (3-staged clustering ad based)，另一個為根據使用者資料的三 階段式分群(3-staged clustering user based)，而三階 段式的分群包含了三個步驟，每一個步驟，均使用 K-means 來分群，其疊代數 (iteration) 設為 1000 底下我們將分別介紹以廣告資料為主和以使用者 資料為主的三階段式分群
3-staged clustering ad based
Step 1:
廣告資料矩陣雖 在先前經過處理 ，然而廣 告金額(M)屬性的值域與廣告排序值域(O)及鏈結總 人數(N)的量仍有相當的差異，將會影響兩個廣告相 似度 因此我們將所有 M N 的數值取對數(log)以 矮化數值，再藉由 min-max 將每個屬性正規化到 0 與 1 之間的數值 經由上述方式得到新的矩陣後， 做為我們分群的輸入資料，透過 K-means 分群演算
法，我們產生廣告分群的結果(Ad clusters) Step 2:
我們將第一階段分群所產生的 Ad clusters 結果 做為縮減使用者廣告鏈結矩陣的依據，使用者 i 對 廣告群 k 的鏈結次數為使用者 i 對廣告群 k 中所有 廣告鏈結次數的總和 同樣的，為了讓鏈結次數分 佈較為平均，我們將相加後的總次數取 log 同樣 的取 min-max 正規化後得到使用者與廣告群的鏈結 矩陣 接著再以縮減完的矩陣當作我們的輸入矩 陣，做 K-means 分群得到使用者分群結果(User groups)
∑
∈=
k
j A
Ad
L
ijk
i
UL
ˆ
2
( )
log
)
,
(
(1)Step 3:
我們將使用者-廣告鏈結資料矩陣轉置成廣告- 使用者鏈結資料，計算每個廣告 Adi有多少個來自
使用群 Uj的鏈結，得到得到廣告×使用者分群的鏈 結矩陣， 將此矩陣與第一階段的廣告資料矩陣合 併後，再在對廣告進行一次 K-means 分群，最後產 生最終的廣告分群結果 其演算法如下：
圖 2 3-staged clustering algorithm (ad based)
3-staged clustering user based
三階段式分群，也可應用在使用者 Lohas 資料 矩陣中，其輸入資料包含了 Lohas 資料矩陣 使用 者-廣告鏈結矩陣及廣告-使用者鏈結矩陣，其步驟 如同之前的陳述，在每一個步驟的分群我們也是使 用 K-means 做分群
Step 1:
我們將廣告資料矩陣以 Lohas 資料矩陣取代， 對使用者分群
Step 2:
Input: Ad feature matrix (Ad) and Link matrix (User and Ad)
1. Apply K-means to Ad matrix to get initial ad clustering Â0
2. User clustering:
a. Merge the User Link matrix by Ad cluster Â0 to get UL
b. Apply K-means to UL matrix to get new user grouping Û0
3. Ad re-clustering:
a. Merge the Ad Link matrix by User grouping Û0 to get AL
b. Apply K-means to Ad+AL matrix to get new ad clustering Â’
我們參考 Step1 所產生的使用者分群，我們將 廣告-使用者矩陣，依照公式(2)，產生廣告-使用者 群的矩陣，並對廣告做分群
∑
∈=
k
j U
User
L
ijk
i
AL
ˆ
2
( )
log
)
,
(
(2)Step 3:
我們參考 Step2 所產生的廣告分群，將使用者 廣告矩陣參考公式(1)，以產生我們的使用者-廣告 群的矩陣，並將此矩陣與 Lohas 資料矩陣合併，對 使用者分群，以產生我們最終的使用者群 其演算 法如下：
圖 3 3-staged clustering algorithm (user based) 4.2 重複式交叉分群
三階段的廣告分群只能夠單獨的對廣告資料 及鏈結矩陣分群，或對使用者 Lohas 資料及鏈結矩 陣做分群，並未同時參照廣告資料及使用者資料 重複式交叉分群主要是改良三階段式的分群 結 果，同時考慮廣告資料及使用者 Lohas 資料矩陣， 並交叉驗證分群結果 在進行重複式交叉分群時， 我們一樣在各個階段使用 K-means 做分群，我們分 別對廣告資料矩陣與使用者 Lohas 資料矩陣做分 群，分別產生廣告群及使用者群結果 接著如同 3-staged clustering 方式，分別與 ad link matrix 和 user link matrix 合併，經過重複式分群，產出我們最終 的廣告和使用者分群結果， 細演算如圖四所示 Step 1:
在第一步驟，我們擁有的初始資料是廣告資料 矩陣和使用者 Lohas 資料矩陣，首先我們先將廣告 資料矩陣透過 Three-staged clustering 第一步驟的方 式，進行 K-means 分群 使用者 Lohas 資料矩陣， 我們將使用者的問卷資料，當作是目錄(categorical) 資料，對使用者做分群，因此在這個階段我們分別 得到廣告分群(ad cluster)和使用者分群(user group) 的結果
Step 2:
第二步驟，我們透過廣告-使用者鏈結矩陣，藉 由使用群的結合得到廣告與使用群鏈結矩陣，再加 以廣告資料矩陣，進行 K-means 分群，得到新的廣 告分群
Step 3:
同理，我們透過使用者與廣告鏈結矩陣，藉由 廣告群的結合得到使用者與廣告群鏈結矩陣，再加 以使用者 Lohas 資料矩陣，進行 K-means 分群，得 到新的使用者分群
Step 4:
重覆步驟二 三，直到一個穩定的分群狀況為 止，通常我們實驗時的重複次數設定為 2 次
圖 4 重複式交叉分群
圖 5 重複式交叉分群架構 Ad (1.a) K-means (1.b) K-means
Ad clusters User groups
(2.a) Ad_link By user group
(3.a) User_link By ad cluster
User
(2.b) K-means (3.b) K-means
Input: lohas matrix (User) and Link matrix (User and Ad)
1. Apply K-means to User matrix to get initial user group Û 0
2. Ad clustering:
a. Merge the Ad Link matrix by User group Û
0 to get AL
b. Apply K-means to AL matrix to get new ad cluster  0
3. User re-grouping:
a. Merge the User Link matrix by Ad cluster Â
0 to get UL
b. Apply K-means to User+UL matrix to get new user group Û
Iterative Cross Co-clustering Algorithm
Input: Ad feature matrix (Ad), User lohas matrix (User), and Link matrix (Link)
1. Initial clustering:
a. Apply K-means to Ad matrix to get initial ad clustering Â0
b. Apply K-means to User matrix to get initial user grouping Û0
c. t:=0; 2. Ad clustering:
a. Merge the link matrix by User groups Ût to get AL b. Apply K-means to Ad+AL matrix to get new ad
clustering Ât+1 3. User grouping:
a. Merge the link matrix by Ad cluster Ât to get UL b. Apply K-means to User+UL matrix to get new user
grouping Ût+1 4. t:=t+1; Go to Step 2;
5. 實驗結果
5.1 分群評量方法分群研究的困難之一在於效能的評估，針對沒 有標準答案的分群工作，必須找出分群背後的最終 目的，提出有效的衡量方法 在這篇論文中，我們 提出兩種評估機制 第一種是以分類準確率為依 據，第二種則是以分群結果的差異度為準則
前者是以廣告特性資料及廣告使用者鏈結兩 者來預測廣告類別，以分群結果做為分類標準答 案，再以十次的決策樹分類平均的 F-measure 來評 估不同分群方法的成效 同樣地，我們也將使用者 資料及使用者鏈結矩陣(user-ad link matrix)做為預 測使用者類別的資料，以分類的準確率做為分群效 能的判斷依據
後者則是針對共分群的特色，分別量測兩兩廣 告群間的使用者群分佈差異 令共分群的結果產生 Â=α1, α2, …αK個廣告群與 Û= υ1, υ2, …, υL個使用
者群 p(Û|αi)為廣告群αi中，使用者群的分佈機率， p(Â|υj)為使用群υj 中，廣告群的分佈機率 我們可 以藉由計算任兩個廣告群αi, αj間的使用者群分佈
機率的 KL divergence，來代表αi, αj,兩個 Ad cluster 之間的差異：
∑
= •= L
k k i
j k i
k
j i
KL
p p p
U p U
p D
1
))
| (
)
| log( ( )
| (
)) ˆ| (
|| ) ˆ| ( (
α ν
α α ν
ν
α α
(3)
而分群結果則可透過廣告群間的平均差異與 使用群間的平均差異代表共分群的效能
∑∑
∑∑
= ≠
= ≠
= −
= −
+
=
L i
L i j
j i
KL User
K i
K i j
j i
KL Ad
User Ad
A p A p L D
KL L
U p U
p K D
KL K
KL KL U A KL
1 1
)) ˆ| (
|| ) ˆ| ( ) (
1 (
1
)) ˆ| (
|| ) ˆ| ( ) (
1 (
1 ˆ) ˆ, (
ν ν
α α
(4) 5.2 廣告分群評量結果
由於並非每個使用者都有參予 Lohas Game， 所以我們原本鏈結矩陣的使者人數有達 7980 人， 但我們取同時有鏈結廣告，且參予 Lohas Game 的 使用者，如此才能夠將 Lohas 資料放進來實驗，因 此，過濾後此部份使用者個數為 1685 人
我們的實驗資料主要是針對 463 個廣告，及 1685 個使用者點選廣告的鏈結矩陣，我們將比較以 下三種不同的分群方法：
(1) baseline：使用 K-means 對廣告特性資料及廣 告鏈結矩陣分群，其疊代數設定為 1000，並將分 群結果當作標準答案
(2)三階段式分群(3-staged clustering)
(3)重複式交叉分群(Iterative cross co-clustering) 我 們 以 廣 告 特 性 資 料 矩 陣 和 廣 告 鏈 結 矩 陣
(ad-user link matrix)做驗證分群的資料，意即我們結 合兩份資料利用決策樹分類，與分群結果做為標準 答案 實驗結果如圖六所示，X 軸代表不同的 K 值， Y 軸代表相對應的 F-measure 我們看 K 設定在 2 群~5 群之間的 F-measure 由圖表得知，重複式交 叉 分 群 (Iterative cross co-clustering) 有 較 佳 的 F-measure，而 baseline 使用相同一份資料做分群， 並拿分群結果當作標準答案，利用決策樹分類，其 F-measure 卻沒有比我們提出的重複式交叉分群結 果好
Ads Classification Performance
0.700 0.800 0.900 1.000 1.100
F-measure
ICCC 1.000 0.981 0.950 0.946 3-stage 1.000 0.981 0.961 0.948 Baseline 0.998 0.926 0.899 0.835
K=2 K=3 K=4 K=5
圖 6 以廣告特性矩陣和廣告鏈結驗證 5.3 雙維共分群評量分析
我們以三個方法過程中所得到的廣告群 Â 與 使用者群 Û，做為合併廣告-使用者鏈結矩陣的參 考 ， 建 置 出 廣 告 群 和 使 用 者 群 的 鏈 結 矩 陣 (AU matrix)，其建置公式如下：
∑ ∑
∈ ∈=
i j
k l
kl
ij Link
AU
α ν
(5)
我們將使用者群(υl)所有使用者所鏈結的廣告次數 且屬於第αk個廣告群(ad cluster)的數值相加，產生 我們所要的廣告群和使用者群的鏈結矩陣 為了計 算 KL divergence，我們將每一個廣告群 αi的鏈結
個數做正規化得 p(Û|αi)，藉以計算廣告群間的平均 KL 差異 KLAd，同理也為每個使用者群υj鏈結個數 做正規化得 p(Â|υj)，藉以計算使用群間的平均 KL 差異 KLUser
圖七呈現 K=5 時 KL divergence 的結果， X 軸 分別代表 KLAd KLUser 及 KL(Â, Û)，Y 軸分別 代表我們觀察在三種方法的廣告群之間的差異 使 用者群之間的差異及兩者加總起來的差異結果 我 們依照各種方法產生的廣告群和使用者群，並根據 鏈結矩陣，建構廣告群鏈結使用者群的矩陣，我們 固定使用者群，分別取特定兩 廣告群計算 其 KL-divergence，計算所有廣告群之間差異後，我們 將所有差異值加總後取平均，反之，我們可以得到 各個使用者群之間的差異 我們可以 現，各群之 間變異性很大，而且 Iterative cross co-clustering 和 Three-staged clustering 的效果都比 baseline 的效果
好，所以透過我們提出的方式均能夠達到較佳的分 群結果
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14
Average KL divergence
U Â Û
Evaluation by KL divergence
I 3 ag
a lin
圖 7 K-L divergence
5.4 廣告分群解析
上述各 實驗結果， 現在群數設定為 5 時其 分群效果為最佳，我們觀察重複分群(Iterative cross co-clustering)的實驗結果並分析其分群狀況，下圖 為利用重複式交叉分群，群數為 5 時，各群分群的 數量如下：
圖 8 重複式交叉分群結果(廣告群分佈 K=5) 我們觀察分群結果 現，在 cluster 0 的廣告 群，多為分潤金額(M)較大的廣告，平均廣告金額 為 800，其點選人數(N)也較多，平均點選人數佔 529 人，其廣告排序也佔較前面幾頁，平均約在第 2 頁， 而且並無設定鏈結人數(L)與其個人點數(K)，比較 具代表性的廣告為人工智慧導向人力資源配置與 管理系統 投資自 明日之星就是你 拼 SQIQ&LK 大獎賽鍊結廣告等等屬於品牌廣告類型
Cluster 1 的廣告其分潤金額(M)普遍偏小，平均 金額為 22，其平均點選人數(N)為 21 人，平均廣告 排序為 26 頁，且 L 和 K 值一樣是沒有設定的狀況， 廣告多為小型商家如聯必優-讓您輕鬆擁有心中的 夢幻手機 洪同慶系統櫥櫃專業施工 台北春風眼
科?專業雷射全視力矯正中心等等
Cluster 3 的廣告與 Cluster 1 的廣告類似，其平 均分潤金額為 27，點選人數(N)為 38 人，廣告排序 為 27 頁，但是和 Cluster 1 不同的是，其 L 和 K 值 是有設定的狀況，比較具代表性的廣告為新賀斯國 際有限公司 台茶國際有限公司 合鈦超硬刀具有 限公司等等小型商家，且大部分皆為 ID 編號 600 以後的廣告
而 Cluster 2 和 Cluster4 則屬於較為中間層的廣 告，其金額和人數大概都介於 cluster0 和 cluster3 之 間，排序也大概落在 15 頁上下的位置
5.5 使用者分群評量結果
同樣的，針對 1685 個完成 Lohas Game 的使用 者，及 463 點選的廣告鏈結矩陣，針對使用者分群 我們比較三種分群的結果：
(1) baseline ：我們使用 K-means 對 lohas game 及 user link 進行分群，其疊代數設定為 1000，並將分 群結果當作標準答案
(2) 三階段式分群(3-staged clustering)
(3) 重複式交叉分群 (Iterative cross co-clustering) 我們使用決策樹做為我們評估的方法，而我們 將 lohas game 及 user link 兩份資料合併當作測試資 料 ， 並 且 以 上 各 個 方 法 所 產 生 的 分 群 ， 透 過
F-measure 來評估各個方法的分群效果為何 根據
實驗結果顯示(圖十)，我們 現 baseline 雖然使用和 測試資料相同的一份資料進行分群，並將其分群結 果當作標準答案，進行分類；然而，其效果卻不如 我們所提出的重複式交叉分群
User Classification Performance
0.650 0.700 0.750 0.800 0.850 0.900 0.950
F-measure
ICCC 0.886 0.844 0.776 0.786 3-stage 0.894 0.794 0.800 0.754 Baseline 0.881 0.823 0.769 0.678
K=2 K=3 K=4 K=5
圖 9 將 lohas 暨 user link 資料接合以驗證三種分 群方式的效果
從實驗結果我們 現，由於 baseline 的部分只 有根據每一個使用者的 lohas_game 及 user_ad link 資料去做分群，由於高維度時距離的計算會較難反 應資料資間的相似性，導致分類的準確度欠佳；而 我們所提出的重複式交叉分群方法，能夠重複的參 考使用者和廣告等的資訊，以利找到最佳的分群
綜合以上評估方式，重複式交叉分群，不僅能
在廣告也能在使用者分群上，達到較佳的分群結 果 重複式交叉分群，同時考慮了廣告資訊 使用 者資訊以及鏈結資訊，綜合以上幾種資訊，並能夠 同時對廣告和使用者進行分群，而且效果比 baseline 的效果來的好
6. 結論
傳統的分群方式，只能針對單向資料進行分 群，以致於無法觀察到雙向資料之間的關係；我們 提出了重複式雙維度共分群的方法，同時參照了廣 告資料和使用者資料，利用單向分群的概念，來達 到共分群的效果，並且也能達到較佳的分群效果， 在觀察廣告分群的同時，也能同時對使用者做分 群，並觀察使用者群和廣告群之間的關係
我們的評估方式是藉由預測類別的方式來驗 證分群，並透過 KL-divergence 來判斷不同 的分群 方法之間的分群差異，經由實驗結果得知，3-staged clustering 由於同時對廣告或同時對使用者做分 群，所以能夠達到較佳的分群效果，然而 Iterative cross co-clustering 因為同時考慮了廣告及使用者資 料進入分群，所以雙向資料互相牽引之下，導致效 果比 3-staged clustering 略差一些，但也能達到一定 水準的分群效果，但 Iterative cross co-clustering 在 共分群的表現上，能夠同時對廣告分群，也能同時 對使用者分群，效果比單向分群的 baseline 方式好 未來我們想要朝向共分群的 展模式前進，希望透 過較為正式的數學定義，以及演算法的理論基礎，
展一套正式的共分群方法
致謝
本論文為國科會計畫，社群網路廣告最佳配置 之研究(NSC98-2622-E-008-023-CC2)與創旭知識科 技應用股份有限公司產學合作研究成果
參考文獻
[1]. A. Banerjee, I. S. Dhillon, J Ghosh, S. Merugu, and D. S. Modha. “A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation.” In KDD’ 04: Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 509-514, Seattle, Washington, USA, 2004. ACM press. [2]. Bo Long, Zhongfei Zhang, and Philip S. Yu
“Co-clustering by Block Value Decomposition.” In KDD ’05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 635-640, Chicago, Illinois, USA, 2005. ACM press.
[3]. Hanisch D, Zien A, Zimmer R, and Lengauer T
“Co-clustering of biological networks and gene expression data.” Institute for Algorithms and Scientific Computing (SCAI), Fraunhofer Gesellschaft, Schloss Birlinghoven, Sankt Augustin, 53754, Germany.
[4]. Inderjit S. Dhillon, “Co-clustering documents and words using bipartite spectral graph partitioning.” In KDD ’01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. San Francisco, California pp. 269 – 274.
[5]. I. S. Dhillon, S. Mallela, and D. S. Modha.
“Information-theoretic co-clustering.” In KDD ’03: Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 89-98, New York, NY, USA, 2003. ACM Press.
