欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

好久沒(méi)有寫(xiě) blog 了，一來(lái)是 blog 下線(xiàn)一段時(shí)間，而租 DreamHost 的事情又一直沒(méi)弄好；二來(lái)是沒(méi)有太多時(shí)間，天天都跑去實(shí)驗室?，F在主要折騰 Machine Learning 相關(guān)的東西，因為很多東西都不懂，所以平時(shí)也找一些資料來(lái)看。按照我以前的更新速度的話(huà)，這么長(cháng)時(shí)間不寫(xiě) blog 肯定是要被悶壞的，所以我也覺(jué)得還是不定期地整理一下自己了解到的東西，放在 blog 上，一來(lái)梳理總是有助于加深理解的，二來(lái)也算共享一下知識了。那么，還是從 clustering 說(shuō)起吧。

Clustering 中文翻譯作“聚類(lèi)”，簡(jiǎn)單地說(shuō)就是把相似的東西分到一組，同 Classification (分類(lèi))不同，對于一個(gè) classifier ，通常需要你告訴它“這個(gè)東西被分為某某類(lèi)”這樣一些例子，理想情況下，一個(gè) classifier 會(huì )從它得到的訓練集中進(jìn)行“學(xué)習”，從而具備對未知數據進(jìn)行分類(lèi)的能力，這種提供訓練數據的過(guò)程通常叫做 supervised learning (監督學(xué)習)，而在聚類(lèi)的時(shí)候，我們并不關(guān)心某一類(lèi)是什么，我們需要實(shí)現的目標只是把相似的東西聚到一起，因此，一個(gè)聚類(lèi)算法通常只需要知道如何計算相似 度就可以開(kāi)始工作了，因此 clustering 通常并不需要使用訓練數據進(jìn)行學(xué)習，這在 Machine Learning 中被稱(chēng)作 unsupervised learning (無(wú)監督學(xué)習)。

舉一個(gè)簡(jiǎn)單的例子：現在有一群小學(xué)生，你要把他們分成幾組，讓組內的成員之間盡量相似一些，而組之間則差別大一些。最后分出怎樣的結果，就取決于你對于“相似”的定義了，比如，你決定男生和男生是相似的，女生和女生也是相似的，而男生和女生之間則差別很大”，這樣，你實(shí)際上是用一個(gè)可能取兩個(gè)值“男”和“女”的離散變量來(lái)代表了原來(lái)的一個(gè)小學(xué)生，我們通常把這樣的變量叫做“特征”。實(shí)際上，在這種情況下，所有的小學(xué)生都被映射到了兩個(gè)點(diǎn)的其中一個(gè)上，已經(jīng)很自然地形成了兩個(gè)組，不需要專(zhuān)門(mén)再做聚類(lèi)了。另一種可能是使用“身高”這個(gè)特征。我在讀小學(xué)候，每周五在操場(chǎng)開(kāi)會(huì )訓話(huà)的時(shí)候會(huì )按照大家住的地方的地域和距離遠近來(lái)列隊，這樣結束之后就可以結隊回家了。除了讓事物映射到一個(gè)單獨的特征之外，一種常見(jiàn)的做法是同時(shí)提取 N 種特征，將它們放在一起組成一個(gè) N 維向量，從而得到一個(gè)從原始數據集合到 N 維向量空間的映射——你總是需要顯式地或者隱式地完成這樣一個(gè)過(guò)程，因為許多機器學(xué)習的算法都需要工作在一個(gè)向量空間中。

那么讓我們再回到 clustering 的問(wèn)題上，暫且拋開(kāi)原始數據是什么形式，假設我們已經(jīng)將其映射到了一個(gè)歐幾里德空間上，為了方便展示，就使用二維空間吧，如下圖所示：

從數據點(diǎn)的大致形狀可以看出它們大致聚為三個(gè) cluster ，其中兩個(gè)緊湊一些，剩下那個(gè)松散一些。我們的目的是為這些數據分組，以便能區分出屬于不同的簇的數據，如果按照分組給它們標上不同的顏色，就是這個(gè)樣子：

