1. 機(jī)器學(xué)習(xí)常用損失函數(shù)

評(píng)價(jià)模型預(yù)測(cè)值和真實(shí)值的函數(shù)為損失函數(shù)（loss function）。它是一個(gè)非負(fù)實(shí)值函數(shù)，損失函數(shù)越小，模型的性能就越好。

損失函數(shù)

模型最終需要優(yōu)化函數(shù)的是代價(jià)函數(shù)（cost function）或者說(shuō)目標(biāo)函數(shù)，需要在損失函數(shù)的基礎(chǔ)上做一些調(diào)整，例如正則化。

代價(jià)函數(shù)

下面主要列出幾種常見(jiàn)的損失函數(shù)。

1.1. log對(duì)數(shù)損失函數(shù)（邏輯回歸損失，交叉熵?fù)p失）

有些人可能覺(jué)得邏輯回歸的損失函數(shù)就是平方損失，其實(shí)并不是。平方損失函數(shù)可以通過(guò)線性回歸在假設(shè)樣本是高斯分布的條件下推導(dǎo)得到，而邏輯回歸得到的并不是平方損失。在邏輯回歸的推導(dǎo)中，它假設(shè)樣本服從伯努利分布（0-1分布），然后求得滿足該分布的似然函數(shù)，接著取對(duì)數(shù)求極值等等。而邏輯回歸并沒(méi)有求似然函數(shù)的極值，而是把極大化當(dāng)做是一種思想，進(jìn)而推導(dǎo)出它的經(jīng)驗(yàn)風(fēng)險(xiǎn)函數(shù)為：最小化負(fù)的似然函數(shù)（即max F(y, f(x)) —> min -F(y, f(x)))。從損失函數(shù)的視角來(lái)看，它就成了log損失函數(shù)了。
log損失函數(shù)的標(biāo)準(zhǔn)形式：

剛剛說(shuō)到，取對(duì)數(shù)是為了方便計(jì)算極大似然估計(jì)，因?yàn)樵贛LE中，直接求導(dǎo)比較困難，所以通常都是先取對(duì)數(shù)再求導(dǎo)找極值點(diǎn)。損失函數(shù)L(Y, P(Y|X))表達(dá)的是樣本X在分類(lèi)Y的情況下，使概率P(Y|X)達(dá)到最大值（換言之，就是利用已知的樣本分布，找到最有可能（即最大概率）導(dǎo)致這種分布的參數(shù)值；或者說(shuō)什么樣的參數(shù)才能使我們觀測(cè)到目前這組數(shù)據(jù)的概率最大）。因?yàn)閘og函數(shù)是單調(diào)遞增的，所以logP(Y|X)也會(huì)達(dá)到最大值，因此在前面加上負(fù)號(hào)之后，最大化P(Y|X)就等價(jià)于最小化L了。
邏輯回歸的P(Y=y|x)表達(dá)式如下（為了將類(lèi)別標(biāo)簽y統(tǒng)一為1和0，下面將表達(dá)式分開(kāi)表示）

將它帶入到上式，通過(guò)推導(dǎo)可以得到logistic的損失函數(shù)表達(dá)式，如下：

邏輯回歸最后得到的目標(biāo)式子如下：

1.2. 平方損失函數(shù)（最小二乘法, Ordinary Least Squares ）

最小二乘法是線性回歸的一種，OLS將問(wèn)題轉(zhuǎn)化成了一個(gè)凸優(yōu)化問(wèn)題。在線性回歸中，它假設(shè)樣本和噪聲都服從高斯分布（為什么假設(shè)成高斯分布呢？其實(shí)這里隱藏了一個(gè)小知識(shí)點(diǎn)，就是中心極限定理，可以參考【central limit theorem】），最后通過(guò)極大似然估計(jì)（MLE）可以推導(dǎo)出最小二乘式子。最小二乘的基本原則是：最優(yōu)擬合直線應(yīng)該是使各點(diǎn)到回歸直線的距離和最小的直線，即平方和最小。換言之，OLS是基于距離的，而這個(gè)距離就是我們用的最多的歐幾里得距離。為什么它會(huì)選擇使用歐式距離作為誤差度量呢（即Mean squared error， MSE），主要有以下幾個(gè)原因：

簡(jiǎn)單，計(jì)算方便；
歐氏距離是一種很好的相似性度量標(biāo)準(zhǔn)；
在不同的表示域變換后特征性質(zhì)不變。
平方損失（Square loss）的標(biāo)準(zhǔn)形式如下：

當(dāng)樣本個(gè)數(shù)為n時(shí)，此時(shí)的損失函數(shù)變?yōu)椋?/p>

