误差与数据处理【业界优制】

1、第1部分：数据、误差与统计计算,1,扶风书屋,Outline,数据信息数据挖掘 物理量的正确值是不可能得到的； 误差： 实验误差 随机误差（偶然误差）、系统误差、过失误差 计算误差 截断误差、舍入误差 先讲计算误差（计算机数值计算的基本问题） 再讲实验误差样本与总体测量值、误差的统计规律性 实验误差的矫正（离群点数据的剔除） 参数估计、统计检验（总体的不同分布） 引出下一章：常用分布函数,2,扶风书屋,数据(Data),数据(Data)：数值数据、非数值数据 信息(Information) 数据挖掘(Data Mining) 模式识别 人工智能 数理统计（理论）统计计算（应用）,3,扶风书屋,

2、数据与误差,实验误差 数据来源：测量（实验） Kolthoff断言：物理量的正确值是不可能得到的。 加工误差（计算误差） 计算过程带来误差,4,扶风书屋,误差分类,实验误差 随机误差（偶然误差） 随机因素引起的不易控制的误差； 统计研究的重点（正态分布） 系统误差 由于某种人为因素引起实验结果有明显的固定偏差 只能进行统计检验，一般不能通过增加实验次数消除 过失误差 明显歪曲实验结果的误差 离群值、异常值、Outlier,统计研究的重点！,5,扶风书屋,误差分类(Cont.),计算误差（加工误差） 截断误差 近似算法（无穷级数逼近） 计算机字长限制 舍入误差 截断舍入（四舍五入） 乘、除运算误

3、差,数值计算研究的重点！,6,扶风书屋,举例：计算地球的表面积,数学模型： 误差： 地球被看成是一个球,简单理想模型 系统误差、人为误差 测量仪器误差 如何测得地球的半径长度R 计算误差 截断误差：公式中的 是无理数 舍入误差：浮点数的计算,7,扶风书屋,误差与“统计计算”,“统计计算”要研究两类误差!,8,扶风书屋,计算误差,利用计算机进行计算带来的误差 数在计算机中的表示 舍入误差 截断误差 计算机算法的基本问题 计算复杂性 稳定性 问题的病态性,数值计算的最基本概念！,9,扶风书屋,数在计算机中的表示-浮点数,计算机中数的表示方式,说明：计算机中的数只有有限多个，同时只能是有限精度，且为

4、实数集的一个子集。称之为浮点数，记为F.,10,扶风书屋,数在计算机中的表示-浮点数,浮点数集合F由（t,L,U)唯一确定,数值实验-floatgui.m（t=3,L=-4,U=3） f = (0:2t-1)/2t; F = ; for e = emin:emax F = F (1+f)*2e; end,t=3,L=-4,U=3 eps=1/8=0.125，则12之间的数的表示： 1 1.125 1.250 1.375 1.500 1.625 1.750 1.825 2 现在给定实数1.0625,1.1249999.如何表达?误差多少？,11,扶风书屋,数在计算机中的表示-浮点数,结论： 浮点

5、数集合F中的元素分布是不均匀的 由于计算机字长有限，浮点数只能是有限的集合：字长增加，浮点数集合变大。 不能直接表达的实数只能“舍”或“入”为与之接近的浮点数,课后练习：运行floatgui.m程序，调整(t,U,L)取值，观察可以表示的浮点数集合的变化。求给定(t,U,L)后可表达的浮点数个数（修改floatgui.m程序）,12,扶风书屋,数在计算机中的表示-浮点数,结论： 尾数多少决定了eps的大小，决定了计算机的精度 L，U决定了可以表示的浮点数的大小范围,13,扶风书屋,数在计算机中的表示-浮点数,IEEE双精度二进制数 使用64位存储一个数，每位取值0或1 位的分配为： 尾数符号

6、1 尾数52 阶码11 t=52,-1023=s=1023但-1023保留做它用,14,扶风书屋,数在计算机中的表示-浮点数,IEEE双精度数系的标志 Binary Decimal eps2(-52)2.2204e-16 realmin2(-1022)2.2251e-308 realmax(2-eps)*210231.7977e+308,数值实验： a = 4/3; b = a 1;c = 3*b;d = 1 - c,得到的d即为机器精度,21024; (1+1-eps)*21023 得到的是最大数,15,扶风书屋,数在计算机中的表示-浮点数,原因： 舍入误差在起作用,数值实验 x = 0.9

