수업 출처) 숙명여자대학교 소프트웨어학부 박동철 교수님, '데이터사이언스개론' 수업

 

1. how measure a model?

- 데이터 분석을 통해 "얻고싶은 것"이 무엇인지 신중히 고려하는 것이 중요하다.

 

- 모델의 수행 능력을 의미있는 방식으로 측정해야 한다.

    - 각 문제에 대한 올바른 평가 방식은 무엇일까?

    - ex) 이동통신사 고객 이탈 문제 (celluar-churn problem) : 정확한 예측의 비율? 이탈한 고객의 비율?

 

2. Evaluation Classifiers (예측모델 평가)

- 알지 못하는 클래스에 대해 이미 갖고 있는 데이터를 바탕으로 예측하는 모델이다.

- 이진 예측 모델의 클래스: positive / negative

- 이러한 모델이 얼마나 잘 수행되는지 어떻게 평가할 것인가?

 

2-1. Plain Accuracy

- 지금까지 우리는 classifier의 성능을 측정하기 위한 간단한 지표를 가정했다. : accuracy (or error rate)

 

- accuracy = 예측 중 맞은 개수 / 전체 개수 = 1 - error rate

 

- 측정하기 쉽고 이해하기 쉽기 때문에 많이 쓰이는 방법이다.

- 하지만, 너무 간단하고, 몇 개의 문제점들이 있다.

 

2-2. Confusion Matrix

- n개의 클래스를 분류하기 위한 n x n 행렬이다.

    - 행(rows) : 예측값

    - 열(columns) : 실제 값

    - 다른 종류의 오차(error)들을 개별적으로 보여준다. : False positives, False negatives

 

- p, n이 실제 클래스에 속하는 값들이고, y, n이 예측한 값들이다. 

- 따라서 y-p에 속하는 값들은 y로 예측했는데 실제로 positive인 값들이다.

 

2-3. Problems with Unbalanced classes

1) 분류 문제에서 한 클래스가 rare하다고 생각해보자.

- 예를 들어, 사기당한 고객을 찾는 경우나, 결함이 있는 부품을 찾는 경우나, 광고 등에 응하는 고객을 찾는 경우 그런 경우들이 흔치 않기 때문에 클래스 분포가 불균형하거나 비스듬할 것이다.

- 이러한 경우에는 accuracy로 성능을 판단하기 어렵다.

- 예를 들어 클래스 값이 999:1 비율이라면, 항상 999의 개체가 속한 클래스를 선택한다면 정확도는 99.9%가 되기 때문이다. 

- 비율 불균형이 그리 크지 않더라도 정확도는 오해의 소지가 매우 크다. 잘못된 해석이 도출될 수 있다.

 

- ex) cellular-churn problem

- 1000명의 churn 예측 모델을 A와 B가 각각 만들었다고 하자. 

- A모델은 churn 클래스는 100% 예측하고, not churn 클래스는 60% 예측한다.

- B모델은 churn은 60%, not churn은 100% 예측한다.

- 이 경우 두 모델은 매우 다르게 작동하지만 accuracy는 80%로 똑같다.

 

2) 또한, accuracy는 테스트 셋에 따라 달라진다. 

 

3) false positive와 false negative를 구별하지 않는다.

- 둘을 같이 세기 때문에 오차들이 모두 똑같이 중요한 것처럼 여겨진다.

- 하지만, 이는 현실 세계에서는 드문 경우이다.

- 다른 종류의 오차는 다른 무게를 갖는다.

- ex) 의학 진단 경우

    - false positive : 실제로 병에 걸리지 않았지만 걸렸다고 진단한 경우 (기분은 나쁠 수 있지만 실제로 정상이기 때문에 괜찮음)

    - false negative : 실제로 병에 걸렸지만 걸리지 않았다고 진단한 경우 (대처를 못하기 때문에 훨씬 심각한 문제를 초래함)

 

- ex) cellular-churn 

    - false positive : 떠날거라고 생각해서 상품을 제공했지만 떠나지 않음 (어쨌든 고객을 유지했기 때문에 괜찮음)

    - false negative : 떠나지 않을거라고 생각해서 제공하지 않았지만 떠남 (고객을 잃었기 때문에 훨씬 손해임)

 

- 대부분의 경우, 우리는 false positive와 false negative를 다르게 다뤄야 한다.

- classifier에 의한 각 결정들의 cost나 benefit을 추정해야 한다.

- 일단 집계되면, 이러한 것들은 classifier에 대한 기대이익(or 기대비용) 추정치를 산출할 것이다.

 

2-3. Generalizing beyond classification

- 데이터사이언스를 활용할 때 목표가 무엇인지, 주어진 목표에 맞게 데이터마이닝 결과를 적절히 평가하고 있는지 중요하게 생각해야 한다.

 

- ex) Regression

    - 데이터사이언스팀이 영화 추천 모델을 만든다고 생각해보자. 

    - 평점은 1 - 5개의 별을 줄 수 있고, 모델은 사용자가 보지 않은 영화를 얼마나 많이 시작할지 예측한다.

    - 모델을 오차의 평균으로 측정해야 할까, 오차 제곱의 평균으로 측정해야 할까?

    - 더 나은 방법이 있는지 확인해야 한다.

회귀모델을 위한 metrics

 

3. Expected Value (EV) : Key Framework

- EV는 데이터 분석적 사고를 돕는 아주 유용한 개념적 도구이다.

- 데이터 분석 문제에 대한 생각을 정리하는데에 아주 유용한 핵심 프레임워크를 제공한다.

- 다음은 EV의 일반적인 계산식이다.

- o𝑖 : 가능한 결정 결과 (ex: classification -> YES or NO)

- p(o𝑖) : o𝑖의 확률

- v(o𝑖): o𝑖의 가치 (ex: cost, benefit or profit)

 

3-1. Using EV for Classifier Use (ex. 타겟 마케팅)

- 각 소비자의 클래스를 예측하여 더 응답할 가능성이 높은 고객들을 예측하고자 한다.

- 불행히도 타겟 마케팅의 경우 각 소비자가 응답할 확률은 대부분 1-2%로 매우 낮다.

- 그래서 우리가 상식적으로 응답할만한 소비자를 결정하기 위해 임계값을 50%로 정한다면 아마 아무도 겨냥하지 못할 것이다.

- 아마 모든 소비자가 '응답하지 않을 것'이라고 분류될 것이기 때문이다.

- 하지만, EV 프레임워크를 활용하면 문제의 핵심을 찾을 수 있을 것이다.

 

- feature vector가 x인 고객들에게 pᵣ(x)를 부여하는 모델을 갖고 있다고 가정하자.

    - pᵣ(x)는 고객 x가 응답할 확률의 추정치이다.

    - 예를 들면 classification tree, logistic regression model 등이 있다.

 

- 그러면 이제 다음과 같이 타겟 고객 x의 기대 수익 (or 기대 비용)을 계산할 수 있다.

    - vᵣ : 우리가 응답으로부터 얻는 가치 (value from a response -> profit)

    - vₙᵣ : 무응답으로부터 얻는 가치 (value from no response -> cost)

 

- example scenario

    - 상품가격 $200

    - 원가 $100

    - 마케팅비 $1

 

- EV 계산식에서 vᵣ = $99, vₙᵣ = -$1 

- 우리는 EV가 0보다 크기만 해도 이익을 얻는 것이다.

따라서 계산을 해보면 pᵣ(x) · $99 - (1 - pᵣ(x)) · $1 > 0

=> pᵣ(x) > 0.01 

- 고객 x가 응답할 확률이 1%만 돼도 남는 장사라는 것을 알 수 있다.

- 따라서 우리가 예상했던 50% 응답률이 아니라, 1% 보다 큰 확률 추정치를 갖는 고객을 타겟으로 삼아야 한다.

 

3-2. Using EV for Classifier Evaluation

- 지금까지 개개인의 결정에 주목했다면, 지금부터는 '결정의 집합'에 더욱 주목하고자 한다.

- 특히 우리는 모델로부터 만들어진 일련의 결정들을 평가해야 한다.

 

- 이 평가를 할 때 서로 다른 모델들을 비교하는 것이 필요하다.

    - 우리의 데이터 중심 모델은 직접 만든 모델보다 더 성능이 좋은가?

    - 분류 트리 모델이 로지스틱 회귀 모델보다 더 성능이 좋은가?

 

- 총체적으로 우리가 관심을 가지는 것은 각 모델이 얼마나 잘 수행하는지, 즉 그것의 expected value가 무엇인지이다.

- EV의 일반 계산식이다.

- 각 o𝑖는 예측 클래스와 실제 클래스의 가능한 조합 중 하나에 해당한다.

((Y,p),(Y, n), (N, p). (N, n))

 

- 그리고 p(o𝑖)는 이미 confusion matrix에 나와있다.

- 각 o𝑖는 confusion matrix의 각 셀에 해당한다.

 

- ex) 

EV의 v(o𝑖)를 구하는 방법은 아래에서 다룬다.

 

1) step 1 : 각 케이스의 비율을 측정한다. (p(o𝑖))

- 각각의 count를 총 개체 수로 나눈다.

- p(h, a) = count(h, a) / T

    - h : 예측된 클래스 (Y / N)

    - a : 실제 클래스 (p / n)

    - T : 총 개체 수

    - count(h, a) : (h, a)케이스에 해당하는 개체 수

    - p(h, a) : (h, a)케이스의 비율 (or 확률 추정치)

 

2) step 2 : 각 케이스의 value를 명시한다. (v(o𝑖))

 

- 하지만, b(h, a)와 c(h, a)는 데이터로부터 추정할 수 없다.

- 이 둘은 일반적으로 분석으로부터 제공되는 외부 정보에 의해 정해진다.

- 그것들을 지정하는 것은 많은 시간과 노력이 필요하다. (ex: 우리가 고객을 유지하는 것이 정말 어느정도의 가치가 있는가?)

 

- ex) 위의 example scenario 예제

    - v(Y, n) = -1

    - v(N, p) = 0

    - p(Y, p) = 99

    - p(N, n) = 0

 

3) step 3 : total expected value (or profit) 을 계산한다.

- 다음 공식을 통해서 모델의 expected profit을 계산한다.

 

- final value는 각 고객 당 total expected profit을 나타낸다.

- 따라서 우리가 필요한 것은

    - 테스트 데이터셋에 대한 confusion matrix 계산

        - p(Y, p), p(Y, n), p(N, p), p(N, n)

    - cost-benefit matrix 생성

        - v(Y, p), v(Y, n), v(N, p), v(N, n)

 

3-3. Alternative Calculation of EV 

- alternative calculation은 종종 실제로! 사용되는 것이다.

- 왜냐하면 우리가 모델 비교 문제를 어떻게 다뤄야 하는지 정확히 알 수 있기 때문이다.

 

- 조건부확률

    - 사전 class : p(p) and p(n)

        - 각각 positive와 negative 개체일 확률이다.

    - p(x, y) = p(y) · p(x | y)

    - p(x | y) = p(x, y) / p(y)

        - (p(x, y) : x 와 y의 교집합)

 

- 다음과 같이 사전 클래스 p(p)와 p(n)을 찾아낼 수 있다.

 

- ex)

- expected profit = p(p) · [p(Y | p) · b(Y , p) + p(N | p) · b(Y , p)] + p(n) · [p(Y | n) · b(Y, n) + p(N | n) · b(N, n)]

    = 0.55 (0.92 · 99 + 0.08 · 0) + 0.45 (0.14 · -1 + 0.86 · 0) 

    ≈ $50.04

- 이를 통해 각 고객 당 평균적으로 약 $50 의 이익을 얻을 수 있다고 예측할 수 있다.

 

- 이제 경쟁 모델에 대한 정확도를 계산하는 대신에, expected values를 계산할 것이다.

- 나아가, 다양한 분포에 대해 두 모델을 쉽게 비교할 수 있다.

    - 각 분포에 대해 우리는 쉽게 사전확률을 대체할 수 있다.

    - 예를 들어, 불균형한 분포는 p(p) = 0.7, p(n) = 0.3 // 균등한 분포는 p(p) = 0.5, p(n) = 0.5라고 할 수 있다.

 

    - expected profit = p(p) · [p(Y | p) · b(Y , p) + p(N | p) · b(Y , p)] + p(n) · [p(Y | n) · b(Y, n) + p(N | n) · b(N, n)] 에서

       p와 n의 분포가 아무리 바뀌어도 [ ] 속에 있는 비율들은 변하지 않기 때문에 p(p)와 p(n)의 값만 바꾸어서 계산하면 된다.

    - p(p), p(n)을 제외한 다른 비율들이 변하지 않는 이유는 같은 모델이기 때문이다. 

 

4. Overview of the EV Calculation

 

5. Other Evaluation Metrics

- 데이터 사이언스에 사용되는 많은 평가 지표들이 있다.

- 모든 지표들은 근본적으로 confusion matrix의 요약본이다.

- Accuracy = (TP + TN) / (TP + FN + FP + TN) : 전체 개체 중 맞은 예측의 비율

- True positive rate (=Sensitivity) = TP / (TP + FN) = 1 - False negative rate : positive 중 맞춘 예측의 비율

- False negative rate = FN / (TP + FN) : positive 중 틀린 예측의 비율

- True negative rate (=Specificity) = TN / (FP + TN) = 1 - False positive rate : negative 중 맞춘 예측의 비율

- False positive rate = FP / (FP + TN) : negative 중 틀린 예측의 비율

 

- Precision 정밀도 = TP / (TP + FP) : positive 로 예측한 경우에서의 정확도

- Recall 재현율 = TP / (TP + FN) =True positivve rate (Sensitivity)

- F-measure F-값 = 2 x {(Precision x Recall) / (Precision + Recall)} : precision과 recall의 조화평균

- 이 세 가지는 정보 검색과 패턴 인식 (텍스트 분류) 에 널리 사용된다.

 

6. Baseline Performance

- 몇몇 경우, 우리는 모델이 어떤 기준선보다 더 나은 성능을 갖고있다고 증명해야 한다.

- 그렇다면 비교의 대상이 되는 적절한 기준선은 무엇일까?

    - 그것은 실제 용도에 따라 다르다.

    - 하지만 몇몇 일반적인 원칙들이 있다.

 

1) Random model

- 통제하기 쉬울 수 있지만, 그다지 흥미롭거나 유익하진 않을 것이다.

- 매우 어려운 문제나 처음 문제를 탐색할 때 유용할 것이다.

 

2) Simple (but not simplistic) model

- ex) weather forecasting

    - 내일의 날씨는 오늘과 같을 것이다.

    - 내일의 날씨는 과거부터 내일까지의 날씨의 평균일 것이다.

    - 각 모델은 랜덤으로 예측하는 것보다 훨씬 나은 성능을 발휘한다. 어떤 새롭고 더욱 복잡한 모델도 이것들보다는 나은 성능을 가져야 한다.

 

3) The majority classifier 다수결

- 항상 훈련 데이터셋에서 다수의 클래스를 선택하는 방법이다.

 

- 우리는 모집단의 평균 값이라는 직접적으로 유사한 기준선을 가지고 있다. 

- 보통 평균이나 중간값을 사용한다.

 

- ex) 추천 시스템    - 특정 영화가 주어졌을 때 고객이 몇개의 별점을 줄 지 예측해보자.    - random model     - simple models        - model 1 : 고객이 영화들에게 준 별점의 평균 값을 사용할 것이다.        - model 2 : 대중이 그 영화에 준 별점의 평균 값을 사용할 것이다.    - combination of multiple simple models : 이 둘에 기초한 간단한 예측은 둘 중 하나를 따로 사용하는 것보다 훨씬 낫다.

 

- 간단한 모델을 비교하는 것 외에도, 배경 지식을 기반으로 한 간단하고 저렴한 모델을 기본 모델로 사용할 수 있다.

 

- ex) Fraud detection 사기 탐지    - 일반적으로 대부분 사기당한 계정들은 갑자기 사용률이 늘어난다고 알려져 있다.    - 거래량 급상승에 대한 계좌 조회는 많은 사기를 잡기에 충분했다.    - 이 아이디어를 구현하는 것은 간단하며, 유용한 기준선을 제공했다.

수업 출처) 숙명여자대학교 소프트웨어학부 박동철 교수님 '데이터사이언스개론' 수업

 

[Similarity]

1. Similarity (유사도)  -> "거리" 개념

: 많은 데이터 사이언스 방법과 솔루션들의 근본이 된다.

 

