五数概括法

四分位数 

四分位数包含第一四分位数、第二四分位数、第三四分位数。分别写成Q1、Q2、Q3，第二四分位数也叫做中位数，是指数值在排序后的集合中最中间的数
IQR 

我们将Q3-Q1的值叫做IQR
五数概括法 

五数概括法即用以下五个数概括一组数据： 

最小值 

第一四分位数 

第二四分位数（中位数） 

第三四分位数 

最大值
如下图所示： 


其中我们将到中位数的距离大于1.5个IQR的值称之为异常值

首先必须清楚中位数的定义：

中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。


然后这个题答案：

内存足够的情况： 可以使⽤用类似quick sort的思想进行，均摊复杂度为O(n)，算法思想如下： 
• 随机选取一个元素，将比它小的元素放在它左边，比它大的元素放在右边 
• 如果它恰好在中位数的位置，那么它就是中位数，可以直接返回 
• 如果小于它的数超过一半，那么中位数一定在左半边，递归到左边处理 
• 否则，中位数一定在右半边，根据左半边的元素个数计算出中位数是右半边的第几大，然后递归 到右半边处理 
内存不⾜足的情况： 
方法⼀：⼆分法 
思路：一个重要的线索是，这些数都是整数。整数就有范围了，32位系统中就是[-2^32, 2^32- 1]， 有了范围我们就可以对这个范围进行二分，然后找有多少个数⼩于Mid,多少数大于mid，然后递归， 和基于quicksort思想的第k大⽅方法类似 
方法二：分桶法 思路：化大为小，把所有数划分到各个小区间，把每个数映射到对应的区间⾥里，对每个区间中数的 个数进行计数，数一遍各个区间，看看中位数落在哪个区间，若够小，使⽤用基于内存的算法，否则 继续划分


然后讲解下快速排序以及基于快排思想的找前k个最大数：


快速排序是对冒泡排序的改进。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序，它采用一种分治(Divide-and-ConquerMethod)的方法
快速排序的思想：

在数组中找到一个基准数（pivot）
分区，将数组中比基准数大的放到它的右边，比基准数小的放到它的左边
继续对左右区间重复第二步，直到各个区间只有一个数，这时候，数组也就有序了。
代码：



[cpp] view
 plain copy


 print?


int Partition(vector<int> &v, int head, int rear){  

    int key = v[head];  

    while (head < rear){  

        while (v[rear] <= key && head < rear){  

            --rear;  

        }  

        swap(v[head], v[rear]);  

        while (v[head] >= key && head < rear){  

            ++head;  

        }  

        swap(v[rear], v[head]);  

          

    }  

    v[head] = key;  

    ++my_count;  

    return head;  

}  

  

void QuickSort(vector<int> &v, int head, int rear){  

    int pivot = -1;  

    if (head < rear){  

        pivot = Partition(v, head, rear);  

        QuickSort(v, head, pivot - 1);  

        QuickSort(v, pivot + 1, rear);  

    }  

}  