那么計算機要如何來(lái)完成這個(gè)任務(wù)呢？當然，計算機還沒(méi)有高級到能夠“通過(guò)形狀大致看出來(lái)”，不過(guò)，對于這樣的 N 維歐氏空間中的點(diǎn)進(jìn)行聚類(lèi)，有一個(gè)非常簡(jiǎn)單的經(jīng)典算法，也就是本文標題中提到的 k-means 。在介紹 k-means 的具體步驟之前，讓我們先來(lái)看看它對于需要進(jìn)行聚類(lèi)的數據的一個(gè)基本假設吧：對于每一個(gè) cluster ，我們可以選出一個(gè)中心點(diǎn) (center) ，使得該 cluster 中的所有的點(diǎn)到該中心點(diǎn)的距離小于到其他 cluster 的中心的距離。雖然實(shí)際情況中得到的數據并不能保證總是滿(mǎn)足這樣的約束，但這通常已經(jīng)是我們所能達到的最好的結果，而那些誤差通常是固有存在的或者問(wèn)題本身的不可分性造成的。例如下圖所示的兩個(gè)高斯分布，從兩個(gè)分布中隨機地抽取一些數據點(diǎn)出來(lái)，混雜到一起，現在要讓你將這些混雜在一起的數據點(diǎn)按照它們被生成的那個(gè)分布分開(kāi)來(lái)：

由于這兩個(gè)分布本身有很大一部分重疊在一起了，例如，對于數據點(diǎn) 2.5 來(lái)說(shuō)，它由兩個(gè)分布產(chǎn)生的概率都是相等的，你所做的只能是一個(gè)猜測；稍微好一點(diǎn)的情況是 2 ，通常我們會(huì )將它歸類(lèi)為左邊的那個(gè)分布，因為概率大一些，然而此時(shí)它由右邊的分布生成的概率仍然是比較大的，我們仍然有不小的幾率會(huì )猜錯。而整個(gè)陰影部分是我們所能達到的最小的猜錯的概率，這來(lái)自于問(wèn)題本身的不可分性，無(wú)法避免。因此，我們將 k-means 所依賴(lài)的這個(gè)假設看作是合理的。

基于這樣一個(gè)假設，我們再來(lái)導出 k-means 所要優(yōu)化的目標函數：設我們一共有 N 個(gè)數據點(diǎn)需要分為 K 個(gè) cluster ，k-means 要做的就是最小化

這個(gè)函數，其中

亦即

下面我們來(lái)總結一下 k-means 算法的具體步驟：

1. 選定 K 個(gè)中心
   
   的初值。這個(gè)過(guò)程通常是針對具體的問(wèn)題有一些啟發(fā)式的選取方法，或者大多數情況下采用隨機選取的辦法。因為前面說(shuō)過(guò) k-means 并不能保證全局最優(yōu)，而是否能收斂到全局最優(yōu)解其實(shí)和初值的選取有很大的關(guān)系，所以有時(shí)候我們會(huì )多次選取初值跑 k-means ，并取其中最好的一次結果。
2. 將每個(gè)數據點(diǎn)歸類(lèi)到離它最近的那個(gè)中心點(diǎn)所代表的 cluster 中。
3. 用公式
   
   計算出每個(gè) cluster 的新的中心點(diǎn)。
4. 重復第二步，一直到迭代了最大的步數或者前后的
   
   的值相差小于一個(gè)閾值為止。

按照這個(gè)步驟寫(xiě)一個(gè) k-means 實(shí)現其實(shí)相當容易了，在 SciPy 或者 Matlab 中都已經(jīng)包含了內置的 k-means 實(shí)現，不過(guò)為了看看 k-means 每次迭代的具體效果，我們不妨自己來(lái)實(shí)現一下，代碼如下（需要安裝 SciPy 和 matplotlib） ：

1            2            3            4            5            6            7            8            9            10            11            12            13            14            15            16            17            18            19            20            21            22            23            24            25            26            27            28            29            30            31            32            33            34            35            36            37            38            39            40            41            42            43            44            45            46            47            48            49            50            51            52            53            54            55            56            57            58            59            60            61            62            63            64            65            66            67            68            69            70            71            72            73            74            75            76            77            78            79            80            81            82            83            84            85            86            87            88            89            90            91            

