深入淺出聚類算法!如何對王者英雄聚類分析,探索英雄之間的祕密
Datawhale
作者:小一 ,Datawhale優秀學習者
寄語:首先,對聚類算法進行了介紹;然後,解釋了EM算法E步、M步 的 原理 ;最後,對sklearn參數進行了詳解,並對王者榮耀英雄利用EM算法聚類,助力深入理解EM算法。
EM算法(Expectation Maximization Algorithm),譯作最大期望化算法或期望最大算法。它是一種迭代算法,是常見且經典的聚類算法之一,用於含有隱變量(hidden variable)的概率參數模型的最大似然估計或極大後驗概率估計。
對聚類算法、EM算法的原理及其實踐進行詳細的講解之前。 首先來看一張EM算法的聚類圖,有個大致直觀地瞭解。
學習框架
數據集及聚類分析代碼後臺回覆 王者榮耀 獲取
聚類算法
先來一段西瓜書裏面的定義: 在“無監督學習”中,訓練樣本的標記信息是未知的,目標是通過對無標記訓練樣本的學習來揭示數據的內在性質及規律,爲進一步的數據分析 提供基礎,此類學習任務中研究最多、應用最廣的是“聚類”(clustering)。
總結一下關鍵詞:標記信息未知、學習、內在性質及規律、聚類。 對,還有一個:無監督學習, 無 監督算法大多都可以用上面的關鍵詞來描述。
以聚類算法爲例,其 目的是對一批未知標記的數據通過某種方式進行聚類,使其能夠有效的分成若干個類別,每一個類別裏面的數據特徵都類似,不同類別的數據差異性較大。
舉個簡單的例子:在中國的鄉村有這樣一個現象,一個村子的姓氏大多相同,不同村子有不同的姓氏。那如果現在把王家村、李家村、趙家村的所有人都聚集在一起,前提是不知道他們是哪個村子的,如何對他們進行聚類?
-
特性①: 姓名,通過姓氏進行聚類,最終聚成三類: 王+李+趙+其它
-
特性②: 性別,通過性別進行聚類,最終聚成兩類: 男+女
-
特性③: 年齡,通過年齡進行聚類,最終聚成三類: 兒童+青年+老年
-
特性④: 價值,通過價值進行聚類,最終聚成三類: 高收入+中收入+低收入
-
特性⑤: 屬性,通過屬性進行聚類,最終聚成三類: 村領導+村幹部+村民
-
…
上面的姓氏、性別、年齡、價值和屬性等都是村民的內在性質(人物特徵),這樣的內在性質有很多,也就決定了聚類的標準並不唯一。
ok,想必大家已經明白了什麼是聚類,通過上面的例子我們總結一下。
1. 何爲聚類
聚類:將數據集中的樣本劃分爲若干個不相交的子集,每個子集內部的樣本之間具有相同的性質,不同子集之間差異性較大。 通常情況下,我們會將子集稱之爲“簇”(cluster)
2. 如何聚類
聚類的本質是將具有相似特徵的樣本劃分在一個簇裏面,根據聚類算法的不同,聚類的實現過程也不盡相同。
例如,聚類算法中k-means是基於均值的聚類,DBSCAN是基於密度的聚類,AGNES是基於層次的聚類,可以針對不同的樣本集使用不同算法進行聚類。
3. 評估聚類
聚類性能的評估比較麻煩,主要有兩個原因:
-
樣本集不存在已標記的類別數據,無法直接計算聚類算法的準確率。
-
若存在標記類別數據,無法直接通過預測前後類別之間的對應關係進行性能評估
針對上面的問題,可以大致分爲兩種,一種是存在已經確定的標記類別數據(類似於分類數據集),一種是完全沒有標記的類別數據。
有標記類別數據的評估: 當前的樣本數據有標記類別數據C1和預測後的標記類別數據C2,但是無法直觀的通過C1、C2去計算聚類錯誤率。
這個時候,可以通過條件熵去分析, 可以認識到兩個指標,分別是齊次性和完整性。 通 過這兩個指標可以評估帶有類別標記樣本的聚類性能 。
其中齊次性表示一個聚類元素只由一種類別的元素組成;完整性則表示給定的已標記的類別 ,全部分配到一個聚類裏。
沒有標記的類別數據的評估: 大多應用於聚類算法的數據都是無標記的,因爲既然數據都有標記了,直接用分類算法不香嗎?
有一個指標叫做輪廓係數,它可以在不需要已標記數據集的前提下,對聚類算法的性能進行評估。
輪廓算法由以下兩個指標構成:
-
a: 一個樣本與其所在相同聚類的平均距離
-
b: 一個樣本與其距離最近的下一個聚類裏的點的平均距離
則針對這個樣本,其輪廓係數s的值爲:
針對一個數據集,其輪過係數s 爲其所有樣本的輪廓係數的平均值。輪廓係數的數值介於[-1,1]之間,-1表示完全錯誤的聚類,1表示完美的聚類,0表示聚類重疊。
EM原理
EM的英文全稱是:Expectation Maximization,所以EM算法也叫最大期望算法。
學習EM之前,希望你已經理解了什麼是極 大似然估計,不瞭解的點這個: 太讚了!機器學習基礎核心算法:貝葉斯分類!(附西瓜書案例及代碼實現)
1. 極大似然估計
先說一下極大似然估計:已知某個隨機樣本滿足某種概率分佈,且某個參數能使這個樣本出現的概率最大,我們把這個參數作爲估計的真實值叫做最大似然估計。也就是求解出現樣本結果的最佳參數θ。
所以極大似然估計需要面臨的概率分佈只能有一個,但是要是不止一個呢? 看個例子:
假設現在有兩枚硬幣A和B,隨機拋擲後正面朝上概率分別爲P_A,P_B。 爲了估計這兩個概率,需要每次取一枚硬幣,連擲10下並記錄下結果,結果如下:
ok,根據以上分佈結果,可以輕鬆算出:
似乎很簡單,但是你要知道每次我們都知道了是拋出哪個硬幣。 換句話說,我們已經提前知道了每次選擇硬幣拋出的樣本分佈。 如果,我們不知道呢? 那會是什麼樣的? 上面的例子變成了這種:
Z{A,B}表示每次選擇A、B兩個硬幣中一個,但是我們現在已經不知道是哪一個了,目標還是估計A、B兩個硬幣正面朝上的概率。當我們知道每一次拋出的硬幣是A還是B,才能利用最大似然估計對A、B正面朝上的概率進行估計。
當我們知道A、B正面朝上的概率,纔會知道拋出的硬幣最有可能是A還是B。 這樣來看,這個 問題就有趣了,我們並不知道是雞生蛋還是蛋生雞,怎麼判斷是先有雞還是先有蛋? 考慮這個問題不妨再來看下面的例子。
2. 分菜問題
大廚炒好了一鍋菜,需要把鍋裏的菜平均分配到兩個碟子裏,大廚應該怎麼辦呢?
如果是浸淫已久的大廚,可能隨便小手一抖就平均到兩個碟子裏了,但是大多數都是僞大廚,手上功夫還不到位,他們應該怎麼做?
僞大廚可能需要多試幾次纔行,比如先隨便分在兩個碟子裏,然後把菜多碟子的菜往另一個碟子勻勻,然後再勻勻,再勻勻…一直到兩個碟子中菜的量大致一樣。
ok,那我們這個問題呢?要不也試試僞大廚的方法?
3. 模仿分菜
首先,我們模仿僞大廚的方法,隨便設置A、B硬幣正面朝上的概率P_A=0.5、P_B=0.9。如果第一枚硬幣是A硬幣,那麼它正面朝上的概率是:
如果第一枚硬幣是B硬幣,那麼它正面朝上的概率是:
同樣的計算方法,其他幾枚硬幣的概率分別是:
按照最大似然法則,每一次取概率最大的作爲我們的結果,則硬幣的順序依次是:AABBA。 這個也就是上面我 們假設的Z值,那麼根據這個Z值我們可以輕鬆的算出:
算出的P_A、P_B的值和我們假設的不一致,這時候說明僞大廚還沒有把菜分均勻。 看來僞大廚還需要再分一次,這個時候A、B正面朝上的值由第一次的:
更新成現在的:
重複上面的步驟,最終A、B正面朝上的概率不再發生變化,且會逐漸逼近一個值,這就是EM算法的工作原理。
4. 模仿的升級
雖然說我們一直在模仿大廚的操作,但是我們也想要超越他成爲更厲害的大廚。
在上面的過程中,我們發現直接每一次選擇最大概率的結果作爲硬幣的選擇有點過於絕對,因爲從計算結果來看另一枚硬幣也是有概率的,只是概率偏小一點。這樣的話,我們在第一輪中可以這樣計算:
如果第一枚硬幣是A硬幣,那麼它正面朝上的概率是:
同理可以求出第2輪到底5輪的概率值
此時,我們可以根據最大似然估計求出的概率,分別算出AB正反面的期望值:
例如:第一輪中,0.994的概率爲A,拋10次,正面朝上的概率爲0.994*5=9.94,同理反正爲0.06。 同理可以求出第2輪到第5輪的期望值:
此時根據期望值我們可以輕鬆的算出:
可以看出, 相比上一種方法,這種方法的收斂會更快些,更加逼近我們的目標值。 這個過程就是EM算法的實現過程。
5. EM工作原理
上面的投擲硬幣屬於A硬幣還是B硬幣我們稱之爲隱含參數,A硬幣和B硬幣的分佈參數我們稱之爲模型參數。
EM 算法解決這個的思路是使用啓發式的迭代方法,既然我們無法直接求出模型分佈參數,那麼我們可以先猜想隱含參數(EM算法的E步),接着基於觀察數據和猜測的隱含參數一起來極大化似然估計,求解我們的模型參數(EM算法的M步)。
由於我們之前的隱含參數是猜測的,所以此時得到的模型參數一般還不是我們想要的結果。我們基於當前得到的模型參數,繼續猜測隱含參數(EM算法的E步),然後繼續極大化似然估計,求解我們的模型參數(EM算法的M步)。
以此類推,不斷的迭代下去,直到模型分佈參數基本無變化,算法收斂,找到合適的模型參數。
畫了一個圖,感受一下:
EM聚類
EM算法在聚類的時候也是要先估計一個隱狀態,這個隱狀態也就是我們的樣本標籤。
有了樣本標籤之後,就可以將原來的無監督學習轉換爲監督學習,然後通過極大似然估計法求解出模型最優參數。
需要解釋一點的是,在整個過程中,隱狀態的估計需要用到EM算法。
硬聚類or軟聚類
k-means算法是通過距離來聚類的,因爲距離是確定的,所以就導致每個樣本只能歸爲一類,這叫做硬聚類。
而EM算法在聚類的過程中,每個樣本都有一定的概率和每個聚類有關,這叫做軟聚類。
通常,我們可以假設樣本符合高斯分佈,因爲每個高斯分佈都屬於這個模型的組成部分,要分成K個簇就相當於是K個組成部分。
這樣我們可以先初始化每個組成部分的高斯分佈的參數,然後再來看每個樣本是屬於哪個組成部分。這就是E步驟; 再通過得到的這些隱含變量結果,反過來求每個組成部分高斯分佈的參數,即 M 步驟。
反覆EM步驟,直到每個組成部分的高斯分佈參數不變爲止,這樣也就相當於將樣本按照高斯模型進行了EM聚類。
EM 算法相當於一個框架,我們可以採用不同的模型來進行聚類,比如 GMM(高斯混合模型)、 HMM(隱馬爾科夫模型)來進行聚類。
GMM通過概率密度來進行聚類,聚成的類符合高斯分佈(正態分佈)。 HMM用到了馬爾可夫過程,通過狀態轉移矩陣來計算狀態轉移的概率。
項目實戰
1. 準備工作
如何創建高斯聚類呢,我們需要先了解一下高斯聚類的參數。在sklearn 中,高斯聚類可以這樣創建:
# 創建高斯聚類模型
gmm = GaussianMixture(n_components=1, covariance_type='full', max_iter=100)
解釋一下主要的參數:
-
n_components:即高斯混合模型的個數,也就是我們要聚類的個數,默認值爲 1。
-
covariance_type: 代表協方差類型。 一個高斯混合模型的分佈是由均值向量和協方差矩陣決定的,所以協方差的類型也代表了不同的高斯混合模型的特徵。
-
max_iter: 代表最大迭代次數,EM 算法是由 E 步和 M 步迭代求得最終的模型參數,這裏可以指定最大迭代次數,默認值爲 100。
其中協方差類型covariance_type又四種取值,分別是:
-
covariance_type=full,代表完全協方差,也就是元素都不爲 0;
-
covariance_type=tied,代表相同的完全協方差;
-
covariance_type=diag,代表對角協方差,也就是對角不爲 0,其餘爲 0;
-
covariance_type=spherical,代表球面協方差,非對角爲 0,對角完全相同,呈現球面的特性。
需要注意的是,聚類的個數往往是由業務決定的,比如對用戶收入進行聚類,可以分爲:高收入羣體、中收入羣體、低收入羣體,根據用戶價值進行聚類,可以分爲:高價值用戶、中價值用戶、低價值用戶、無價值用戶等等。
當然如果你無法確定聚類的個數,可以通過設置不同的聚類個數進而選擇具有最優效果的模型。
2. 瞭解數據
本次實戰我們的數據是王者榮耀的英雄屬性數據,通過對69個英雄的22個屬性數據,其中包括英雄的最大生命、生命成長、最大發力、最高物攻等等,通過每個英雄之間的特徵,對69個英雄進行“人以羣分,物以類聚”。
感興趣的同學可以嘗試一下最終的結果能否應用於實際遊戲中。 ok,先來看看我們本次數據的整體描述:
df_ori.head(5)
再來看看各個英雄屬性的整體情況:
"""數據的EDA操作"""
"""
1.數據整體描述
"""
df.data=df_ori.copy()
df.data.drop('英雄',axis=1,inplace=True)
#次要定位存在空值
df.data.info()
一共22個英雄屬性(不包括姓名),其中次要定位存在空值,且空值較多。 再來看看數值型數據的整體分佈情況:
df_data.describe()
數據分佈沒有什麼異常,但是應該需要考慮進行標準化,這個後面再說。 最大攻速字段應該是數值型的,我們需要對其進行處理:
df_ori.head(5)
另外,次要定位屬性缺失值太多,而且沒有有效的填充方法,直接刪掉它
# 最大攻速爲百分比需要替換成數值
df_data['最大攻速'] = df_data['最大攻速'].apply(lambda str: str.replace('%', ''))
# 次要定位數據無法填充,且已存在主要定位,直接刪除該字段
df_data.drop('次要定位', axis=1, inplace=True)
3. 數據探索
一共只有69數據,但是卻有22個屬性,是否存在屬性重複的情況呢? 我們知道在建模過程中,重複的屬性對最終結果不會產生影響。 所以我們可以通過關聯度分析,看一下數據之間的關聯度情況,這種方式在前面的實戰種很多次都用到過。
可以看到,用紅框標出的,都是屬性之間相互關聯度特別大的,對於這些我們只需要保留其中的一種屬性即可。 通過篩選,我們最終確定了13個英雄屬性
"""進行特徵選擇"""
features=df_data.columns.values.tolist()
duplicates_features=['生命成長','最大法力','法力成長','物攻成長','物防成長','每5秒回血成長','最大每5秒回血成長','每5秒回藍成長']
features=features
for feature in duplicates_features:
features.remove(feature)
df_data=df_data[features]
df_data.head()
再來看英雄屬性: 攻擊範圍和主要定位,是離散型特徵,直接對其進行特徵量化
"""通過標籤編碼實現特徵量化"""
for feature in ['攻擊範圍', '主要定位']:
le = preprocessing.LabelEncoder()
le.fit(df_data[feature])
df_data[feature] = le.transform(df_data[feature])
最後就是數據的規範化,直接通過Z-Score進行數據規範
"""採用Z-Score規範化數據,保證每個特徵維度的數據均值爲0,方差爲1"""
stas = StandardScaler()
df_data = stas.fit_transform(df_data)
4. 建模
選用我們前面提到的GMM進行建模
# 構造GMM聚類
gmm = GaussianMixture(n_components=30, covariance_type='full')
gmm.fit(df_data)
# 訓練數據
prediction = gmm.predict(df_data)
最終的模型聚類結果是這樣的:
#將分組結果輸出到CSV文件中
df_ori.insert(0,'分組',prediction)
df_ori.sort_values('分組').head(15)
5. 總結
上面的圖中放了前20的英雄,組號相同的英雄表示屬性相近,感興趣的同學不妨在遊戲中試試?
另外,聚類算法屬於無監督的學習方式,我們並沒有實際的結果可以進行對比來區別模型的準確率。 這裏我們試着用輪廓係數進行模型的評分。
"""根據輪廓係數計算模型得分"""
from sklearn.metrics import silhouette_score
score=silhouette_score(df_data,prediction,metric='euclidean')
score
最後得分0.246,也不是很高,說明聚類的效果不是特別好,應該還是英雄屬性的原因,例如,通過主要定位就可以對英雄就行聚類,或者通過攻擊範圍進行聚類,但是這兩個屬性和其他屬性的結合,有時候並非是最好的,對遊戲理解比較深刻的同學可以考慮一下優化方法。
數據集及代碼在後臺回覆 王者榮耀 獲取
“爲沉迷學習 點贊 ↓