網誌搬家了 I moved to github!

我的網誌移到 github 上囉! 以後的新文章都會發佈在 https://yenhsunlin.github.io/

留言

張貼留言

這個網誌中的熱門文章

IA9a - K-means分群與EM算法: 理論

圖片
市場內分門別類的產品 原則上 K-means分群 是 EM算法 (expectation-maximization algorithm) 的一個特例，相較於EM從似然函數 (likelihood) 的方式出發並導出不同資料點對不同群 (或稱聚類、簇，cluster) 的貢獻度，K-means單純用歐氏距離來分類，雖然這加快了K-means算法的計算效率，但顯然的這麼naïve的方法會產生明顯的缺陷。但仍讓我們會先從簡單的K-means開始，並探討K-means算法的結果在某些情況下和人類肉眼辨識的結論會產生明顯的歧義，接著再推進到通用的EM算法，除了 python 的demo外，我也會證明在數學上如何從EM得到K-means的極限 (僅限高斯混合的情況)，而在這個part內，讓我們先從數學理論的角度來面。 一、K-means分群 今天如果我有一大坨資料共120個點如圖1所示，從資料的散佈趨勢來看，很明顯的分成兩群，那我們是不是可以有一個演算法來自動化將資料點如同我們臆測的一樣分成兩袋？一個最簡單的發法便是使用K-means分群，而這個大寫K表示群的數量，以圖1而言，我們猜測K=2，所以是個2-means分群問題。 圖1. 資料散佈圖 (普魯士藍) 與初始化的紅綠兩點 　所以為了達成分群，我們需要先初始化兩個點，這兩個點代表兩群的中心。事實上，初始化的位置不必要一定剛好在兩群的中心，可以是任意挑選的地方，但為了計算方便，我們會將起始化的兩點開始在靠近資料點的平均值附近，如同圖1中紅綠兩點。我們將這兩個初始化的點叫作pk其中k=1,2表示第k群。另外將資料點的集合用D={d1,d2⋯dn⋯d120}表示，所以我們計算每個點dn=(xdn,ydn)和pk=(xpk,ypk)的歐氏距離 ℓn,k=√(xdn−xpk)2+(ydn−ypk)2. 若該點和p1的距離小於和p2的距離 (ℓn,1<ℓn,2)，則我們說dn比較靠近p1且應該...
閱讀完整內容

IA9b - K-means分群與EM算法: 實作

圖片
這一篇文章延續了上一篇IA9a的內容，但側重在 python 的實作，所以所有的節數、圖案以及公式編號都會依照IA9a的編號接序下來，所以重複的內容就直接引用，不在這裡重新贅述。 四、實作EM 4.1 高斯混合分佈 讓我們從1.1節的協方差矩陣開始，生成的圖形就如圖4 (腳本內加了seed random方便我們每次追蹤)，另外也看到了執行5次K-means算法後 (再多次也不會變了) 得到的分群結果如圖5，這顯然與我們的預期有極大的落差！ 　但我們將按照3.3結給出EM算法的偽代碼，假設資料群是高斯混合分佈的形式，重新執行一遍分群，我們將看到EM算法能很好的分出我們預期的兩群的結果。我們預計會有兩群，所以k=1,2，且第一步需要初始化參數組θ={μk,Σk,πk}。初始化的過程是給定一個起始點，原則上隨機選擇的方式是合理的，不過為了計算上方便，可以讓初始的協方差矩陣都為單位矩陣，πk則為每個群均分 (這裡就是每個都是0.5)，如下代碼 # Initializing parameters sigma1,sigma2 = np.eye(2),np.eye(2) pi1 = 0.5 pi2 = 1-pi1 N = len(cluster) 完成初始的參數選擇後，我們用偽代碼的第二步，也就是E-step計算置信度γ(znk)。這裡我將Eq. (10)列出來方便解說 γ(znk)=πkN(x|μk,Σk)∑2k=1πkN(x|μk,Σk). 因為我們是假設兩群都是高斯分佈，所以對第一個群而言的分子就是 # Starting E-step: Calculating responsibilities # Numerator for k=1 k1 = pi1*multivariate_normal.pdf(cluster,p1,sigma1) 直接透過 python 腳本我們很容易理解了分子的意義便是計算每個資料點分別對應到\(\{...
閱讀完整內容

PS2 — 因果本無心，天機皆可洩: 統計!

圖片
Fortuna (1754), Tadeusz Kuntze 世間多少荒唐事，何獨神仙有是哉 一、眾言落花本有意 每周接到騷擾電話的次數、補教名師表示今年指考物理科非常的簡單，可我怎麼都不會寫！我在台灣算是低收入戶嗎？股票投資會賺錢嗎？醫療險推銷員說台灣人一生花在在醫療上的經費平均超過300萬，早買賺愈多、半(扮)仙老師鐵口直斷年過40接下來會遭婦女病纏身……等等。 　生活中總充滿著無盡的變數與不確定性，正是這種混沌的狀態，另我們感到迷惘，甚至很怕遭逢意外人生便從此跌入谷底萬劫不復。甚至當大家說發生的機率很低時卻發生在我身上，這是因為我太幸運還是因為業障積太多，就跟老婆子的陳年宿便一樣令人擔憂。所以在傻傻的以為有買有保庇時，其實簽的都是滿紙荒唐言，一把辛酸淚；都云買家癡，誰解其中味？~笑！ 二、是偶然還是注定？統計分布 (statistical distribution) 在討論到底這件事會不會發生的問題時，問題本身看似單一，但不同時刻同個問題可能有不同的發生機率，這就是事件對時間的分布。尤有甚者，同個問題還可以劃分出不同的子事件Ai，其中A1好發於年輕族群、A2則在壯年、A3較易於發生在男人生上……這也是分布，而且是更複雜，含有更多維度(multi-dimensional)資訊的分布(我知道你在想什麼，但絕對不是像星際效應那種蟲洞黑洞的時空維度XD)。我們接著來看看這些看似隨機而且雜亂的事件，其中到底蘊含了什麼奧妙？又該怎麼看待發生在每個人身上的機率這件事？ 1. 關於事件分布的二三事 在開始討論統計分布以前，我們先來預備一些基本知識。首先對真實世界而言，母體(沒有人在演駭客任務!)的事件數是非常大量，或者可以說趨近於無限大(∞)，基本上我們不可能有時間與人力去普查一個無限大量的事件，所以我們會對母體做採樣(sampling)，採集出來的結果就稱作樣本(sample)，如果採集的過程是隨機的，那麼這一組樣本資料則可視為是隨機變量(random variables)。 圖1.  房間粒子溫度採樣，非按照比例繪製 　直接看圖1會比較好理解，假設一個房間內有大量的粒子，每個粒子有不同的溫度Ti，我們不可能把每個粒子都抓...
閱讀完整內容