- ex) 비슷한 것들 검색, 비슷한 것들 그룹화 (클러스터링), 상품 추천, 비슷한 케이스로부터의 추론

 

- objects 간의 "거리"를 이용해서 유사도 측정

 

- 각각의 object를 feature vector로 표현 -> 두 벡터간의 유클리드 거리 계산

 

* Euclidean Distance 유클리드 거리

- 두 점 사이의 직선 거리를 계산하는 보편적인 방법

- d(A, B) = √ {(a₁-b₁)² + (a₂-b₂)² + ... + (aₙ-bₙ)²}

 

[Neighbors]

2. Nearest-Neighbor Reasoning (NN)

- Nearest-Neighbor : 가장 유사한 개체들

 

- 우수한 기업고객과 가장 유사한 기업 탐색, 온라인에서 기업의 소매 고객과 가장 유사한 고객 탐색 등  

    -> 영업인력 직접적으로 도움, 타겟 마케팅

 

- ex) 위스키 분석 

    - 며칠 전 저녁에 맛 본 "Bunnahabhain" 위스키가 마음에 들었다고 하자. 다른 single malt 위스키들 중 유사한 것을 어떻게 찾을 수 있을까?

    - 각각의 single malt 위스키들을 feature vector로 나타낸다. 그리고 저 위스키와 가장 가까운 이웃을 찾는다.

    - 이처럼 각각의 특징들을 숫자 형태로 나타낸다.

    - 그러면 이처럼 특징들을 바탕으로 다른 위스키들과의 거리를 구할 수 있다. "Glenglassaugh"가 가장 유사하다고 볼 수 있다.

 

- Nearest Neighbors for Predictive Modeling

    - 타겟 변수를 예측하고자 하는 새로운 데이터가 주어진다.

    - 훈련 데이터셋으로부터 가장 유사한 데이터들을 선택한다.

    - 그들의 타겟 값들에 기반하여 새로운 데이터의 타겟 값을 예측한다.

 

 

3. Classification Using NN

- 새로운 데이터의 클래스(label)을 어떻게 예측할 수 있을까? (이웃을 이용하여 새로운 개체 분류)

 

- k개의 가장 가까운 이웃들을 찾는다.

- 그들의 타겟 변수를 참조한다.

    예를 들어, k=3이고, 두 개의 타겟 값은 (+), 한 개의 타겟 값은 (-)이면 다수결에 의해 (+)으로 예측할 수 있다.

 

- ex) 신용카드 마켓팅 문제

    - 아래 자료에 근거하여 David가 신용카드 제안에 응답할 지 예측한다.

    - 거리가 가까운 3명의 이웃을 찾을 수 있다. (Rachael, John, Norah)

    - 그들의 타겟 값을 이용하여 다수결로 예측하면 Yes로 예측할 수 있다.

 

4. Probability Estimation Using NN

- 새로운 데이터가 클래스에 속할 확률을 어떻게 구할 수 있을까?

 

- k개의 가장 가까운 이웃을 찾는다.

- 각 클래스의 빈도 비율을 계산한다.

    예를 들어, k=3일 때 Yes가 두 명, No가 한 명이면 Yes에 속할 확률은 2/3(66.7%), No에 속할 확률은 1/3(33.3%)로 계산할 수 있다.

 

5. Regression Using NN

- 새로운 데이터의 값을 어떻게 측정할 수 있을까? 

 

- k개의 가장 가까운 이웃들을 찾는다.

- 그들의 타겟 값들의 평균(or 중간값)을 계산한다.

    예를 들어, 위의 자료에서 David의 수입을 예측하고자 한다. Rachael, John, Norah의 수입이 각각 50, 35, 40이기 때문에 평균은 42, 중간값은 40으로 예측해 볼 수 있다.

 

6. NN의 두가지 이슈

1) 몇 개의 이웃을 선택해야 하는가?

    - nearest neighbor 알고리즘은 종종 k-nn 으로 불린다.

    - k를 결정하는 데에 관한 간단한 답은 없다. *_* 

 

    - 다수결을 활용하기 위해서 홀수로 정하는 것이 좋다.

    - k가 클수록 추정치가 더욱 평준화된다. outlier의 영향을 덜 받기 때문에 나쁘지 않다.

    - k = n이면 전체 데이터셋이 예측에 활용되기 때문에

        - classification 에서는 항상 가장 많은 값의 클래스에 속할 것이고,

        - regression 에서는 타겟 값이 항상 모든 값들의 평균으로 예측될 것이며,

        - class probability estimation 에서는 항상 base rate 확률로 예측될 것이다.

 

2) 모든 이웃들을 동일하게(평등하게) 간주해야 할까?

- 몇몇의 가까운 이웃들은 다른 가까운 이웃들보다 더욱 가까울 수 있다.

 

- 다수결 예측이나 평균을 구할 때 문제가 된다.

    - 이들은 이웃이 새로운 데이터와 얼마나 가까운지는 고려하지 않는다.

    - 위의 David 예제에서 k=3 일 때에는 세개의 데이터들의 거리가 모두 15 근처로 비슷하다. 하지만 k=4 로 정하면 4번째 가까운 이웃과의 거리는 122가 되기 때문에 다른 3개의 이웃들과는 많이 차이가 난다. 이를 동일하게 취급하는 것은 문제가 있다.

 

- 이를 해결하기 위해서는 유사도에 따른 가중치를 부여하면 된다. 

    - 다수결을 이용할 때 모든 표를 1로 정하지 않고, w₁ x 1 + w₂ x 1 + w₃ x 1 + ... 의 형태로 구한다.

    - wᵢ 는 유사도에 비례하여 할당되며, 보통 Σwᵢ = 1이 되도록 설정한다.

 

    - 평균을 구할 때에도 값을 더할 때 가중치를 곱하여 더한다.

    - (w₁ v₁ + w₂ v₂ + ... wₙ vₙ) / n

    - 마찬가지로 wᵢ 는 유사도에 비례하여 할당되며, 보통 Σwᵢ = 1이 되도록 설정한다.

 

- ex) weighted voting, k = 4

    - 각 가중치를 1/distance² 으로 구한다. 제곱을 하는 이유는 이상치의 가중치를 낮추기 위해서이다.

    - 그리고 비율을 따져서 가중치들의 합이 1이 되도록 한다. 

 

    - 위와 같이 가중치를 이용하여 비율을 구할 수 있고, Yes의 값이 더욱 크기 때문에 Yes라고 예측할 수 있다.

 

7. Geometric Interpretation of NN (NN의 기하학적 해석)

- 명시적으로 경계가 형성되진 않지만, 각 점의 분류를 결정함으로써 암시적은 영역을 계산할 수 있다. 

 

- k=1 로 분류한 그래프이다. k=1인 경우 자기 자신만을 그룹으로 가지며 정확도는 100%이다. 따라서 overfitting이 된다.

 

- 그래프 관찰

    - 경계들은 불규칙적이며, 특정한 기하학적 모양을 찾아볼 수 없다.

    - 훈련 데이터셋의 개체를 둘러싼 경계는 매우 구체적이다.

    - 경계는 이상치에 매우 민감하다. 위의 그래프에서 '+' 사이에 있는 '·' 의 경우가 그렇다.

 

7. Overfitting & Complexity Control of NN 

- 1-NN 

    - 훈련 포인트 자체는 자기 자신으로 예측되며, 자기 자신이 가장 가까운 이웃으로 검색된다.

    - 그러므로 1-NN 은 overfitting이 매우 강하게 발생한다.

 

- k-NN 

    - k는 복잡도 파라미터이다. (complexity parameter)

    - 극도로 복잡하게 만드려면 k = 1로 지정할 수 있다. 

    - 다른 경우에는 k = n이 된다. 그러면 모든 모델에서 그다지 복잡하진 않을 것이다.

 

- k를 선택하는 방법은 모델에 따라 다르다.

 

- 일반적인 방법

    - 다양한 k값에 따른 중첩 교차 검증을 실시한다.

    - 테스트셋에서 가장 좋은 성능을 보여준 k를 선택한다.

    - 전체 훈련 데이터셋에 대한 k-NN 모델을 형성한다.

 

    - 선형 모델이나 트리 구조 모델에서 경계는 부드러운 곡선이나 일정한 조각의 기하학적 영역이 아니다.

 

9. NN 모델의 이슈

1) Intelligibility 명확성 (얼마나 이해하기 쉬운가)

- 단일 인스턴스가 어떻게 결정되는지 설명하는 것은 쉽다.

- 하지만, 데이터로부터 어떤 '지식'이 도출되었는지 설명하는 것은 어렵다.

    - 데이터로부터 어떤 시스템을 배웠는지, 어떤 근거로 결정을 내렸는지

- 따라서, 모델에 정당성을 부여하는 것이 중요할 땐 k-NN은 바람직하지 않다.

 

2) Computational efficiency 계산 효율

- 훈련시키는 것은 매우 빠르게 진행된다.

    - 보통 저장된 개체들만 활용하기 때문에 모델을 만드는데 큰 노력을 들일 필요가 없다.

- 하지만, 예측/분류는 많은 노력과 시간이 필요하다.

    - 데이터베이스에서 새로운 개체와 가장 가까운 이웃들을 찾아야 하기 때문이다.

- 따라서, k-NN 방법은 실시간 적용에 활용하기엔 실용적이지 않을 수 있다.

 

10. 이질적인 속성들을 다루는 기술

1) 범주형 속성을 어떻게 다룰 것인가?

- 범주형 속성을 숫자형으로 바꾼다. 

- ex) Sex: Male / Female -> 0 / 1

- 이진 변수는 바꾸기 쉽지만, 여러개의 값은 어떻게 바꿔야할까?

 

2) 값이 큰 변수들은 거리에 매우 큰 영향을 미친다.

- 따라서 변수들의 범위와 규모(축척)을 측정해야 한다.

- ex) Age : [0, 100] , Income : [0, 100,000] -> Age : [0, 1], Income : [0, 1]

 

11. 거리를 구하는 다른 함수들

11-1. Euclidean distance (L2 norm)

- 가장 많이 사용되는 거리 함수

- 직관적이고 계산하기 쉽다.

 

11-2. Manhattan distance (L1 norm)

- 격자에서 이동한 거리의 총합

- ex) d((3,4), (5,2)) = |3-5| + |4-2| = 4

 

11-3. Jaccard distance 

- 두 집합의 유사도를 측정하는 방법이다.

- 두 집합이 공통적인 요소를 많이 가질수록 거리가 감소한다.

 

11-4. Cosine distance

- 두 벡터 사이 각의 cos값을 측정하는 방법이다.

- 특히 벡터의 크기를 무시하고자 하는 경우 유용하다.

- 텍스트 분류를 통해 두 문서 사이의 유사도를 측정하고자 할 때 종종 사용된다.

 

[Clustering]

12. Clustering (군집화)

- 비슷한 개체들끼리 자연스럽게 맺어지는 그룹을 찾는 방법이다.

- 특정한 타겟 속성이 없다.

- unsupervised segmentation (비지도 분할) 이라고도 부른다.

 

- ex) 더 나은 서비스를 위해 고객 그룹화, 더 보기 좋게 진열/정리 하기 위해 상품 그룹화

 

- 그룹 내의 개체들은 비슷하며, 서로 다른 그룹의 개체들은 그다지 비슷하지 않다.

 

- 지도 모델은 알고있는 데이터의 타겟 변수 값을 기반으로 특정한 타겟 변수 값을 예측하기 위한 패턴을 발견하는 것이다.

- 비지도 모델은 데이터셋에서 타겟 변수에 초점을 맞추지 않고, 다른 종류의 정규성을 찾는 모델이다.

 

- ex) 위스키 분석 (위의 예제)

    - 이번엔 '맛'이 비슷한 위스키끼리 클러스터링을 해보려 한다.

    - 계층적 클러스터링, k-means 클러스터링을 고려해볼 수 있다.

 

 13. Hierarchical Clustering 계층적 클러스터링

- 각 개체의 고유한 클러스터에서 시작한다.

- 반복적으로 가장 가까운 클러스터끼리 합친다. 

    - 유사도나 거리함수를 이용한다.

- 이론적으로는 하나의 클러스터가 될 때까지 반복한다. 하지만 통상적으로 이정도로 많이 반복하지는 않는다.

hierarchical clustering

 

14. 클러스터 사이의 거리 (distance function = linkage function)

1) Min distance

- 각 클러스터에서 가장 가까운 점 사이의 유클리드 거리

 

2) Centroid distance  

- 클러스터의 중간(모든 데이터들의 '평균값') 사이의 유클리드 거리 

 

15. Dendrogram 계통도

- 클러스터의 계층을 명시적으로 보여주는 그림

- 계통도를 수평으로 잘라서 원하는 수의 클러스터를 구할 수 있다. 

- 이를 통해 언제 클러스터링을 멈출 지 알 수 있다.

- 아래로 갈수록 클러스터의 수가 늘어난다.

 

16. 계측적 클러스터링의 장점

- 클러스터의 수를 결정하기 전에 이미 계통도를 통해 그룹화가 된 것을 볼 수 있다.

- 원하는 수의 클러스터에서 계통도를 자를 수 있다. (클러스터링을 멈출 수 있다.)

 

17. ex) Hierarchical Clustering of Scotch Whiskeys

 

- 클러스터는 스코틀랜드의 지역과 완전히 일치하지는 않다.

- 단순히 잘 알려진 것을 구입하는 대신, 각자의 클러스터에서 선택할 수 있다.

- 혹은 다른 '가장 비슷한' 위스키를 추천하는 가이드를 만들 수도 있다.

 

18. k-Means Clustering 

- k개의 그룹을 만드는 클러스터링 알고리즘이다.

- 가장 유명한 centroid-based clustering algorithm 이다.

 

- k는 데이터에서 찾은 클러스터의 개수이다. (사용자에 의해 특정된다.)

- means는 중심을 뜻한다. 클러스터에 속한 점들의 '평균값'을 의미한다.

 

19. k-Means Algorithm

- 초기 k개의 클러스터 중심을 고른다. (보통 랜덤으로 정한다.)

- 각 점을 그로부터 가장 가까운 중심이 해당하는 클러스터에 할당한다.

- 모든 점들이 할당된 이후, k개의 클러스터의 중심을 갱신한다.

- 그리고 다시 모든 점들을 그들의 가장 가까운 클러스터에 재할당한다.

- 더 이상 점들이 클러스터를 이동하지 않고 안정될 때까지 3-4번 반복한다.

 

- 각 중심들이 클러스터의 결과이다.

- 각 점들은 각각의 클러스터에 소속되어 있다.

 

20. ex

- 90개의 점을 k=3으로 하여 클러스터링 하는 과정이다.

- 분홍색, 초록색, 파란색 선은 각각 클러스터의 중심이 이동한 경로이다.

- 경로의 끝에 까만 점이 최종 클러스터의 중심이다.

 

21. Initial k Centroids 고르기

- k-means 알고리즘을 한 번 돌리는 것은 최상의 클러스터링이 아닐 것이다.

    - 초기 중심의 위치가 클러스터링의 결과를 만들게 되기 때문이다.

 

- 해결책은 초기의 랜덤 중심부를 다르게 하여 여러번 k-means 알고리즘을 돌리는 것이다.

- 그렇게 나온 결과들 중 가장 클러스터링이 잘 된 결과를 선택한다.

- 가장 좋은 클러스터링은 클러스터의 평균 직경을 최소화하는 것이다. (각 점에서부터 중심까지의 거리의 평균)

 

22. 올바른 k 값 고르기

- 실생활에서 최적의 k 값을 고르는 방법은 알 수 없다.

- 하나의 간단한 전략은, k-means 를 여러번 돌려서 가장 클러스터링이 잘 된 k를 고르는 방법이다.

- 그것은 클러스터의 평균 직경이 작고, 클러스터의 수가 그리 많지 않은 것이다.

- 다음 그래프에서는 기울기가 완만해지는 지점인 k = 3이 가장 좋은 k이다.

 

23. ex) Clustering business news stories

- 문서들을 단어들의 집합으로 나타낸다.

- Jaccard distance 를 이용하여 두개의 문서 사이의 거리를 구한다. (1-교집합/합집합)

 

 

24. ex) Clustering wiskey

- 각 위스키의 feature vector를 나타낸다 (1, 0, 1, 1, 0, ...)

- 두 위스키 사이의 거리를 유클리드 거리로 구한다.

 

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "데이터사이언스개론", 박동철 교수님

 

1. Overfitting

- 데이터 사이언스에서 가장 중요한 근본 개념 중 하나이다.