#!/usr/bin/python                         from __future__ import with_statement            import cPickle as pickle            from matplotlib import pyplot            from numpy import zeros, array, tile            from scipy.linalg import norm            import numpy.matlib as ml            import random                         def kmeans(X, k, observer=None, threshold=1e-15, maxiter=300):            N = len(X)            labels = zeros(N, dtype=int)            centers = array(random.sample(X, k))            iter = 0                         def calc_J():            sum = 0            for i in xrange(N):            sum += norm(X[i]-centers[labels[i]])            return sum                         def distmat(X, Y):            n = len(X)            m = len(Y)            xx = ml.sum(X*X, axis=1)            yy = ml.sum(Y*Y, axis=1)            xy = ml.dot(X, Y.T)                         return tile(xx, (m, 1)).T+tile(yy, (n, 1)) - 2*xy                         Jprev = calc_J()            while True:            # notify the observer            if observer is not None:            observer(iter, labels, centers)                         # calculate distance from x to each center            # distance_matrix is only available in scipy newer than 0.7            # dist = distance_matrix(X, centers)            dist = distmat(X, centers)            # assign x to nearst center            labels = dist.argmin(axis=1)            # re-calculate each center            for j in range(k):            idx_j = (labels == j).nonzero()            centers[j] = X[idx_j].mean(axis=0)                         J = calc_J()            iter += 1                         if Jprev-J < threshold:            break            Jprev = J            if iter >= maxiter:            break                         # final notification            if observer is not None:            observer(iter, labels, centers)                         if __name__ == '__main__':            # load previously generated points            with open('cluster.pkl') as inf:            samples = pickle.load(inf)            N = 0            for smp in samples:            N += len(smp[0])            X = zeros((N, 2))            idxfrm = 0            for i in range(len(samples)):            idxto = idxfrm + len(samples[i][0])            X[idxfrm:idxto, 0] = samples[i][0]            X[idxfrm:idxto, 1] = samples[i][1]            idxfrm = idxto                         def observer(iter, labels, centers):            print "iter %d." % iter            colors = array([[1, 0, 0], [0, 1, 0], [0, 0, 1]])            pyplot.plot(hold=False)  # clear previous plot            pyplot.hold(True)                         # draw points            data_colors=[colors[lbl] for lbl in labels]            pyplot.scatter(X[:, 0], X[:, 1], c=data_colors, alpha=0.5)            # draw centers            pyplot.scatter(centers[:, 0], centers[:, 1], s=200, c=colors)                         pyplot.savefig('kmeans/iter_%02d.png' % iter, format='png')                         kmeans(X, 3, observer=observer)

代碼有些長(cháng)，不過(guò)因為用 Python 來(lái)做這個(gè)事情確實(shí)不如 Matlab 方便，實(shí)際的 k-means 的代碼只是 41 到 47 行。首先 3 個(gè)中心點(diǎn)被隨機初始化，所有的數據點(diǎn)都還沒(méi)有進(jìn)行聚類(lèi)，默認全部都標記為紅色，如下圖所示：

然后進(jìn)入第一次迭代：按照初始的中心點(diǎn)位置為每個(gè)數據點(diǎn)著(zhù)上顏色，這是代碼中第 41 到 43 行所做的工作，然后 45 到 47 行重新計算 3 個(gè)中心點(diǎn)，結果如下圖所示：

可以看到，由于初始的中心點(diǎn)是隨機選的，這樣得出來(lái)的結果并不是很好，接下來(lái)是下一次迭代的結果：

可以看到大致形狀已經(jīng)出來(lái)了。再經(jīng)過(guò)兩次迭代之后，基本上就收斂了，最終結果如下：

不過(guò)正如前面所說(shuō)的那樣 k-means 也并不是萬(wàn)能的，雖然許多時(shí)候都能收斂到一個(gè)比較好的結果，但是也有運氣不好的時(shí)候會(huì )收斂到一個(gè)讓人不滿(mǎn)意的局部最優(yōu)解，例如選用下面這幾個(gè)初始中心點(diǎn)：

最終會(huì )收斂到這樣的結果：

不得不承認這并不是很好的結果。不過(guò)其實(shí)大多數情況下 k-means 給出的結果都還是很令人滿(mǎn)意的，算是一種簡(jiǎn)單高效應用廣泛的 clustering 方法。

Filed under:
Machine Learning by pluskid