第八章 連結分析 Link Analysis

連結分析 簡介 圖形基本觀念 個案研究 連結分析的優、缺點

簡介 商業世界是一個佈滿著關係的世界，透過關係，我們可以將人們，地方及事物連結在一起。

簡介 關係無所不在，這些關係中包含了大多數資料採礦技術無法直接利用的豐富資訊。連結分析（LA）就是可以利用這些關係技術。

圖形基本觀念 一個圖形包括了兩個部分： 頂點(nodes，有時候稱為頂點vertices)，指的圖形中有關係的事物，他們都有名稱，且通常另外還有有用的特質。 稜（edges）指的是由關係連結在一起的一組頂點，稜以其連結的兩個頂點來表達，因此（A，B）或AB即指連結AB兩點的稜。

圖形基本觀念 下圖是個加權圖形（weighed graph）的例子中，其中每個稜都有一個權值。在這個例子中，各個加點代表顧客所購買的產品，稜的權值代表包含兩種產品的購買量。

圖形基本觀念 此一圖形提供了解決購物籃分析(market basket analysis）問題的方法，正如我們在第八章所討論的，這對於將購物籃資料視覺化也是很有用的工具。 下面將描述圖形理論中兩個經典的問題，這兩個例子將可以清楚地說明圖形呈現問題和解決問題的威力。在此，我們藉由範例提供圖形理論中的關鍵概念，可以讓讀者熟悉圖形的運用，並且成為進一步討論連結分析的基礎。

康尼斯堡的七座橋 康尼斯堡在普格河上有兩個彼此相連的島，還透過七座橋與城市的其他地方相連。下圖中畫出可以一次橫跨城市裡的五座橋的一條路徑。

康尼斯堡的七座橋 尤拉提出一個問題：是不是可能從城裡的任一個地方為起點，一次走過城裡的七座橋，而不必弄濕自己？ 為了解決此一問題。尤拉發明了圖形的概念。他將康尼斯堡的圖以四個頂點和七個稜的圖形來表示，如下圖，部分頂點之間有一條以上的稜相連，表示這之間有一座以上的橋相接。要找出能一次視察康尼斯堡所有橋樑的路線，就等於找出可以一次走過圖形中所有稜的路徑。

康尼斯堡的七座橋 尤拉利用圖形中由每個頂點起始和結束的稜的數目，找出解答．此種稜的收目稱為頂點的自由度 (degrees) 。尤拉告訴我們，只有在圖形中所有頂點的自由度皆為偶數時，尤拉路徑才可能存在，除非圖形中僅有兩個頂點。

業務員旅行的問題 一位業務員必須拜訪在許多城市的客戶，他計畫飛到其中一個城市，租一輛車，拜訪那裡的客戶後，然而開到其他城市去拜訪其他的客戶，他把車子留在最後一個城市，之後飛回家。何種路線可以讓他旅行距離最短，卻可以一次拜訪所有的城市？

業務員旅行的問題 四個頂點的圖形中最複雜的要算是四個頂點間兩兩彼此相連結的圖形。在此圖形，有24條不同路徑可以一次走完四個頂點。為了計算路徑的數目，我們可以從任一頂點開始（四種可能性），然後走到任何其他的三個頂點，之後走到任何其他二個頂點，然後是最後一個頂點（4x3x2x1=24!）。包含ｎ個頂點的完全連結圖形有ｎ階乘個路徑來走完所有頂點。

業務員旅行的問題 如果把圖形理論擱在一旁，電腦有非常好的啓發式演算法可以提供業務員旅行問題合理的解答。電腦可以找出相當短的路徑，然而無法保証是其中最短的一條。如果你有一個類似的問題，這是相當有用的事實。常見的演算法是貪婪演算法(greedy algorithm): 路徑是從圖形最短的稜開始，接著從最短稜的兩頂點中找其中一個新的頂點繼續走下去。這樣找出來的路徑通常相當短，但不必然最短的。

業務員旅行的問題

個案研究(1) 誰從家裡用傳真機？ 連結分析能用來分析本地電話公司的紀錄，以確認哪些家庭用戶家裡比較可能有傳真機？ 為什麼要找出傳真機？ 為什麼要找出傳真機？  在本個案中，業者已經針對在家工作的SOHO族發展了一套服務，針對此類顧客的行銷目的，對該公司而言是一個革命性的概念。

個案研究(1) 原先他們對這些顧客收取較高的公司電話費率，而非一般住宅的電話費率。他們非但沒有針對這些顧客給予特別的行銷計畫，反而讓他們無法享有一般住宅的低廉費率-因為視他們如同一家小公司而懲法他們。 對這家公司而言，發展和銷售SOHO族的套裝計畫來改善對SOHO族顧客的服務代表對客服務的新出擊。但誰才是我們的目標顧客呢？

個案研究(1) 發送和接收傳真的顧客至少會有兩個號碼 - 如果他們只有一號碼，業者將有機會賣給他們第二個號碼。為了提供較好的顧客服務，只使用一個號碼的傳真顧客必須知道如何讓插撥進來的電以等待的狀態保留，否則可能會干擾傳真的進行。也有其他的可能性：擁有傳真機的顧客也許喜歡以傳真而非郵件的方式收到帳單，可以省下郵資和印刷成本。簡言之，能確認誰從家裡收送傳真是相當有價值的資訊，此一資訊可以提供增加收益，減少成本，以及提高顧客的滿意度。

個案研究(1) 資料就是圖形 此一分析所做的原始資料是通話明細資料帳單系統每月帳單，每筆資料包含80個位組的資料，資料就像： 資料就是圖形  此一分析所做的原始資料是通話明細資料帳單系統每月帳單，每筆資料包含80個位組的資料，資料就像： ●撥號者10位數的電話號碼：包括三位數的區域 碼，三位數的交換碼，四位數是該線路的號碼; ●收話者10位數的電話號碼; ●付費者的10位數的電話號碼; ●通話日期和時間; ●通話時間長度; ●其他，如星期幾以及該通電話是否在一個付費電 話上進行。

個案研究(1) 此一分析將資料減少三個變數：通話時間長度；撥號者的電話號碼和收話者的電話號碼。電話號碼是圖形中的頂點，電話本身則是稜，以通話時間長度為其權值。首先，注意圖形共不是相連結的，它包括了兩個完全分開的部分。第二個差異更為重要，這裡的稜是有箭號的，表示他們以有方向性。每一個稜始於撥號者，結束於收話者。

個案研究(1)

個案研究(1) 方法： 找傳真機是基於一個簡單觀察：傳真機只能與傳真機通話。一己知有傳真機的號碼能擴充至其撥出或收到的號碼。實際上一個住宅型顧客可能有幾類的傳真機使用情況： ●傳真機專用的線路： ●兼用的線路： ●資料的線路：

個案研究(1) 假設傳真機只能撥給其他傳真機，對使用專屬線路的傳真機而言是正確的，雖然此─規則也有例外：例如撥錯號碼時。為了區別兼用路，專屬線路以及資料線路，我們假設任何曾經撥過查號台─104的電話必然是語音線路兼用的傳真線路或者只是一般的語音電話；當兼用線路撥給另一個號碼時，我們無法得知該通電話是語音或資料傳輸。另一方面，這些兼用線路的確代表我們賣給顧客一個新號碼機會。

個案研究(1) 用來找出傳真機的過程包含以下的步驟： 從已知的一組傳真機開始。（從工商名錄 收集而來） 2. 找出打給或接到上述這組號碼，且這些電話的通話時間必須在10秒以上。這些電話號碼都具有候選資格。 ●如果這些候選的號碼曾經與104的通話記錄， 或者某一號碼確認為兼用的號碼，則這個號碼將 歸屬於語音/傳真兼用號碼那一組。 ●否則，這個號碼則歸類為已知傳真號碼那組。 3. 重複步驟一與步驟二直到找出確認所有號碼的情況。

個案研究(1) 部分結果： 我們使用的電話記錄樣本包括了3,011,819通話，這些電話是一個月內從19,764個家庭中撥出的。找出傳真機是一種圖形著色的演算法（graph coloring algorithm）。這種類型的演算法必須檢視整個圖形而且把不同頂點標示不同的顏色。在這個個案中，顏色分別為「傳真」、「兼用」、「語音」、「未知」，而為紅色，綠色，黃色，和藍色。一開始所有頂點都是「未知」的頂點，得到其他意義性的標示。

個案研究(1) 下圖顯示一個有15個號碼和19個電話的通話圖形。首先，已知是傳真機的號碼標示為「F」兼用的號碼標示為「I」。 ●任何連結到一個「傳真」頂點的「語音」頂 點，標示為「兼用」。 ●任何連結到「傳真」頂點的「未知」頂點， 標示為「傳真」。  這個流程持續進行，一直到所有連結到「傳真」頂點的所有頂點都有「傳真」或「兼用」的標示。

個案研究(1)

個案研究(1)

個案研究(2) 區隔行動電話顧客： 本個案研究將連結分析應用於行動電話業務上，為了在現在顧客中進行區隔，以銷售析的服務。 區隔行動電話顧客：  本個案研究將連結分析應用於行動電話業務上，為了在現在顧客中進行區隔，以銷售析的服務。   資料：行動電話資料與在上一個傳真機個案研究中的電話明細資料相似。每個電話都包含下幾項變數： ●撥話端和接話端的電話號碼。 ●電話撥出的位置。 ●撥出電話的顧客帳號。 ●該通電話的通話時間。 ●時間和日期。 ●其他，與本研究無關者。

個案研究(2) 未利用圖形理論的分析： 在未利用連結分析之，行銷部使用單一指標來進行市場區隔，這個指標是通話長度(MOU)，也就是每一顧客每個月使用行動電話時間長度。這項關聯性並不精確，因為它並未考慮折價時段以及免費夜間和週末。儘管如何，MOU還是一個好指標。除了MOU以外，他們對顧客行為的了解僅止於其帳單總額，以及顧客是否準時付款。他們仍然留了許多資料未能使用。

個案研究(2) 兩個顧客的比較(利用LA)： 下圖舉例說明兩個顧客在一個典型的月份中的通話型態。這兩位顧客有相似MOU，然而其通話型態卻極端不同。約翰的通話模式是一個相當小且緊密的圖形，而珍的通話模式卻因為許多不同的通話對象而開展成很大的圖形。

個案研究(2)

個案研究(2) 如果珍滿意她的行動電話服務，她的使用很可 能會成長，甚至影響許多她的朋友和同事轉換 行動電話服務廠商。舉例來說，提供珍每通電 話第三分鐘免費服務，可能誘使她延長其許多 通話時間較短的電話。 另一方面，如果提供約翰同樣的服務，若可能 減少的帳款金額。

個案研究(2) 現在，如果競爭對手試圖接觸珍和約翰，那麼 會發生什麼狀況？誰更可能接競爭對手的條件？ 猜測珍有較高的價格敏感度，因此可能對其他 條件較為敏感。然而，再想一想會發現，改變 行動電話服務廠商對珍來說可能很不方變，因 為她必須要改變電話號碼。仔細觀察打電話給 她的人數，我們可以看到珍相當依賴她的行動 電話號碼。她甚至使用語音信箱的服務。她必 須通知的人數是一道阻止她改變行動話業者的 慣性。

個案研究(2) 約翰沒有此種慣性，而且對其行動電話業者可 能沒有忠誠度─只要該業者能提供他星期三上 45分鐘電話會議不中斷的服務品質即可。 珍也有很大的影響力，因為她與這麼多不同的 人通話，他們都知道珍滿意或不滿意她的行動 電話服務。她是一個行動電話業者想要讓她滿 意的顧客。但是，她不是用傳統市場區隔方法 會設定的顧客。

個案研究(2) 連結分析的威力：連結分析在分析行動電話資料時扮演了兩種角色: 視覺化的威力。可以看出有些圖形代表通話型態，使通話型態的部分特性，如慣性及影響力更為明顯。以這個例子來說，我們選擇兩個從先前市場區隔技巧看來十分相似的顧客。連結分析顯示出他們特定的通話型態，以及他們之間的差異。 應用連結分析在視覺化產生的概念來擴大顧客群。 例如：進行電話會議的能力是我們想要的，但是誰會是最佳的潛在顧客？一個可能找出彼此互相通的顧客群。

連結分析的優、缺點 連結分析的優點： ●它適用於連結類型的資料 ●它在視覺化方面很有用處。 ●它創造出衍生的特性。 連結分析的缺點：   連結分析的缺點： ●它並不適用於很多類型的資料 ●很少工具支援連結分析。 ●在關聯式資料庫上的操作效率不佳。