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

Simple Linear Regression (Least Squares)

Fit the best straight line through data points with the least squares formulas.

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

  • Fit a line with closed-form formulas
  • Compute slope and intercept
  • Understand what best fit means

Đề bài

Xem bản dịch

Linear regression finds the line y = slope × x + intercept that best fits the data, meaning the sum of squared errors is as small as possible. For one input variable there is an exact formula:

  • slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
  • intercept = ȳ - slope × x̄

where x̄ and ȳ are the means of xs and ys. If all xs are equal, return slope 0 and intercept ȳ.

Implement linear_regression(xs, ys).

Input

xs, ys: The x and y values of the data points (same length).

Output

Return [slope, intercept].

Ràng buộc

1 ≤ number of points ≤ 10,000

-10,000 ≤ each value ≤ 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

The points lie exactly on y = 2x + 1. x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 and Σ(x - x̄)² = 5, so slope = 2 and 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 and ȳ = 2. Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 and Σ(x - x̄)² = 2, so slope = 0.5 and 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

The best-fit line comes from how x and y vary together around their means.

Gợi ý 2

Compute the means first, then accumulate the numerator and denominator for the slope formula.

Gợi ý 3

If all x-values are the same, the slope is undefined, so return a flat line through the average y-value.

Độ phức tạp mong đợi

O(n) time, O(1) extra space

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.