- 모델을 만들 때 너무 flexible하게 만들면 모델이 특정한 데이터셋(훈련 데이터셋)에 너무 적합해진다.

 

- 모델이 훈련 데이터셋을 넘어선 일반적인 데이터셋에는 잘 적용되지 않는 경우이다.

- 모델은 새로운 데이터 개체도 잘 예측해야 한다.

 

2. 근본적인 부작용

- 더 복잡한 모델을 사용하면 정확도는 높아지겠지만, outfitting의 가능성 또한 높아진다.

- 한번에 overfitting을 제거할 방법은 없다.

- 가장 좋은 전략은 overfitting을 인지하고, 원칙적인 방법으로 복잡도를 조절하는 것이다.

 

- fitting graph : 복잡도 함수로써 모델의 정확도를 보여주는 그래프이다.

 

- 보통 모델을 만들 때 훈련 데이터에서 일정 부분을 holdout data로 빼놓고 훈련 데이터로 모델을 만든 다음 정답을 알고 있는 테스트 데이터로 정확도를 평가한다.

- 조금 더 general한 정확도를 측정할 수 있다.

- 위의 그림에서 오른쪽이 fitting graph이다.

 

3. overfitting 인지

- 모델이 충분히 복잡하지 않을 때 : 훈련데이터와 테스트 데이터 모두에서 정확도가 낮다. → underfitting

- 모델이 너무 복잡해질 때 : 훈련데이터에서는 정확도가 높아진다. 하지만, 테스트 데이터에서는 정확도가 낮아진다. → overfitting

 

- (ex) : customer churn table model.

    - 극단적인 예시는 fitting graph가 독특할 것이다.

    - 행의 개수가 많을수록 복잡도가 커질 수 있다.

 

    - learning에 'churn' data만 넣고, 여기에 없는 데이터는 'stay' data로 인식하도록 했다.

 

    - 모델이 증가하면서 훈련 데이터의 에러는 감소하지만, 테스트 데이터의 에러는 어느 특정 값에서 시작해서 변하지 않는다.

    - 이유 : 학습을 할 때 churn data만 put했다. 그러면 테스트 데이터는 그 안에 포함되어 있지 않기 때문에 모두 'stay' data로 인식한다. 하지만 그 중에 churn data가 있을 것이다. 따라서 (holdout 'churn' data) / (holdout data) 의 값이 holdout data의 base error rate (=b) 가 된다.

 

 

4. overfitting in tree induction

- 극단적인 classification tree : 모든 leaf node들이 pure할 때까지 데이터를 나눈 tree

    - 정확도는 100% 일 것이다.

    - overfitting 되었을 확률도 ^^..

 

- tree 모델의 복잡도는 노드의 개수에 비례한다.

    - tree 노드 개수에 제한이 없다면 어느 정확도에도 맞출 수 있을 것이다.

    - 따라서, tree가 자람에 따라 overfit 되는 경향이 있다.

 

- fitting graph for tree induction

    - ex) tree가 모집단의 특징이 아니라 훈련 데이터의 디테일한 부분을 고려하기 시작했을 때..

    - holdout data의 정확도가 떨어지는 순간 (= overfit이 시작되는 순간) 을 "sweet spot" 이라고 한다.

    - 그러므로 위의 경우 노드가 100개 정도 되는 순간부터 overfitting이 된다고 볼 수 있다.

    - 따라서 우리는 tree의 크기를 이 사이즈 (100) 로 제한해야 한다.

 

    - 하지만, 이론적으로 sweet spot을 정확하게 찾을 방법은 없다.

    - 따라서 이 부분은 데이터 과학자의 경험에 의해 결정해야 한다.

 

5. overfitting in mathematical functions

- 수학적 함수를 복잡하게 만드는 한 가지 방법은 변수나 항의 수를 늘리는 것이다.

 

 

- 더 많은 속성들을 사용하면서 모델은 훈련 데이터에 더 적합해질 수 있다. ( + overfitting 위험성)

- 즉, 변수나 항을 늘릴수록 훈련 데이터셋에서의 정확도는 증가한다.

 

- overfitting을 피하기 위해서는 오직 정보를 얻을 수 있는 유용한 속성들만 사용하고, 

- holdout technique을 활용해서 overfitting을 확인할 수 있다.

 

6. Holdout Evaluation

- 모델을 만들 때 holdout data를 빼놓고 형성한다.

- holdout data를 가지고 모델의 정확도를 평가한다.

- 목표는 모델의 일반화 성능을 추정하는것이다. 

- 답을 알고 있고, 훈련할 때 사용하지 않았기 때문에 정확도를 평가할 수 있다.

 

- 문제 

    - 이 테스트로부터 얻은 성능의 추정값은 단지 한번의 테스트를 통한 추정값이다.

    - 한 번의 추정만으로 모델 정확도에 확신을 얻는 방법은 운이 좋게 테스트 데이터를 한번에 잘 고르는 방법이 있겠다.

 

7. Cross-Validation (CV)

- holdout evaluation 의 더욱 정교화된 방법이다.

- holdout 평가를 여러번 진행한 뒤 그것의 통계값을 이용하는 방법이다.

 

- 추정된 성능에 대해 몇가지 통계값을 얻을 수 있다.

    - mean 평균 : 평균적으로 어느 정도의 성능이 예상되는가

    - variance 분산 : 데이터셋마다 성능이 얼마나 다른가

 

- k-fold cross-validation : 데이터셋을 k번으로 나누어서 나눈만큼 평가를 반복하는 방법이다.

 

- (ex) predict which customers are going to churn

    1) information gain

 

    2) classification tree

 

    3) 언제 tree building을 멈추는가?

        - 그렇게 복잡해지기 전에 멈춰야 한다.

        - 이 문제는 model generality와 overfittingr과 밀접한 관련이 있다.

 

    4) tree를 원래 데이터셋에 적용했을 때 정확도가 73%이다.

        - 이 값을 믿을 수 있는가?  다른 데이터셋에 적용해도 73%가 나올까?

        - 정확도가 73%인 것이 이 모델이 좋다는 의미인가? 좋지 않다는 의미인가?

 

8. Learning Curves

- 일반적으로, 모델의 일반화 성능은 어떠한 지점까지는 훈련 데이터 수를 증가시킴으로써 가능하다.

- learning curve : tree와 logistic regression에서 훈련 데이터 크기에 따른 일반화 성능을 나타낸 그래프이다.

 

 

- observations

    - decision tree가 logistic regression에 비해 더 유연하다.

    - 크기가 작은 데이터셋에 대해서는 logistic regression이 더 낫다. 

    - 크기가 큰 데이터셋에 대해서는 tree가 더 nonlienar 관계를 잘 표현한다.

 

- learning curve vs. fitting graphs

    - learning curve : 훈련 데이터의 일반화 성능을 보여준다. (x축 : training data 양)

    - fitting graph : 훈련 데이터 성능과 holdout 데이터 성능 2가지 모두 보여준다.  

 

9. Overfitting Avoidance and Complexity Control

- Regularization : 가장 대표적인 overfitting avoid 방법, 모델의 복잡도를 줄이는 방법이다.

 

9-1. for tree induction

- main problem

    - leaf node들이 순수해질 때까지 tree를 키우는 것

    - 이로 인해 크고 복잡한 데이터가 데이터에 맞지 않을 수 있다.

 

- 3 regularization

    - 더 복잡해지기 전에 멈추기

    - 충분히 tree 크기가 커질 때가지 키운 다음에, '가지치기' 해나가면서 다시 사이즈 줄이기

    - 서로 다른 크기를 가진 tree를 여러 개 만든 다음, 최선의 모델 선택하기

 

1) limit tree size

- 분할된 leaf node에 들어갈 개체의 최소 개수를 정해둔다. 

- 즉, 최소 개수 이하의 수가 되면 더이상 분할하지 않는다.

 

 

- 이 경우, 최소 개수를 20개로 정했기 때문에 각 그룹의 개체 수가 20개 이하가 되었을 때 growing을 멈췄다.

 

2) Prune An Overly Large Tree

- node와 branch들을 잘라내고, 그자리를 leaf node로 바꾸는 방법이다.

- 대체했을 때 정확도가 낮아지지 않을 때까지 진행한다.

- 성능이 떨어지지 않을 때까지 하위 그룹에서 반복되며 진행될 수 있다.

 

 

3) Build Many Trees And Pick The Best

- tree를 많이 만들어놓고, 그 중 가장 정확도가 높은 tree를 택하는 방법이다. 

 

9-2. for linear models

- 항이 많을수록 복잡하다.

 

1) Sequential forward selection (SFS)

- 순차적으로 항을 한 개씩 골라서 성능을 테스트한다. 그 중 가장 정확도가 높은 xᵢ를 선택하여 f(x) 에 넣는다.

- 그 다음, 처음으로 추가한 항을 포함하여 또 한 개의 항을 골라서 성능을 테스트한다. 그 중에서 가장 성능이 좋은 xᵢ를 선택하여 f(x) 에 넣는다.

- 이 과정을 계속 반복한다.

- 항을 추가하는 것이 테스트 데이터에서의 정확도를 더이상 높이지 않을 때까지 반복한다.

 

2) Sequential backward elimination (SBE)

- 위의 과정을 반대로 진행하는 것이다.

- 전체 f(x)에서 항을 한 개씩 선택하여 제거한 후 성능을 테스트한다.

- 제거했을 때 가장 성능이 좋은 xᵢ를 선택하여 제거한 후, 그 다음 또 항을 한 개 골라서 제거하고 성능을 테스트한다.

- 이 과정을 계속 반복한다.

- 마찬가지로 항을 제거하는 것이 더이상 정확도를 높이지 않을 때까지 반복한다.

 

10. Nested Cross-Validation

- 중첩된 CV

- 모델의 복잡도를 가장 크게 좌우하는 파라미터가 무엇인지 모를 때 사용한다.

- (ex) decision tree → number of nodes, linear model → number of features ···

 

- 즉, 복잡도 파라미터의 최적값을 찾기 위해 사용한다.

- (ex) What is the best number of nodes in a decision tree?

 

- 중첩된 loop 를 이용한다. (outer & inner loop)

    - outer loop :  만들어진 모델의 일반적인 성능 측정한다. (k-fold CV)

    - inner loop : best complexity parameter 찾아낸다.

 

    - inner loop → outer loop

 

- 단점 : inner loop 개수가 많을수록 실행 시간이 매우 길어진다.

 

 

 

 

 

 

 

 

 

 

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "데이터사이언스개론", 박동철 교수님

 

1. Predictive Modeling

- 다른 속성들을 통해서 타겟 속성의 값의 모형을 찾는 것이다.

 

-  Nonparametric modeling

    - 모델 모양이 정해져 있지 않은 모델이다

    - 모델의 구조는 데이터로부터 결정된다.

    - (ex) classificaiton 'tree' - 가지의 수, 모양 등은 데이터를 통해서 알 수 있다.

 

- Parametric modeling 

    - 모델이 정해져 있다.

    - 모델의 구조는 데이터 분석가에 의해 지정된다.

    - (ex) linear classify - y = ax + b의 모양으로, 모양은 정해져 있으며 데이터로부터 파라미터인 a, b만 찾아낸다.

 

2. Nonparametric modeling 

- 분석가가 모델의 구조를 지정하지 않는다. 데이터로부터 학습된다.

 

3. Parametric modeling (= parameter learning)

- 특정 파라미터 값이 지정되지 않은채로 모델의 구조가 정의된다.

- (ex) Y = aX + b -> a, b : parameter

 

- 주어진 훈련 데이터셋을 통해서 최상의 파라미터 값을 찾는다.

- (ex) linear regression

 

- 모델의 형식은 배경 지식이나 다른 데이터 마이닝 기술들을 통해서 결정한다.

 

- 목적은 모델 파라미터의 '최적'값을 찾아내는 것이다.

- 이때 어떤 모델이 가장 데이터를 잘 표현하는지 결정하는 것이 중요하다.

 

3-1. Classification Trees

- space는 결정 범위에 의해 여러 개의 클래스로 나눠진다.

 

- 새로운 개체가 들어왔을 때, 개체의 타겟 값은 분류된 타겟 값을 통해 결정된다.

 

- 다른 방식으로도 공간을 분류할 수 있다.

 

3-2. Linear classifier

- linear combination을 이용해서 속성을 분류한 것이다.

- linear combination은 속성 값에 가중치를 부여하여 더한 것이다. 

- (ex) 1 x Age = Balance x -1.5 + 60

- 선을 기준으로 윗 부분 :  Age > balance x -1.5 + 60, 아랫 부분 : Age < Balance x -1.5 + 60

 

3-3. classification tree vs. linear classifier

- 목표는 같다. : 타겟 속성에 대해 값을 기준으로 데이터를 분류하기 위한 모델이다.

 

- 차이점 : 구조

 

- classificaiton tree

    - 각 속성 별로 class를 분류해서 값을 집어넣는 방식이다.

 

- linear classifier

    - 여러 속성들을 가중치를 파라미터로 하여 더해서 관계성을 찾는 방식이다.

 

4. Linear Classifier

- general linear classifier 

    - f(x) = w₀ + w₁x₁ + ··· + wₙxₙ

 

- shpe of decision boundary

    - n = 2 → line

    - n = 3 → plane

    - n = 4 → hyperplane

 

- goal

    - 훈련 데이터를 통해서 가장 적절한 가중치 값을 찾는 것이다. 

    - 훈련 데이터를 잘 분류하고, 새로운 데이터도 가능한 적절하게 예측할 수 있도록

 

    - 가중치 w𝑖 가 클수록 x𝑖가 타겟을 분류하는 데 중요한 역할을 한다는 것이다. 

    - w𝑖가 0에 가까우면 x𝑖는 보통 무시되어도 괜찮다.

 

- 가중치 선택하는 일반적인 방법

    - 목표에 맞는 objective function을 정의한다.

    - objective function을 극대화 (최소화) 하는 최적의 가중치 값을 찾는다.

 

- 다음 모델들은 같은 linear 구조이지만, 다른 objective function을 사용한다. 

    - support vector machine (SVM) : classification

    - linear regression : regression

    - logistic regression : classification

 

    - 동일한 linear classifier f(x) = w₀ + w₁x₁ + ··· + wₙxₙ 를 사용한다.

 

    - (ex) svm vs. logistic regression : 둘 다 분류 모델이지만, 다른 경계를 형성한다. 

 

4-1. Support Vector Machine

- linear calssifier 모델이다. 

- 속성들의 선형 조합에 기반하여 개체를 분류한다.

 

- "margin을 최대화하는 선이 최적의 linear classifier이다"

    - margin : 각 그룹의 값들 중 가장 바깥 쪽에 있는 값을 그은 두 dash line 사이의 거리

    - margin이 가장 큰 두 선의 중간에 있는 선이 svm의 linear classifier이다.

    - 즉, 최적의 선은 두 클래스에서 모두 멀리 떨어진 선이다.

 

- misclassificaiton

    - 물론 아래와 같이 한 줄로 데이터들을 완벽하게 분리할 수 없는 경우도 많다. 

 

- original function : margine size 최대로 하는 선

- new objective function : 잘못 분류된 훈련 데이터 개체에 패널티를 부여하는 것이다.

 

 

- 패널티는 margin 경계로부터의 거리에 비례해서 부여된다.

- 이러한 방식을 'hinge loss function' 이라고 한다.

 

4-2. Linear Regression

- 데이터를 가장 잘 표현하는 linear 함수를 찾는 모델이다.

- 타겟 속성의 값을 "예측" 할 때 사용된다.

 

 

- 다른 objective function을 사용하는 많은 선형 회귀 방법들이 있다.

 

- 일반적인 절차

    - 훈련 데이터에서 각 점들에 대한 오차를 계산한다. 

    - 오차 : 선과 점 사이의 거리

    - 오차의 절댓값들을 더한다.

    - 오차의 절대합을 최소화하는 가중치를 구한다.

 

4-2-1. 최소제곱법

- 가장 일반적인 표준 선형 회귀 절차이다.

- objective function : 오차의 제곱합을 최소로 하는 가중치 w₀, w₁, ··· , wₙ 찾기

- 오차의 절댓값을 더하면 선을 다르게 해도 차이가 그리 크지 않고, 수학적 계산도 어렵기 때문에 제곱합을 사용한다.

 

- 장점

    - 더 높은 검정력으로 지수가 높아질수록 이상치의 오차가 극대화될 것이다.

    - 이차 함수는 수학적으로 다루기 쉽다. 미분해서 도함수가 0이 되는 값이 최소값이 된다.

