파동함수 기반 버스 내부 혼잡도 알고리즘 구현

1. 혼잡도를 파동함수로 비유할 수 있지 않을까?

---

알고리즘 설계를 위해 자료를 살펴보던 중 몇 가지 문제를 얻었다.

 

1. 자료가 너무 없다.

버스 관련 api 가 너무 적다. 이에 필요한 정보 접근도 어려웠고 말이다.

또한, 내가 원했던 데이터가 존재했더라도 어떻게 활용할지 알기 힘들었다

 

2. 자료가 애매하다.

가령 30분 별 승차인원 데이터를 얻었다고 치자. 이 데이터는 30분 동안 얼마의 버스가 해당 정류장을 지나쳤을지 모른다.

관련 api를 가져와서 알고리즘을 짜야한다는 것이다.

이 외의 자료에서 간접적인 구조가 많았다.

 

궁리하던 중 문득 내가 하고 있는 이 알고리즘 설계는 알고리즘이 아니라 휴리스틱과 유사한 점이 더 많은 것 같았다.

근거는 아래와 같다.

 

나의 알고리즘이 휴리스틱과 알고리즘의 중간인 이유의 근거

• 혼잡도를 단순 데이터 계산이 아닌 경험 기반 근삿값으로 추정해야 한다.
• 사용자는 실시간으로 사용할 가능성이 높으므로 시스템은 최대한 정확하고 빠르게 판단해야 한다.
• 불완전한 정보에서 최선의 추론을 보여야 한다.
• 거의 감에 의존한다.

= 즉 완전한 확률모델이 아니다. 그러나 꽤나 잘 맞는 알고리즘을 만들어낸다면 그건 휴리스틱모델일 것이다.

 

양자역학적 관점

• 수학적 정밀도와 경험적 휴리스틱의 중간에 위치한다.
• 고정된 결정론보다는 확률 기반 비결정성을 가진다.
• 물리적 시스템이 아니라 정보 시스템의 양자역학적 유사 모델이다.

 

식을 유도하며 자세히 설명하겠다.

 

2. 양자역학 파동함수의 유도

---

혼잡도 개념을 확률화 하기 위해선 다음과 같은 조건이 필요하다.

1. 중첩. 한 정류장에서 0~1까지의  혼잡도가 동시 존재할 수 있다. *0~1이란 의미는 확률을 의미한다. 0=0%, 1=100%
2. 확률기반 예측. 예측 전에는 확률 상태이지만 결과가 나타나면 값이 결정된다.
3. 비결정성. 알고리즘이 완벽하지 않아 모든 조건이 같아도 매번 결과가 달라질 수 있다.

단, 관측이 상태를 변화시키지는 않는다. 정확히 예측했다고 해서 현실의 혼잡도 결과에 영향이 가지 않기 때문이다.

 

---

어느 노선의 버스 내부의 혼잡도는 시간대 t에 따라 다음의 확률 밀도 함수로 표현 가능하다.

확률 밀도 함수는 아래와 같은 형식이다.

 

c는 혼잡도이다. 0~1의 값을 가진다.

0 = 여유

1 = 혼잡

 

파동함수인 ψ를 제곱하고 절댓값 취한 꼴이 확률밀도함수이다.

 

나의 혼잡도에 대한 파동함수는 x좌표 c값이 0~1 사이일 혼잡도 확률 y를 가지고 있다.

따라서 정규분포 형식을 띨 것이며 다음과 같은 꼴을 가질 것이다.

*(A, λ, α 는 양의 실수이다.)

이 식의 의미는 뭘까?

 

혼잡도 c = 0~1 값 중 하나일 때, 그 값에서의 일어날 확률을 의미한다.

 

 

예를들어, c=0.8 부근에서 ψ^2=1을 가진다

= c가 0.8이라는 말은 꽤나 혼잡한 상태라는 의미 인 동시에 이 0.8이라는 혼잡이 일어날 확률이 1, "즉 반드시 일어난다"라고 해석이 가능하다.

 

하지만 이는 적분하지 않은 불연속적인 값의 해석이므로 불완전한 해석이다.

 

보기 편하게 연속된 파동함수를 e(c)라고 정의하겠다.(쓰기도 쉽게)

연속 분포로 다시 보면 다음과 같이 정리된다.

적분 내에 위치한 e(c)가 확률밀도함수이고 적분값인 P(c)가 x축 a, b에서 혼잡도가 발생할 확률이다.

 

a=0, b=1 일 경우 적분 값은 1이 된다.

왜냐하면 모든 확률을 전부 더하면 1이 되기 때문이다.

 

이 연속된 분포에 대한 확률 공식은 다음과 같다.

 

양자역학 1장 확률[Griffiths]

에서 유도한 적 있으므로 자세한 유도과정은 위 포스팅을 참고하라.

 

이 과정을 통해 얻어내거나 활용할 수 있는 정보는 다음과 같다.

1. 기대 혼잡도
2. 알고리즘에서 불확실성(오차) 범위로 활용
3. 경고 트리거
4. 보정계수

