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