- 단점

    - 이상치가 선을 결정하는 데 너무 큰 영향을 미친다.

 

4-3. Logistic Regression 

- linear regression 과 비슷하다. 

    - 둘 다 지도학습 알고리즘이다.

    - 둘 다 라벨링된 데이터셋을 예측하기 위한 알고리즘이다. (class 값이 정해진)

    - 하지만, linear regression은 회귀 모델이고, logistic regression은 이름은 regression이지만 분류 모델이다.

 

- 타겟이 될 "이항" 결과 (범주형 종속 변수) 와 서로 종속되어 있는 많은 속성들이 있을 때 사용한다.

- Y = aX + bZ 일 때, Y 가 타겟이고, X와 Z가 독립인 다른 속성들이다. a와 b가 파라미터이다. 

- Y는 X와 Z의 영향을 받는다.

 

- 실생활의 이항 결과들은 이러한 것들이 있다.

- game (win / loss), sales( buying / not buying), loan( default / non default ), marketing( response / no response )

 

- 새로운 개체가 관심있는 클래스에 속할 확률을 추정할 때 linear model f(x)을 이용한다.

- (ex) f(x) = 0.85 → x가 그 특정 클래스에 속할 확률이 85%이다.

 

- 하지만! 이 f(x) 함수를 logistic regression에 바로 적용할 수 없다.

- f(x) 는 범위가 (-∞, ∞) 지만, logistic regression 의 범위는 확률로 [-1, 1] 이어야 하기 때문이다.

 

그래서 오른쪽과 같이 S-Curve 형태가 나오도록 함수를 조절하여 사용한다.

 

4-3-1. logistic function p(x)

 

standard logistic function

- 다음 방정식을 따르는 s-shaped curve (sigmoid curve) 형태의 p(x) 함수를 적용한다.

- 확률값을 추정하여 return 한다.

- linear function f(x) 를 변형한 형태로, linear 함수를 사용하는 것은 맞다.

 

- ln(p/(1-p)) = w₀ + w₁x₁ + ··· + wₙxₙ = f(x)

 

- Odds 승산

    - 사건이 발생하지 않을 확률에 대한 사건이 발생할 확률이다.

    - p / (1-p)

    - (ex) probability = 0.5 → odds = 1, p = 0.9 → odds = 9

 

- log odds → ln(p / (1-p)) = f(x)

 

4-3-2. objective function

- likelihood model 최대화

probability

- Σ g(x, w) 값을 최대화 하는 w𝑖 를 구하는 것이다.

 

- g(x, w)는 x의 특징에 기반한 x의 실제 클래스를 통해 모델의 추정 확률을 반환한다.

- 이제 라벨링된 데이터셋의 모든 개체들에 대한 g(x, w) 값을 모두 더한다.

- 그리고 다른 파라미터를 가진 모델에 대해서 또 진행한다.

- 그러면 logistic regression에 대한 다양한 가중치 집합이 생성된다.

- 가장 합이 큰 모델이 데이터에 대해 가장 높은 확률을 갖는 모델이다. (가장 가능성이 큰 모델)

- 가능성이 가장 큰 모델은 평균적으로 가능한 예제들에 대해 가장 높은 확률을 반환하고, 적절하지 않은 모델에 대해서 가장 낮은 확률을 반환한다.

 

- 적용

    - 위와 같이 p(x) 확률값에 따라 개체들을 분류할 수 있다.

 

4-4. Linear regression vs. Logistic regression

Linear regression Logistic regression
연속적이고 종속적인 변수를 예측할 때 사용한다.
Regression 회귀 문제
카테고리형 (범주형) 종속 변수를 예측할 때 사용한다.
Classification 분류 문제
가격, 나이와 같은 연속적인 값을 예측한다. yes or no, 0 or 1과 같은 범주형 값을 예측한다.
output을 쉽게 예측할 수 있는 가장 fit 한 line을 찾는다. 예제들을 쉽게 분류할 수 있는 S-Cruve line을 찾는다.
정확도 측정에 "최소제곱법"이 사용된다. 정확도 측정에 "최대 가능도 방법"을 사용한다.
독립적인 변수와 종속적인 변수 사이에 반드시 선형 관계가 존재해야 한다. 꼭 선형 관계가 존재할 필요는 없다.

 

4-5. Classification trees vs. Linear classifiers

Classification tree Linear classifier
축에 수직인 결정 경계 (decision boundaries)를 사용한다. 결정 경계의 방향이 정해져있지 않다.
여러 영역으로 분류한다. 공간을 2개로 나눈다.

 

4-6. 어떤 모델이 더 좋은가..?

-  어떤 결정 경계가 가장 좋은 선택일지 아마 미리 볼 수 없을 것이다.

- 하지만 이해력의 차이가 있다.

    - logistic regression은 통계학을 잘 모르는 사람드은 이해하기 쉽지 않다.

    - decision tree는 대부분의 사람들이 이해하기 쉽다.

 

- 많은 경우 이해관계자들에게 모델을 만족시켜야 한다.

- 그렇기 때문에 성능과 이해도를 잘 조절하여 모델을 선택해야 한다.

 

5. Linear Regression 예제

- Wisconsin Breast Cancer Dataset : 유방암 진단 데이터

- 각 예는 세포 핵 이미지를 나타낸다. 

- 376개의 양성 데이터와 212개의 음성 데이터가 있다.

 

- attributes : 세포핵의 특성을 묘사한 디지털화된 이미지를 계산한다. 

    - radius, texture, perimeter, area 등의 각각의 속성에 대해서 평균, 표준편차, 최대값을 계산한다.

 

- linear equation

 

- test 결과 정확도가 98.8%이다. (6 mistakes / 588 images)

- 같은 데이터셋으로 classification tree 모델을 만들면 정확도가 99.1% 이다.

 

 

- Q1 : 정확도가 98.8%이면 좋은 결과인가 아닌가?

    - 그정도 값은 데이터 마이닝에서 많이 볼 수 있는 정확도 수치이다.

    - 그러나 실생활 문제에 대한 분류 모델 평가는 보다 복잡하고 어렵다.

 

- Q2 : classificaiton tree가 정확도가 더 높으니까 좋은 모델인가?

    - 차이는 오직 하나의 추가적인 오차로부터 발생했다.

    - 게다가, 평가된 정확도는 훈련 데이터셋으로 활용한 동일한 데이터로 평가한 것이기 때문에 높은 것이 당연하다.

 

6. Linear Classifier for Ranking Instances

- 많은 경우 단순히 개체가 클래스에 속하는지 아닌지만 예측하고 싶지 않을 수 있다.

- 한 클래스나 다른 클래스에 속할 가능성으로 순위를 매길 수있다.

- (ex) will the customer respond to this ad? → Which customers are mostly likely to respond to this ad?

 

- 이 질문을 linear classifier 을 활용해서 해결할 수 있다.

 

- 결정 경계로부터 가까우면 해당 클래스에 명확히 속하지 않는 개체이다. ( |f(x)| ≈ 0 )

- 결정 경계로부터 멀리 떨어질수록 해당 클래스에 속할 확률이 크다. ( |f(x)| >> 0 )

- 따라서 결정 경계로부터 멀리 떨어진 개체일수록 rank를 높게 매긴다. 

 

 

7. Nonlinear model

- 머신러닝의 경우 대부분의 모델이 nonlinear한 형태로 나타난다.

- f(x) = w₀ + w₁x₁ + ··· + wᵢxᵢ² + wⱼxⱼ³ + wₖxᵢxⱼ + ···

 

- nonlinear term : 곱, 나눗셈, 지수, 로그 등이 포함되어 선형으로 나타나지 않는다.

- support vector machine과 logistic regression 의 nonlinear model이다.

 

- Artificial neural network 인공 신경망

    - 복잡한 nonlinear function을 학습시킬 때 사용한다.

    - 많은 nonlinear function을 연결한다.

 

 

- nonlinear model로 flexibility를 너무 높이면, 그 모델은 훈련 데이터에 너무 적합하게 형성된다. → overfitting

- overfitting → 훈련 데이터에만 fit하고, 정작 예측해야 할 새로운 데이터에 적용하면 성능이 급격히 낮아진다.

- 따라서 우리는 훈련 데이터를 넘어서 새로운 데이터에도 잘 작동할 모델을 형성해야 한다.

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "데이터사이언스개론", 박동철 교수님

 

1. Predictive Modeling 예측 모델

 

- 일반적인 절차

    - training data를 가장 잘 표현하는 모델 설정

    - 새로운 데이터에 모델 적용하여 결과 예측

 

- 아마 처음으로 classification을 생각할 것이다.

    - 새로운 데이터가 어느 클래스에 속할지 training dataset을 기반으로 확인한다.

    - (ex) 이 고객이 회사를 금방 떠날 것 같은가? → YES / NO

 

2. Model

 

- 현실을 목적에 맞는 것만 남도록 간략하게 표현한 것이다. 

- 중요한 것과 중요하지 않은 것을 기반으로 간략화한다.

- 부적절한 정보는 날리고 관련이 있는 데이터들만 남긴다.

- (ex) 지도, 청사진 

 

2-1. Predictive Model

- 타겟에 대해 모르는 값을 추정하는 공식이다. 

- 예측의 정확도로 성능을 평가한다.

- 수학적인 표현(ex: linear regression)과 논리적인 표현(ex: decision tree)이 있다.

 

2-2. Descriptive Model

- 데이터에 내재되어 있는 인사이트를 얻는 것이 주 목적인 모델이다. 

- 즉, 예측"값"을 얻는 것이 목적이 아니다.

- 예시로는 clustering, profiling 등이 있다.

- 도출된 지능과 이해가능성으로 성능을 평가한다.

 

- 많은 모델들이 두가지 목적을 모두 제공할 수 있다. 

 

3. Model Induction 모델 유도

 

- 데이터로부터 모델 유도

    - 특정한 사례를 일반적인 규칙으로 일반화하는 것이다.

 

- 모델은 통계학적 의미에서 일반적인 규칙이다.

    - 항상 100% 맞진 않는다.

 

- Induction algorithm 유도 알고리즘 (leaner) : 데이터로부터 모델을 형성하기 위한 절차이다. 

- Training data 훈련 데이터 (labeled data) : 모델을 유도하기 위해 유도 알고리즘에 대입하는 데이터이다. 이미 라벨 값을 알고있다.

 

4. Supervised Segmentation 지도 분할

4-1. Basic idea

- 타겟에 대해 서로 다른 값들을 갖는 하위 그룹으로 분할하는 방법이다.

- 즉, 그룹끼리는 타겟에 대해 같은 (비슷한) value를 가진다.

- 분할에 사용된 변수 (값, attribute) 를 예측의 타겟 속성으로 사용할 수 있다.

 

 - 데이터를 가장 잘 분류할 수 있는 속성을 선택하는 것이 중요하다.

 

4-2. Selecting Information Attributes

- 효과적으로 데이터를 분류하기 위해서는 유용한 속성을 사용해야 한다.

- 유용한 속성은 해당 변수에 대해 중요한 값을 갖는 속성이다.

- 즉, 타겟의 값을 예측하는 것을 도와줄 수 있는 속성이다.

 

- (Ex)

- 사람들을 'yes' 와 'no'로 분류하고자 한다.

- 속성

    - 머리 : 정사각형 / 원

    - 몸 : 직사각형 / 타원

    - 몸 색 : 검정 / 하양

 

- target variable : 체납 여부 - yes / no

 

- 어떤 속성이 사람들을 yes와 no로 가장 잘 분류할 수 있을까?

- 우리는 그룹을 가능한 pure하게 분류하고자 한다.

 

- pure 

    - 그룹이 타겟 값에 대해 동일한 값을 갖는 상태를 말한다.  

    - 하나의 멤버라도 다른 값을 가지면 그 그룹은 impure하다고 말한다.

 

- 문제

    - 속성이 완벽하게 그룹으로 분리되는 경우는 거의 없다. 

 

        - 머리 모양과 몸 색을 각각 그룹을 분리한 결과이다. 어떤 속성이 더 그룹을 잘 분리한 것일까?

 

    - 모든 속성이 위의 예제처럼 2가지로 나누어지는것은 아니다. 더 많은 경우에는 어떻게 분리할 수 있을까?

    - (연속적인) 숫자 값을 가지는 속성은 어떻게 분류하는 것이 좋을까? (ex: 나이)

 

- 분류 기준

    - 속성이 데이터를 얼마나 잘 분류하는지를 평가하는 공식을 만들 수 있다.

    - 그 공식은 '순도'에 기반할 수 있다. 

 

- Information Gain

    - 가장 대표적인 분류 기준이다.

    - 순도를 측정하는 "엔트로피"에 기반한다.

 

- Entropy 무질서도

    - 무질서도를 측정하는 기준이다. 타겟의 관점에서 분류가 얼마나 impure하게 되었는지 측정한다.

    - H(S) = Σ p𝑖 log₂ (1/p𝑖)

        - p𝑖 : S에서 𝑖를 가질 확률 (Σ p𝑖 = 1)

        

    - (Ex) 

    - attribute S = {yes, yes, yes, no, no} → p₁(yes) = 3/5, p₂(yes) = 2.5

    - H(S) = 3/5 log₂(5/3) + 2/5 log₂(5/2) = 0.97 → very impure

 

plot of entropy H(S)

 

4-3. Information Gain

- 엔트로피는 각각의 분할이 얼마나 impure한지만 측정한다.

- 즉, 한 개의 속성만 고려한다.

 

- information gain은 속성이 만드는 전체 분할에 대한 엔트로피 증감 정도를 측정한다.

    - 엔트로피가 감소하면 유용한 정보이고, 엔트로피가 증가하면 정보를 얻을 수 없는 속성으로 분할한 것이다.

 

- IG = H(parent) - [ Σ p(c𝑖) ·H(c𝑖) ]

    - 각 child (분류된 그룹)에 대한 엔트로피는 각각의 그룹에 속하는 인스턴스의 비율에 가중된다.

- Information Gain 값이 클수록 유용한 속성이다. 

 

4-4. Numerical Variables

- 회귀 문제와 같이 속성 값이 "숫자형"인 경우는 카테코리값을 가진 속성보다 분류하기 어렵다.

 

1) Discretize 이산화

    - 한 개 이상의 분할점을 선택해서 숫자 값을 이산화하는 방법이다.

    - 그 후 카테고리형 속성과 같이 다룰 수 있다. 

 

2) 여러 개의 후보 분할점을 고르는 방법

    - 각각의 후보 분할점에 대해 IG 를 계산한 후 가장 IG 값이 큰 경우를 선택하는 방법이다. 

 

 

5. Classificaiton Tree Segmentation

-  여러 개의 속성을 사용해서 데이터를 분류하는 방법이다. → 트리 모양

 

- structure

    - interior node : 분류의 기준이 되는 속성 이름이다.

    - leaf node : 분류된 class(결과?)를 말한다.

    - branch : 속성의 구분되는 값을 말한다. (분류 기준, 범위)

    - path from the root to a leaf : 분류의 특징을 설명하는 길이다.

 

 

- procedure

    - 분류 값을 모르는 예시들이 있다.

    - root node에서부터 예시들의 특정 속성 값들로 branches를 선택하면서 interior nodes를 타고 내려온다.

    - terminal node (leaf node)에 도달하면 그것은 분류가 된 것이다.

 

- (ex)

    - balance = 115K, employed = no, age = 40 인 사람을 분류해보자.

    - root node인 employed 부터 no, ≥50K, <45 path를 따라서 내려온다.

    - 결과적으로 class = Not Write-off 로 특정된 leaf node에 도착한다.

    - 따라서 우리는 그 사람이 체납하지 않을 것이라고 예측할 수 있다.

 

- divide-and-conquer approach 

    - 전체 데이터셋을 나누기 가장 좋은 속성을 찾는다.

    - 각 서브 그룹에 대해서 재귀적으로 가장 좋은 속성들을 찾아나간다. 

 

- (ex) 위의 사람모형 예시

    - 일련의 과정에서 IG 값의 크기에 따라 큰 순서대로 몸 모양 - 몸 색 - 머리 모양 순으로 그룹을 분류한다.

 

그 결과 위와 같은 classification tree를 얻을 수 있다.

 

- 요약해보면, 데이터를 재귀적으로 나누는 과정이다.

- 각 과정에서 모든 속성을 테스트하고 그룹을 가장 순수하게 나누는 (IG값이 큰) 속성을 선택한다.

 

