کمترین مربعات (برازش خط)
خطی را پیدا می‌کند که جمع مربع فاصله‌های عمودی نقطه‌ها از آن کمترین باشد؛ با حل دو معادله‌ی نرمال، با کسرهای دقیق.
نقطه‌های (x, y) تقریباً روی یک خط‌اند ولی دقیقاً نه. کمترین مربعات خطی y = c0 + c1·x را انتخاب می‌کند که جمع مربع خطاها Σ (y − c0 − c1·x)² کمترین باشد.
- زمان:
O(n) - حافظه:
O(n) - CLRS، بخش ۲۸.۳
پنج نقطه که تقریباً روی یک خط‌اند؛ خط برازش y = 3/5 + 21/10·x است و خطاها جمع صفر دارند.
from fractions import Fractiondef least_squares(points):# The line y = c0 + c1·x with the smallest sum of squared vertical errors.n = len(points)sx = sy = sxx = sxy = 0for x, y in points:sx = sx + xsy = sy + ysxx = sxx + x * xsxy = sxy + x * y# The normal equations: n·c0 + sx·c1 = sy and sx·c0 + sxx·c1 = sxy.det = n * sxx - sx * sxif det == 0:return Nonec0 = Fraction(sy * sxx - sx * sxy, det)c1 = Fraction(n * sxy - sx * sy, det)rows = []for x, y in points:guess = c0 + c1 * xrows.append((x, y, guess, y - guess))return str(c0), str(c1)
شروع اجرا
points
| 0 | 1 |
| 1 | 2 |
| 2 | 5 |
| 3 | 7 |
| 4 | 9 |
rows
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
points list
Call stack
- least_squares()خط 4
توضیح
ایده
نقطه‌های (x, y) تقریباً روی یک خط‌اند ولی دقیقاً نه. کمترین مربعات خطی y = c0 + c1·x را انتخاب می‌کند که جمع مربع خطاها Σ (y − c0 − c1·x)² کمترین باشد.
معادله‌های نرمال
با مشتق‌گیری نسبت به c0 و c1 و برابر صفر قرار دادن، دو معادله‌ی خطی به دست می‌آید:
n·c0 + Σx·c1 = Σy
Σx·c0 + Σx²·c1 = Σxy
این همان Aᵀ·A·c = Aᵀ·y است که A ستون‌های 1 و x دارد؛ برای چندجمله‌ای‌های درجه‌ی بالاتر هم همین روش با ستون‌های x², x³, … کار می‌کند.
در trace به چه چیزی نگاه کنی
- جدول
rowsبرای هر نقطه پیش‌بینی خط و خطا را نشان می‌دهد؛ جمع ستون خطا صفر است.