Đề bài
Hồi quy tuyến tính tìm đường thẳng y = slope × x + intercept khớp nhất với dữ liệu, tức là tổng bình phương sai số nhỏ nhất. Với một biến đầu vào có công thức chính xác:
- slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
- intercept = ȳ - slope × x̄
với x̄ và ȳ là trung bình của xs và ys. Nếu mọi xs bằng nhau, trả về slope 0 và intercept ȳ.
Hãy cài đặt linear_regression(xs, ys).
Đầu vào
xs, ys: Giá trị x và y của các điểm dữ liệu (cùng độ dài).
Đầu ra
Trả về [slope, intercept].
Ràng buộc
1 ≤ số điểm ≤ 10.000
-10.000 ≤ mỗi giá trị ≤ 10.000
Ví dụ
Đầu vào:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]
Kết quả mong đợi:
expected = [2.0, 1.0]
Đầu vào:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};
Kết quả mong đợi:
std::vector<double> expected = {2.0, 1.0};
Đầu vào:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};
Kết quả mong đợi:
double[] expected = new double[] {2.0, 1.0};
Giải thích
Các điểm nằm đúng trên y = 2x + 1. x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 và Σ(x - x̄)² = 5, nên slope = 2 và intercept = 6 - 2 × 2.5 = 1.
Đầu vào:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]
Kết quả mong đợi:
expected = [0.5, 1.5]
Đầu vào:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};
Kết quả mong đợi:
std::vector<double> expected = {0.5, 1.5};
Đầu vào:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};
Kết quả mong đợi:
double[] expected = new double[] {0.5, 1.5};
Giải thích
x̄ = 1 và ȳ = 2. Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 và Σ(x - x̄)² = 2, nên slope = 0.5 và intercept = 2 - 0.5 × 1 = 1.5.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đường thẳng khớp tốt nhất đến từ cách x và y cùng biến thiên quanh mean của chúng.
Gợi ý 2
Tính mean trước, rồi cộng dồn tử số và mẫu số cho công thức slope.
Gợi ý 3
Nếu mọi giá trị x đều giống nhau, slope không xác định, nên trả về một đường ngang đi qua giá trị y trung bình.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.