第３９卷 第６Ａ期２０１２年６月计算机科学
ＣｏｍｕｔｅｒｃｉｅｎｃｅＳＶｏｌ．３９Ｎｏ．６Ａ
Ｊｕｎｅ２０１２最小二乘法分段直线拟合
田 垅 刘宗田
（）上海大学计算机工程与科学学院 上海２０００７２
摘 要 曲线拟合是图像分析中非常重要的描述符号。最常用的曲线拟合方法是最小二乘法，然而一般的最小二乘法有一定的局限性，已经有不少学者对其进行了一些改进。进一步对最小二乘法进行改进，提出一种新的分段直线拟合算法来代替多项式曲线拟合，以达到简化数学模型的建立和减少计算的目的，使其能够更好地对点序列进行拟合。关键词 直线拟合，最小二乘法，分段
中图法分类号 ＴＰ３０１ 文献标识码 Ａ
ＬｅａｓｔｓｕａｒｅｓＭｅｔｈｏｄＰｉｅｃｅｗｉｓｅＬｉｎｅａｒＦｉｔｔｉｎ－ ｑｇ
ＴＩＡＮＬｏｎＩＵＺｏｎｔｉａｎ Ｌ －ｇｇ
（，，）ＳｃｈｏｏｌｏｆＣｏｍｕｔｅｒＥｎｉｎｅｅｒｉｎ＆ＳｃｉｅｎｃｅＳｈａｎｈａｉＵｎｉｖｅｒｓｉｔＳｈａｎｈａｉ２０００７２，Ｃｈｉｎａ ｐｇｇ ｇｙｇ
，Ａｂｓｔｒａｃｔｕｒｖｅｆｉｔｔｉｎｉｓａｖｅｒｉｍｏｒｔａｎｔｄｅｓｃｒｉｔｏｒｉｎｉｍａｅａｎａｌｓｉｓｔｈｅｍｏｓｔｃｏｍｍｏｎｌｕｓｅｄｃｕｒｖｅｆｉｔｔｉｎｍｅｔｈｏｄｉｓ Ｃ ｇｙｐｐｇｙｙｇ ，ｓｕａｒｅｓｍｅｔｈｏｄ．Ｂｕｔｏｒｄｉｎａｒｌｅａｓｔｓｕａｒｅｓｍｅｔｈｏｄｈａｓｓｏｍｅｌｉｍｉｔａｔｉｏｎｓａｎｄｔｈｅｒｅａｒｅｍａｎｓｃｈｏｌａｒｓｈａｖｅｍａｄｅｌｅａｓｔ－ － ｑｙｑｙ ｒｏｏｓｅｄｉｅｃｅｗｉｓｅｓｔｕｄｏｆｉｍｒｏｖｉｎｉｔ．Ｔｈｅａｕｔｈｏｒｓｍａｄｅｆｕｒｔｈｅｒｉｍｒｏｖｅｍｅｎｔｏｎｌｅａｓｔｓｕａｒｅｓｍｅｔｈｏｄａｎｄａｎｅｗ － ｐｐｐｙｐｇｐｑ ｌｉｎｅａｒｆｉｔｔｉｎａｌｏｒｉｔｈｍｉｎｓｔｅａｄｏｆｏｌｎｏｍｉａｌｃｕｒｖｅｆｉｔｔｉｎ．Ｔｈｅｎｅｗａｌｏｒｉｔｈｍａｃｈｉｅｖｅｓｔｈｅｏａｌｏｆｓｉｍｌｉｆｉｎｔｈｅｍａｔｈ －ｇｇｐｙｇｇｇｐｙｇ ，，ｏｉｎｔｅｍａｔｉｃａｌｍｏｄｅｌｒｅｄｕｃｉｎｔｈｅｃａｌｃｕｌａｔｉｏｎａｎｄｍａｋｅｓｉｔｂｅｔｔｅｒｔｏｆｉｔｓｅｕｅｎｃｅ． ｐｇｑ ，，ＫｅｗｏｒｄｓｉｎｅａｒｆｉｔｔｉｎＬｅａｓｔｓｕａｒｅｓｍｅｔｈｏｄＰｉｅｃｅｗｉｓｅ Ｌ － ｇｑｙ
往往是有序数对，根据误差平方和最小化原则，找出这些数据的最佳函数匹配。
（最小二乘法的数学原理为：给定一组数据（ｘｉ＝１，ｉ，ｉ）ｙ…，，，设其经验方程为Ｆ（方程中含有一些待定系数２，ｎ）ｘ），代入方程求差ｙ为了考虑整体的误ａｘｘｎ。将（ｉ，ｉ）ｉ－Ｆ（ｉ）ｙ可以取平方和，之所以要平方是考虑到误差正负直接相加差，
可以相互抵消，所以记误差为：
∧
）ｅ＝∑（Ｆ（ｘ２ｉ－ｉ）ｙ
１ 引言
在工程技术和科学实验中，常常得到两个有函数关系观测量的一系列有序对。如何根据这些有序对来确定它们的函这就是实验数据处理中的曲线拟合问题。曲线拟合数曲线，
如在计量经济学领域中可以利用历年的经的应用十分广泛，
１］
，济统计数据来预测下一阶段的经济发展趋势［在医学统计
学领域中可以通过发现某种毒物剂量与动物死亡率之间的定在传感技术领域可以用于多传感器量关系来指导医学工作，
２］
。常用的曲线拟合方法是最小二乘法。最小二乘测量标定［
通过求ｅ的极小值可以求出ａ从而求出该组数据的最ｎ，该函数使得误差平方和最小。佳拟合函数，
最小二乘法不仅可以用于曲线拟合，也可以用于直线拟合。如果经验方程Ｆ（是线性的，形如ｙ＝ａ＊ｘ＋那么利ｘ）ｂ，用最小二乘法得到的就是线性回归。
５］
张东林［对最小二乘法进行了改进，即将ｎ个有序对
法（又称最小平方法）是一种数学优化技术，它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以并使得这些求得的数据与实际数据简便地求得未知的数据，
之间误差的平方和最小。在利用最小二乘法实现曲线拟合虽然能够很好地拟合有序对，并且有很好的数学理论支时，
４］
持［和很高的精确度，但是需要进行大量复杂的计算，而且得
（（…，…，分成ｋ组Ｎ１，ｘｉ＝１，２，ｎ）Ｎ２，Ｎｋ：ｉ，ｉ）ｙ
，（，…，（（ｘｘｘ１１，１１）１２，１２）１Ｎ１，１Ｎ１）ｙｙｙ （，（，…，（ｘｘｘ２１，２１）２２，２２）２Ｎ２，２Ｎ２）ｙｙｙ …
（，（，…，（ｘｘｘｋ１，ｋ１）ｋ２，ｋ２）ｋＮｋ，ｋＮｋ）ｙｙｙ
然后对每组有序对进行线性拟合，得到ｋ条拟合直线（…，。张东林的这种算法虽然ｘ）＝ａｘ＋ｂｉ＝１，２，ｋ）ｉ（ｉ＊ｙ＝ｇ
能够实现分段直线拟合，并且进一步可以实现曲线拟合，但是…，其并没有给出ｋ和Ｎｉ（的取值规定。ｉ＝１，２，ｋ）
到的拟合函数往往是高次的，这进一步增加了复杂性。为了减少计算量，本文提出了一种新的简化建立数学模型的算法，
利用最小二乘法实现分段直线拟合的方法，以对观测到的有序对进行建模。
２ 最小二乘法研究现状
最小二乘法的基本思想是：给定一组实验数据，这些数据
），）本文受国家自然科学基金（国际竹藤组织基础科学研究项目（资助。６０９７５０３３１６３２００９００６
，：，田 垅（男，硕士生，主要研究方向为自然语言处理和数据挖掘，刘宗田（男，教授，博士生导师，１９８７－）Ｅ－ｍａｉｌｈｕｂｕ１９３１＠１６３．ｃｏｍ；１９４６－）主要研究方向为智能信息处理、软件工程等。
·４８２·
３］
谢友宝［也对最小二乘法进行了改进。设拟合直线初始
），），计算ｆ（具体过程为：４ｋ，ｓｅ
，，）调用函数ｆ（得到第一条最佳拟合直线ｙ＝ｉ．１ｓｍｉｎａｋ１＊
、，起点和初始终点为Ｓ（设终点的下一个点ｘＥ（ｘｓ，ｓ）ｅ，ｅ）ｙｙ，为Ｎ（计算线段ＥｘＳ和ＳＮ的夹角为：ｎ，ｎ）ｙ
（）／（ＳＮ＝ａｒｃｃｏｓＳＥ２＋｜ＳＮ２－｜ＥＮ２２ＳＥ∠Ｅ｜｜｜｜｜｜＊
）ＳＮ｜｜
式中，ＳＥＳＮＥＮＥ、ＳＮ、ＥＮ的长度。｜｜、｜｜、｜｜分别为线段Ｓ
观察这个角度是否小于给定的阈值，若小于阈值，则将Ｅ和Ｎ往后移一位重新计算，直到大于阈值；否则用最小二乘法计算拟合直线。谢友宝的这种算法虽然实现了有序对的分段直线拟合，并且得到了一种最优的解决方案，但是他没有从整体上来考虑，得到的只是局部最优，而局部最优不一定是整体最优。在此作者进一步对最小二乘进行改进，使其能够从整体上给出最优的分段直线拟合。
ｘ＋ｂｋ１；
）调用函数ｆ（得到ｋ－１条最佳拟合直ｉｉ．ｋ－１，ｍｉｎ＋１，ｅ…，线ｙ＝其中ｊ＝２，ａｘ＋ｂ３，ｋ。ｋｋｊ＊ｊ，
但是如何确定拟合直线的条数呢？一种方法是根据具体人工进行设定；另一种方法是给定一个阈值β，的工程需求，
若连续两次误差平方和的降幅低于这个阈值，则停止拟合的（，），）／，计算，比如，若（ｅｋ－３，ｓｅ－ｅ（ｋ－２，ｓｅ）ｅ（ｋ－３，ｓｅ）＞β（，）（，）／，（，且（ｅｋ－２，ｓｅ－ｅｋ－１，ｓｅ）ｅ（ｋ－２，ｓｅ）ｅ（ｋ－１，ｓ＜β，）（，））／ｅ（，则设定拟合直线的条数为ｅ－ｅｋ，ｓｅｋ－１，ｓｅ）＜β，
ｋ。
３．２ 实现该算法的部分ｊａｖａ代码
３ 改进的最小二乘法分段直线拟合
３．１ 基本思想
］，］）（…，，给定一组有序对（假设ｘｘ［ｉｉｉ＝０，１，ｎ－１）ｙ［为整型数组，给定的阈值为β。ｙ为双精度浮点型数组；
计算误差的Ｊａｖａ代码：
（，）｛ｄｏｕｂｌｅｅｉｎｔｋ，ｉｎｔｓｔａｒｔｉｎｔｅｎｄ ｏｕｂｌｅｅｍｉｎ＝０； ｄ
［］［］；ｏｕｂｌｅｆｅ＝ｎｅｗｄｏｕｂｌｅｎ ｄ ／一条直线拟合 ／
（）｛ｉｆｋ＝＝１
；ｏｕｂｌｅＡ＝０，Ｂ＝０，Ｃ＝０，Ｄ＝０，ｄｅｌｔａ ｄ ｏｕｂｌｅｅ１＝０； ｄ ，ｏｕｂｌｅａｂ； ｄ
（；；ｆｏｒｉｎｔｉ＝ｓｔａｒｔｉｎｄｉ＋＋） ＜＝ｅ ｛
［］［］；ｉｉ Ａ＋＝ｘ＊ｘ［］；ｉ Ｂ＋＝ｘ
［］［］；ｉｉ Ｃ＋＝ｘ＊ｙ［］；ｉ Ｄ＋＝ｙ ｝
ｉｎｔｔ＝ｅｎｄ－ｓｔａｒｔ＋１； ｅｌｔａ＝Ａ＊ｔ－Ｂ＊Ｂ； ｄ
／；＝（Ｃ＊ｔ－Ｂ＊Ｄ）ｄｅｌｔａ ａ
／；Ａ＊Ｄ－Ｃ＊Ｂ）ｄｅｌｔａ ｂ＝（
（；；｛ｆｏｒｉｎｔ＝ｓｔａｒｔｎｄ＋＋） ＜＝ｅｑｑｑ
［］［］）［］［］）；１＋＝（－ａ－ｂ－ａ－ｂ ｅ＊ｘ＊（＊ｘｙｑｑｙｑｑ ｝
Ｂ＝０；Ｃ＝０；Ｄ＝０； Ａ＝０； ｝ｍｉｎ＝ｅ１；ｅｌｓｅ ｅ ｛
（ｆｏｒｉｎｔｉ＝ｓｔａｒｔ＋１；ｉ＜＝ｅｎｄ－２＊ｋ＋２；ｉ＋＋） ［］（，）（）；ｆｅｉ＝ｅ１，ｓｔａｒｔｉ＋ｅｋ－１，ｉ＋１，ｅｎｄ
ｉｎｔｍｉｎ＝ｓｔａｒｔ＋１； ［］；ｏｕｂｌｅｔｅｍ＝ｆｅｍｉｎ ｄ ｐ
（ｆｏｒｉｎｔｒ＝ｓｔａｒｔ＋１；ｒ＜＝ｅｎｄ－２＊ｋ＋２；ｒ＋＋）｛ ［］）｛ｉｆ（ｔｅｍｅｒ ｐ＞ｆ［］；ｔｅｍ＝ｆｅｒ ｐ；／／间断点ｉｎ＝ｒ ｍ ｝
，）设函数ｆ（的返回值为空，其功能是利用最小二乘１，ｓｅ，（，…，（进行一条法对一组有序对（ｘｘｘｓ，ｓ）ｓ＋１，ｓ＋１）ｅ，ｅ）ｙｙｙ（，直线拟合，得到拟合直线ｙ＝而函数ｅａｘ＋ｂ１，ｓｅ）是１１＊１１；
∧
，））其返回值为∑（相应的误差平方和，１，ｓｅ２。ｉ－ｙｆ（
，类似地，可以定义函数ｅ（为利用最小二乘法对该２，ｓｅ）组有序对进行两条直线拟合时得到的误差平方和，且其返回值为对该组有序对进行两条直线拟合时的最小误差；而ｆ（２，，）的功能是得到两条最佳的拟合直线ｙ＝ａｓｅｂ２１＊ｘ＋２１和ｙ＝ａｘ＋ｂ２２＊２２。
（，）、，，，现在利用ｅ来得到ｅ（和ｆ（１，ｓｅ１，ｓｅ）２，ｓｅ）２，ｓｆ（），具体步骤如下：ｅ
），（，…，（将该组有序对分为两组（１ｘｘｘｓ，ｓ）ｓ＋１，ｓ＋１）ｉ，ｙｙ，（，…，（，和（其中ｉｘｘｘ＝ｓ＋１，ｓ＋ｉ）ｉ＋１，ｉ＋１）ｉ＋２，ｉ＋２）ｅ，ｅ）ｙｙｙｙ…，２，ｅ－２；
）（，）），（），分别求出ｅ和ｅ（计算ｔ２１，ｓｉ１，ｉ＋１，ｅｉ＝ｅ（１，ｓ）（）；ｉ＋ｅ１，ｉ＋１，ｅ
）（）（），（，）（）；求出ｔ的最小值ｔ那么ｅ３ｉｍｉｎ２，ｓｅ＝ｔｍｉｎ），），计算ｆ（具体过程为：４２，ｓｅ
，，）调用函数ｆ（得到第一条最佳拟合直线ｙ＝ｉ．１ｓｍｉｎａ２１＊
ｘ＋ｂ２１；
，，）调用函数ｆ（得到第二最佳条拟合直线ｙ＝ｉｉ．１ｍｉｎ＋１ｅ
ａｘ＋ｂ２２＊２２。
，，类似地，可以在ｅ（和ｆ（已知的情况ｋ－１，ｓｅ）ｋ－１，ｓｅ）下，利用递归求出ｋ条最佳拟合直线及其相应的最小误差平方和，步骤如下：
），（，…，（将该组有序对分为两组（１ｘｘｘｓ，ｓ）ｓ＋１，ｓ＋１）ｉ，ｙｙ，（，…，（，和（其中ｉｘｘｘ＝ｓ＋１，ｓ＋ｉ）ｉ＋１，ｉ＋１）ｉ＋２，ｉ＋２）ｅ，ｅ）ｙｙｙｙ…，２，ｅ－２；
）（，）（），（）（分别求出ｅ和ｅ计算ｔ２１，ｓｉｋ－１，ｉ＋１，ｅｉ＝ｅ１，，）（）；ｓｉ＋ｅｋ－１，ｉ＋１，ｅ
）（）（），（，）（）；求出ｔ的最小值ｔ那么ｅ３ｉｍｉｎｋ，ｓｅ＝ｔｍｉｎ
·４８３·
；ｍｉｎ＝ｔｅｍ ｅｐ ｝ ｝
ｅｔｕｒｎｅｍｉｎ； ｒ ｝
００６．４１４６８０４７５２８０４＊ｘ－１９７３８２８．８５２１６１２２５９ｙ＝１
误差为：４５５２３３．６３７０７４３４２０６第三条直线从ｘ＝２００１到ｘ＝２００７解析式为：
９８．６２１６５３２１３７９２９＊ｘ－１７５９６５３．８１８２３９７９６ｙ＝８
误差为：９１８９２８．４６７７５４４３１４第四条直线从ｘ＝２００８到ｘ＝２００９解析式为：
２２５．８３７３５００１０８７２＊ｘ＋４５１２８０６．３３７７６８５５５ｙ＝－２
误差为：８．９０２７３０４８４２４０６７３Ｅ－９误差之和为：１６０７９６０．０９０７３９８７１
结束语 以上实例说明，采用改进的最小二乘法进行分段直线拟合，在对实验数据进行处理的过程中，能明显地简化能够更好地对点序列进行拟合，数学模型的建立和减少计算，
从而证明本方法是可行的。另一方面，本方法可以自动确定分线段数，自动寻找折点位置，得到整体最优拟合，从而证明本方法是高效的。
但是本方法也有一定的局限性，即对随机变化的数据进但是对变化比较缓慢的数行拟合时往往得不到理想的结果，
［］ｘ２０００ ２００１ ２００２ ２００３ ２００４ ２００５ ２００６ ２００７ ２００８ ２００９
［］ｙ３９１７５．２１４７４７３８９５９．０８２４６１３９１４８．６９９２４７３９７８８．２０５８９９４０９０７．７５４１９１４２５３４．８１７９０６４３２５８．３５１４７８４３６９０．９１２４００４３３２４．９３８８８２４１０９９．１０１５３２
计算拟合直线条数的Ｊａｖａ代码：
（）｛ｉｎｔｋ ｉｎｔｉ＝３；
（；／）；｛ｆｏｒｉ２ｎｉ＋＋） ＜＝（
（（）（）／（）ｉｆ（ｅｉ－２，０，ｎ－１－ｅｉ－１，０，ｎ－１）ｅｉ－２，０，ｎ－１ｅ＜β＆＆（（）（，））／（））｛ｉ－１，０，ｎ－１－ｅｉ０，ｎ－１ｅｉ－１，０，ｎ－１＜β；ｂｒｅａｋ ｝｝
；ｅｔｕｒｎｉ ｒ ｝
３．３ 实例说明
表１是某工程中的观测数据。假设阈值为４现利用０％，改进的最小二乘法对其进行分段直线拟合。
表１
［］ｘ１９９０ １９９１ １９９２ １９９３ １９９４ １９９５ １９９６ １９９７ １９９８ １９９９
［］ｙ
３１６３６．２９９７６３ ３１０９０．６６００１７ ３１７２９．４１３７５８ ３２２２６．４１１９３６ ３３２０２．９２９２０１ ３３６８９．０４２６５２ ３４５９６．１４４３０３ ３５８０４．４４２８８２ ３６９４０．３３９４１８ ３８１８９．９３４１２３
尤其是单调或者近似单调的数据。据可以得到较好的效果，
在实际工作中，试验取得的数据往往是非随机变化的，因此本方法的应用范围还是比较广泛的。
参考文献
［］赫尔穆特·鲁克波尔，马库斯·克莱茨希．应用时间序列计量经１
济学［行健，邓可斌，译．北京：机械工业出版社，Ｍ］．２００８［］都强，］杭柏林．最小二乘法在多传感器测量标定中的应用［传２Ｊ．
（）：感技术学校，２００５，１８２２４４２４６－
［］谢友宝．］最小二乘法分段直线拟合［南昌航空工业学院学报，３Ｊ．
（）：１９９２２１９２５－
［］程玉民．］移动最小二乘法研究进展与述评［计算机辅助工程，４Ｊ．
（）：２００９，１８２５１１－
［］张东林．］：分段最小二乘法曲线拟合［沈阳大学学报，５Ｊ．１９９４（２）
８０８３－
［］Ｐ［］６ｌａｃｋｅｔｔＲＬ．ＴｈｅｄｉｓｃｏｖｅｒｏｆｔｈｅｍｅｔｈｏｄｏｆｌｅａｓｔｓｕａｒｅｓＪ． ｙｑ
，１９７２，５９：２３９２５１Ｂｉｏｍｅｔｒｉｋａ－
［］Ｂ７ａｔｅｓＤ Ｍ，ＷａｔｔｓＤＧ．Ｎｏｎｌｉｎｅａｒｒｅｒｅｓｓｉｏｎａｎａｌｓｉｓａｎｄｉｔｓａ －ｇｙｐ
［，ｌｉｃａｔｉｏｎｓＭ］．Ｎｅｗ Ｙｏｒｋ：Ｗｉｌｅ１９８８ｐｙ
［］Ｈ８ａｒｅｒＨ Ｌ．Ｔｈｅｍｅｔｈｏｄｏｆｌｅａｓｔｓｕａｒｅｓａｎｄｓｏｍｅａｌｔｅｒｎａｔｉｖｅｓ ｐｑ
分段直线拟合图如图１所示。
图１
［，，，Ｍ］．ＰａｒｔＩＩＩＩＩＩＶ，Ｖ，ＶＩ．ＩｎｔｅｒｎａｔｉｏｎａｌＳｔａｔｉｓｔｉｃａｌＲｅｖｉｅｗ， ；４２，１４７１７４；４２，２３５２６４；４３，１４４；４３，１２５１９０；４３，２６９２７２４４，－－－－－１１３１５９－
［］Ｓ９ｈｉｍｉｚｕＴ，ＫｏｃｈｉＳ，ＩｋｅｈａｒａＭ．Ａ ＤｅｓｉｎｏｆＤｕａｌｒｅｅＣｏｍ－ －Ｔ ｙｇ
ｌｅｘ ＷａｖｅｌｅｔＴｒａｎｓｆｏｒｍＢａｓｅｄｏｎＬｅａｓｔＳｕａｒｅｓＭｅｔｈｏｄ［Ｃ］ ∥ｐｑＤｉｉｔａｌＳｉｎａｌＰｒｏｃｅｓｓｉｎＷｏｒｋｓｈｏａｎｄ５ｔｈＩＥＥＥＳｉｎａｌＰｒｏ －ｇｇｇ ｐｇ ｃｅｓｓｉｎＥｄｕｃａｔｉｏｎ Ｗｏｒｋｓｈｏ．２００９：５７６５８１－ｇｐ
第一条直线从ｘ＝１９９０到ｘ＝１９９２解析式为：
６．５５７０００００１２７１５７＊ｘ－６１２０９．５２９１７４８０４６９ｙ＝４
误差为：２３３７９７．９８５９１１０８８５３第二条直线从ｘ＝１９９３到ｘ＝２０００解析式为：
·４
８４·
第３９卷 第６Ａ期２０１２年６月计算机科学
ＣｏｍｕｔｅｒｃｉｅｎｃｅＳＶｏｌ．３９Ｎｏ．６Ａ
Ｊｕｎｅ２０１２最小二乘法分段直线拟合
田 垅 刘宗田
（）上海大学计算机工程与科学学院 上海２０００７２
摘 要 曲线拟合是图像分析中非常重要的描述符号。最常用的曲线拟合方法是最小二乘法，然而一般的最小二乘法有一定的局限性，已经有不少学者对其进行了一些改进。进一步对最小二乘法进行改进，提出一种新的分段直线拟合算法来代替多项式曲线拟合，以达到简化数学模型的建立和减少计算的目的，使其能够更好地对点序列进行拟合。关键词 直线拟合，最小二乘法，分段
中图法分类号 ＴＰ３０１ 文献标识码 Ａ
ＬｅａｓｔｓｕａｒｅｓＭｅｔｈｏｄＰｉｅｃｅｗｉｓｅＬｉｎｅａｒＦｉｔｔｉｎ－ ｑｇ
ＴＩＡＮＬｏｎＩＵＺｏｎｔｉａｎ Ｌ －ｇｇ
（，，）ＳｃｈｏｏｌｏｆＣｏｍｕｔｅｒＥｎｉｎｅｅｒｉｎ＆ＳｃｉｅｎｃｅＳｈａｎｈａｉＵｎｉｖｅｒｓｉｔＳｈａｎｈａｉ２０００７２，Ｃｈｉｎａ ｐｇｇ ｇｙｇ
，Ａｂｓｔｒａｃｔｕｒｖｅｆｉｔｔｉｎｉｓａｖｅｒｉｍｏｒｔａｎｔｄｅｓｃｒｉｔｏｒｉｎｉｍａｅａｎａｌｓｉｓｔｈｅｍｏｓｔｃｏｍｍｏｎｌｕｓｅｄｃｕｒｖｅｆｉｔｔｉｎｍｅｔｈｏｄｉｓ Ｃ ｇｙｐｐｇｙｙｇ ，ｓｕａｒｅｓｍｅｔｈｏｄ．Ｂｕｔｏｒｄｉｎａｒｌｅａｓｔｓｕａｒｅｓｍｅｔｈｏｄｈａｓｓｏｍｅｌｉｍｉｔａｔｉｏｎｓａｎｄｔｈｅｒｅａｒｅｍａｎｓｃｈｏｌａｒｓｈａｖｅｍａｄｅｌｅａｓｔ－ － ｑｙｑｙ ｒｏｏｓｅｄｉｅｃｅｗｉｓｅｓｔｕｄｏｆｉｍｒｏｖｉｎｉｔ．Ｔｈｅａｕｔｈｏｒｓｍａｄｅｆｕｒｔｈｅｒｉｍｒｏｖｅｍｅｎｔｏｎｌｅａｓｔｓｕａｒｅｓｍｅｔｈｏｄａｎｄａｎｅｗ － ｐｐｐｙｐｇｐｑ ｌｉｎｅａｒｆｉｔｔｉｎａｌｏｒｉｔｈｍｉｎｓｔｅａｄｏｆｏｌｎｏｍｉａｌｃｕｒｖｅｆｉｔｔｉｎ．Ｔｈｅｎｅｗａｌｏｒｉｔｈｍａｃｈｉｅｖｅｓｔｈｅｏａｌｏｆｓｉｍｌｉｆｉｎｔｈｅｍａｔｈ －ｇｇｐｙｇｇｇｐｙｇ ，，ｏｉｎｔｅｍａｔｉｃａｌｍｏｄｅｌｒｅｄｕｃｉｎｔｈｅｃａｌｃｕｌａｔｉｏｎａｎｄｍａｋｅｓｉｔｂｅｔｔｅｒｔｏｆｉｔｓｅｕｅｎｃｅ． ｐｇｑ ，，ＫｅｗｏｒｄｓｉｎｅａｒｆｉｔｔｉｎＬｅａｓｔｓｕａｒｅｓｍｅｔｈｏｄＰｉｅｃｅｗｉｓｅ Ｌ － ｇｑｙ
往往是有序数对，根据误差平方和最小化原则，找出这些数据的最佳函数匹配。
（最小二乘法的数学原理为：给定一组数据（ｘｉ＝１，ｉ，ｉ）ｙ…，，，设其经验方程为Ｆ（方程中含有一些待定系数２，ｎ）ｘ），代入方程求差ｙ为了考虑整体的误ａｘｘｎ。将（ｉ，ｉ）ｉ－Ｆ（ｉ）ｙ可以取平方和，之所以要平方是考虑到误差正负直接相加差，
可以相互抵消，所以记误差为：
∧
）ｅ＝∑（Ｆ（ｘ２ｉ－ｉ）ｙ
１ 引言
在工程技术和科学实验中，常常得到两个有函数关系观测量的一系列有序对。如何根据这些有序对来确定它们的函这就是实验数据处理中的曲线拟合问题。曲线拟合数曲线，
如在计量经济学领域中可以利用历年的经的应用十分广泛，
１］
，济统计数据来预测下一阶段的经济发展趋势［在医学统计
学领域中可以通过发现某种毒物剂量与动物死亡率之间的定在传感技术领域可以用于多传感器量关系来指导医学工作，
２］
。常用的曲线拟合方法是最小二乘法。最小二乘测量标定［
通过求ｅ的极小值可以求出ａ从而求出该组数据的最ｎ，该函数使得误差平方和最小。佳拟合函数，
最小二乘法不仅可以用于曲线拟合，也可以用于直线拟合。如果经验方程Ｆ（是线性的，形如ｙ＝ａ＊ｘ＋那么利ｘ）ｂ，用最小二乘法得到的就是线性回归。
５］
张东林［对最小二乘法进行了改进，即将ｎ个有序对
法（又称最小平方法）是一种数学优化技术，它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以并使得这些求得的数据与实际数据简便地求得未知的数据，
之间误差的平方和最小。在利用最小二乘法实现曲线拟合虽然能够很好地拟合有序对，并且有很好的数学理论支时，
４］
持［和很高的精确度，但是需要进行大量复杂的计算，而且得
（（…，…，分成ｋ组Ｎ１，ｘｉ＝１，２，ｎ）Ｎ２，Ｎｋ：ｉ，ｉ）ｙ
，（，…，（（ｘｘｘ１１，１１）１２，１２）１Ｎ１，１Ｎ１）ｙｙｙ （，（，…，（ｘｘｘ２１，２１）２２，２２）２Ｎ２，２Ｎ２）ｙｙｙ …
（，（，…，（ｘｘｘｋ１，ｋ１）ｋ２，ｋ２）ｋＮｋ，ｋＮｋ）ｙｙｙ
然后对每组有序对进行线性拟合，得到ｋ条拟合直线（…，。张东林的这种算法虽然ｘ）＝ａｘ＋ｂｉ＝１，２，ｋ）ｉ（ｉ＊ｙ＝ｇ
能够实现分段直线拟合，并且进一步可以实现曲线拟合，但是…，其并没有给出ｋ和Ｎｉ（的取值规定。ｉ＝１，２，ｋ）
到的拟合函数往往是高次的，这进一步增加了复杂性。为了减少计算量，本文提出了一种新的简化建立数学模型的算法，
利用最小二乘法实现分段直线拟合的方法，以对观测到的有序对进行建模。
２ 最小二乘法研究现状
最小二乘法的基本思想是：给定一组实验数据，这些数据
），）本文受国家自然科学基金（国际竹藤组织基础科学研究项目（资助。６０９７５０３３１６３２００９００６
，：，田 垅（男，硕士生，主要研究方向为自然语言处理和数据挖掘，刘宗田（男，教授，博士生导师，１９８７－）Ｅ－ｍａｉｌｈｕｂｕ１９３１＠１６３．ｃｏｍ；１９４６－）主要研究方向为智能信息处理、软件工程等。
·４８２·
３］
谢友宝［也对最小二乘法进行了改进。设拟合直线初始
），），计算ｆ（具体过程为：４ｋ，ｓｅ
，，）调用函数ｆ（得到第一条最佳拟合直线ｙ＝ｉ．１ｓｍｉｎａｋ１＊
、，起点和初始终点为Ｓ（设终点的下一个点ｘＥ（ｘｓ，ｓ）ｅ，ｅ）ｙｙ，为Ｎ（计算线段ＥｘＳ和ＳＮ的夹角为：ｎ，ｎ）ｙ
（）／（ＳＮ＝ａｒｃｃｏｓＳＥ２＋｜ＳＮ２－｜ＥＮ２２ＳＥ∠Ｅ｜｜｜｜｜｜＊
）ＳＮ｜｜
式中，ＳＥＳＮＥＮＥ、ＳＮ、ＥＮ的长度。｜｜、｜｜、｜｜分别为线段Ｓ
观察这个角度是否小于给定的阈值，若小于阈值，则将Ｅ和Ｎ往后移一位重新计算，直到大于阈值；否则用最小二乘法计算拟合直线。谢友宝的这种算法虽然实现了有序对的分段直线拟合，并且得到了一种最优的解决方案，但是他没有从整体上来考虑，得到的只是局部最优，而局部最优不一定是整体最优。在此作者进一步对最小二乘进行改进，使其能够从整体上给出最优的分段直线拟合。
ｘ＋ｂｋ１；
）调用函数ｆ（得到ｋ－１条最佳拟合直ｉｉ．ｋ－１，ｍｉｎ＋１，ｅ…，线ｙ＝其中ｊ＝２，ａｘ＋ｂ３，ｋ。ｋｋｊ＊ｊ，
但是如何确定拟合直线的条数呢？一种方法是根据具体人工进行设定；另一种方法是给定一个阈值β，的工程需求，
若连续两次误差平方和的降幅低于这个阈值，则停止拟合的（，），）／，计算，比如，若（ｅｋ－３，ｓｅ－ｅ（ｋ－２，ｓｅ）ｅ（ｋ－３，ｓｅ）＞β（，）（，）／，（，且（ｅｋ－２，ｓｅ－ｅｋ－１，ｓｅ）ｅ（ｋ－２，ｓｅ）ｅ（ｋ－１，ｓ＜β，）（，））／ｅ（，则设定拟合直线的条数为ｅ－ｅｋ，ｓｅｋ－１，ｓｅ）＜β，
ｋ。
３．２ 实现该算法的部分ｊａｖａ代码
３ 改进的最小二乘法分段直线拟合
３．１ 基本思想
］，］）（…，，给定一组有序对（假设ｘｘ［ｉｉｉ＝０，１，ｎ－１）ｙ［为整型数组，给定的阈值为β。ｙ为双精度浮点型数组；
计算误差的Ｊａｖａ代码：
（，）｛ｄｏｕｂｌｅｅｉｎｔｋ，ｉｎｔｓｔａｒｔｉｎｔｅｎｄ ｏｕｂｌｅｅｍｉｎ＝０； ｄ
［］［］；ｏｕｂｌｅｆｅ＝ｎｅｗｄｏｕｂｌｅｎ ｄ ／一条直线拟合 ／
（）｛ｉｆｋ＝＝１
；ｏｕｂｌｅＡ＝０，Ｂ＝０，Ｃ＝０，Ｄ＝０，ｄｅｌｔａ ｄ ｏｕｂｌｅｅ１＝０； ｄ ，ｏｕｂｌｅａｂ； ｄ
（；；ｆｏｒｉｎｔｉ＝ｓｔａｒｔｉｎｄｉ＋＋） ＜＝ｅ ｛
［］［］；ｉｉ Ａ＋＝ｘ＊ｘ［］；ｉ Ｂ＋＝ｘ
［］［］；ｉｉ Ｃ＋＝ｘ＊ｙ［］；ｉ Ｄ＋＝ｙ ｝
ｉｎｔｔ＝ｅｎｄ－ｓｔａｒｔ＋１； ｅｌｔａ＝Ａ＊ｔ－Ｂ＊Ｂ； ｄ
／；＝（Ｃ＊ｔ－Ｂ＊Ｄ）ｄｅｌｔａ ａ
／；Ａ＊Ｄ－Ｃ＊Ｂ）ｄｅｌｔａ ｂ＝（
（；；｛ｆｏｒｉｎｔ＝ｓｔａｒｔｎｄ＋＋） ＜＝ｅｑｑｑ
［］［］）［］［］）；１＋＝（－ａ－ｂ－ａ－ｂ ｅ＊ｘ＊（＊ｘｙｑｑｙｑｑ ｝
Ｂ＝０；Ｃ＝０；Ｄ＝０； Ａ＝０； ｝ｍｉｎ＝ｅ１；ｅｌｓｅ ｅ ｛
（ｆｏｒｉｎｔｉ＝ｓｔａｒｔ＋１；ｉ＜＝ｅｎｄ－２＊ｋ＋２；ｉ＋＋） ［］（，）（）；ｆｅｉ＝ｅ１，ｓｔａｒｔｉ＋ｅｋ－１，ｉ＋１，ｅｎｄ
ｉｎｔｍｉｎ＝ｓｔａｒｔ＋１； ［］；ｏｕｂｌｅｔｅｍ＝ｆｅｍｉｎ ｄ ｐ
（ｆｏｒｉｎｔｒ＝ｓｔａｒｔ＋１；ｒ＜＝ｅｎｄ－２＊ｋ＋２；ｒ＋＋）｛ ［］）｛ｉｆ（ｔｅｍｅｒ ｐ＞ｆ［］；ｔｅｍ＝ｆｅｒ ｐ；／／间断点ｉｎ＝ｒ ｍ ｝
，）设函数ｆ（的返回值为空，其功能是利用最小二乘１，ｓｅ，（，…，（进行一条法对一组有序对（ｘｘｘｓ，ｓ）ｓ＋１，ｓ＋１）ｅ，ｅ）ｙｙｙ（，直线拟合，得到拟合直线ｙ＝而函数ｅａｘ＋ｂ１，ｓｅ）是１１＊１１；
∧
，））其返回值为∑（相应的误差平方和，１，ｓｅ２。ｉ－ｙｆ（
，类似地，可以定义函数ｅ（为利用最小二乘法对该２，ｓｅ）组有序对进行两条直线拟合时得到的误差平方和，且其返回值为对该组有序对进行两条直线拟合时的最小误差；而ｆ（２，，）的功能是得到两条最佳的拟合直线ｙ＝ａｓｅｂ２１＊ｘ＋２１和ｙ＝ａｘ＋ｂ２２＊２２。
（，）、，，，现在利用ｅ来得到ｅ（和ｆ（１，ｓｅ１，ｓｅ）２，ｓｅ）２，ｓｆ（），具体步骤如下：ｅ
），（，…，（将该组有序对分为两组（１ｘｘｘｓ，ｓ）ｓ＋１，ｓ＋１）ｉ，ｙｙ，（，…，（，和（其中ｉｘｘｘ＝ｓ＋１，ｓ＋ｉ）ｉ＋１，ｉ＋１）ｉ＋２，ｉ＋２）ｅ，ｅ）ｙｙｙｙ…，２，ｅ－２；
）（，）），（），分别求出ｅ和ｅ（计算ｔ２１，ｓｉ１，ｉ＋１，ｅｉ＝ｅ（１，ｓ）（）；ｉ＋ｅ１，ｉ＋１，ｅ
）（）（），（，）（）；求出ｔ的最小值ｔ那么ｅ３ｉｍｉｎ２，ｓｅ＝ｔｍｉｎ），），计算ｆ（具体过程为：４２，ｓｅ
，，）调用函数ｆ（得到第一条最佳拟合直线ｙ＝ｉ．１ｓｍｉｎａ２１＊
ｘ＋ｂ２１；
，，）调用函数ｆ（得到第二最佳条拟合直线ｙ＝ｉｉ．１ｍｉｎ＋１ｅ
ａｘ＋ｂ２２＊２２。
，，类似地，可以在ｅ（和ｆ（已知的情况ｋ－１，ｓｅ）ｋ－１，ｓｅ）下，利用递归求出ｋ条最佳拟合直线及其相应的最小误差平方和，步骤如下：
），（，…，（将该组有序对分为两组（１ｘｘｘｓ，ｓ）ｓ＋１，ｓ＋１）ｉ，ｙｙ，（，…，（，和（其中ｉｘｘｘ＝ｓ＋１，ｓ＋ｉ）ｉ＋１，ｉ＋１）ｉ＋２，ｉ＋２）ｅ，ｅ）ｙｙｙｙ…，２，ｅ－２；
）（，）（），（）（分别求出ｅ和ｅ计算ｔ２１，ｓｉｋ－１，ｉ＋１，ｅｉ＝ｅ１，，）（）；ｓｉ＋ｅｋ－１，ｉ＋１，ｅ
）（）（），（，）（）；求出ｔ的最小值ｔ那么ｅ３ｉｍｉｎｋ，ｓｅ＝ｔｍｉｎ
·４８３·
；ｍｉｎ＝ｔｅｍ ｅｐ ｝ ｝
ｅｔｕｒｎｅｍｉｎ； ｒ ｝
００６．４１４６８０４７５２８０４＊ｘ－１９７３８２８．８５２１６１２２５９ｙ＝１
误差为：４５５２３３．６３７０７４３４２０６第三条直线从ｘ＝２００１到ｘ＝２００７解析式为：
９８．６２１６５３２１３７９２９＊ｘ－１７５９６５３．８１８２３９７９６ｙ＝８
误差为：９１８９２８．４６７７５４４３１４第四条直线从ｘ＝２００８到ｘ＝２００９解析式为：
２２５．８３７３５００１０８７２＊ｘ＋４５１２８０６．３３７７６８５５５ｙ＝－２
误差为：８．９０２７３０４８４２４０６７３Ｅ－９误差之和为：１６０７９６０．０９０７３９８７１
结束语 以上实例说明，采用改进的最小二乘法进行分段直线拟合，在对实验数据进行处理的过程中，能明显地简化能够更好地对点序列进行拟合，数学模型的建立和减少计算，
从而证明本方法是可行的。另一方面，本方法可以自动确定分线段数，自动寻找折点位置，得到整体最优拟合，从而证明本方法是高效的。
但是本方法也有一定的局限性，即对随机变化的数据进但是对变化比较缓慢的数行拟合时往往得不到理想的结果，
［］ｘ２０００ ２００１ ２００２ ２００３ ２００４ ２００５ ２００６ ２００７ ２００８ ２００９
［］ｙ３９１７５．２１４７４７３８９５９．０８２４６１３９１４８．６９９２４７３９７８８．２０５８９９４０９０７．７５４１９１４２５３４．８１７９０６４３２５８．３５１４７８４３６９０．９１２４００４３３２４．９３８８８２４１０９９．１０１５３２
计算拟合直线条数的Ｊａｖａ代码：
（）｛ｉｎｔｋ ｉｎｔｉ＝３；
（；／）；｛ｆｏｒｉ２ｎｉ＋＋） ＜＝（
（（）（）／（）ｉｆ（ｅｉ－２，０，ｎ－１－ｅｉ－１，０，ｎ－１）ｅｉ－２，０，ｎ－１ｅ＜β＆＆（（）（，））／（））｛ｉ－１，０，ｎ－１－ｅｉ０，ｎ－１ｅｉ－１，０，ｎ－１＜β；ｂｒｅａｋ ｝｝
；ｅｔｕｒｎｉ ｒ ｝
３．３ 实例说明
表１是某工程中的观测数据。假设阈值为４现利用０％，改进的最小二乘法对其进行分段直线拟合。
表１
［］ｘ１９９０ １９９１ １９９２ １９９３ １９９４ １９９５ １９９６ １９９７ １９９８ １９９９
［］ｙ
３１６３６．２９９７６３ ３１０９０．６６００１７ ３１７２９．４１３７５８ ３２２２６．４１１９３６ ３３２０２．９２９２０１ ３３６８９．０４２６５２ ３４５９６．１４４３０３ ３５８０４．４４２８８２ ３６９４０．３３９４１８ ３８１８９．９３４１２３
尤其是单调或者近似单调的数据。据可以得到较好的效果，
在实际工作中，试验取得的数据往往是非随机变化的，因此本方法的应用范围还是比较广泛的。
参考文献
［］赫尔穆特·鲁克波尔，马库斯·克莱茨希．应用时间序列计量经１
济学［行健，邓可斌，译．北京：机械工业出版社，Ｍ］．２００８［］都强，］杭柏林．最小二乘法在多传感器测量标定中的应用［传２Ｊ．
（）：感技术学校，２００５，１８２２４４２４６－
［］谢友宝．］最小二乘法分段直线拟合［南昌航空工业学院学报，３Ｊ．
（）：１９９２２１９２５－
［］程玉民．］移动最小二乘法研究进展与述评［计算机辅助工程，４Ｊ．
（）：２００９，１８２５１１－
［］张东林．］：分段最小二乘法曲线拟合［沈阳大学学报，５Ｊ．１９９４（２）
８０８３－
［］Ｐ［］６ｌａｃｋｅｔｔＲＬ．ＴｈｅｄｉｓｃｏｖｅｒｏｆｔｈｅｍｅｔｈｏｄｏｆｌｅａｓｔｓｕａｒｅｓＪ． ｙｑ
，１９７２，５９：２３９２５１Ｂｉｏｍｅｔｒｉｋａ－
［］Ｂ７ａｔｅｓＤ Ｍ，ＷａｔｔｓＤＧ．Ｎｏｎｌｉｎｅａｒｒｅｒｅｓｓｉｏｎａｎａｌｓｉｓａｎｄｉｔｓａ －ｇｙｐ
［，ｌｉｃａｔｉｏｎｓＭ］．Ｎｅｗ Ｙｏｒｋ：Ｗｉｌｅ１９８８ｐｙ
［］Ｈ８ａｒｅｒＨ Ｌ．Ｔｈｅｍｅｔｈｏｄｏｆｌｅａｓｔｓｕａｒｅｓａｎｄｓｏｍｅａｌｔｅｒｎａｔｉｖｅｓ ｐｑ
分段直线拟合图如图１所示。
图１
［，，，Ｍ］．ＰａｒｔＩＩＩＩＩＩＶ，Ｖ，ＶＩ．ＩｎｔｅｒｎａｔｉｏｎａｌＳｔａｔｉｓｔｉｃａｌＲｅｖｉｅｗ， ；４２，１４７１７４；４２，２３５２６４；４３，１４４；４３，１２５１９０；４３，２６９２７２４４，－－－－－１１３１５９－
［］Ｓ９ｈｉｍｉｚｕＴ，ＫｏｃｈｉＳ，ＩｋｅｈａｒａＭ．Ａ ＤｅｓｉｎｏｆＤｕａｌｒｅｅＣｏｍ－ －Ｔ ｙｇ
ｌｅｘ ＷａｖｅｌｅｔＴｒａｎｓｆｏｒｍＢａｓｅｄｏｎＬｅａｓｔＳｕａｒｅｓＭｅｔｈｏｄ［Ｃ］ ∥ｐｑＤｉｉｔａｌＳｉｎａｌＰｒｏｃｅｓｓｉｎＷｏｒｋｓｈｏａｎｄ５ｔｈＩＥＥＥＳｉｎａｌＰｒｏ －ｇｇｇ ｐｇ ｃｅｓｓｉｎＥｄｕｃａｔｉｏｎ Ｗｏｒｋｓｈｏ．２００９：５７６５８１－ｇｐ
第一条直线从ｘ＝１９９０到ｘ＝１９９２解析式为：
６．５５７０００００１２７１５７＊ｘ－６１２０９．５２９１７４８０４６９ｙ＝４
误差为：２３３７９７．９８５９１１０８８５３第二条直线从ｘ＝１９９３到ｘ＝２０００解析式为：
·４
８４·