1. 机器学习常用损失函数

评价模型预测值和真实值的函数为损失函数（loss function）。它是一个非负实值函数，损失函数越小，模型的性能就越好。

损失函数

模型最终需要优化函数的是代价函数（cost function）或者说目标函数，需要在损失函数的基础上做一些调整，例如正则化。

代价函数

下面主要列出几种常见的损失函数。

1.1. log对数损失函数（逻辑回归损失，交叉熵损失）

有些人可能觉得逻辑回归的损失函数就是平方损失，其实并不是。平方损失函数可以通过线性回归在假设样本是高斯分布的条件下推导得到，而逻辑回归得到的并不是平方损失。在逻辑回归的推导中，它假设样本服从伯努利分布（0-1分布），然后求得满足该分布的似然函数，接着取对数求极值等等。而逻辑回归并没有求似然函数的极值，而是把极大化当做是一种思想，进而推导出它的经验风险函数为：最小化负的似然函数（即max F(y, f(x)) —> min -F(y, f(x)))。从损失函数的视角来看，它就成了log损失函数了。
log损失函数的标准形式：

刚刚说到，取对数是为了方便计算极大似然估计，因为在MLE中，直接求导比较困难，所以通常都是先取对数再求导找极值点。损失函数L(Y, P(Y|X))表达的是样本X在分类Y的情况下，使概率P(Y|X)达到最大值（换言之，就是利用已知的样本分布，找到最有可能（即最大概率）导致这种分布的参数值；或者说什么样的参数才能使我们观测到目前这组数据的概率最大）。因为log函数是单调递增的，所以logP(Y|X)也会达到最大值，因此在前面加上负号之后，最大化P(Y|X)就等价于最小化L了。
逻辑回归的P(Y=y|x)表达式如下（为了将类别标签y统一为1和0，下面将表达式分开表示）

将它带入到上式，通过推导可以得到logistic的损失函数表达式，如下：

逻辑回归最后得到的目标式子如下：

上面是针对二分类而言的。这里需要解释一下：之所以有人认为逻辑回归是平方损失，是因为在使用梯度下降来求最优解的时候，它的迭代式子与平方损失求导后的式子非常相似，从而给人一种直观上的错觉。

1.2. 平方损失函数（最小二乘法, Ordinary Least Squares ）

最小二乘法是线性回归的一种，OLS将问题转化成了一个凸优化问题。在线性回归中，它假设样本和噪声都服从高斯分布（为什么假设成高斯分布呢？其实这里隐藏了一个小知识点，就是中心极限定理，可以参考【central limit theorem】），最后通过极大似然估计（MLE）可以推导出最小二乘式子。最小二乘的基本原则是：最优拟合直线应该是使各点到回归直线的距离和最小的直线，即平方和最小。换言之，OLS是基于距离的，而这个距离就是我们用的最多的欧几里得距离。为什么它会选择使用欧式距离作为误差度量呢（即Mean squared error， MSE），主要有以下几个原因：

简单，计算方便；
欧氏距离是一种很好的相似性度量标准；
在不同的表示域变换后特征性质不变。
平方损失（Square loss）的标准形式如下：

当样本个数为n时，此时的损失函数变为：

Y-f(X)表示的是残差，整个式子表示的是残差的平方和，而我们的目的就是最小化这个目标函数值（注：该式子未加入正则项），也就是最小化残差的平方和（residual sum of squares，RSS）。

而在实际应用中，通常会使用均方差（MSE）作为一项衡量指标，公式如下：

上面提到了线性回归，这里额外补充一句，我们通常说的线性有两种情况，一种是因变量y是自变量x的线性函数，一种是因变量y是参数α的线性函数。在机器学习中，通常指的都是后一种情况。

1.3.指数损失函数（Adaboost）

学过Adaboost算法的人都知道，它是前向分步加法算法的特例，是一个加和模型，损失函数就是指数函数。在Adaboost中，经过m此迭代之后，可以得到fm(x):

Adaboost每次迭代时的目的是为了找到最小化下列式子时的参数α 和G：

而指数损失函数(exp-loss）的标准形式如下

可以看出，Adaboost的目标式子就是指数损失，在给定n个样本的情况下，Adaboost的损失函数为：

1.4.Hinge损失函数（SVM）

在机器学习算法中，hinge损失函数和SVM是息息相关的。在线性支持向量机中，最优化问题可以等价于下列式子：

下面来对式子做个变形，令：

于是，原式就变成了：

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

可以看出，该式子与下式非常相似：

前半部分中的l就是hinge损失函数，而后面相当于L2正则项。
Hinge 损失函数的标准形式

可以看出，当|y|>=1时，L(y)=0。

1.5. 其它损失函数

除了以上这几种损失函数，常用的还有：

0-1损失函数

绝对值损失函数

---

Python
先记录一下python中数据结构字典的排序方法。
字典以键或值排序：

>>> dict1={"Beijing":2, "Shanghai":3, "Guangzhou":1}  
>>> sorted(dict1.items(), key=lambda A:A[0])   
#在python2.7中第一个参数需要改为dict1.iteritems()
[('Beijing', 2), ('Guangzhou', 1), ('Shanghai', 3)]  
>>> sorted(dict1.items(), key=lambda A:A[1])  
[('Guangzhou', 1), ('Beijing', 2), ('Shanghai', 3)] 

如果要以从大到小进行排序，只需要加上reverse=True参数即可。
>>> 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()的第一个参数为iterable。因为字典本身并不是iterable的，需要利用items()函数将字典转换为可迭代的。

冒泡排序

#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

插入排序

描述：
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

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页例子
#key的左边都是排好的，插入排序就是把key插入到左边排好的序列中去
#因为左边已经排好了，所以如果比最后一个元素大就只需要和最后一个元素比就行
#否则key向前移动，直到比较完前面所有的值
#一个key插入完以后，key自增，直到右边没有元素为止
def Insert_sort(list1):
    count = len(list1)
    for i in range(1,count): #假设第一个数是排序好的
        key = list1[i] #取出当前未排序的数
        j = i - 1 #从后往前，先取未排序数的前一个数（已经排序好的数）
        while j >= 0 and list1[j] > key:#若当前未排序的数比排序好的数还小，并没有到数组的开头。
            list1[j+1] = list1[j] #排序好的数往后挪一个位置
            j = j - 1 #去排序好的数的前一个数进行比较
        list1[j+1] = key #插入当前要排序的数
    return list1

希尔排序

希尔排序(Shell Sort)是插入排序的一种。
也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 同时该算法是冲破O(n^2）的第一批算法之一。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；推荐的增量是 length/2,虽然他不一定是最好的。
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

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中//代表整除，/代表小数除
#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交换；以此类推，第i次在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕，对初始排列不敏感，无论怎样都要比较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 

堆排序

一个完全二叉树大根堆需要满足：

i 为下标，n为元素个数，i是从1开始的，0位置需要使用占位符

流程：

1.首先构造堆
2.取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造一个大根堆
3.重复第二步，直到这个大根堆的长度为1，此时完成排序。

#占位符比较麻烦，直接使用python中的链表结构
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)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

递归构造堆，伪代码：
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）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

算法导论中的版本

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