C++로 주어진 점 집합을 가장 잘 나타내는 직선 구하기

이 글에서는 주어진 점 집합을 가장 잘 표현하는 직선을 구하는 방법을 살펴봅니다. 점들의 좌표 값(x, y)이 주어졌을 때, 최적의 직선 y = mx + c를 찾아야 합니다. 즉, 우리가 구해야 할 것은 기울기 m과 y절편 c의 값입니다.

입력: no_of_points = 4
x1 = 2, y1 = 3,
x2 = 5, y2 = 6,
x3 = 1, y3 = 3,
x4 = 4, y4 = 5.

출력: m = 0.8, c = 1.85
설명: 구한 m과 c의 값을 식 y = mx + c에 대입하면 모든 점을 포괄하는 최적의 직선을 얻을 수 있습니다.
(x2, y2)에 m과 c를 대입하면,
좌변(L.H.S): mx + c = 0.8 * 5 + 1.85 = 5.85
우변(R.H.S): y = 6 으로 좌변과 거의 일치합니다.

입력: no_of_points = 3
x1 = 3, y1 = 6,
x2 = 2, y2 = 4,
x3 = 1, y3 = 3,

출력: m = 1.5, c = 1.33

해결 접근 방법

이 문제를 해결하려면 m과 c의 값을 구해야 합니다. 점이 정확히 2개일 때는 유일한 해가 존재하지만, 점이 2개보다 많아지면 모든 점을 지나는 직선이 존재하지 않을 수도 있습니다.

점의 개수를 n이라고 하겠습니다. 그러면 n개의 방정식 f_i = mx_i + c를 얻게 됩니다.

이 직선이 최적의 적합(best fit)이 되려면 각 f_i의 값이 실제 값 y_i와 같거나 최대한 가까워야 합니다.

Z = (f_i − y_i)² 로 정의해 보겠습니다. 음수 값의 영향을 상쇄하기 위해 (f_i − y_i) 항을 제곱했습니다. 이제 모든 점에 대해 Z의 값을 최소화하는 것이 목표입니다.

Z가 최솟값이 되려면 다음 조건을 만족해야 합니다.

∂Z/∂m = 0 그리고 ∂Z/∂c = 0

이 방정식들을 풀면 다음 두 식을 얻습니다.

Σy = m · Σx + n · c
Σxy = m · Σx² + c · Σx

이를 정리하면,

m = (n · Σxy − Σx · Σy) / (n · Σx² − (Σx)²)
c = (Σy − m · Σx) / n

이제 최종 직선의 m과 c를 구할 수 있는 직접적인 공식을 얻었습니다.

예제

위 접근 방식의 C++ 코드

#include <cmath>
#include <iostream>
using namespace std;
int main(){
    int X[] = { 3, 2, 1 };
    int Y[] = { 6, 4, 3};
    int no_of_points = sizeof(X) / sizeof(X[0]);
    float m, c;
    int sum_of_X = 0, sum_of_X2 = 0, sum_of_Y = 0, sum_of_XY = 0;
    // 수식에 필요한 모든 항을 계산합니다.
    for (int i = 0; i < no_of_points; i++) {
        sum_of_X = sum_of_X + X[i];
        sum_of_X2 = sum_of_X2 + pow(X[i],2);
        sum_of_Y = sum_of_Y + Y[i];
        sum_of_XY = sum_of_XY + (X[i] * Y[i]);
    }
    // 공식을 이용해 m과 c의 값을 계산합니다.
    m = (no_of_points * sum_of_XY - sum_of_X * sum_of_Y) / (no_of_points * sum_of_X2 - pow(sum_of_X,2));
    c = (sum_of_Y - m * sum_of_X) / no_of_points;
    cout << "m = " << m;
    cout << "\nc = " << c;
    return 0;
}

실행 결과

m = 1.5
c = 1.33333

결론

이 튜토리얼에서는 주어진 점 집합을 표현하는 최적 적합 직선을 찾는 방법을 알아보았습니다. 먼저 m과 c에 대한 공식을 유도한 뒤 이를 그대로 적용하는 간단한 접근 방식을 다루었으며, 이를 구현한 C++ 프로그램도 함께 살펴보았습니다. 물론 이 방법은 C, Java, Python 등 다른 프로그래밍 언어로도 동일하게 구현할 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.