7、88:.0001:1.012; y = x.7-7*x.6+21*x.5-35*x.4+35*x.3-21*x.2+7*x-1; plot(x,y) 或plot(x,(x-1).7),16,扶风书屋,数在计算机中的表示-浮点数,避免舍入误差的过度影响（算法设计） 注意计算次序 避免相近的大数值相减或相差很大的两数值做加减运算； 简化计算公式，减少计算次数；,17,扶风书屋,计算机算法的基本问题,构造算法的基本手段： 近似 研究算法的核心问题： 近似对计算结果的影响 算法的稳定性 不能扩散舍入误差 算法的复杂度 算法的收敛性 问题的病态性,18,扶风书屋,算法的稳定性,Algorithm 1,A

8、lgorithm 2,问题：En=1-nEn-1, E1=1/e 递推算法，且E=0,19,扶风书屋,Program of algorithm 1,clear ep(1)=1/exp(1) N=15; for n=2:N ep(n)=1.0-n*ep(n-1); end plot(ep,b*);,20,扶风书屋,Algorithm 1 with N=15,21,扶风书屋,Algorithm 1 with N=100,22,扶风书屋,Program of algorithm 2,clear ep(100)=0 N=100; for n=N:-1:2 ep(n-1)=(1.0-ep(n)/n; e

9、nd plot(ep,b*);,23,扶风书屋,Algorithm 2 with N=100,24,扶风书屋,Algorithm 2 with N=500,25,扶风书屋,算法的稳定性,结论： 可以使用的算法是 Algorithm 2！ 原因： 设两个算法初值的舍入误差一样，均为e1,则算法1计算到第n步时，误差累计为n!e1,而算法2，误差衰减为e1/(n!/m!),m=n-1,n-2,1 稳定的算法-算法中产生的任何误差，对后续计算的影响是衰减或可以控制的。,不稳定的算法=不能用的垃圾！,26,扶风书屋,算法的复杂度,指数型算法 算法计算量是问题规模的指数函数 只能够处理规模很小的问题 多

10、项式型算法 算法计算量是问题规模的多项式函数 可以处理规模较大的问题,27,扶风书屋,Complexity,Descriptor Size in Bytes Storage Mode Tiny 102 Piece of Paper Small104 A Few Pieces of Paper Medium 106 A Floppy Disk Large 108 Hard Disk Huge 1010 Multiple Hard Disks Massive 1012 Robotic Magnetic Tape Storage Silos Super-massive1015 Distributed

11、 Data Archives The Huber-Wegman Taxonomy of Data Set Sizes,28,扶风书屋,O( n1/2 ) Plot a Scatter-plot O( n )Calculate Means, Variances, Kernel Density Estimates O(n log(n)Calculate Fast Fourier Transforms O(n c)Calculate Singular Value Decomposition of an r x c Matrix; Solve a Multiple Linear Regression

12、O( n 2 ) Solve most Clustering Algorithms O( a n ) Detect Multivariate Outliers,Algorithmic Complexity,29,扶风书屋,Complexity,30,扶风书屋,Complexity,31,扶风书屋,Complexity,32,扶风书屋,算法的收敛性,误差 收敛性,33,扶风书屋,问题的病态性,考虑如下的问题 f(x)=(x-1)(x-2).(x-20) 显然方程 f(x)=0 的解是 1 2 3 4 19 20 请问: 如下方程的解是什么？,34,扶风书屋,Matlab program,p=po

13、ly(1:20); %help poly ep=zeros(1,21); ep(3)=1.0e-5; re=roots(p+ep) plot(re,b+); hold on plot(1:20,0,r*); hold off,35,扶风书屋,=10e-5,36,扶风书屋,=10e-6,37,扶风书屋,=10e-8,38,扶风书屋,计算误差分析作业,1. Explain the output produced by t = 0.1 n = 1:10 e = n/10 - n*t 2. What does each of these programs do? How many lines of o

14、utput does each program produce? What are the last two values of x printed? x = 1; while 1+x 1, x = x/2, pause(.02), end x = 1; while x+x x, x = 2*x, pause(.02), end x = 1; while x+x x, x = x/2, pause(.02), end,39,扶风书屋,计算误差分析作业,3. The classic quadratic formula says that the two roots of the quadrati

15、c equation Use this formula in Matlab to compute both roots for a = 1; b =-100000000; c = 1 Compare your computed results with roots(a b c) What happens if you try to compute the roots by hand or with a hand calculator? You should find that the classic formula is good for computing one root, but not

16、 the other. So use it to compute one root accurately and then use the fact that x1x2 = c/a to compute the other.,40,扶风书屋,计算误差分析作业,4. The power series for sin x is This Matlab function uses the series to compute sin x. function s = powersin(x) % POWERSIN. It tries to compute sin(x) from a power serie

17、s s = 0; t = x; n = 1; while s+t = s; s = s + t; t = -x.2/(n+1)*(n+2).*t; n = n + 2; end What causes the while loop to terminate? Answer the following questions for How accurate is the computed result? How many terms are required? What is the largest term in the series? What do you conclude about th

18、e use of floating-point arithmetic and power series to evaluate functions?,41,扶风书屋,实验误差及处理,实验误差(Outline) 随机误差随机变量 总体、样本 总体的数字特征 样本特征量及其计算 直方图概率密度函数 总体分布的估计与检验 正态性检验：QQ检验 数据的变换与校正,42,扶风书屋,随机误差与随机变量,随机误差 由于某些无法控制的因素的随机波动而形成的误差，又称为偶然误差； 随机现象 由于随机误差的存在，在基本条件不变的情况下，重复测量会得到不同的结果 随机事件 随机现象中的某种结果（如测量中得到某个值）

19、 概率 随机事件A的概率P(A)表示事件A发生的可能性大小,43,扶风书屋,随机误差与随机变量,概率的公理体系 随机事件A的概率满足 必然事件U的概率为1 如果随机事件A,B互斥（不相交），则P(A+B)=P(A)+P(B) 频率 如果在n次试验中，随机事件A出现了a次，则称 F(A)=a/n 为随机事件A在n次试验中出现的频率 频率与概率 当n趋向无穷大，即测量次数无限多时，频率的极限为该事件发生的概率,44,扶风书屋,随机误差与随机变量,随机变量 就是随着试验结果的不同而随机地取各种值的变量。（随机现象与随机变量的取值） 离散型随机变量 有些随机变量，只能在离散点上取值，例如，掷一个骰子掷

20、出的点数，同时扔两个硬币出现正面向上的硬币个数； 连续型随机变量 有些随机变量，它们的取值范围是实数轴上的连续区间，例如，加工零件时的加工误差，炮弹落点到目标的距离，两次电话来到之间的时间间隔等 事件的概率采用随机变量的取值进行刻画,45,扶风书屋,总体与样本,总体 随机变量X的所有可能取值组成研究的对象全体称为总体 有穷总体与无穷总体 随机变量的取值具有规律性分布函数 离散型 X是离散型随机变量，将可能取的所有的值以及它取这些值的概率一一列举出来，这样得到的一组概率，称为X的概率分布 常见离散型概率分布(参见：常见概率分布.doc),46,扶风书屋,总体与样本,连续型,常见连续型概率分布及密

21、度函数 (参见：常见概率分布.doc),47,扶风书屋,总体与样本,随机变量的数字特征(总体） 用于描述随机变量X取值的基本统计特性 数学期望（Expectation,均值）E(X) 方差(Variance)D(X)和标准差(Standard Deviation) 协方差(Covariance)和相关系数（Correlation Coefficient） (参见：随机变量的特征.doc),48,扶风书屋,总体与样本,个体 对总体的每一次观测所得到的测量值称为一个个体 样本 n个个体组织在一起构成对总体观测的一个样本，其中观测次数n称为样本容量 一次观测就是总体X取得一个值；样本容量为n的样本可

22、以看成是n个来自同一总体的随机变量的不同取值。所取得的值又称为样本观测值。 样本具有二重性： 在观测（抽样）前，它是n个随机变量（与来自的总体同分布） 在观测（抽样）后，它是n个观测值（随机变量的取值）,49,扶风书屋,总体与样本,为什么要研究样本 抽样实验 研究样本的目的 估计总体的特征 怎样产生样本 有放回抽样、无放回抽样 简单随机样本 组成样本的每个个体与总体同分布 组成样本的每个个体彼此相互独立,50,扶风书屋,总体,选择个体,样本,观测样本,样本观察值,(数据),数据处理,样本有关结论,推断总体性质,统计量,统计的一般步骤,51,扶风书屋,总体与样本,统计量 为了集中简单随机样本所带

23、来的总体信息,考虑样本的函数,且不含任何未知参数,这样的“不含未知参数的样本的函数”称为统计量 抽样分布 统计量的分布称为抽样分布,52,扶风书屋,(2) 样本均值,(4) 样本方差,(5) 样本标准差,(3) 样本k阶中心矩,(1) 样本k阶原点矩,注：,常用样本统计量,53,扶风书屋,样本统计量的Matlab计算,均值Mean 方差Var 标准差Std 极值Range 中位数Median 算例：a=randn(100,1); mean(a); a=randn(100000,1) mean(a);,54,扶风书屋,随机变量的概率分布,测量值随机变量概率分布？ 画直方图 找出最大值和最小值，求

24、出极差R 根据样本容量大小进行分组。大样本分10-20组，小样本（n50)分为5-6组，然后根据组数k与极差R确定组距dx=R/k 确定分点 计算测量值落在各组内的个数ni,求出频率ni/n及相对频率ni/n/dx 以分点为横坐标，相对频率为纵坐标画直方图,55,扶风书屋,随机变量的概率分布,直方图,Matlab算例 (doc hist) x = -2.9:0.1:2.9; y = randn(10000,1); hist(y); hist(y,x),56,扶风书屋,随机变量的概率分布,直方图到概率密度,57,扶风书屋,随机误差的分布(密度函数),伽利略原则(Galileo) 所有观测值都可以

25、有误差，其来源归因于观测者、仪器工具以及观测条件等：存在性 绝对值小的误差出现的概率大，绝对值大的误差出现的概率小：单峰性 绝对值相等的正、负误差出现的概率相等，随机误差的总体平均值为0：对称性 绝对值很大的误差出现的概率极小，小概率事件：有界性,58,扶风书屋,随机误差的分布(密度函数),辛普森的工作(Simpson, 1710-1761) 一封信：在应用天文学中取若干个观测值的平均值的好处 平均的可信度与“最谨慎观测所得值”的可信度 拉普拉斯的工作(Laplace) 误差密度函数f(x)应该关于0对称 f(x)在x=0处增加时，f(x)值下降 选择了-df(x)/dx=mf(x), x=0

26、,59,扶风书屋,随机误差的分布(密度函数),高斯的工作(Gauss,1777-1855) 饶日天体运动的理论 推导出随机误差分布的概率密度函数 高斯分布（正态分布）,60,扶风书屋,从样本估计总体：参数估计,正态分布总体,采用来自同分布的样本构造统计量进行估计！ 参数估计 点估计极大似然估计 区间估计,61,扶风书屋,从样本估计总体：参数估计,极大似然估计,62,扶风书屋,从样本估计总体：参数估计,极大似然估计,63,扶风书屋,极大似然估计高斯分布,推导随机误差分布的密度函数,64,扶风书屋,极大似然估计高斯分布,65,扶风书屋,极大似然估计高斯分布,66,扶风书屋,极大似然估计高斯分布,6

27、7,扶风书屋,假设检验,假设检验的原理(参见：假设检验.doc) 假设检验的应用 测量值的正态概率分布 等距直方图总体的概率密度函数（前已介绍） 等频率直方图拟合优度检验法 QQ检验法（直线检验法）,68,扶风书屋,假设检验,等频率直方图拟合优度检验法,69,扶风书屋,假设检验,70,扶风书屋,假设检验,QQ检验法,71,扶风书屋,假设检验,QQ检验法(续),72,扶风书屋,假设检验,QQ检验法(续),73,扶风书屋,假设检验,QQ检验法(续),74,扶风书屋,假设检验,QQ检验法(续),75,扶风书屋,假设检验,QQ检验法(数值试验),Matlab程序（源程序） 经验分布函数：cdfplot

28、 正态性假设检验：qqplot, normplot,76,扶风书屋,假设检验,假设检验QQ检验法 例：已知20名学生的各科平均成绩为：56，23，59，74，49，43，39，51，61，99，23，56，49，75，20. 请检验其正态性。,Matlab程序： A=56 23 59 74 49 43 39 51 61 99 23 56 49 75 20 qqplot(A),normplot(A),77,扶风书屋,假设检验,作业1： 根据上述介绍的算法，自行设计实现myqqplot(x)，图示数据正态性检验，计算相关系数r并将其值显示在图上适当的位置; 使用myqqplot针对上例数据进行正态

29、分布性检验。,78,扶风书屋,数据集中离散程度的可视化度量,Box plot（盒图） 分位数 (quartile) P(XXp)=p，则Xp称为p分位数 p=0.5时，Xp又称为中位数 四分位数 下四分位数：p=0.25； 中位数：p=0.5； 上四分位数：p=0.75 直观解释： 将所有数值按大小顺序排列并分成四等份，处于三个分割点位置的得分就是四分位数。 最小的四分位数称为下四分位数：所有数值中，有四分之一小于下四分位数，四分之三大于下四分位数。 中点位置的四分位数就是中位数； 最大的四分位数称为上四分位数：所有数值中，有四分之三小于上四分位数，四分之一大于上四分位数,79,扶风书屋,数据集中离散程度的可视化度量,四分位数间距interquartile range (IQR) IQR=q0.75-q0.25 代表中间50%数据的极差值 下界lower limit (LL) 和上界upper limit (UL) LL=q0.25 1.5*IQR UL=q0.75 + 1.5*IQR 超出LL和UL的观测点可视为异常点（Outlier） 邻近值Adjacent values 如果不存在异常点，则邻近值为观测值的最大值和最小值 否则，邻近值为LL和UL,80,扶风书屋,数据集中离散程度的可视化度量,81,扶风书屋,数据集中离