而在實(shí)際應(yīng)用中，通常會(huì)使用均方差（MSE）作為一項(xiàng)衡量指標(biāo)，公式如下：

上面提到了線性回歸，這里額外補(bǔ)充一句，我們通常說(shuō)的線性有兩種情況，一種是因變量y是自變量x的線性函數(shù)，一種是因變量y是參數(shù)α的線性函數(shù)。在機(jī)器學(xué)習(xí)中，通常指的都是后一種情況。

1.3.指數(shù)損失函數(shù)（Adaboost）

學(xué)過(guò)Adaboost算法的人都知道，它是前向分步加法算法的特例，是一個(gè)加和模型，損失函數(shù)就是指數(shù)函數(shù)。在Adaboost中，經(jīng)過(guò)m此迭代之后，可以得到fm(x):

Adaboost每次迭代時(shí)的目的是為了找到最小化下列式子時(shí)的參數(shù)α 和G：

可以看出，Adaboost的目標(biāo)式子就是指數(shù)損失，在給定n個(gè)樣本的情況下，Adaboost的損失函數(shù)為：

1.4.Hinge損失函數(shù)（SVM）

在機(jī)器學(xué)習(xí)算法中，hinge損失函數(shù)和SVM是息息相關(guān)的。在線性支持向量機(jī)中，最優(yōu)化問(wèn)題可以等價(jià)于下列式子：

下面來(lái)對(duì)式子做個(gè)變形，令：

如若取λ=1/2C，式子就可以表示成：

1.5. 其它損失函數(shù)

除了以上這幾種損失函數(shù)，常用的還有：

0-1損失函數(shù)

絕對(duì)值損失函數(shù)

Python
先記錄一下python中數(shù)據(jù)結(jié)構(gòu)字典的排序方法。
字典以鍵或值排序：

>>> dict1={"Beijing":2, "Shanghai":3, "Guangzhou":1}  
>>> sorted(dict1.items(), key=lambda A:A[0])   
#在python2.7中第一個(gè)參數(shù)需要改為dict1.iteritems()
[('Beijing', 2), ('Guangzhou', 1), ('Shanghai', 3)]  
>>> sorted(dict1.items(), key=lambda A:A[1])  
[('Guangzhou', 1), ('Beijing', 2), ('Shanghai', 3)] 

如果要以從大到小進(jìn)行排序，只需要加上reverse=True參數(shù)即可。
>>> sorted(dict1.items(), key=lambda A:A[0], reverse=True)  
[('Shanghai', 3), ('Guangzhou', 1), ('Beijing', 2)]  
>>> sorted(dict1.items(), key=lambda A:A[1], reverse=True)  
[('Shanghai', 3), ('Beijing', 2), ('Guangzhou', 1)]  

注意：sorted()的第一個(gè)參數(shù)為iterable。因?yàn)樽值浔旧聿⒉皇莍terable的，需要利用items()函數(shù)將字典轉(zhuǎn)換為可迭代的。

冒泡排序

#89,45,68,90,29,34,17
#倒序排列
list1 = [89,45,68,90,29,34,17]
for i in range(len(list1)):
    for j in range(len(list1)-1-i):
        if list1[j + 1] < list1[j]:
            list1[j],list1[j + 1] = list1[j + 1],list1[j]

#正序排列
def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists

插入排序

描述：
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。
插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置），而第二部分就只包含這一個(gè)元素（即待插入元素）。在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。

list1 = [89,45,68,90,29,34,17]
for i in range(1, len(list1)):
    key = list1[i]
    j = i - 1
    while j >= 0:
        if list1[j] > key:
            list1[j + 1] = list1[j]
            list1[j] = key
        j = j - 1
print (list1)
    

#算法課本P104頁(yè)例子
#key的左邊都是排好的，插入排序就是把key插入到左邊排好的序列中去
#因?yàn)樽筮呉呀?jīng)排好了，所以如果比最后一個(gè)元素大就只需要和最后一個(gè)元素比就行
#否則key向前移動(dòng)，直到比較完前面所有的值
#一個(gè)key插入完以后，key自增，直到右邊沒(méi)有元素為止
def Insert_sort(list1):
    count = len(list1)
    for i in range(1,count): #假設(shè)第一個(gè)數(shù)是排序好的
        key = list1[i] #取出當(dāng)前未排序的數(shù)
        j = i - 1 #從后往前，先取未排序數(shù)的前一個(gè)數(shù)（已經(jīng)排序好的數(shù)）
        while j >= 0 and list1[j] > key:#若當(dāng)前未排序的數(shù)比排序好的數(shù)還小，并沒(méi)有到數(shù)組的開(kāi)頭。
            list1[j+1] = list1[j] #排序好的數(shù)往后挪一個(gè)位置
            j = j - 1 #去排序好的數(shù)的前一個(gè)數(shù)進(jìn)行比較
        list1[j+1] = key #插入當(dāng)前要排序的數(shù)
    return list1