- 멈추는 단계는 모든 leaf node가 pure할 때, 변수를 끝까지 나눴을 때 등이 있지만, 이렇게까지 나누면 모델이 overfitting될 것이다. 

 

6. Visualizing Segmentation

- classification tree 결과를 공간 상에 시각화할 때 사용한다.

- 하지만, 시각화는 두세개의 특징으로만 가능하다.

- 그럼에도 고차원 공간까지 적용할 수 있는 인사이트를 얻을 수 있다.

 

7. 규칙

- classification tree는 구현하기 쉽기 때문에 자주 사용되며, 수학적 공식이 그렇게 복잡하지 않다. 

- 논리적 문장으로 classification tree를 구현할 수 있다.

    - 각각의 path가 statement가 된다.

    - 각 sement는 path와 "AND"로 구성된다.

 

 

8. 확률 추정

- 단순한 분류보다 확률 추정을 할 때

- (ex) he will not write-off → the probability of him writing-off = 40%

- ranking과 같이 더욱 정교한 의사결정을 해야할 때 사용할 수 있다.

 

- Frequency-based propbability estimation

    - 확률을 추정하기 위해 각 leaf 에서의 개체 수를 사용한다.

    - leaf에서 그에 해당하는 개체 (positive) 가 n개, 해당하지 않는 개체 (negative) 가 m개라면, 새로운 개체가 그에 해당할 확률은 n/(n+m)이 된다.

 

8-1. overfitting problem

- 개체 수가 아주 적은 분류 그룹의 확률은 굉장히 높아질 수 있다. 

    - (ex) 개체 수가 1개인 그룹은 무조건 100%가 나올텐데, 그것이 좋은 분류라고 할 수 있을까? - 다른 그룹의 개체 수가 나머지 99개인 경우?

 

8-2. Laplace correction 라플라스 보정

- 단순히 빈도를 계산하는 대신, 빈도수 기반 추정치의 smoothed된 버전을 사용하는 것이다.

 

- (ex) p₁ : 2 postitive, no negative, p₂ : 20 positive, no negative

    - frequency-base : p₁ = p₂ = 1

    - laplace correction : p = 0.75, p₂ ≈ 0.95

 

- 개체 수가 증가할수록 라플라스 방정식은 빈도수 기반 측정값에 수렴한다.

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

 

1. 탐색

- 다수의 레코드 집합에서 특정 키 값과 일치하는 레코드를 찾는 작업이다.

- 레코드는 객체의 속성에 해당하는 필드들의 집합으로 표현된다.

 

2. 순차 탐색

- 정렬되지 않은 레코드들에 대해 조건에 맞는 목표 키를 찾을 때까지 순차적으로 비교를 반복하는 작업이다.

- 정렬과 같은 요구 조건이 없어서 알고리즘은 단순하지만, 최상의 경우(1)와 최악의 경우(n) 탐색 성능에 큰 편차가 발생할 수 있다.

- 레코드 수(n)가 클수록 탐색 시간이 많이 걸린다

- 순차 탐색 알고리즘의 평균 비교 횟수 : (n + 1) / 2

 

#include <stdio.h>

int seq_search(int num[], int key, int n);

void main()
{
    int pos;
    int num[] = {12, 5, 6, 19, 23, 3, 7, 34, 89, 45, 22};
    
    pos = seq_search(num, 89, 11);
    printf("position = %d\n", pos);
    
    pos = seq_search(num, 43, 11);
    printf("position = %d\n", pos);
}

int seq_search(int num[], int key, int n)
{
    int i;
    for (i = 0; i < n; i++)
        if (num [i] == key) return i;
        
    return -1;
}

 

3. 이진 탐색

- 항목들을 정렬한 후 탐색을 적용한다.

- 겹치는 값이 없어야 한다.

 

- 오름차순으로 정렬된 항목들에 대해 중간값을 찾아 탐색 키와 비교한다.

- 탐색 키와 중간 값이 같으면 중간 값의 위치(인덱스)를 반환하고 탐색을 종료한다.

- 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽에 있는 항목들로, 중간 값보다 크면 중간 값 오른쪽에 있는 항목들로 탐색 범위를 변경한다.

- 변경된 범위 항목에 대해 위의 과정을 반복한다.

- 탐색 대상 항목 수가 0이면 탐색 키를 찾지 못한 경우로 탐색을 종료한다.

 

- 시간 복잡도는 O(log₂ⁿ ) 이므로 순차 탐색에 비해 속도가 빠르다.

 

#include <stdio.h>

int binary_search(int mylist[], key, left, right);

void main() 
{
    int pos, size = 9;
    int mylist[] = {0, 1, 5, 9, 13, 17, 23, 32, 45};
    
    pos = binary_search(mylist, 45, 0, size-1);
    print("position = %d\n", pos);
    
    pos = binary_search(mylist, 8, 0, size-1);
    print("position = %d\n", pos);
}

int binary_search(int mylist[], key, left, right)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (key == mylist[mid]
            return mid;
        else if (key < mylist[mid])
            right = mid - 1;
        else if (key > mylist[mid])
            left = mid + 1;
    }
    return -1
}

 

4. 보간 탐색

- 항목들이 정렬되어 있을 때 키 값의 차이와 위치의 차이가 비례한다는 가정을 바탕으로 한다.

- 탐색 키와 탐색 경계 값과의 차이를 고려하여 비교 키의 위치를 결정한다. 

- (list[right] - list[left]) : (key - list[left]) = (right - left) : (탐색 위치 - left)

- (양쪽 경계 값들의 차이) : (키 값과 왼쪽 경계 값의 차이) = (양쪽 범위의 거리) : (탐색 위치와 왼쪽 경계의 거리 차이)

 

 

#include <stdio.h>

int interpolate_serarch (int list[], int size, int key);

void main()
{
    int size = 12;
    int key = 39;
    int pos;
    int list[] = {2, 3, 5, 7, 8, 10, 13, 20, 25, 39, 45, 55};
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
    key = 2;
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
    key = 55;
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
}

int interpolate_search(int list[], int size, int key)
{
    int pos;
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        pos = left + (key - list[left]) * (right - left) / (list[right] - list[left]);
        if (list[pos] < key)
            left = pos + 1;
        else if (list[pos] > key)
            right = pos - 1;
        else return pos;
    }
    return -1;
}

 

5. 해싱 탐색

- 탐색 키에 직접 산술적인 연산을 적용하여 탐색 키의 정보가 저장되어 있는 테이블 상의 위치를 계산하고 이 주소를 통해서 정보에 접근하는 방식이다.

- 즉, 반복적인 비교를 수행하는 것이 아니라, 키 자체에 있는 해답을 해시 함수를 통해 찾아내는 것이다.

- 시간 복잡도는 이론적으로 O(1)로 입력의 수 n에 상관없이 일정한 상수 시간을 갖는다.

 

- (ex) Dictionary

    - Entry (key, value)  // (word, definition)

    - Applications

        - Word / Thesaurus references

        - Spelling checker in word processor or editor

        - Electronic signature encoding/decoding

    - Operations

        - determine if a particular symbol(key) exists in the table (단순조회)

        - retrieve the attributes of a key (키의 속성값을 참조하는 연산)

        - modify the attributes of a key (키의 속성값 변경)

        - insert a new entry with a key and value (새로운 entry 추가)

        - delete an entry (entry 삭제)

 

해싱의 원리

 

5-1. Terms

- 해시 테이블 : 명칭(identifier)들이 저장된 고정된 크기의 표

- 명칭 밀도(ID) : 전체 명칭의 개수(T) 중 해시 테이블에 적재된 명칭 개수(n)의 비율 = n / T

- 적재 밀도(LD) : 해시 테이블의 크기에 대해 적재된 명칭 개수의 비율 = n / N

- 동의어(synonym) : 해시 테이블의 동일한 버켓 주소로 매핑된 서로 다른 명칭들, f(i₁) = f(i₂) 이면 i₁와 i₂는 동의어이다.

- 오버플로우 (overflow) : 명칭 i가 이미 꽉 찬 버켓으로 해싱(매핑)되는 경우 오버플로우가 발생한다고 말한다.

- 충돌 (collision) : 두 개의 서로 다른 명칭이 해시 테이블의 같은 버켓 주소로 매핑되면 충돌이 발생한다고 한다. 버켓의 크기가 1이면 충돌과 오버플로우가 동시에 발생한다.

 

- 해시 함수 : 해시 함수는 계산이 쉬워야 하고 명칭 간의 충돌을 최소화하여야 한다. 또한, 비대칭 편중분포를 막아야 한다.

 

    - 균등 해시 함수 : 각 버켓에 적재될 확률이 1/b 인 해시 함수 (P[f(x) = i] = 1 / b

    - 중간 제곱 해시 함수 : 명칭을 2진수로 변환한 후 제곱한 결과값에서 중간의 일부분을 해시 테이블 주소로 활용하는 함수, 테이블에 2ⁿ개의 버켓이 존재한다면 n개의 비트를 추출한다. collision을 최소화하기 위해 사용된다. 

    - 나눗셈 해시 함수 : 명칭을 특정 수로 나눈 나머지를 해시 테이블 주소로 사용하는 방법,예를 들어 해시 테이블 크기가 D라면 명칭 x를 D로 나눈 나머지 (0 ~ D-1)을 주소 값으로 사용한다. 이때 D는 분포에 영향을 주기 때문에 "소수"를 사용하는 것이 가장 좋고, 짝수는 사용하지 않는다. 나누는 수로 짝수를 사용하면 편중분포가 나타나기 때문이다.

    - 폴딩 해시 함수 : 명칭에 해당하는 비트 열을 해시 테이블 크기만큼 여러번 접어서 주소값으로 사용하는 것이다.

        - 이동 폴딩 : 명칭을 k 자리수로 분할한 뒤 순서대로 더한 결과값을 오른쪽에서 k자리 만큼 추출하여 주소 값으로 사용

        - 경계 폴딩 : 분할한 문자열에서 짝수 번째 문자열을 뒤집어서 덧셈을 수행한 후 k 자리의 문자열을 추출하여 사용

    - 키 분석 해시 함수 : 명칭의 구성과 내용을 미리 예측할 수 있는 경우에는 명칭을 분석하여 해시 테이블 주소로 사용할 키 값을 추출하는 방법을 사용할 수 있다. 예를 들어서 명칭이 학번일 경우, 앞의 두 자리는 입학년도임을 알고 그 부분은 배제하고 생각할 수 있다.

 

5-2. Static Hashing

- 해시 테이블의 크기가 고정되어있어 프로그램을 변경하지 않는 한 크기가 변경되지 않는 해싱 탐색 방법이다.

 

cf) Dynamic Hashing - 키 충돌 빈도에 따라 유연하게 해시 테이블 크기를 재구성하는 방법이다.

 

5-3. Hash Table 생성

// 해시 테이블 선언문

#define TABLE_SIZE 13

struct bucket
{
    int flag;
    char key[10];
};

struct bucket hash_table[TABLE_SIZE];
// 해시 테이블 초기화

void init_table()
{
    int i;
    for (i = 0; i < TABLE_SIZE; i++)
        hash_table[i].flag = 0;
}

 

5-4. Overflow 처리 방법

- Linear Probing 선형 탐색

    - static hashing 인 경우에 적용 가능하다.

    - overflow가 발생했을 때 선형적으로(순차적으로) 다른 비어있는 slot을 찾아가는 방법이다.

    - 이 결과 다른 home bucket으로 값이 저장될 수 있다.

 

    - HT[f(x) + j] % TABLE_SIZE, where 0 ≤ j ≤ TABLE_SIZE

 

    - 선형탐색에 의한 명칭 삽입 처리시 다음의 4가지 겨우 중 한 가지가 발생한다.

 

    1) 탐색된 버켓에 삽입하려는 명칭이 이미 저장되어 있는 경우 : 중복된 명칭으로 보고하고 오류 처리 or 특정 필드 값 갱신

    2) 탐색된 버켓이 비어 있는 경우 : 해당 버켓에 명칭 저장

    3) 탐색된 버켓이 x가 아닌 다른 명칭을 포함하고 있는 경우 : 다음 버켓 탐색 지속

    4) 탐색 결과 홈 버켓ㅇ로 다시 돌아온 경우 : 전체 버켓이 모두 꽉 찬 상태 → 오류 보고 후 종료

 

    - 문제점 : 명칭들이 서로 모여서 클러스터를 형성한다. 충돌 횟수가 증가할수록 탐색 속도도 느려진다. 

 

- 해시 함수 정의 

    - 키 (명칭)들을 ASCII 숫자값으로 변환한 뒤 해시 주소를 계산하는 방법이다.

// sum of ASCII codes of string chars

int transform (char *key)
{
    int number = 0;
    while (*key)                // NULL 값이 아니면
        number += *(key++);     // 정수 + 문자 -> 문자가 ASCII 코드로 변환됨
    return number;
}

int hash (char *key)
{
    return (transform(key) % TABLE_SIZE);
}

    - (ex)

F O R \0

이 경우 number는 F, O, R 의 ASCII 코드의 합이 된다. 그리고 그 합을 table size로 나눈 나머지가 주소가 된다.

 

5-5. Overflow 해결방법

- Linear probing 선형탐색법

    - ht[(f(x) +i) % b], 0 ≤ i ≤ b-1

 

- Quadratic probing 이차조사법

    - ht[f(x)], ht[f(x) + i²) % b], ht[f(x) - i²) % b], ..., 

    - 선형탐색법을 양방향으로 번갈아 탐색하는 방법이라고 볼 수 있다.

    - 선형탐색법은 한 방향으로 계속 탐색하기 때문에 cluster를 형성하기 쉬웠고, 이 방법은 그것을 해결할 수 있다.

 

- Rehashing 재해싱

    - overflow가 발생할 때마다 또 다른 해시 함수를 통해서 새로운 버켓을 탐색하는 방법이다.

    - 준비한 모든 해시 함수를 적용해도 빈 버켓 주소를 찾지 못하면 오류를 보고하거나 준비된 처리를 시행한다.

 

- Chaining 해시 체인

    - 각 버켓을 연결 리스트로 구현하여 특정 버켓에 충돌되는 명칭들을 연결 리스트로 관리하는 방법이다.

    - 근본적으로 overflow를 방지할 수 있다.

    - 하지만, 버켓 수에 비례하는 연결 리스트가 필요하며 원래 해싱 탐색 시간인 O(1)에 연결 리스트 탐색 시간 O(n)이 추가적으로 ㅣㄹ요하다. 

    - 각 연결 리스트에는 버켓의 헤드 노드가 존재한다.

                                                                    

 

 

'Software > Data Structures' 카테고리의 다른 글

