Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Hồi quy tuyến tính đơn (bình phương tối thiểu)

Tìm đường thẳng khớp nhất với các điểm dữ liệu bằng công thức bình phương tối thiểu.

Bạn sẽ học được gì

  • Khớp đường thẳng bằng công thức đóng
  • Tính hệ số góc và hệ số chặn
  • Hiểu thế nào là khớp tốt nhất

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.