在线时间 90 小时 最后登录 2018-12-27 注册时间 2016-4-22 听众数 17 收听数 0 能力 20 分 体力 23473 点 威望 2 点 阅读权限 200 积分 7546 相册 0 日志 0 记录 0 帖子 126 主题 100 精华 2 分享 0 好友 6
升级 50.92%
TA的每日心情 开心 2018-6-4 15:01
签到天数: 7 天
[LV.3]偶尔看看II
群组 : 2018年大象老师国赛优
群组 : 高考备战
群组 : 2018中小学数学建模冬
统计算法总览 " O) u& L6 D* l( O* j: W1 B1 H; `# @
% Z: A' l1 m* c9 B% @
统计一词源于国情调查,一般来说包括三个含义:统计工作、统计资料和统计科学。其中统计工作是指的搜集、整理和分析客观事物总体数量方面的资料,统计资料则是由统计工作所获得的各项数字或文字资料,一般反映在图表、分析报告、统计年鉴里面,而统计科学则是指导统计工作的原理、原则和方法。* |5 g2 Q) ~2 E
因此,在数学建模比赛中统计问题一定要有文献资源和数据资源的搜集,并且这一部分内容也要反映在论文中,而整理通常来说是将搜集到的资料以图表的形式呈现在论文中,最后分析自然就是数据预处理和统计算法建模求解。; W& L% D' a* F5 p; [* ~0 q
1 ?8 ~4 M' ^8 [ 1.预测 + |# _5 ^# ?$ y# z P
8 p8 B; U' t# I3 O
预测,顾名思义,即根据先用数据规律推算接下来的数据。而预测按照算法可以分为四大类,一为回归分析,二为概率估计,三为时间序列,四为机器学习。# q# w2 h: @9 k+ r1 g
) s$ r2 G( u6 J (1)回归分析 / J' K2 i- |6 E# L% B$ z* m1 p% `
* P, g j% `" {+ Q! w
对于回归分析,该类算法适用于求解单一输出的问题,在某种程度上可以叫做函数拟合,即利用一种函数去逼近原有数据 。我们在高中阶段学习的线性回归就属于一种预测方法,下面给出几种函数类型:( D0 }) w2 H) f v E$ W
! N$ {5 G* m+ d 多项式拟合:
! P- L' j- b% S' \. r
0 r: B4 Y8 o+ F1 s! e 非线性拟合:
4 B7 r& d s# w [3 ?3 R# b" K2 X # S& k1 |3 |' N; _7 {3 J! l7 j
多元拟合:
; d4 S7 f; }5 c3 k Y5 L# W
* a, e9 X$ o, h
如下图所示,该图像是利用了非线性函数对原有数据进行了逼近,有了函数自然也就可以根据输入计算出接下来的数据,所以回归分析也只适用于单输出问题。而回归分析的关键问题就是对某一函数模型的参数进行求解,matlab中有专门的拟合工具箱polyfit和lsqcurvefit:: \$ ^% R1 m3 z. @5 H; A5 `3 M2 Z
4 d. f$ Q/ W7 i 这里小编用MATLAB编了两种基础的回归分析程序。 ( Y! j$ w' k. ]2 f% d+ |, K
效果如下:3 t* W- z. r; A1 k. R1 H3 [
: X& R- | J6 _2 y5 B& L
" ^3 J: e; D4 R* I (2)概率估计
B) d/ z$ j) B& K
E+ S2 e* m& G( D' X: O$ Z 而对于概率估计,其中的代表是马尔科夫链算法,即先给数据划分状态,然后将数据的分布规律用状态转移来解释。最后对于当时数据的状态,利用根据状态间的转移概率可以求得未来的状态概率分布,自然也能求得下一状态的预测值。
# h1 _6 [ X/ o8 J7 y 5 q- O0 F* y7 m+ b" }' v0 p
比方说,我只去A,B,C,D四个食堂吃饭,现在告诉你我吃饭的记录,现在就需要计算我在这四个食堂中的转移概率,如我去食堂A吃过后再去四个食堂吃饭的概率是多少?通过这些转移概率不断推算我下一个要去的食堂,再根据四个转移概率得到最大可能去的食堂。但是这只是离散问题的预测,对于连续问题,自然也就需要将连续数据划分为若干个离散的状态,在使用此方法。& r: d3 A$ P% w- i1 g0 D
% x4 I3 \, W, J2 G. B( E" x 此方法对于初学者来说掌握会比较困难,不过如果能成功使用会为论文添色不少,有兴趣的同学可以自行查找资料了解。(《数学建模算法与应用》一书上有讲解)
% H1 }8 |. Z! m4 w; o 4 n) y( @& N8 v& Q
(3)时间序列 7 k3 y; y4 C1 ?+ @
1 u+ ~4 F3 M7 g9 ]2 t 第三类称其为时间序列,因为输入是按顺序的离散值,大多数情况下就是时间,针对此类问题,由于输入以稳定步长增长的,所以不用考虑输入,直接研究输出的变化规律,这一点类似于高中学的数列,比方说有名的斐波那契数组:1,1,2,3,5...,它的数据特征是f(n+2)=f(n)+f(n+1),现在我们要求后面的数就直接利用该数据特征就行了,当然也可以求出其通项公式,有兴趣的同学可以求着试试。
- o0 P, c- l# D6 V) [ i. K+ K ' o3 C4 W1 J1 v' i! |0 y3 P8 C+ J
而时间序列方面的算法其实就是猜测数据前后存在着什么关系,比如说:一次移动平均算法就是猜测每一个数据 与最近的部分数据的均值存在着某种关系,指数平滑法就是猜测每个数据都跟之前的历史数据的加权平均存在着某种关系。这些算法都可以算作是时间序列算法,不过以上算法都是对数据特征简单的猜测,而对于更复杂的数据特征则可能会用到微分方程,利用微分方程,即可以直接预测,还能用于灰色系统,从而将无规则数据转化为有规律的生成序列。& U/ {( M6 c7 f* L+ V
& d2 r6 S/ E6 e0 f, X3 `
(4)机器学习
% E+ a9 t$ ? h+ }( M# v% N1 j 6 H$ `$ d& [3 [. E; S
最后一个就是机器学习,即我们只需要搭好框架,数据特征则会由其自己挖掘,比较有名的有:支持向量机(SVM)、决策树、神经网络(深度学习)。这种算法的最终目的是模拟人脑的结构,它的好处就是在搭建好网络结构之后,通过对已有数据的学习,网络会自行提取数据特征,然后只要我们输入一个数据,网络将自行计算,然后输出它的预测值。这种方法的优点是方便,无需考虑数据规律和数据维度,而缺点则是要求数据量要大,少量样本的训练效果一般不具有适用性。( _" j/ S) o1 r
# a5 S& `6 f# J1 d) ?
(5)模型检验 6 k2 p2 Z& y$ S" ^ W) Y a9 C1 m
, N7 ]) Z( k4 I$ x( g2 } 预测问题中尤其还要注意的是对结果的检验,通常使用残差和后验误差等作为概率统计的检验,也可以用均方误差MSE检验。
1 ^7 r% y# R. b
; i& i$ z! B: _8 {$ l( K 残差值反映了预测值和原始数据的相对差距:
, Y9 F0 e2 h9 b0 N
# D8 T! u5 [$ t# S3 E 
( \4 Q) I, z6 S5 d% O5 r
7 d5 _; i2 a; x- A 后验误差反映模型的精度:
- C7 x: g$ a+ h$ \* h8 l
: A% R- z! _4 p( j / q* X; H2 R3 v7 s: K+ t# Q k
; S' l8 A6 w2 \. t* }) r/ a- X
然后依据下表判断模型精度:& v3 n# M1 K, s5 ?' y6 h
* b& _8 X! k$ t: }7 e! o- p7 Z
# I: r3 @3 k: j : ~" t0 Z! x0 c1 [
0 B: B9 h' T5 e 均方误差则是一个简单的误差效果:
& h/ ~" [& N2 F' M0 s) y1 M
6 O2 O0 S. R' B+ h# A* Y, e ) k. ^4 B3 G6 G0 J/ R
7 T# K0 S! G$ r/ t: m+ I0 |+ l
2.分类/聚类
1 P, Z+ n% J+ a2 X1 g3 }, T- @ , q/ G' s7 k7 U
首先要弄明白分类和聚类的区别:
; r2 v8 @' N! X) f' j3 f3 n. f c- N$ }/ w& ~8 b8 q, P X& E
分类(判别):数据包含数据特征部分和样本标签部分,分类的目的就是判别新的数据特征到其应有的样本标签(类别)中。. t# I3 T, G5 y: x% |6 ?
, o" O2 Q' K- l: |/ ^: }
比方说,现在告诉大家一个教室里面其中一半人每个人的性别(男女),现在需要大家将另一半人中每个人的性别判断出来,因此大家首先要做的的找到区分性别的特征,然后应用到另一半人身上,将其归类。
/ Y! @1 K- ~9 F( X2 W: m ) J& T- ~8 X+ U& o e
聚类:数据中只有数据特征,需要根据某一标准将其划分到不同的类中。
- V' ~3 J7 ]4 x& _' A6 v1 r6 K$ V ) T9 \$ ^7 [5 w- q% [# D
同样的,现在一个教室里面所有人都没什么标签,现在需要你将整个教室的人分为两类,那么你可以从性别、体型、兴趣爱好、位置等等角度去分析。( {. P) l$ a% U# f; c H
! {. _6 o' l( I$ Z( L" V" }+ o
可以看到,分类其实跟预测差不多,只不过输出是一维的,并且还是整数,所以可以用预测中的机器学习方法来解决分类问题。而聚类则不同,一般来说,聚类需要定义一种相似度或者距离,从而将相似或者距离近的样本归为一类,常见的有:kmeans算法、分层聚类、谱聚类等。$ G( |5 c1 e' W! M* Y. u+ ?6 q
+ U: u( v+ u1 G0 [ 对于聚类来说,除了相似性的度量之外,还有一个比较重要的是终止条件,即需要聚成多少类,一般来说,基本都是在聚类之前就设定好需要聚成多少类,其中kmeans就是先设定几个类中心,然后将与类中心相近的数据归到那一类,然后不断更新类中心,直至所有数据聚类完毕,而分层聚类则是相反,先将所有数据各自为一类,然后将相似的类合并,直至达到k类为止...! {8 d* y# M# Y& L
当然,也可以将终止条件改为当最小的距离大于某一阈值时,不再合并类(适用于分层聚类),除了这些算法,还有机器学习方法,如:自组织竞争网络(SOM),可以自行了解。" i9 P* w6 h, W) }1 n
; M7 J9 v6 o' Y& B* ~$ B% Q/ ` 接下来我们以分层聚类为例进行讲解,这一部分例子来自于《数学建模算法与应用》,用以辅助说明。通常来说,分层聚类有两类,一类是从上到下的分裂(即现将所有个体看做一个类,然后利用规则一步步的分裂成多个类),另一类是从下到上的合并(即先将每个个体看作一个类,然后依据规则一步步合并为一个类)。因此分层聚类最终可以得到一个金字塔结构,每一层都有不同的类别数量,我们可以选取需要的类别数量。. N' a( }. Q7 y6 H; G! u+ l; N% z- q
# _9 |" O2 U+ w8 j% | ^5 `, P" W( E 例子:设有5个销售员w1,w2,w3,w4,w5,他们的销售业绩由二维变量(v1,v2)描述:, ]5 n. n- L( e3 i# q% c; D
% B% S% M7 n) A. S5 D" H

5 }6 a2 o9 A) C- ^5 Q l P
7 G& I) ^9 _. V 将5个人的两种数据看作他们的指标,首先,我们简单定义任意两组数据的距离为:: O2 q5 m6 G5 A7 n3 Z- j
3 N" L6 p7 g# `* R# C t ( ^% q8 D! r2 ~3 F; x

7 y U+ x @* v$ c3 z " g; e( R$ H% q- m. @7 C
与此相对应的,当有样本归为一类后,我们要计算类间距离就又得需要一个计算方式,我们定义任意两类间的距离为两类中每组数据距离的最小值:! Y; m, d- B8 F% z& V, B6 X& J
6 c+ v( R* F& C' ?4 H; x' R9 y- d) n 
% j: `# c# o" j A , j' F/ n; G4 s q7 i4 d) C5 I
因此,可以得到任意两个销售员的数据距离矩阵:( t' f# F; G6 c ~6 `8 b
, G2 |- T6 K; Q r/ S8 C

7 n/ h n2 `6 r7 T O9 v0 b# f" K+ B9 u
Step1 首先,最相近的两组样本是w1和w2,他们的距离为1,所以先将其聚为一类;
; g7 S1 D( \: t ! i+ E1 `* h- r6 U
Step2 然后,剩下的样本为{w1,w2},w3,w4,w5,我们发现除了距离1之外,最相似的是 w3,w4,他们的距离为2,所以将其聚为一类;
$ t# }5 a2 T$ v, |
5 j6 U6 ]1 P: \; w Step3 然后,剩下的样本为{w1,w2},{w3,w4},w5,我们发现除了距离1,2之外,最相似的 是{w1,w2}和{w3,w4},他们的距离以 w2和w3的距离为准,距离为3,所以将这两类聚为一类; 8 e) J7 Z& ?3 }2 ~6 N$ Z
" C L$ n6 q5 t$ k3 r/ r& d
Step4 最后,剩下的样本为{w1,w2,w3,w4},w5,只剩最后两类了,所以最后一类为 {w1,w2,w3,w4,w5},类间距以w3/w4与w5的距离4为准。
% S. a! X% K' V# a& ^- M4 n
2 g: c2 L) F: M. @* i k 用matlab编程结果如下:
) x: X' c5 z* [7 C9 L# n2 \7 B4 Q$ U
, d2 T& I! j, R3 ]8 c6 v m5 g7 P4 J 
- W M2 U, X( s2 C- {+ t
$ T! ]/ ]1 _, {* ~
: N$ k, g9 s& w9 y/ h, d2 ?
/ p* G9 u" W, c8 K' ~" S * D* i2 P" J1 |; e. a
3 ?: T( V: \1 m8 z) p* i0 a5 K
zan