[Python] 2. Python Data Type  (0) 2022.04.16
[Python] 1. Introduction  (0) 2022.03.08
[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18
[자료구조] 알고리즘 성능 분석  (0) 2021.04.17

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

 

1. 순서 리스트

- 원소들을 순서에 따라 배열한 리스트이다.

- (ex) days of week, months of year, ...

- C언어의 경우 같은 자료형으로 이루어져 있다.

 

- Array 배열

    - 선언한 뒤 원소의 개수를 바꿀 수 없다.

    -따라서 크기를 잘 설정하지 않으면 공간이 부족하거나 메모리 낭비가 발생할 수 있다.

    - 메모리에서 연속적으로 할당되며, 인덱스로 접근한다.

    - 중간에 원소를 추가하거나 제거하기도 어렵다.

 

- Linked list 연결 리스트

    - 메모리에 분산된 장소로 저장되어 있다.

    - 즉, 노드들이 메모리에 흩어져 있지만, 포인터로 연결되기 때문에 순서는 존재한다.

    - 크기 조절이 가능하다.

    - 중간에 원소 변경도 가능하다.

    - 하지만, 관리를 잘못했을 때 overhead 등 심각한 오류가 발생할 수 있다.

    - 사용자가 직접 연결 리스트의 노드를 실행 중에 관리하는 것을 '동적 메모리 관리'라고 한다.

 

2. 연결 리스트

- 특징

    - 원소들은 메모리 상에서 물리적으로 분산되어 있다.

    - 논리적으로는 포인터로 연속적으로 연결되어 있다.

    - 원소들은 필요할 때 생성될 수 있다.

 

- 표현

    - 연결 리스트의 원소는 '노드'라고 부르며 구조체로 선언된다.

    - 데이터 필드 : 정보를 저장한다. 데이터 필드를 추가함으로써 구조체를 확장할 수 있다.

    - 링크 포인터 필드 : 노드와 다음 노드를 연결하는 연결 포인터이다.

    - 연결 리스트의 노드는 자신과 동일한 구조체 자료형을 참조하기 때문에 자기 참조형 구조체라고도 부른다.

 

- ex

#include <stdio.h>

typedef struct node_type * note_ptr;

struct node_type
{
    int data;
    note_ptr link;
};

void main()
{
    struct node_type node1, node2, node3;
    node1.data = 7;
    node2.data = 11;
    node3.data = 13;
    node1.link = &node2;
    node2.link = &node3;
    node3.link = NULL;
    printf("%d %d %d", node1.data, node2.data, node3.data);
}

3개의 노드가 링크로 연결된 연결 리스트 예제이다. 

노드는 node_type 구조체형으로 선언되고, 링크 포인터는 구조체에 대한 포인터이며 node_ptr로 선언된다.

이 연결 리스트는 정적 메모리 공간에 노드 객체를 생성하여 연결한 경우이다.

따라서 실행 중에는 노드를 위한 공간을 할당할 수 없다.

 

- 연결 리스트 노드의 멤버에 접근할 때에는 ' -> ' 화살표 연산자를 사용한다.

- node1 -> data

- 필요 없는 노드는 free함수를 통해 해제하고 힙 공간으로 반환하는 것이 좋다.

 

따라서 위의 코드는 다음과 같이 나타낼 수 있다.

//node1.data = 7;
node1 -> data = 7;

//node2.data = 11;
node2 -> data = 11;

//node1.link = &node2;
node1 -> link = node2;

//node2.link = &node3;
node2 -> link = node3;

printf("node1 : %d", node1 -> data);

 

주소 변수 메모리
100 1000 node1 정적 메모리
     
110 1300 node2
     
120 1200 node3
     
1000 7 data 동적 메모리
  1200 link
1200 13 data
  NULL link
1300 11 data
  1200 link
     

- 자료형으로 선언된 변수인 node1, node2, node3 은 정적 공간에 할당된 반면, malloc 함수에 의해 생성된 연결 리스트 노드들은 힙 메모리에 저장되어 있다. 

 

3. 동적 메모리 할당

- 정적 메모리 : 컴파일 할 때 메모리가 할당된다. 자료형이 있고, 선언되는 모든 변수가 정적 메모리를 가진다.

- 동적 메모리 : 실행될 때 메모리가 할당된다.

 

3-1. Operators

- malloc 

    - 지정된 크기의 메모리 할당을 요청한다.

    - 할당된 장소의 주소를 반환한다.

    - malloc으로 할당된 메모리 공간은 free() 를 선언하기 전까지 사라지지 않는다.

 

- free 

    - 할당된 메모리 공간을 해제하는 함수이다.

    - 해제하지 않으면 메모리 고갈이 발생한다.

 

3-2. Example (dynamic memory == heap memory)

void heap_test()
{
    int *pi;
    float *pf;
    
    pi = (int *) malloc (sizeof(int));
    pf = (float *) malloc (sizeof(float));
    *pi = 1024;
    *pf = 3.14;
    
    printf("%d, %f, %u\n", *pi, *pf, &pi);
    free(pi);
    free(pf);
}

 

처음 *pi와 *pf는 정적 메모리 공간에 할당되었다.

 

    pi = (int *) malloc (sizeof(int));
    pf = (float *) malloc (sizeof(float));

 

이 두 문장으로 pi와 pf 에 각각 동적 메모리 공간을 가리키는 포인터를 할당하였다.

 

    *pi = 1024;
    *pf = 3.14;

 

이 두 문장은 각각의 포인터가 참조하는 공간에 해당하는 값을 저장하는 실행문이다. 

 

따라서 메모리 공간이 아래와 같이 할당되었을 때, 프린트문을 실행하면 결과값은 다음과 같이 나온다.

1024, 3.14, 100

 

 

4. 단방향 연결 리스트

- 노드들이 한 방향으로만 연결된 경우를 단방향 연결 리스트라고 한다.

- 첫번째 노드를 참조하는 포인터를 '리스트 포인터'라고 한다.

- 이를 통해 리스트 노드들을 탐색한다.

 

- 노드 삽입

    - malloc 함수로 삽입할 노드를 생성하고, 그 주소를 포인터 노드에 할당한다.

    - 생성된 노드의 데이터 필드에 값을 저장하고, 링크 필드에 NULL을 저장한다.

    - 연결 리스트 포인터가 list라고 가정할 때 

 

        1) 연결 리스트가 비어 있는 경우 (empty)

            - 삽입할 노드가 유일한 노드이므로 이 노드가 첫 노드가 되도록 리스트 포인터(list)에 노드의 주소 값을 저장하고 종료한다.

 

        2) 비어 있지 않은 경우

            - 리스트 중간에 삽입되는 경우 (앞 노드가 있는 경우)

            → 앞 노드의 링크 필드 값을 노드의 링크에 저장한다.

            → 앞 노드의 링크 필드에 노드의 주소 값을 저장하고 종료한다.

 

            - 리스트 맨 앞에 삽입되는 경우

            → 삽입할 노드의 링크 필드에 연결리스트 포인터 값 지정한다.

            → 연결리스트 포인터가 노드를 가리키도록하고 종료한다.

- malloc 함수로 새 공간을 요청해도 가용 힙 메모리가 더 이상 없다면 주소 값 대신 NULL 값이 반환된다.

 

- 선언

typedef struct list_node *list_ptr;
struct list_node {
    char data[4];
    list_ptr link;
};
list_ptr ptr = NULL;

 

- macro function for empty list

#define IS_EMPTY(ptr) (!ptr)

ptr이 NULL값이면 IS_EMPTY(ptr)은 1을 반환한다.

 

- 노드 초기화

ptr = (list_ptr) malloc (sizeof(struct list_node));
strcpy(ptr -> data, "com");
ptr -> link = NULL;

 

- 노드 삽입

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr list;
void insert_node(node_ptr prev, int data);
void print_list(node_ptr list);

void main()
{
    node_ptr node1, node2, node3;
    
    node1 = (node_ptr) malloc(sizeof(struct node_ytpe);
    node1 -> data = 100;
    node1 -> link = NULL:
    list = node1;
    
    node2 = (node_ptr) malloc(sizeof(struct node_ytpe);
    node2 -> data = 200;
    node2 -> link = NULL:
    list = node2;
    
    print_list(list);
    insert_node(node1, 150);
    printf_list(list);
}

void insert_node(node_ptr prev, int data)
{
    node_ptr node;
    node = (node_ptr) malloc (sizeof(struct node_type));
    if (!node) exit(1);
    node -> data = data;
    node -> link = NULL;
    
    if (!list) {
        list = node;
    }
    else if(prev) {
        node -> link = prev -> link;
        prev -> link = node;
    }
    else {
        node -> link = list;
        list = node;
    }
}

void print_list (node_ptr list) 
{
    while (list) {
        printf("%d ", list -> data);
        list = list -> link;
    }
    printf("\n");
         
}               

 

- 노드 삭제

 

    1) 리스트가 비어 있는 경우 

        - 그대로 종료한다.

    2) 리스트에 노드가 존재하는 경우 

    2-1) 중간 노드 삭제

        - 삭제 노드의 앞 노드의 링크 필드에 삭제할 노드의 링크를 저장한다.

    2-2) 맨 앞 노드 삭제

        - 리스트 포인터에 삭제할 노드의 링크를 저장한다.

    - 노드를 삭제하고 종료한다.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr list;
void delete_node (node_ptr prev, node_ptr node);
void print_list (node_ptr list);

void main()
{
    node_ptr node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 100;
    node1 -> link = NULL;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 200;
    node2 -> link = NULL;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 300;
    node3 -> link = NULL;
    node2 -> link = node3;
    
    print_list(list);
    delete_node(node1, node2); // node1 : prev, node2 : delete
    print_list(list);
}

void delete_node(node_ptr prev, node_ptr node)
{
    if (prev) {
        prev -> link = node -> link;
    }
    else {
        list = node -> link;
    }
    free(node);
}

void print_list(node_ptr list)
{
    while(list) {
        printf("%d", list -> data);
        list = lsit -> link;
    }
    printf("\n");
}

 

5. 연결 리스트 연산자

5-1. 연결 리스트 길이

- 노드 수로 계산한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

int length_list(node_ptr list);

void main()
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 100;
    node1 -> link = NULL;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 200;
    node2 -> link = NULL;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 300;
    node3 -> link = NULL;
    node2 -> link = node3;
    
    printf("list lentgh is %d\n", length_list(list));
}

int lentgh_list (node_ptr list)
{
    int count = 0;
    node_ptr temp = list;
    while (temp)
    {
        count ++;
        temp = temp -> link;
    }
    return count;
}

 

5-2. 연결 리스트의 결합

- 두 개의 연결 리스트를 연결하여 하나로 합치는 것이다. 

- 결합 연산은 앞 리스트의 노드 수에 비례하여 시간이 걸리므로, 시간복잡도는 O(첫번째 리스트의 길이) 가 된다.

 

- 첫 번째 리스트가 빈 리스트라면 두 번째 리스트를 그대로 반환하고 종료한다.

- 첫 번째 리스트가 빈 리스트가 아니라면 두 번째 리스트를 확인한다.

    - 두 번째 리스트가 빈 리스트라면 첫 번째 리스트를 그대로 반환하고 종료한다.

    - 두 번째 리스트가 빈 리스트가 아니라면 결합하기 위해 첫 번째 리스트의 마지막 노드를 탐색하고, 마지막 노드의 링크 필드에 두 번째 리스트 포인터(list2)를 저장한 후 첫 번째 리스트 포인터(list1)를 반환하고 종료한다.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr concat_list(node_ptr list1, note_ptr list2);
void print_list(list1);

void main()
{
    node_ptr list1, list2, node1, node2;
    list1 = (node_ptr) malloc (sizeof(struct node_type));
    list1 -> data = 100;
    
    node1 = (node_ptr) malloc (sizeof(struct node_type);
    node1 -> data = 150;
    node1 -> link = NULL;
    
    list1 -> link = node1;
    
    list2 = (node_ptr) malloc (sizeof(struct node_type));
    list2 -> data = 200;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 250;
    node2 -> link = NULL;
    
    list2 -> link = node2;
    
    print_list(list1);
    print_list(list2);
    list1 = concat_list(list1, list2);
    print_list(list1);
}

node_ptr concat_list (node_ptr list1, node_ptr list2)
{
    node_ptr temp;
    if (!list1)
        return list2;
    else {
        if (list2) {
            temp = list1;
            while (temp -> link)
                temp = temp -> link;
                
            temp -> link = list2;
        }
        return list1;
    }
}

void print_list(node_ptr list)
{
    while (list) {
        printf("%d", list -> data);
        list = list -> link;
    }
}

 

6. 순환 연결 리스트

- 연결 리스트의 마지막 노드의 링크가 NULL이 아니고, 그 리스트의 첫 노드에 다시 연결되어 있는 형태를 말한다.

- 시작 노드가 변경되어도 전체 노드들이 여전히 연결되어 있는 상태이기 때문에 시작 노드 변경이 용이하다.

 

- 순환 연결 리스트의 길이

    - 시작노드로 다시 되돌아올 때가 전체 노드를 모두 탐색한 시점이다.

    - do - while 문 사용

 

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

int clist_length(node_ptr list);

void main() 
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type);
    node1 -> data = 7;
    list = node1;
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 11;
    node1 -> link = node2;
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 13;
    node2 -> link = node3;
    node3 -> link = node1;
    
    printf("circular list length = %d", clist_length(list));
}

int clist_length(node_ptr list)
{
    node_ptr move;
    int num = 0;
    if (list) {
        move = list;
        do {
            num ++;
            move = move -> link;
        } while (move != list);
    }
    
    return num;
}

 

7. 역순 연결 리스트

- 리스트 노드의 연결 순서를 반대로 뒤집어서 리스트로 반환하는 형식이다.

- (ex) [7 - 11 - 13] → [13 - 11 - 7]

- 시간 복잡도는 리스트의 길이(노드의 개수)에 비례한다.

 

- 리스트가 비어있거나 노드가 1개만 있는 경우 그대로 리스트 포인터(one)를 반환하고 종료한다.

- 리스트에 노드가 2개 이상인 경우 2개의 임시 포인터 변수(two, three)를 더 사용하여 연결 순서를 변환한다.

    - 노드 포인터(three)가 노드 포인터(two)를 참조하게 한다.

    - 노드 포인터(two)가 노드 포인터(one)를 참조하게 한다.

    - 노드 포인터(one)를 다음 노드로 이동시킨다.

    - 노드 포인터(two)의 링크 필드에 노드 포인터(three) 값을 저장하여 두 노드를 연결 시킨다.

    - 노드 포인터(one)가 NULL이 아닐 때까지 반복한다.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type 
{
    int data;
    node_ptr link;
};

node_ptr reverse_list(node_ptr);
void print_list(node_ptr);

void main()
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 7;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 11;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 13;
    node2 -> link = node3;
    node3 -> link = NULL;
    
    print_list(list);
    list = reverse_list(list);
    print_list(list);
}

node_ptr reverse_list(node_ptr one)
{
    node_ptr two, three;
    two = NULL;
    while (one) {
         three = two;
         two = one;
         one = one -> link;
         two -> link = three;
    }
    return two;
}