希爾排序

希爾排序(Shell Sort)是插入排序的一種。
也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因DL．Shell于1959年提出而得名。 同時(shí)該算法是沖破O(n^2）的第一批算法之一。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；推薦的增量是 length/2,雖然他不一定是最好的。
隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

list1 = [89,45,68,90,29,34,17]
count = len(list1)
step = 2
group = count // step
while group > 0:
    for i in range(0, group):
        j = i + group
        while j < count:
            k = j - group
            key = list1[j]
            while k >= 0:
                if list1[k] > key:
                    list1[k + group] = list1[k]
                    list1[k] = key
                k -= group
            j += group
    group =  group // step
print (list1)




#python2中/代表整除，python3中//代表整除，/代表小數(shù)除
#list1 = [89,45,68,90,29,34,17]
def shell_sort(lists):
    # 希爾排序
    count = len(lists)
    step = 2
    group = count // step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = lists[j]
                while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group =  group // step
    return lists

選擇排序

描述：
基本思想：第1次比較，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2次比較，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類(lèi)推，第i次在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長(zhǎng)直到全部排序完畢，對(duì)初始排列不敏感，無(wú)論怎樣都要比較n-1次。

list1 = [89,45,68,90,29,34,17]
count = len(list1)
for i in range(count):
    min = i
    for j in range(i + 1, count):
        if list1[min] > list1[j]:
            min == j
    list1[min],list1[j] = list1[j],list1[min]
print (list1)   

def select_sort(lists):
    # 選擇排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists 

堆排序

一個(gè)完全二叉樹(shù)大根堆需要滿足：

i 為下標(biāo)，n為元素個(gè)數(shù)，i是從1開(kāi)始的，0位置需要使用占位符

流程：

1.首先構(gòu)造堆
2.取出這個(gè)大根堆的堆頂節(jié)點(diǎn)(最大值)，與堆的最下最右的元素進(jìn)行交換，然后把剩下的元素再構(gòu)造一個(gè)大根堆
3.重復(fù)第二步，直到這個(gè)大根堆的長(zhǎng)度為1，此時(shí)完成排序。

#占位符比較麻煩，直接使用python中的鏈表結(jié)構(gòu)
from collections import deque

def swap_param(L, i, j):
    L[i], L[j] = L[j], L[i]
    return L

def heap_adjust(L, start, end):
    temp = L[start]

    i = start
    j = 2 * i

    while j <= end:
        if (j < end) and (L[j] < L[j + 1]):
            j += 1
        if temp < L[j]:
            L[i] = L[j]
            i = j
            j = 2 * i
        else:
            break
    L[i] = temp

def heap_sort(L):
    L_length = len(L) - 1

    first_sort_count = L_length // 2
    for i in range(first_sort_count):
        heap_adjust(L, first_sort_count - i, L_length)

    for i in range(L_length - 1):
        L = swap_param(L, 1, L_length - i)
        heap_adjust(L, 1, L_length - i - 1)

    return [L[i] for i in range(1, len(L))]

def main():
    L = deque([50, 16, 30, 10, 60,  90,  2, 80, 70])
    L.appendleft(0)
    print (heap_sort(L))

if __name__ == '__main__':
    main()

描述:
堆排序(Heapsort)是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹(shù)。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。

遞歸構(gòu)造堆，偽代碼：
MAX-HEAPIFY(A, i)
1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4 then largest ← l
5 else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest ← r
8 if largest ≠ i
9 then exchange A[i] <-> A[largest]
10 MAX-HEAPIFY(A, largest)

快速排序

一趟快速排序的算法是：

1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；

2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；

3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換；

4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換；

5）重復(fù)第3、4步，直到i=j； (3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。

算法導(dǎo)論中的版本

def quick_sort(array, l, r):  
    if l < r:  
        q = partition(array, l, r)  
        quick_sort(array, l, q - 1)  
        quick_sort(array, q + 1, r)  

def partition(array, l, r):  
    x = array[r]  
    i = l - 1  
    for j in range(l, r):  
        if array[j] <= x:  
            i += 1  
            array[i], array[j] = array[j], array[i]  
    array[i + 1], array[r] = array[r], array[i+1]  
    return i + 1