Note: Partition函数中 v[rear] <= key 以及 v[head] >= key 表达式必须包含等于的判断，否则当数组两头的数相等时将会造成死循环  例如 {5,2,6,2,9,10,5}
Partition函数：最慢情况下快速排序会进行 size(）- 1 次 Partition函数，而每次调用，Partition函数会选择一个基准数，例如v[head]或者v[rear]，或者任意一个数组中的数。之后分别从两头扫描，碰到比基准数大或者小的数就与上一个head或rear交换，或者直到head大于等于rear时，此次循环结束。
QuickSort函数：该函数采用递归的方法，每次调用一次Partition函数，得到一个基准数的索引和相对基准数有序的数列，之后将该基准数左边的数组和右边的数组分别调用QuickSort函数，也就是它本身。直到数组中只有一个数时，这条递归序列便结束。
基于快速排序的查找前k个最大数

由上可知，快排的思想是每次找到一个基准数，将数组排列成基准数左边的每个数都比基准数大，右边的每个数都比基准数小的序列。
通过这个思想，我们可以稍微修改QuickSort函数，使它变成QuickSearch函数，使之拥有快速查找前k个最大的数。



[cpp] view
 plain copy


 print?


int QuickSearch(vector<int> &v, int head, int rear, int k){  

    int pivot = -1, len = 0;  

    if (head < rear){  

        pivot = Partition(v, head, rear);  

        len = pivot - head + 1;  

        if (len < k){  

            pivot = QuickSearch(v, pivot + 1, rear, k - len);  

        }  

        else if (len > k){  

            pivot = QuickSearch(v, head, pivot - 1, k);  

        }  

    }  

    return pivot;  

}  

上图中，我们可以发现，函数参数多了一个k，这个值是表示要获取前k个最大数。
函数中多了一些逻辑，每次执行完Partition函数，根据获取的基准值索引，计算基准值左边数组的长度。
若len < k，则说明，在基准值左边的数组中已经有了len个最大数，此时，我们只需在基准值右边的数组再找k - len个最大数即可，所以只要再次调用QuickSearch函数，并传入k-len参数以及基准值右边的数组索引。
若len > k，则说明，此时基准值左边已经有了len个最大值，然而len大于k，我们并不需要那么多的最大值，所以再次调用QuickSearch函数，传入基准值左边的数组索引，以及k，获得这个长度len的最大数集的子集

本博文源于matlab基础，主要讲述常用统计量的计算包括均值、中位数、极差、方差和标准差。

其中相应的函数如下，然后我们用一个例子讲述函数的实战。




函数
功能格式




mean(x)
求x阵列的均值，格式：M=mean(x)


median(x)
求x阵列的中位数，格式:M=median(X)


range(x)
求x阵列的极差，格式：R=range(x)


var(x)
求x阵列的方差,格式:V=var(x)


std(x)
求x阵列的标准差，格式:S=std(x)


例子求A的均值、中位数、极差、方差和标准差
A的数据保存在A.txt
74 63 78 76 89 56
65 83 72 41 39 72
90 46 54 61 75 76
77 78 53 74 59 50
59 47 45 67 75 36

将数据复制进去，然后另存为A.txt大家应该能理解。然后将上面代码输入一遍，就是简单的演示，博主的代码如下：
>> load A.txt
>> mean(A)

ans =

   73.0000   63.4000   60.4000   63.8000   67.4000   58.0000

>> median(A)

ans =

    74    63    54    67    75    56

>> range(A)

ans =

    31    37    33    35    50    40

>> var(A)

ans =

  141.5000  292.3000  194.3000  197.7000  364.8000  268.0000

>> std(A)

ans =

   11.8954   17.0968   13.9392   14.0606   19.0997   16.3707

>> 

如果大家不放心可以用计算器/手算验证，但是matlab我们要相信，毕竟这是为了后面更快速做更高深的内容做准备！

1.前言

前面我介绍的都是确定模式所属类别的模式识别算法。对于模式基于概率进行分类的手法称为概率分类法。这是这一篇博客重点讨论的内容。
基于概率的模式识别，是指与模式x所对应的类别y的后验概率p(y|x)进行学习。其所属类别为后延概率达到最大值时所对应的类别。


类别的后验概率p(y=y'|x).可以理解为模式x属于类别y的可信度。通过这样的方法，在可信度非常低的时候就不用强行进行分类，从而避免了错误分类，而且可以设置一些实用的选项，比如吧这样的样本丢掉。另外，基于概率的模式识别还有一个优势，就是对于多种类别分类问题通常会有较好的分类结果。

2.Logistic回归

先谈一谈简单又实用的Logistic回归。
2.1 Logistic模型的最大似然估计
Logistic回归，使用线性对数函数对分类后验概率p(y|x)进行模型化。


上式中，分母是与所有的y=1,...,c对应的，满足概率总和为1的约束条件的正则化项。上述的模型q(y|x:Θ)中包含的参数{Θj}j=1->b，在每个类别y=1,...,c中都不一样，因此包含所有参数的向量Θ有bc次维。


Logistic回归模型的学习，通过对数似然为最大师的最大似然估计进行求解。
似然函数是指，将手头的训练样本{（xi,yi）}i=1->n由现在的模型生成的概率，看作是关于参数Θ的函数，对数似然是指其对数：


似然是q(yi|xi,Θ)经过n次相乘的结果，例如对于所有的i=1,...,n，q(yi|xi,Θ)=0.1的时候，其似然：


是一个非常小的值，经常会发生丢为的现象。对于这种情况，一般使用对数来解决，即利用将乘法变换为加法的方法来防止丢位现象的发生。
Logistic回归学习模型有下事的最优化问题来定义：

上面的目标函数对于参数Θ是可以微分的，因此我们还可以用梯度下降策略来求最大似然估计的解Θ’。
概率梯度下降法的Logistic回归学习算法如下图所示：


2.2 对数高斯模型
下图表示的是对对数高斯核模型进行Logistic回归学习的实例。


在该例中，高斯核的带宽h=1。


通过结果，我们可以看出，类别的后验概率P(y|x)得到了很好的学习。
2.3 使用Logistic损失最小化学习来解释
首先从2分类问题y∈{+1,-1}进行说明：


通过使用上述关系式，Logistic模型的参数个数就可以由2b个降为b个。


这个模型的对数似然最大化的准则：


可以改写为上述形式。根据关于参数的线性模型：

的间隔m=fΘ(x)y，可以知道上式与使用Logistic损失：


的Logistic损失最小化学习是等价的。如下图所示：


Logistic损失函数

3.最小二乘概率分类

这里只是简单性回顾一下在平方误差准则下进行与Logistic回归相同学习的最小二乘概率分类器。
最小二乘概率分类器，对于各个类别y=1,...,c的后验概率p(y|x)，使用于参数相关的线性模型：


进行模型化。与Logistic模型不同的是，这个模型仅仅依赖与各个类别y对应的参数


然后，对这个模型进行学习，是下面的平方误差最小：


上式中，P(x)表示的是训练输入样本的概率密度函数。
上式的第二项可以进行变形为：


上式中，p(x|y)是属于类别y的训练输入样本的概率密度函数，p(y)表示的是训练输出样本{yi}i=1->n的概率密度函数。
我们应该注意到，Jy中包含了如下比较难以处理的：


分别表示与p(x)和P(x|y)相关的数学期望值。这些期望值一般无法直接计算，而是采用样本的平均值进行模拟：


应该注意的是，对于Jy，他的第三项与Θ无关，所以没必要再研究。此外，我们引入L2正则化项，得到如下的计算准则：


可以发现，这个学习准则是关于Θ的凸二次式，对其进行偏微分并置零可以得到最优解。


然而，如果按照上式计算，类别的后验概率可能会出现负的。因此，需要对负的输出加一个下届为零的约束条件：


下面是最小二乘概率分类的例子，使用的数据与Logistic回归数据一致，分类结果如下图所示：


最小二乘概率分类的实例

4.总结

最小二乘概率分类器能够得到与Logistic回归基本相同的学习结果。Logistic回归模型包括正则项，因此，与各个类别的基函数个数b和类别c相对应，其参数个数为bc个。另一方面，最小二乘概率分类器使用了没有正则化的线性模型，所以是对有b个参数的模型，对各类别进行c次独立学习的过程。在类别数c很大的情况下，最小二乘概率分类效率更高一点。
同时，由于Logistic回归学习包含非线性的对数函数，必须要通过反复迭代的方式进行求解，需要花费大量的学习时间。但是，最小而成概率分类器中可以得到解析解，更有效率。
但是，最小二乘概率分类器也不是完美无瑕的。因为，最小二乘概率分类器的输出为概率的形式，所以需要进行一系列的后期处理。在样本容量很大的情况下，后续处理几乎没影响，范式当训练样本非常小的情况下，就会导致学习效率低下。
因此，一般的处理方式是，当训练样本是较多的时候，采用最小二乘分类器；而当训练样本较少的时候，则采用Logistic回归方法。