void print_list(node_ptr list)
{
    while(list) {
        printf(%d ", list -> data);
        list = list -> link;
    }
}

 

8. 양방향 연결 리스트          

- 각 노드가 자신의 이전과 이후 노드에 대한 링크 포인터를 가지고 있다.

- 노드 삽입 또는 삭제 시 앞 노드를 추가로 알려줄 필요가 없기 때문에 편리하다.

- 대표적으로 이진 트리에 사용된다.

 

- node == node -> llink -> rlink == node -> rlink -> llink

 

- 단방향 연결 리스트와 달리 모든 노드의 링크 필드 값을 채워야 한다.

- 따라서 삭제할 수 없는 head 노드가 사용된다.

- 시작 노드의 llink 필드는 head 노드를 참조하도록 초기화된다.                  

// 양방향 연결 리스트의 선언

typedef struct node_type * node_ptr;
struct node_type 
{
    node_ptr llink;
    int data;
    node_ptr rlink;
};

 

- 노드 삽입

    - 노드의 llink를 prev 노드로 연결한다.

    - 노드의 rlink를 prev 다음 노드로 연결한다.

    - prev 다음 노드의 llink가 노드를 참조하도록 연결한다.

    - prev 노드의 rlink가 노드를 참조하도록 연결한다.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct dll_node_type * dll_node_ptr;
struct dll_node_type 
{
    dll_node_ptr llink;
    int data;
    dll_node_ptr rlink;
};

void insert_dll (dll_node_ptr prev, dll_node_ptr node);
void print_dll_list (dll_node_ptr list1);

void main()
{
    dll_node_ptr head, list, node1, node2, node3;
    head = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 -> data = 7;
    list = node1;
    
    head -> llink = NULL;
    head -> rlink = node1;
    node1 -> llink = head;
    
    node2 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node2 -> data = 13;
    node2 -> llink = node1;
    node2 -> rlink = head;
    node1 -> rlink = node2;
    
    node3 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node3 -> data = 11;
    node3 -> llink = NULL;
    node3 -> rlink = NULL;
    head -> llink = node2;
    
    print_dll_list(head, list);
    insert_dll(node1, node3);
    print_dll_list(head, list);
}

void insert_dll (dll_node_ptr prev, dll_node_ptr node)
{
    node -> llink = prev;
    node -> rlink = prev -> rlink;
    prev -> rlink -> llink = node;
    prev -> rlink = nodel
}

void print_dll_list (dll_node_ptr head, dll_node_ptr list) 
{
    while (list != head) {
        printf("%d ", list -> data);
        list = list -> rlink;
    }
    printf("\n");
}

 

- 노드 삭제

    - head 노드는 삭제가 불가능하다.

    - 일반 노드의 삭제일 경우 삭제할 노드의 이전 노드의 rlink에 삭제할 노드의 다음 노드 주소를 저장한다.

    - 삭제할 노드의 다음 노드의 llink에 노드 이전 노드를 복사한다.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct dll_node_type * dll_node_ptr;
struct dll_node_type 
{
    dll_node_ptr llink;
    int data;
    dll_node_ptr rlink;
};

void delete_dll (dll_node_ptr head, dll_node_ptr node);
void print_dll_list (dll_node_ptr head, dll_node_ptr list);

void main()
{
    dll_node_ptr head, list, node1, node2, node3;
    head = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 -> data = 7;
    list = node1;
    
    head -> llink = NULL;
    head -> rlink = node1;
    node1 -> llink = head;
    
    node2 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node2 -> data = 13;
    node2 -> llink = node1;
    node1 -> rlink = node2;
    
    node3 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node3 -> data = 11;
    node3 -> llink = node2;
    node3 -> rlink = head;
    node2 -> rlink = node3;
    head -> llink = node3;
    
    print_dll_list(head, list);
    insert_dll(node1, node3);
    print_dll_list(head, list);
}

void insert_dll (dll_node_ptr prev, dll_node_ptr node)
{
    node -> llink = prev;
    node -> rlink = prev -> rlink;
    prev -> rlink -> llink = node;
    prev -> rlink = nodel
}

void print_dll_list (dll_node_ptr head, dll_node_ptr list) 
{
    while (list != head) {
        printf("%d ", list -> data);
        list = list -> rlink;
    }
    printf("\n");
}

                                                                                                                                                                     

'Software > Data Structures' 카테고리의 다른 글

[Python] 1. Introduction  (0) 2022.03.08
[자료구조] 탐색  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18
[자료구조] 알고리즘 성능 분석  (0) 2021.04.17
[자료구조] Recursion 재귀 호출  (0) 2021.04.17

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

 

1. 다차원 배열

- 2차원 이상의 배열을 다차원 배열이라고 한다.

- 논리적으로는 m차원이지만, 물리적으로는 1차원으로 메모리 상에 표현됟나.

 

- m차원 배열 A : int A[n₀][n₁] ··· [nₘ₋₁];

- 배열 A에 저장되는 원소의 총 개수 : n₀ x n₁ x ··· n

   예를 들어 A[10][9][8]로 선언된 배열 원소의 총 개수는 10 x 9 x 8 = 720개이다.

 

1-1. 행 우선 순서 (Row-major order)

- 기본 주소에서부터 행을 기준으로 원소가 저장된다. 

- 배열 원소의 오른쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 왼쪽 옆자리가 1씩 증가된다.

- 이런식으로 인덱스 값이 오른쪽에서 왼쪽 방향으로 증가하면서 메모리에 저장된다.

 

- (ex) A[0][0] → A[0][1] → A[1][0] → A[1][1] → A[2][0] → A[2][1]

 

1-2.  열 우선 순서

 

- 열을 우선적으로 채워가는 형식이다.

- 배열 원소의 왼쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 오른쪽 옆자리가 1씩 증가된다.

- (ex) A[0][0] → A[1][0] → A[2][0] → A[0][1] → A[1][1] → A[2][1]

 

2. 원소의 주소

 

2-1. 1차원 배열

- 원소의 위치는 시작주소(α) + 오프셋(offset) 값으로 계산된다.

- n개의 원소를 가지고 있는 1차원 배열 A의 시작 주소가 α이고, 각 원소에 s바이트가 할당된다고 할 때,

 &A[0] = α + 0 * s

 &A[1] = α + 1 * s

 ...

 &A[n-1] = α + (n-1) * s

 

→ &A[i] = α + i * s

 

2-2. 2차원 배열

- A[u][u]으로 선언된 2차원 배열에서 A[i][j] 주소는 α + (i * u + j) * s 이다.  // 행 우선 순서일 때

- 열 우선 순서일 때의 주소는  α + (i + u * j) * s 이다.

 

 

2-3. 3차원 배열

- A[u][u₁][u₂] 으로 행 우선 순서로 선언된 2차원 배열에서 A[i][j][k]의 주소는 α + (i * u₁ * u₂ + j * u₂ + k) * s이다.

 

- 열 우선 순서로 저장된 배열의 주소는 α + (i * u₁ * u₂ + j + u₁ * k) * s이다.

 

3. Stack 스택

- 선형 리스트의 특별한 형태로, 한 방향으로 쌓아둔 것을 의미한다.

- 후입 선출 구조이다. (LIFO : Last-In, First-Out)

- 함수 호출 관리, 문법 검사, 연산식 평가 등에 활용된다.

- S = [a₀, a₁, ..., aₙ₋₁] 형식으로 원소들의 리스트로 정의할 수 있다.

- a₋₁ 이 가장 나중에 삽입된 원소이다.

 

- 스택에 원소를 추가하는 연산을 "push"라고 하고, 원소를 삭제하는 연산을 "pop"이라고 한다.

- top 포인터는 가장 나중에 삽입된 원소를 가리키며, 그 위치에 해당하는 배열 인덱스 값을 갖는다.

- 빈 스택에서 top 포인터는 -1 값을 갖는다.

- 1차원 배열로 구성된 스택에 최초로 들어오는 원소는 stack[0]에 저장된다.

 

- (ex) Function Call

    - A()가 실행 중일 때 B를 호출하면, B()가 끝날 때까지 A()는 멈춰있다.

    - 새로운 함수가 실행될 때마다 현재 실행 중인 함수의 환경 변수를 시스템 스택에 Stack Frame 형태로 저장해야 한다.

 

    - Stack Frame (Activation record)

        - 지역 변수

        - 재개할 때 다음에 실행될 명령어의 주소

        - 이전 stack frame의 포인터

 

 

#define STACK_SIZE 100
int stack[STACK_SIZE];
int top = -1;

void push(int item);
int pop;
void print_stack();

void main() 
{
    push(3);
    push(4);
    push(5);
    pop();
    print_stack();
    pop();
    print_stack();
    pop();
    print_stack();
    pop();
    print_stack();
}

void print_stack()
{
    int i;
    for(i = 0; i <= top; i++)
        printf("%d", stack[i]);
    
    printf("\n");
}

void push(int item)
{
    if (top >= STACK_SIZE - 1){
        printf("stack full");
        return;
    }
    
    stack[++top] = item;
    print_stack();
}

int pop()
{
    if (top < 0) {
        printf("stack empty");
        return -999;
    }
    return stack[top--];
}

 

- 실행 결과

3

3 4

3 4 5

3 4

3

 

stack empty

 

4. Queue 큐

- 처리를 기다리고 있는 원소들의 리스트라고 볼 수 있다.

- 스택과 같은 선형 리스트 구조이다.

- 스택과 다른 점은 "선입 선출" 방식이라는 것이다. (FIFO : First-In, First-Out)

- 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고, 큐의 맨 앞(front)원소가 가장 먼저 삭제된다.

- Q = [a₀, a₁, ..., aₙ₋₁] 형식으로 정의할 수 있으며, a₀가 가장 먼저 삽입된 원소이고, aₙ₋₁가 가장 나중에 삽입된 원소이다.

- 큐의 맨 앞과 맨 뒤를 가리키기 위한 두 개의 포인터 (front, rear) 가 필요하다.

 

- 원소가 삽입될 때에는 rear 포인터가, 삭제될 때에는 front 포인터가 각각 사용된다.

- rear 포인터 값이 큐의 상한 경계와 같으면 full queue로 판단하고, rear와 front 포인터의 값이 같으면 empty queue로 간주한다.

 

#define QUEUE_SIZE 100
int queue[QUEUE_SIZE];
int rear = -1;
int front = -1;
void print_queue();
void addq(int item);
int deleteq();

void main()
{
    int temp;
    
    addq(3);
    addq(5);
    addq(7);
    temp = deleteq();
    print_queue;
}

void print_queue()
{
    int i;
    
    for (i = front + 1; i <= rearl i ++)
        printf("%d", queue[i]);
    
    printf("\n");
}

void addq(int item)
{
    if(rear == QUEUE_SIZE - 1) {
        printf("Queue Full. item not added");
        return;
    }
    queue[++rear] = item;
    print_queue;
}

int deleteq()
{
    if (front == rear) {
        printf("Queue empty.");
        return -999;
    }
    return queue[++front];
}

 

- 실행 결과

3

3 5

3 5 7

5 7

 

4-1. 일반 큐

- 원소의 삽입, 삭제 시 rear와 front 포인터 값이 모두 증가된다.

- 삽입 삭제 빈도가 증가할수록 큐에서 원소들의 저장 위치가 점점 오른쪽으로 이동하게 되고, 왼쪽에 빈공간이 생기게 된다.

- 따라서 원소가 다 차지 않았음에도 queue full 신호가 발생할 수 있다.

 

- 큐의 빈공간을 재사용하기 위해서는 원소들을 왼쪽으로 이동시키는 작업을 주기적으로 해주어야 한다. 이를 해결한 자료구조가 "순환 큐"이다.

 

4-2. 순환 큐

- 큐의 오른쪽 끝을 반대편 끝과 연결하여 원소가 이동할 필요 없이 전체 공간을 모두 사용할 수 있다.

 

- 일반 큐와 마찬가지로 front와 rear 포인터 값이 같을 때를 empty queue로 정의한다.

- front와 rear의 초기값은 각각 0이다. 

- 순환 큐의 모든 공간에 원소가 삽입되면 front와 rear 값이 또 같아지게 된다.

- 이런 상황을 피하기 위해 rear = front - 1인 시점, 즉 원소가 n-1개 삽입된 상태를 full queue로 간주한다.

 

#include <stdio.h>
#define QUEUE_SIZE 100
int front, rear;
int cqueue[QUEUE_SIZE];
void addcq(int item);
int deletecq;
void print_queue();

void main()
{
    int temp;
    front = rear = 0;
    
    addcq(11);
    addcq(13);
    addcq(17);
    addcq(19);
    
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
}

void addcq(int item)
{
    if (front == ((rear + 1) % QUEUE_SIZE) {
        printf("queue full");
        return;
    }
    rear = (rear + 1) % QUEUE_SIZE;
    cqueue[rear] = item;
    print_queue();
}

int deletecq()
{
    if (front == rear) {
        printf("queue empty");
        return -999;
    }
    front = (front + 1) % QUEUE_SIZE;
    return cqueue[front];
}

void print_queue()
{
    int i = front;
    while (i != rear) {
        i = (i + 1) % QUEUE_SIZE;
        printf("%d", cqueue[i]);
    }
    printf("\n");
}

 

- 일반 큐와는 달리 순환 큐이기 때문에 if (front == ((rear + 1) % QUEUE_SIZE) 와 같이 "%" 연산자를 사용해야 한다.

- (ex) QUEUE_SIZE = 6이면 인덱스는 0 ~ 5가 존재한다. 이번에 마지막 칸인 인덱스가 5인 칸에 값을 넣었다면 그 다음칸은 6 % 6 인 0이 되어야 한다. 그리고 그것이 front 값과 같기 때문에 full queue가 되었음을 알 수 있다.

 

5. Deque 

- Double ended queue

- 양방향으로 삽입과 삭제가 모두 가능한 자료구조이다.

 

 

6. 수식 평가

- 수식은 연산자와 피연산자로 구성된 문장이다.

- 연산자는 산술 연산자, 논리 연산자, 대입 연산자 등이 있다.

- 피연산자는 변수 또는 상수가 될 수 있다.

 

- 표기법

    - 중위 표기법

        - a / b - c + d * e - a * c

    - 후위 표기법

        - ab / c - d e * + a c *

    - 전위 표기법

        - - + - / a b c * d e * a c

 

6.1 후위 수식 계산 알고리즘

    - 수식을 왼쪽에서 오른쪽으로 스캔한다.

    - 수식에서 들어온 입력이 피연산자이면 스택에 넣는다.

    - 입력이 연산자이면 스택에서 피연산자를 2개 꺼내서 계산한 후 결과 값을 다시 스택에 넣는다. 

 

- 수식 평가 스택

#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100

typedef enum
{
    open_b, close_b, plus, minus, times, divide, mod, eos, operand
} priority;        // 열거형 -> 0, 1, 2, ..., 8

int stack[STACK_SIZE];    // 수식 평가 스택
char expr[EXPR_SIZE];     // 수식 문자열
int pos = 0;              // 문자열 현재 위치
char sym;
int sym_type;
int top = -1;

 

- 후위 수식 평가

int eval_postfix();
void push(int item);
int pop();

void main()
{
    // strcpy(expr, "57 * 9 + 34 / -");        // 5 * 7 + 9 - 3 / 4
    strcpy(expr, "936 + 5 - / 7 * 64 - *");    // 9 / (3 + 6 - 5) * 7 * (6 - 4)
    eval_postfix();
}

int eval_postifx()
{
    char sym;
    int op1, op2;
    sym = read_item();
    while (sym_type != eos) {
        if (sym_type == operand)
            push(sym - '0');
        else {
            op2 = pop();
            op1 = pop();
            switch (sym_type) {
                case plus : push(op1 + op2);
                case minus : push(op1 - op2);
                case times : push(op1 * op2);
                case divide : push(op1 / op2);
                case mod : push(op1 % op2);
            }
        }
        sym = read_item();
    }
    return pop();
}
 
void push (int item) 
{
    if (top >= STACK_SIZE - 1) {
        printf("stack full");
        return;
    } 
    stack[++top] = item;
    print_stack;
}

int pop() 
{
    if (top < 0) {
        printf("empty stack");
        return -999;
    }
    return stack[top--];
}

 

- 심볼 입력

char read_item()
{
    char sym;
    sym = expr[pos++];
    
    switch (sym)
    { 
        case '(' : sym_type = open_b;
            break;
        case ')' : sym_type = close_b;
            break;
        case '+' : sym_type = plus;
            break;
        case '-' : sym_type = minus;
            break;
        case '*' : sym_type = times;
            break;
        case '/' : sym_type = divide;
            break;
        case '%' : sym_type = mod;
            break;
        case '\0' : sym_type = eos;
            break;
        default : sym_type = operand;    // 피연산자
    }
    
    return sym;
}

- 실행 결과

9 3 6 + 5 - / 7 * 6 4 - *

 

9

9 3

9 3 6

9 9

9 9 5

9 4

2

2 7

14

14 6

14 6 4

14 2

28

6-2. 중위 수식 → 후위 수식

    - 입력이 피연산자이면 그대로 출력한다.

    - 입력의 우선 순위가 스택 top의 연산자보다 높거나, 스택이 비어있으면 입력을 스택에 넣는다.

    - 스택의 연산자 우선 순위가 입력보다 크거나 같으면 스택 연산자를 pop하고 입력을 스택에 넣는다.

    - 입력이 '(' 이면, ')'이 들어올 때까지 다음 연산자를 위의 규칙을 따라서 스택에 넣는다.

    - 입력이 ')' 이면, '('이 나올 때까지 스택에서 계속 연산자를 pop해서 출력하고 '(' 은 출력하지 않고 버린다.

    - 입력이 문자열의 끝(eos)이면, 스택의 모든 연산자를 꺼내서 출력한다.

 

- (ex)

a + (b * c + d) * e

 

입력 출력 스택
a a  
+ a +
( a + (
b a b + (
* a b + ( *
c a b c + ( *
+ a b c * + ( +
d a b c * d + ( +
) a b c * d + +
* a b c * d + + *
e a b c * d + e  + *
\0 a b c * d + e * +  

 

#include <stdio.h>
#include <ctype.h>
#define STACK_SIZE 100

char token_stack[STACK_SIZE];
int token_top = -1;
void infix_to_postfix();
int precedence(char op);
void push_token(char sym);
char pop_token();

void main()
{
    infix_to_postfix();
}

void infix_to_postfix()
{
    char expr[50], sym, token;
    int pos = 0;
    
    printf("Enter the expression :: ");
    scanf("%s", expr);
    
    while ((token = expr[pos++]) != '\0') {
        if (isalnum(token))          // 알파벳 또는 숫자
            printf("%c", token);
        else if (token == '(')
            push_token(token);
        else if (token == ')') {
            while ((sym = pop_token()) != '(')
                pirntf("%c", sym);
        }
        else {
            while(precedence(token_stack[token_top]) >= precedence(token) && 
                  token_top != -1) {
                  printf("%c", pop_token());
            }
            push_token(token);
        }
    }
    while (token_top != -1) 
        printf("%c", pop_token());
}

int precedence (char op)
{
    if (op == '(')
        return 0;
    else if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/' || op == '%')
        return 2;
}

void push_token(char sym)
{
    if (token_top < STACK_SIZE -1)
        token_stack[++token_top] = sym;
    else
        printf("token stack full\n");
}

char pop_token()
{
    if (token_top >= 0)
        return token_stack[token_top--];
        
    printf("token stack empty\n");
    return ' ';
}
            

- 실행 결과

Enter the expression :: a + (b * c + d) * e

a b c * d + e * +

 

Enter the expression :: 5 * 7 + (4 - 3) / 6 % 9

5 7 * 4 3 - 6 / 9 % +

'Software > Data Structures' 카테고리의 다른 글

[자료구조] 탐색  (0) 2021.04.20
[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 알고리즘 성능 분석  (0) 2021.04.17
[자료구조] Recursion 재귀 호출  (0) 2021.04.17
[자료구조] C언어 기초  (0) 2021.04.17

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

 

1. 성능 분석 (실행 가능한 기준)

    - 공간 복잡도 (space complexity) : 필요한 메모리 양

    - 시간 복잡도 (time complexity) : 프로그램 수행 시간

 

2. 공간 복잡도 

- Fixed space requirements (Sc)

    - 실행 도중에 변하지 않는 것

    - 명령어, 단순 변수, 고정된 구조체 변수, 상수 등

    - 공간 복잡도에 고려하지 않는다.

 

- Variable space requirement (Sv)

    - 프로그램 실행 중에 요구되는 공간으로 가변적이고 예측이 어렵다.

    - 함수 간 배열 전달, 재귀 호출 등

    - 위험 요소를 내포하고 있으며, 공간 복잡도 평가에서 더욱 중요하다.

 

- S = (Sc +) Sv

 

- (ex1)

float abc (float a, float b, float c)
{
    return a + b + b * c + (a + b - c) / (a + b) + 4.00;
}

    -input과 output이 단순 변수로만 이루어져 있고, 명령어도 단순 계산이기 때문에 고정 메모리 공간만 활용하는 코드이다. 

    -Sv(abc) = 0

 

- (ex2)

float Sum (float list[], int n)
{
    int i;
    float total = 0;
    
    for (i = 0l i < n; i++)
        total = total + list[i];
    
    return total;
}

     - 함수를 호출할 때 배열이 전달되었기 때문에 가변 메모리 공간도 활용한다. 

     - 이 경우 시간 복잡도는 배열 전달 방법에 따라 결정된다.

 

- (ex3)

float rsum(float list[], int n)
{
    if (n)
        return rsum(list, n-1) + list[n-1];
    else
        return 0;
}

    - 배열이 전달되었고, 재귀 호출이 사용되었기 때문에 가변 메모리 공간을 사용한다.

    - 이 때 rsum함수가 처음을 제외하고 n번 호출되었다.

    - 한 번 호출될 때마다 float list[], int n, rsum(list, n-1) 이 세가지 환경 변수들 (매개 변수 저장공간, 함수 회귀 주소) 이 저장되며, 각각 4bytes의 크기를 갖고 있기 때문에 S = 12n 이다. 

 

- Call by value 

    - 함수에 배열 "값"을 직접 전달하는 방식이다.

    - 배열 크기에 비례하는 추가적인 메모리 공간이 요구된다.

    - Sv(sum) = n    // n == array size

    - (ex) Pascal

 

- Call by reference

    - 함수에 배열 "주소"를 전달하는 방식이다.

    - 추가적인 메모리 공간이 필요하지 않다.

    - Sv(sum) = 0

    - (ex) C

 

3. 시간 복잡도

- Time complexity (T)

    - 알고리즘을 수행하는데 필요한 시간이다. 

    - 컴파일 시간(Tc)과 실행 시간(Te)으로 구성되는데, 컴파일은 완료되고 나면 더이상 수행되지 않으므로 실행 시간을 더 중요시한다.

    - 실행 시간은 컴퓨터 하드웨어 환경에 따라 다르다.

    - 따라서 실제 수행 시간보다는 명령문의 수를 시간 복잡도로 간주하여 사용한다.

 

- 실행 명령문 표

    - 한 문장에 포함된 명령문의 수 (steps) 를 결정한다.

    - 이 문장이 반복 실행되는 빈도 (frequency) 를 결정한다.

    - (명령문 수) x (빈도)로 이 문장의 총 실행 횟수를 계산한다.

 

    - 이 때 함수 헤더, 변수 선언, 블록의 시작과 끝은 명령문으로 간주하지 않는다.

 

    - Σ steps * frequency

 

- iterative sum 

float sum (float list[], int n) {     // 1
    int i;                            // 2
    float temp = 0;                   // 3
    for (i = 0; i < n; i++)           // 4
        temp += list[i];              // 5
    return temp;                      // 6
}                                     // 7
Statement steps frequency total steps
// 1 함수 헤더 0 0 0
// 2 변수 선언 0 0 0
// 3 변수 선언 후 "대입" 1 1 1
// 4 반복문 & 변수 대입 [0, n] → n + 1 번 실행 1 n + 1 n + 1
// 5 계산문 [0, n-1] → i = n 이면 실행되지 않음, n 번 실행 1 n n
// 6 return  1 1 1
// 7 블록의 끝 0 0 0
total step counts     2n + 3

 

- recursive sum

float rsum (float list[], int n) {            // 1
    if(n)                                     // 2
        return rsum(lsit, n-1) + list[n-1];   // 3
    return 0;                                 // 4
}                                             // 5
Statement steps frequency total steps
// 1 함수 헤더 0 0 0
// 2 if 문 [0, n] → n + 1 1 n + 1 n + 1
// 3 함수 실행문 [0, n-1] → n 1 n n
// 4 return  1 1 1
// 5 블록 끝 0 0 0
total step counts     2n + 2

 

- matrix addition

void add() {                              // 1
    int i, j;                             // 2
    for (i = 0; i < rows; i++)            // 3
        for (j = 0; j < cols; j++)        // 4
            c[i][j] = a[i][j] + b[i][j];  // 5
}                                         // 6
Statement steps frequency total steps
// 1 0 0 0
// 2 0 0 0
// 3 1 rows + 1 rows + 1
// 4 1 rows * (cols + 1) rows * (cols + 1)
// 5 1 rows * cols rows * cols
// 6 0 0 0
total step counts     2 rows * cols + 2rows + 1

 

4. 점근적 표기법 

- 입력의 수 n이 매우 커질 때 알고리즘의 복잡도가 증가하는 패턴을 근사적으로 표현하는 것이다. 

- 알고리즘의 성능을 비교하는 데 사용한다.

- n이 매우 증가하는 경우를 가정하여 시간 복잡도의 상한선, 하한선, 상한-하한선의 존재 유무에 따라 O, Ω, θ 등의 기호로 근사적인 복잡도를 표현한다.

- 예를 들어, 두 프로그램의 시간 복잡도가 각각 n² + n, 10n 이라고 가정하자.

  n이 작을 땐 계수에 따라 좌우되겠지만, 결국 n이 커질 경우 다항식의 차수가 더 큰 영향을 미친다.

    - (n <= 9) n² + n <= 10n

    - (n > 9) n² + n > 10n

- 이와 같이 두 개의 시간 복잡도 함수의 실행 명령문의 수가 바뀌는 시점을 분기점이라고 한다. 

- 일반적으로 n이 매우 큰 경우의 수행 성능이 더 중요하다.

 

4-1. Big Oh O 

- "상한선"

- n₀ 이상인 모든 n에 대해서 f(n) ≦ c·g(n)을 만족하는 양의 상수 c와 n₀가  존재한다면 시잔 복잡도 함수 f(n) = O(g(n))이라고 표기할 수 있다. 이 반대의 경우도 성립한다. 

- f(n) = O(g(n)) 이라고 표기할 수 있다면, 이 알고리즘의 수행 시간이 상한선 c·g(n)을 넘지 않는다는 의미이다.

 

- (ex1) 

    - f(n) = 10n + 10,000 ∈ O(n)

    - c = 20, n₀ = 1,000 이라고 결정한다면

    - f(n) ≦ 20n for all n ≥ 1,000 인 상황에서 Big Oh를 사용할 수 있다.

- (ex2)

    - f(n) = n³ + n² + n ∈ O(n) 

    - c = 3, n = 1 이라고 결정한다면

    - f(n) ≦ 3n³ for all n ≥ 1 인 상황에서 Big Oh를 사용할 수 있다.

 

- c는 최고차항의 계수와 f(n)의 항 수로 결정할 수 있다.

n₀는 그래프를 통해서 결정할 수 있다.

- O(1) 은 n에 관계없이 항상 일정한 명령어 수 k를 갖는다는 의미이다.

 

4-2. Big Omega Ω

- "하한선"

- n₀ 이상인 모든 n에 대해서 f(n) ≥ c·g(n) 을 만족하는 양의 상수 c와 n₀가 존재한다면, 시간 복잡도 함수 f(n) = Ω(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.

- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선인 c·g(n) 보다 항상 많이 걸린다. 이 알고리즘의 수행 시간은 최소한 하한선 이상으로 걸린다는 의미이다.

 

4-3. Big Theta θ

- "상한-하한선"

- n₀ 이상인 모든 n에 대해서 c₁·g(n) ≤ f(n)  c₂·g(n)  을 만족하는 양의 상수 c₁, c₂, n₀가 존재한다면, 시간 복잡도 함수 f(n) = θ(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.

- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선 (c₁·g(n))과 상한선 (c₂·g(n)) 사이에 존재한다는 의미이다.

 

4-4. 시간 복잡도 함수의 종류

- O(1) = constant (Fast)

- O(log n) = logarithm

- O(n) = linear

- O(n log n) = log linear

- O(n²) = quadratic

- O(n³) = cubic

- O(2ⁿ) = exponential

- O(n!) = factorial (Slow)

- O(1) ~ O(n²) : 다루기 쉽기 때문에 n이 클 때 유용하다.

- O(2ⁿ) ~ O(n!) : 다루기 어렵기 때문에 n이 아주 작을 때 유용하다.

'Software > Data Structures' 카테고리의 다른 글

[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18
[자료구조] Recursion 재귀 호출  (0) 2021.04.17
[자료구조] C언어 기초  (0) 2021.04.17
[자료구조] Introduction  (0) 2021.04.17

 

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

 

1. 재귀호출

- 함수가 실행 중에 자기 자신을 다시 호출하는 것이다.

- 같은 작업을 반복하는데 조금씩 상황이 바뀌는 경우에 사용한다.

 

- 함수에 반드시 종결 조건이 있어야 한다.

- Divide & Conquer 전략에 사용된다.

- 재귀 호출문은 if-else나 while문을 활용한 반복문으로 바꿀 수 있다.

- 컴파일러의 관점에서 재귀 호출은 새로운 함수를 호출하는 것과 같다.

- 따라서 함수를 호출할 때마다 함수의 지역 변수, 복귀 주소 등 컨텍스트 정보를 활성 레코드에 저장해야 한다.

 

- 장점 : 알고리즘을 깔끔하게 표현할 수 있다.

- 단점 : 함수를 실행할 때마다 메모리에 환경 변수를 저장하기 때문에 메모리의 소모가 일어난다.

 

2. 팩토리얼 예제

- n! = 1 x 2 x ... x (n-1) x n = (n-1)! x n

 

- 같은 일 (곱셈) 을 반복하면서 n = 0이면 n! = 1 이라는 종결 조건이 포함되어있기 때문에 재귀 호출을 사용할 수 있다.

 

long factorial (int n)
{
    if (n == 0)
        return 1;
    else 
        return n * factorial (n-1);
}

이와 같이 n = 0 이면 1을, n > 0 이면 n * (n-1)! 을 반환하는 형식으로 표현할 수 있다.

 

3. 최대공약수 (GCD) 예제

- 공통으로 나누는 수 중 가장 큰 수 

 

- 조건 (by 유클리드 호제법)

    - gcd (x, y) = gcd (y, x % y)  (if (y > 0))

    - gcd (x, 0) = x

 

ind gcd (x, y)
{
    if (y == 0)
        return x;
    else return gcd (y, x % y);
}

 

4. Binary Search 이진 탐색

- 정렬된 항목 리스트에 대해서 중간값과 크기를 비교하고 그 결과에 따라 가능성이 있는 절반의 리스트에 대해서만 과정을 반복하는 탐색 알고리즘이다.

 

- 한 번 비교할 때마다 탐색 대상 원소의 수가 절반으로 감소한다.

- 원소의 수가 n개일 때 이진탐색은 총 log₂ⁿ 번의 비교 횟수를 요구한다. 따라서 순차 탐색보다 속도가 빠르다.

- 조건은 리스트 안에 겹치는 숫자가 없어야 한다는 것이다. 

 

-while문과 if문을 이용한 이진탐색

#include <stdio.h>
int binsearch (int mylist[], int item, int left, int right);

void main()
{
    int pos, maxnum = 12, item = 60;
    int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
    pos = binsearch(mylist, item, 0, maxnum - 1);
    printf("position = %d", pos);
}

int binsearch (int list[], int item, int left, int right)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (list[mid] == item)
            return mid;
        else {
            if (item < list[mid]
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    return -1;
}

 

- 재귀호출 형식의 이진탐색

#include <stdio.h>
int rbinsearch (int mylist[], int item, int left, int right);

void main()
{
    int pos, maxnum = 12, item = 60;
    int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
    pos = binsearch(mylist, item, 0, maxnum - 1);
    printf("position = %d", pos);
}

int rbinsearch (int list[], int item, int left, int right)
{
    int mid;
    if (left <= right)
    {
        mid = (left + right) / 2;
        if (item == list[mid] 
            return mid;
        else if (list[mid] < item)
            return rbinsearch(list, item, mid + 1, right);
        else 
            return rbinsearch (list, item, left, mid - 1);
     }
     return -1;
 }
        

 

5. 하노이 타워 예제

- 세 개의 기둥과 크기가 다양한 원판이 존재한다. 

- 해결할 문제는 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮기는 것이다.

- 조건

    - 한 번에 하나의 원판만 옮길 수 있다.

    - 큰 원판이 작은 원판 위에 놓일 수 없다.

 

- 알고리즘

    - 세 개의 기둥 A, B, C 가 있고, A에서 B로 n개의 원판을 옮긴다.

    1) A에서 (n-1)개의 원판을 C로 옮긴다.

    2) A에 남은 1개의 원판을 B로 옮긴다.

    3) C에 있는 (n-1)개를 B로 옮긴다. 

 

- 기둥 a = 1, b = 2, c = 6 - a - b // a, b 제외한 빈 기둥이 c

- 총 이동횟수 : 2ⁿ - 1

 

#include <stdio.h>
void htower(int n, int a, int b);

int count = 0;

void main()
{
    int n;
    count = 0;
    printf("Enter disc number = ");
    scanf("%d", &n);
    htower(n, 1, 2);
    printf("# move for %d discs : %d\n", n, count);
}

void htower (int n, int a, int b)
{
    int c;
    count ++;
    if (n == 1)
        printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, b);
        
    else {
        c = 6 - a - b;
        htower(n-1, a, c);
        printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, c);
        htower(n-1, c, b);
    }
}

 

- Time complexity 시간 복잡도 

    - t(1) = 1 : 하나의 디스크 옮기는데 필요한 시간

    - time to move n disks : t(n)

        - t(n) = 2 t(n-1) + 1

                 = 2 (2 t(n-2) + 1) + 1

                 = ...

                 = 2ⁿ⁻¹ + 2² + ... + 2¹ + 2⁰

                 = 2ⁿ - 1 ≅ 2

    - t(n) = O(2ⁿ) 

    → n 이 크면 사용하지 않는 것이 좋다.

 

6. Permutation 순열

- 순서를 다르게 나열하는 방법의 수

 

- {a, b, c, d}  → ₄P₄ = 4! = 24

a) (a, Perm (b, c, d))  →  Perm(b, c, d) = (b, Perm (c, d)), (c, Perm (b, d)), (d, Perm (b, c)) 

b) (b, Perm (a, c, d))

c) (c, Perm (a, b, d))

d) (d, Perm (a, b, c))

 

// i : start index of range
// n : end index of range

void perm(char list[], itn i, int n)
{
    int j;
    if (i == n)      // list print
    { 
        for (j = 0; j <= n; j++)
            printf("%c", list[j]);
        printf("   ");
    }
    else {
        for (j = i; j <= n; j++) {
            Swap(list[i], list[j]);    // 두 수 교환
            perm(list, i + 1; n);
            Swap(list[i], list[j]);
        }
    }
}
    

'Software > Data Structures' 카테고리의 다른 글

[자료구조] 연결 리스트  (0) 2021.04.20
[자료구조] 선형 자료구조  (0) 2021.04.18
[자료구조] 알고리즘 성능 분석  (0) 2021.04.17
[자료구조] C언어 기초  (0) 2021.04.17
[자료구조] Introduction  (0) 2021.04.17

+ Recent posts