新一季的《權力的遊戲》終於開播了！
和各位望眼欲穿的粉絲一樣，我也無比好奇，黑腦洞的編劇在這一季又安排了哪些角色去領盒飯。所以我決定，做一個按照角色死亡可能性由高到低的排名算法。
本文的全部分析結果在新一季開播前已經完成，如與劇情雷同，純屬巧（niu）合（bi）。
《權力的遊戲》的世界和人物關係非常複雜，社會地位和真正的朋友顯得格外重要，所以我用網絡科學（Network Science）工具來量化每一個角色的社會互動模式，用機器學習的方法預測他們的命運。
建立維斯特洛大陸的社交網絡
我在一個粉絲網站上收集對話格式的劇中字幕作為數據源。不幸的是，第二季和第三季的多數劇集都是缺失的，但是剩下的四季包含將近600個場景，都能夠用統一格式獲取。
首先，我建立了劇中社交系統的集成網絡。在這個網絡中，每個節點都代表一個故事中的角色，每兩個點之間的連線粗細代表他們的關係強度。我把劇中的場景作為衡量社交互動的基礎單位（每集平均有大概20個場景）。這代表兩個人物在同一個場景中出現一次（n次）就會有一個強度為1（n）的關係聯結，並且在一個場景中出現的任意兩個人都會互相聯結。
換句話說，場景就是完備圖（complete graph），或者團集（clique），在其中出現的任意一對人物都會讓自己的關係強度增加。通過計算這些場景級的完備網絡，並且把他們集成起來，我們會得到維斯特洛大陸上的全局社交網絡（與全景相連結），這張網絡有將近400各結點和超過3000條邊。
在網絡可視化中，不同大家族中的成員用不同的顏色表示（例如，藍色—史塔克家族Starks，紅色—蘭尼斯特家族Lannisters，黃色—馬泰爾家族Martells），其他非大家族成員都用灰色表示。
結點的大小與角色的聯繫人個數成比例，最核心的角色名稱標註在了結點旁邊。度（下文會解釋什麼是節點的度）較低的、不那麼有趣的節點被過濾掉了。
我們可以發現，什麼都不懂的瓊恩·雪（Jon Snow）的周圍是個獨立的社交群體，這表示北境長城附近的角色與王國內其他角色的聯繫極少。小惡魔（Tyrion）有一個獨立的角色：他將龍媽（Daenerys Targaryen）與社交網絡的的中心包括君臨城聯繫起來。
這個中心主要包括兩個大型集群，即史塔克家族Starks和蘭尼斯特家族Lannisters以及他們影響和交互過的區域，譬如像史塔克Stark和徒利Tully家族（狼媽家）的結盟，以及蘭尼斯特家族Lannisters和馬泰爾家族Martells之間的衝突，這些在故事的核心形成了一張緊密的網。
下面我們了解一下數學原理。節點的重要程度有多重度量方法。我們認為這些度量指標能夠表明一個角色在這個社交生態系統中的重要性。這些指標包括：
（1）節點度—一個角色有多少聯繫人；
（2）加權度—節點邊權值的和；
（3）群集性—各對聯繫人節點互相聯繫的頻率；
（4）中間中心性—通過度量一個節點出現在另外節點對之間最短路徑上頻率，衡量它在多大程度上是一座信息溝通橋梁。
除了更好地了解誰重要誰不重要之外，我們也能從前六季中哪些角色領盒飯的數據中吸取經驗。我們目標是把網絡位置和倖存者聯繫起來：位置是否能預測倖存概率？換句話說，我們希望訓練一個算法，來弄清楚哪個網絡指標能夠預測一個角色是否死亡。
橫坐標：小喬大帝、班楊·史塔克、希恩·葛雷喬伊、瓊恩·雪、梅麗·桑卓
縱坐標：度、加權度、網頁排名、群集性、特徵中心性、緊密中心性、中間中心性、死亡與否
開始我的表演：強力預測
有94個角色值得我們關注。他們都可以用七個不同的基於網絡的指標來描述，這些指標代表了不同維度的社交重要度。我們也知道哪些角色已經死了（其中的61個）。基於這些指標，通過下面的方法，對於哪個角色會在接下來死去我們可以形成有根據的推測：了解還活著的人有哪些和已經死去的角色有相似的特徵。
這個問題類似於眾所周知的流失問題，多種基於分類的算法能解決這類問題。在這個分析中我們使用SVM（支持向量機），這也是最準確的模型。如果你想自己在家嘗試的話，它在Python中有一個很容易上手的應用。
機器學習算法會把所有特徵計算在內，並預測目標變量可能的值。在這個例子中，數據被多次隨機分為測試和訓練集，所有分組數據都能生成預測值，並進一步得到最終結果。
在這種交叉驗證中，SVM分類器有72.3%的概率預測到正確的分類結果（死了或者活著），考慮到數據的類型和規模這個結果是合理的。為了說明模型準確度，模型認為有八個角色不應該死掉，但是在故事中他們死了——模型無法預測到他們的死亡。比如小玫瑰（Margaery Tyrell），似乎皇后死亡比皇帝死亡可能性小，還有Janos Slynt（前都城衛隊司令），他被從君臨城流放到了北境長城，導致他極有勢力的朋友無法救他，儘管模型建議他們去救。
需要說明的是，有其他一些手段可以增加預測的準確性，例如引入其他特徵類型（比如：性別、是否是貴族、對話情感分析等等），擁有更完備的數據集，對比電視劇和原著小說等。這個模型也忽視了一些差異性，如瓊恩·雪（Jon Snow）死而復生、班楊·史塔克（Benjen Stark）介於活與死之間。
結論：劇透預警！
使用SVM模型我們得到了答案——每個重要角色死亡的概率。因為網絡指標經常相關性很高，我們無法找到單獨一個或兩個能非常準確預測結論的指標，但似乎高中間中心性，低群集性和高節點度的角色更不容易被殺害。
不論在哪種情況下，機器學習在大量的特徵中準確地找到了隱藏的關係。在預測中，我使用五折交叉檢驗，並且把這個過程重複了100次來獲得統計值和概率誤差的估算。最後，下面是按照最終預測模型顯示的存活率升序排列的角色列表：
橫坐標從上而下分別為：Tyene（紅毒蛇的小女兒）、龍媽、灰蟲子、勞勃艾林（乖羅賓，新任鷹巢城公爵）、波德瑞克（小惡魔前侍從）、艾德慕徒利、大瓊恩安柏、賈坤、波隆、艾麗婭史塔克、獵狗桑鐸克裡岡、美人布蕾妮、梅麗桑卓、老玫瑰奧倫娜提利爾、雅拉葛雷喬伊、次子團團長達裡奧納哈裡斯、詹姆蘭尼斯特、詹德利（勞勃拜拉席恩的私生子）、布蘭登史塔克、三傻史塔克、八爪蜘蛛瓦裡斯、小惡魔提利昂蘭尼斯特、小指頭培提爾貝裡席、科本學士
縱坐標：死亡概率、誤差
預測死亡概率最高的是上圖這位妹子，我說什麼好？
這個死亡概率列表其實告訴我們很多有趣的事：
由於和很多死亡嫌疑人的網絡重疊，龍媽Daenerys很可能馬上會掛，但小惡魔Tyrion和瓊恩·雪（Jon Snow）是相對安全的。
一直受歡迎的艾麗婭·史塔克（Arya Stark）和不太友好的獵狗，之前已多次面臨死亡，現在也都在非常危險的位置上。
令人驚訝的，現在正坐在鐵王座上的瑟曦（Cersei），和正在努力爭取坐上去的小指頭（Baelish），看起來安全得多。
看起來喬拉莫爾蒙爵士（Jorah Mormont）將會找到灰鱗病的治療方法，儘管希恩·葛雷喬伊歷盡艱難，卻可能會倖存。
鷹巢城艾林家族的命運就很難說了。
這個預測是不是很有趣…...各位粉絲怎麼看？