등등...

 

3. 나의 생각, 공부

---

왜 양자역학 개념을 사용하자는 아이디어가 떠올랐는지는 정확히 잘 모르겠습니다.

하지만 혼잡도를 측정할 관련 데이터를 조사하던 중 마땅한 데이터가 없었습니다.

 

그래서 "간접적으로라도 측정하자."라는 발상을 하게되었죠. 이게 시작인 듯 싶습니다.

 

제일 처음에 생각한 간접적인 방법은 연세대 교육에서 배웠던 통계기법인 회귀분석법이었습니다.

예비취업자를 위한 DIY-반도체 공정모델링 기초 [연세대BIT팹연구소]

 

종속변수인 혼잡도라는 c 값을 정의할 독립변수들인 시간, 환경, 행사, 날짜 등등...

 

명분과 근거가 적당해 보였죠. 하지만 뭔가 부족해보였습니다.

 

왜냐하면 실험할 c값이 필요했습니다.

 

그래서 어디서 이 혼잡도 값을 구하느냐?

두 가지 길이 있습니다.

1. 직접 거리로 나가 버스 내부 혼잡도를 측정하고 데이터를 축적한다.
2. 승차인원 데이터 엑셀 파일을 사용한다.

첫 번째 방법은 터무니 없습니다. 직접 전국 각지의 모든 버스 하나하나를 다 측정해야하는 문제가 있다는 거죠.

몇 년은 걸릴겁니다.

 

두 번째 방법이 그나마 나은 방법입니다. 하지만 정확한 내부 승객 인원을 제공받지는 못했습니다.

 

하지만 데이터를 다듬는 등의 활용은 가능했죠.

이 엑셀 데이터를 회귀분석용 데이터로 변환시켜야 합니다.

 

시간 별 그래프를 그려 접선, 기울기, 진폭, 분산 등을 계산할 수 있습니다.

이 변환 과정을 통해 혼잡도 c의 추측값을 추출할 수 있을 겁니다.

 

이후 독립 변수들과 종속 변수를 통해 회귀함수를 구축하면 각종 독립변수들의 계수를 찾을 수 있을 것입니다.

다른 지역마다 비슷한 계수의 값이 도출된다면 이건 완전히 성공입니다.

 

어떤 변수들이 더 혼잡도에 영향을 주는지 알 수 있게 되는 거니까요.

 

사실 이 변수들이 혼잡도 c에 주는 영향의 정도를 얻어내는게 이 회귀 분석에서의 가장 중요한 핵심 포인트입니다.

 

단순히 혼잡도 측정을 위한 방법이 아니라는 거죠.

 

저는 현재 혼잡도 측정할 방법을 찾고 있는 중입니다.

앱의 MVP를 만들기 위해선 일단 최대한 높은 정확도를 가진 극도로 단순한 알고리즘 구축하고 혼잡도를 추출해야하니까요.

 

그래서 회귀분석은 부족하다는 이야기 였습니다.

 

즉, 회귀분석법을 이용해 추출할 보정상수 정보들은 앱 배포 이후의 해야할 일들이라는 말입니다.

 

이때 즈음 "아 일단, 아주 간단한 로직에서 혼잡도 c를 먼저 추출해야겠구나"를 깨달았죠.

그래서 생각난 것이 '확률'이었습니다.

 

버스 내부의 혼잡도는 마치 제게있어서 확률 같았으니까요.

하지만 주의할 점은 양자역학에서의 확률밀도함수의 유도는 가우스 정규분포의 수학을 이용해 유도된겁니다.

저는 여기에 영감을 받은 것이고요.

 

저번에 대학 재학 중 배웠던 양자역학관련 공식 유도도하고 문제도 풀었던 위의 포스팅 글이 떠올랐죠.

 

이걸 활용했습니다.

 

이제 이 파동함수를 왜, 어떻게 물고 뜯고 했는지 다음 글에서 다루겠습니다.

---

알고있는 정보들을 극한까지 활용하는 중입니다. 스스로도 잘하고 있다고 생각합니다.

그러나 이외의 다양한 지식이 별로 없다는 겁니다.

 

더 많은 지식이 있었다면 다양하고 효율적으로 프로젝트 진행이 가능했을지도 모르니까요.

 

그래서 지금 백준에서 코딩 테스트하며 살고있습니다.

가장 현재 제게 연관이 가장 높고 알고리즘 짜는 능력과 문제해결력을 키울 수 있으니까요.

 

물론 아직 방구석에 놓여진 통계법, 양자역학 등의 공부를 더 이어가야겠지만 말입니다.

 

결론은 Random Forest, LSTM, 머신러닝 기초 등... 실제 데이터 구축 경험과

실무 경험인 설비 제어, 신호처리 등을 위해 DSP, 최적화 이론, 상태공간 모델 등 공정 전용 지식들도 천천히 익혀야 할 것 같다.

 

긴 글 읽어 주셔서 감사합니다.