현경이의 삽질기록

[딥러닝 모델을 사용한 서버 배포하기 #3] Flask로 서버 개발하기

Wed, 11 Sep 2019 15:38:00 +0900

Keras모델을 사용하는 Flask서버 개발하기

앞의 포스팅에서 Tensorflow 모델을 Keras 모델로 바꾸어 사용하는 방법을 알아보았습니다.

이제는 이 Keras 모델을 사용해 어떻게 서버를 만드는지 알아보도록 하겠습니다.

Flask의 기본 개념에 대한 내용은 생략합니다. 기본 개념은 공식문서를 참고하세요!

미리보기)

만들 서버의 모습입니다! 간단한 UI와 ~~멋있는 사진~~ 결과를 볼 수 있습니다!
입력으로 이미지의 URL을 받아 Keras 모델을 사용해 결과물을 얻고, 그 결과를 웹 화면에 보여주는 방식입니다.

순서는

flask 코드 작성
json 값을 이용해 html 화면에 결과 띄우기

로 진행하겠습니다.

flask 코드 작성

우선은 app.py 파일을 작성합니다. (flask를 실행할 파일)

app = flask.Flask(__name__)

@app.route("/", methods=["GET"])
def main():
    return render_template('index.html')

main 함수에서는 index 페이지만 보여주도록 합니다.

@app.route("/model", methods=["GET"])
def model():
	if request.method == "GET":
        # 1. url을 입력으로 받아서
		url = request.args.get('url')
		# 2. url을 이미지로 변환한 후
        image = url_to_image(url)
        # 3. Keras 모델의 input으로 사용
		result_file = test_model(image)
        # 4. json 형태로 리턴
		result_dict = {
						'url' : url,
						'result' : encode_image(result_file)
					  }

		return json.dumps(result_dict)

이번에는 실제로 모델을 사용하는 함수를 작성하겠습니다.

1. 이미지의 url을 입력으로 받음

request.args.get('url') 이라고 하면, /model?url= 뒤에 들어가는 url값을 가져옵니다.
예를들어 /model?url=http://zum.com/ 이라는 입력이 들어오면 url 변수에는 ‘http://zum.com’ 이 들어갑니다.

2. 이미지의 url을 이미지 배열로 변환

def url_to_image(url):

	resp = urllib.request.urlopen(url)
	image = np.asarray(bytearray(resp.read()), dtype="uint8")
	image = cv2.imdecode(image, cv2.IMREAD_COLOR)
	
	return image

url을 읽어 array로 변환하고, 3차원 형태의 이미지 배열로 다시한번 변환하는 코드 입니다.

3. 이미지 배열을 모델의 input으로 사용해 모델 테스트

model.py

model = load_model('./model_complete.h5', custom_objects={'tf': tf})
model.load_weights('./model_weights.h5')
model._make_predict_function() # predict 할 때 매번 쓰기 위해 사용하는 함수

def test_model(image):
	output = model.predict(image)
	
	filename = 'temp.png'
	cv2.imwrite(filename, image)
	
	return filename

위 코드는 model.py에 작성한 내용입니다. Flask에서 일반적으로 route를 가진 함수가 아니면 다른 파일로 분리해 작성하는 방식을 사용하기 때문에, 따로 분리해서 작성했습니다.

여기서 중요한 두 가지가 있는데, 첫번째로 중요한 것은 model.py 안에서 모델을 로드한다는 점입니다!
model.py 내에서 모델을 로드하면, app.py 실행 시 맨 위에서 model.py를 한번만 부르기 때문에 앱 실행동안 한번만 모델을 로드할 수 있습니다.

만약 app.py내의 라우트를 가진 함수들 내에서 모델을 로드하면, 함수를 매번 호출할 때 마다 모델 파일을 읽기 때문에 매우 비효율적인 앱이 될 것입니다.

두 번째로는 model._make_predict_function() 부분입니다.
model.predict()를 하기 전에 호출을 해야 predict를 정상적으로 할 수 있습니다.

정확한 사용 이유는 공식 문서에도 잘 나와있지 않습니다. Keras github Issue들에도 여러 질문이 있지만, 아직 명확한 답변은 나와있지 않습니다. 답변이 추가되면 수정하겠습니다!

4. 결과를 json 형태로 리턴

result_dict = {
                'url' : url,
                'result' : encode_image(result_file)
			  }

return json.dumps(result_dict)

매번 이미지 결과를 얻어서 이미지로 저장을 하면 저장공간 상의 문제가 될 수도 있어, encode_image라는 함수 내에서 이미지를 인코딩 한 후 인코딩 값만 리턴하고 파일은 삭제하도록 구현을 했습니다.

json형식으로 리턴을 하면 서버에서 UI 없이 라우트로만 요청을 보내도 결과를 볼 수 있고, html에서 json형식의 결과를 사용하기 쉽다는 장점이 있습니다.

이제 서버개발은 모두 끝났습니다!
python app.py 를 실행한 후 /model?url=[url주소] 를 입력하게 되면 json 형식의 결과를 볼 수 있습니다!~~~!~!

하지만 좀 더 편리하게 사용하기 위해 간단한 UI까지 개발해보도록 하겠습니다!

2. json 값을 이용해 html 화면에 결과 띄우기

우선 flask에서 html 파일을 사용하기 위해서는 정해진 디렉토리 규칙이 있습니다.

app.py
model.py
templates
	- index.html

이런식으로 templates 폴더 내에 html 파일을 넣어주면 별다른 경로 지정 없이 flask가 html파일을 읽을 수 있습니다.

index.html

<!DOCTYPE html>
<html>
<head>
	<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <title>VIP</title>
</head>
<body>

<h2>saliency map을 구할 이미지의 URL을 입력하세요</h2>
<form class='url'>
	<input type="text" name="url"/>
	<button type="button" id="submit">submit</button>
</form>

<table id="result">
</table>
<script
  src="https://code.jquery.com/jquery-3.4.1.js"
  integrity="sha256-WpOohJOqMqqyKL9FccASB9O0KwACQJpFTUBLTYOVvVU="
  crossorigin="anonymous"></script>
 

<script>

	const Result = ({ url, result }) => `
	<tr>
		<td><img class="crop-result" src="${url}"></td>
		<td><img class="crop-result" src="data:image/png;base64, ${result}"></td>
	</tr>
	`;

	$(function() {
		$('#submit').click(function() {

			var input = $('form.url').serialize();
			console.log(input);

			$.ajax({
				url: '/model',
				data: input,
				type: 'GET',
				success: function(response) {
					var result = JSON.parse(response);
					console.log(result);
					$('#result').html([result].map(Result).join(''));
				},
				error: function(error){
					console.log(error);
				}

			});
		});
	});
</script>
</body>

이게 전부입니다..! easy..!

1. input tag로 입력값 받기

<form class='url'>
	<input type="text" name="url"/>
	<button type="button" id="submit">submit</button>
</form>

...
<script>
	$(function() {
		$('#submit').click(function() {

			var input = $('form.url').serialize();
...
</script>

input tag에 name='url'속성을 주었고, form tag의 기본 method는 GET방식이므로, input에 값을 넘겨주면 ?url=값 으로 넘어가게 됩니다.
이 때 값이 넘어가는 시점은 submit 버튼을 누를 때 입니다. 따라서 submit 버튼을 클릭할 때 처리 함수가 작동하도록 하면 됩니다.
script 태그 내의 input 변수에 ?url=값 까지 넘어간 상태 입니다.

2. 입력받은 값으로 요청 보내기

<script>
...
$.ajax({
    url: '/model',
    data: input,
    type: 'GET',
...
</script>

이제 앞에서 flask로 작성한 함수에 요청을 보낼 차례 입니다.

ajax 형식에 맞게 작성만 하면 됩니다. 어떤 url로 보낼 것인지, 어떤 데이터를 보낼 것인지, 어떤 방식으로 보낼것인지 정의합니다.
위와 같이 작성하게 되면 /model?url=input 값 형태로 요청이 넘어갑니다.

3. 요청을 보낸 결과를 받아 파싱해서 뿌리기

<script>
...
success: function(response) {
    var result = JSON.parse(response);
    $('#result').html([result].map(Result).join(''));
},
error: function(error){
	console.log(error);	
}
...
</script>

요청을 보낸 결과를 json 형식으로 정의해 놓았기 때문에 JSON.parse 로 쉽게 값을 사용할 수 있습니다.

여기서 한 가지 봐야할 것은 json 형태의 array를 mapping 해서 사용하는 부분입니다.

<table id="result"></table>

<script>
const Result = ({ url, result }) => `
    <tr>
        <td><img class="crop-result" src="${url}"></td>
        <td><img class="crop-result" src="data:image/png;base64, ${result}"></td>
    </tr>
`;
</script>

mapping 시 사용한 Result라는 상수는 script의 윗 부분에서 정의했습니다.
이 상수 내에서는 json에서 사용하는 key값을 간단히 사용할 수 있습니다.
안에 사용할 key 값들을 나열해주고, ${ … }로 값을 사용해주면 됩니다!

그럼 이제 정말 끝입니다! (고양이 사진도 가능합니다!)

[딥러닝 모델을 사용한 서버 배포하기 #2] Tensorflow모델을 Keras로 바꾸기

Wed, 11 Sep 2019 13:40:00 +0900

Tensorflow로 작성된 코드를 Keras로 바꾸기

앞에서 설명한 논문의 코드는 Tensorflow로 구현된 것이었습니다.

하지만 배치단위로 처리하는 코드였기 때문에 실시간으로 한 개씩 처리에는 적합하지 않았고,
배치마다 그래프를 다시 읽어야 하는 방식으로 구현되어 있었습니다.

그래서 Tensorflow로 된 코드를 Keras로 바꾸고, 그래프는 실행시 한번만 읽을 수 있도록 로직을 수정하기로 했습니다!

1. 코드 바꾸기

레이어 부분의 코드를 바꾸는 일은 어렵지 않습니다.
tensorflow에서 지원하는 layer들은 대부분 Keras에도 있기 때문에 함수명과 인자만 잘 맞춰주면 됩니다.

예를 들어 아래 tensorflow 코드는

layer01 = tf.layers.conv2d(images, 64, 3,
                           padding="same",
                           activation=tf.nn.relu,
                           data_format=self._data_format,
                           name="conv1/conv1_1")

layer02 = tf.layers.conv2d(layer01, 64, 3,
                           padding="same",
                           activation=tf.nn.relu,
                           data_format=self._data_format,
                           name="conv1/conv1_2")

layer03 = tf.layers.max_pooling2d(layer02, 2, 2,
                                  data_format=self._data_format)

Keras로 이렇게 변환하면 됩니다. (Keras의 layer 작성 방식 중 Functional API를 사용했습니다.)

from keras.layers import Conv2D
from keras.layers.pooling import MaxPooling2D

x = Conv2D(filters=64, kernel_size=3, 
           strides=(1, 1), padding='same',
           activation='relu', name='conv1/conv1_1', 
           data_format=self._data_format)(img_input)

x = Conv2D(filters=64, kernel_size=3, 
           strides=(1, 1), padding='same',
           activation='relu', name='conv1/conv1_2', 
           data_format=self._data_format)(x)

x = MaxPooling2D(pool_size=(2, 2), strides=(2, 2), 
                 name="pool1", padding='valid', 
                 data_format=self._data_format)(x)

여기서 data_format 인자는 GPU 사용시 쓰이는 인자 입니다.

기본적으로 tensor는 (num, w, h, channel) 순서로 구성되어 있고, 그렇기 때문에 data_format의 디폴트값은 data_format='channel_last' 입니다.
data_format='channel_first' 라고 하면 tensor의 순서가 (channel, num, w, h)로 변경되고, GPU 연산을 위해서는 반드시 명시해 주어야 하는 인자 입니다.

문제는 tensorflow는 layer 중간에 tensor를 처리하는 함수를 넣을 수 있지만, Keras는 layer를 쌓아가는 형태이기 때문에 별도의 처리함수를 사용할 수 없다는 점이었습니다.

예를들어

branch5 = tf.reduce_mean(features,
                         axis=self._dims_axis,
                         keepdims=True)

branch5 = tf.layers.conv2d(branch5, 256, 1,
                           padding="valid",
                           activation=tf.nn.relu,
                           data_format=self._data_format,
                           name="aspp/conv1_5")

tensorflow에서는 tensor처리 후 layer를 사용할 수 있지만, Keras에서는 사용할 수 없습니다.
Keras에서 이런 방식을 사용하려면 첫번째 branch5도 layer 형태여야 합니다.

Keras에서는 Lambda 라는 layer를 지원하고 있습니다.

Lambda를 이용하면 tensor처리한 것을 layer형태로 만들어 다음 layer에 적용할 수 있습니다.

from keras import backend as K
from keras.layers import Lambda, Conv2D

branch5 = Lambda(lambda inputs: K.mean(inputs, 
                                       axis=self._dims_axis, 
                                       keepdims=True))(encoder_output)

branch5 = Conv2D(filters=256, kernel_size=1, 
                 strides=(1, 1), padding='valid',
                 activation='relu', name='aspp/conv1_5', 
                 data_format=self._data_format)(branch5)

이렇게 하면 tensorflow에서 사용하는 여러 처리 함수들도 쉽게 불러와서 쓸 수 있습니다.

#tensorflow
stack = tf.image.resize_bilinear(stack, (shape[self._dims_axis[0]] * factor,
                                         shape[self._dims_axis[1]] * factor))

#Keras
stack = Lambda(lambda inputs: tf.image.resize_bilinear(stack,
													  (shape[self._dims_axis[0]]*factor, 														shape[self._dims_axis[1]]*factor))

2. Weight 파일 바꾸기

사용한 딥러닝 모델의 깃허브는 .pb 형태의 weight 파일을 제공하고 있습니다.
하지만 이 파일을 Keras의 load_model 로 읽으면 에러가 나는데, load_model은 .h5 형태의 파일만 지원하기 때문입니다. (공식 문서 참고)

즉, Keras를 사용하기 위해서는 .h5 형태의 weight 파일이 필요합니다. 가장 좋은 방법은 1번에서 새로 작성한 모델 구조로 다시 학습을 시켜 .h5 파일을 만드는 것인데, ~~시간도 자원도 부족합니다,,, 기브미GPU,,,~~

그래서 최대한 .pb 파일을 사용해보기로 했습니다!

전체적인 과정은 다음과 같습니다.

Keras로 작성한 모델을 저장 후 불러옴
Keras로 작성한 모델 구조 (초기화 시 랜덤으로 들어간 weight 값을 포함)에서 변수명과 weight 값을 가져옴
.pb 파일을 읽어 그래프 구조를 파싱
그래프의 노드 이름과 Keras 모델의 레이어 이름을 짝으로 비교해 weight를 저장
1번에서 저장한 모델 구조에 3번에서 얻은 weight를 넣음

Keras로 작성한 모델을 저장 후 불러옵니다.

import tensorflow as tf

model.save('model_structure_gpu.h5')
model_structure = load_model('model_structure_gpu.h5', custom_objects={'tf': tf})

.pb 파일의 그래프 노드들의 이름과 비교하기 위해 Keras 모델의 레이어 이름을 저장합니다.
또한 그래프 노드에서 weight값을 가져와 저장하기 위해 랜덤으로 초기화된 weight값들도 저장합니다.

target_model_variable = model_structure.weights # 모델의 레이어 이름
target_model_weights = model_structure.get_weights() # 모델의 weight들

.pb파일을 읽어 그래프들을 노드단위로 파싱합니다.

import tensorflow as tf
from tensorflow.python.platform import gfile

GRAPH_PB_PATH = './model_salicon_gpu.pb' 

with tf.Session() as sess:
    with gfile.FastGFile(GRAPH_PB_PATH,'rb') as f:
        graph_def = tf.GraphDef()
        graph_def.ParseFromString(f.read())
        sess.graph.as_default()
        tf.import_graph_def(graph_def, name='')
        graph_nodes=[n for n in graph_def.node]

그리고 노드 중 속성이 상수인 노드 (= weight) 만 불러옵니다.

wts = [n for n in graph_nodes if n.op=='Const'] # weight만 불러옴

weight 노드들의 이름과 Keras 모델의 레이어 이름들을 비교하면서, 이름이 같으면 초기화된 weight 값이 있던 부분에 weight 노드의 weight 값을 넣어줍니다.

from tensorflow.python.framework import tensor_util

# 노드명이 일치하면 weight를 바꿔줌
for n in wts:
    for idx, var in enumerate(target_model_variable):
        if str(n.name) == str(var.name)[:-2]:
            target_model_weights[idx] = tensor_util.MakeNdarray(n.attr['value'].tensor)

[:-2] 로 슬라이싱 해 비교한 이유는 여기서 .pb 파일의 노드 이름은 aspp/conv1_2/kernel 형식이고, Keras 레이어 이름은 aspp/conv1_2/kernel:0 형식이기 때문입니다.

이제 다했습니다! 마지막으로 set_weights 함수를 이용해 방금 만든 weight를 처음 모델에 적용해주면 됩니다!

model_structure.set_weights(target_model_weights)

이제 테스트를 위해 모델을 저장하고 불러오기만 하면 됩니다!

import tensorflow as tf

model_structure.save('model_weights_gpu.h5')
model_gpu = load_model('model_structure_gpu.h5', custom_objects={'tf': tf})
model_gpu.load_weights('model_weights_gpu.h5')

여기서 custom_objects 옵션으로 Lambda 레이어에서 사용한 라이브러리들을 작성해야만 정상적으로 모델을 불러올 수 있습니다.

테스트 결과 .pb 파일로 얻은 결과물과 동일한 결과물을 얻을 수 있었습니다!
약간 미련한 짓으로 보일수도 있겠지만,,, 다시 학습할 시간과 자원을 아꼈습니다,,! 시간은 금이니까요~ 다들 아껴쓰시길 바라며 포스팅 마무리하겠습니다!

[딥러닝 모델을 사용한 서버 배포하기 #1] 어떤 모델을 사용할까

Wed, 11 Sep 2019 11:20:00 +0900

딥러닝 모델을 사용해 서버 배포하기 첫번째는 어떤 모델을 사용할까에 관한 내용입니다!

이번에 제가 사용해 본 모델은 Saliency map을 딥러닝으로 예측하는 모델입니다.
saliency map 예측 관련 벤치마크를 비교해 놓은 사이트가 있는데,
저는 여기서 python으로 구현된 모델들 중 MSI-Net을 사용했습니다.

이번 포스팅에서는 MSI-Net논문의 내용을 리뷰하면서 어떤 모델인지 살펴보겠습니다.

Contextual Encoder-Decoder Network for Visual Saliency Prediction

논문 주소 : https://arxiv.org/pdf/1902.06634.pdf
깃헙 주소 : https://github.com/alexanderkroner/saliency

Saliency map이란

사람이 어떤 장면을 봤을 때 집중해서 보게되는 부분을 시각화한 것

처음에는 밝기차이, 색상차이 등의 low level feature를 이용했다면, 최근의 연구에서는 CNN등의 모델을 통해 다양한 feature를 이용하고 있음

모델 구조

크게 Encoder, ASPP, Decoder 세 부분으로 나뉨

Encoder : 기본적으로 VGG16 구조를 사용하고, 몇 가지의 수정사항을 추가

Dilation Convolution Layer 사용

기본 Convolution 연산은 필터크기와 동일한 시야 (receptive field)를 가지는데 비해,

Dilation Convolution 연산은 같은 연산비용 대비 더 넓은 시야를 가짐
- pre-trained 된 VGG16모델을 사용할 때 파라미터 수가 동일하기 때문에 그대로 사용할 수 있음
- 논문에서는 위의 사진과 같이 rate=2 인 필터를 사용했으며, 33 필터이지만 55와 거의 유사한 영역을 봄
~~선행 연구에서 Saliency Map에는 Dilation Convolution이 좋다고 해서 사용…~~
Pooling layer들을 concat한 값을 최종 결과로 사용

각각 다른 level에서의 pooling layer 값들은 공간적 특징을 보존하므로,

w*h 차원이 같은 마지막 세 pooling layer들을 concat해서 공간적 특징을 보존하는 activation map 생성
- 모델 구조에서 첫 번째 pooling layer의 shape는 (?, w, h, 256) 이고,
```
 두 번째와 세 번째 pooling layer의 shape는 (?, w, h, 512) 이므로 
    
 axis=3 기준으로 concat했을 때 최종 (?, w, h, 1280) 인 activation map 생성
```

ASPP

DeepLab V2 (Segmentation 모델) 에서 제안된 방법

갯수는 같고 파라미터 (rate, size, padding)가 다른 여러 필터를 적용한 후 concat 해 사용

논문에서는 총 5개 종류의 필터 종류를 사용
- 각 필터를 거친 결과는 (?, w, h, 256) 이고 5개를 concat 하므로 (?, w, h, 256*5)
- 최종 출력은 (?, w, h, 256) 이어야 하므로 concat 결과에 마지막으로 필터 256개를 사용하는 1*1 convolution 연산을 해줌

Decoder

원본 이미지와 같은 크기의 Saliency map을 생성하기 위해 convolution + upsampling

bilinear로 upsampling
앞에서 22 pooling 을 세 번 했으므로 upsampling+convolution도 22 로 세 번 해주면 됨
upsampling 결과를 128 → 64 → 32 → 1 개의 필터로 convolution 하며 최종 saliency map 생성

학습하기

Encoder는 ImageNet 과 Places2로 pre-train된 VGG16구조를 사용
- ImageNet : 1000개의 클래스로 구성된 물체 이미지 데이터셋
  - https://gist.github.com/aaronpolhamus/964a4411c0906315deb9f4a3723aac57 (클래스목록)
  - 이미지 + 이미지의 클래스 정보 로 구성
- Places2 : 400개의 클래스로 구성된 장소 이미지 데이터셋
  - https://github.com/metalbubble/places_devkit (클래스목록)
  - 이미지 + 이미지의 클래스 정보 로 구성
ASPP와 Decoder weight는 Xavier 초기화를 사용

https://reniew.github.io/13/ (Xavier 초기화 설명)

Loss는 KL Divergence 를 사용

saliency map 을 분포 예측이라고 생각
Q는 target 분포, P는 예측 분포, i는 각 픽셀의 인덱스

학습 데이터 셋은 세 가지
MIT1003 : 실내, 실외 풍경 데이터 300개
CAT2000 : 20개 카테고리 (예술작품, 만화 등 ..) 데이터 4000개
- 이미지 + 이미지의 saliency 정보 (matrix)
SALICON : COCO 이미지 중 160개 카테고리에 대해
- 이미지 + 이미지의 saliency annotation 정보 (json)

한계점

(a) 어두운 얼굴 (b) 작은 글씨 (c) 사진 내 사람들의 시선 (d) low-level의 대비되는 feature 을 잘 못 찾음

[최신 정보검색론] 정보검색평가

Fri, 12 Apr 2019 13:50:00 +0900

Chapter 8 정보 검색 평가

이 글은 최신 정보검색론 을 읽고 정리 한 내용입니다.

정보 검색 시스템은 문헌 검색, 문서 분류 등의 작업으로 구성됩니다. Chapter 8 에서는 이 작업들의 평가 척도를 알아보겠습니다.

8.1 순위 없는 검색 집합의 평가

1) 정확률과 재현율

시스템의 유효성을 측정하는 지표에는 크게 정확률(Precision) 과 재현율(Recall)이 있습니다.

쉽게 설명하자면 정확률은 검색된 것 중에 적합하게 검색 된 것의 비율이고, 재현율은 적합한 것 중에 검색된 것을 의미합니다.

분할표로 나타내면 아래와 같습니다.

	적합	부적합
검색	긍정 정답(tp)	긍정 오류(fp)
미검색	부정 오류(fn)	부정 정답(tn)

여기서 Precision 은 tp/(tp+fp) 이고, Recall 은 tp/(tp+fn) 이라고 정의할 수 있습니다.

일반적으로 쓰는 Accuracy 는 (tp+tn)/전체 인데, 이것은 정보 검색 모델에는 적합하지 않습니다. 대부분 tp 보다는 tn 이 많게 때문에 틀린것을 틀리다고 분류해도 Accuracy 전체는 올라가기 때문입니다.

이런 경우 처럼, tp와 tn 의 균형이 매우 불균형 한 경우 Accuracy 대신에 F-Score 라는 개념을 사용합니다.

2) F-Score

F-Score 는 Precision과 Recall 을 적절히 고려해 사용하는 지표입니다. Precision 과 Recall 의 조화 평균을 사용합니다. 조화 평균을 사용함으로써 Precision 과 Recall 의 크기의 불균형을 조절할 수 있습니다.

$ F = \frac{ (\beta^2 + 1) P R}{\beta^2P + R}$ 식에서 $ \beta $ 는 그 불균형을 얼마나 조절할까에 대한 파라미터 입니다. 보통은 $ \beta = 1 $ , 즉 P와 R에 동일한 가중치를 주는 값을 많이 쓰고, 이것을 F1-Score 라고 부릅니다.

8.2 순위 검색 결과의 평가

위에서 살펴본 내용들은 순위가 없는 집합 기반의 평가 척도입니다. 다시말해 검색결과가 적합/부적합 인 것에 대한 평가만 가능합니다. 얼마나 적합/부적합 한지를 평가하려면 (순위가 있으면) 새로운 척도가 필요합니다.

1) 평균 정확률(MAP)

얼마나 적합한지 평가하기 위해서 가장 간단한 방법은 상위 k개에 대해서만 평가하는 것입니다.

MAP 는 이름 그대로 평균적인 정확률을 보여줍니다. 한 쿼리에 대한 적합 문헌 집합들 중 k 개를 선정해 평균을 낸 것을 그 쿼리에 대한 정확률로 보는 것입니다.

주의)

순위 검색을 위해서도 결국은 Precision과 Recall 개념을 사용하게 됩니다. 하지만 이 둘은 trade-off 가 있기 때문에 Recall 을 일정수준에 고정시킨 후, 그 수준에서의 최고 Precision 값을 찾는것이 좋습니다.

Precision 과 Recall 이 trade-off 관계인것이 이해가 가지 않는다면 여기 를 참고해주세요.

8.3 시스템 품질과 사용자 유용도

1) 시스템 문제

시스템 자체의 평가를 위해서는 다양한 기준들이 있습니다.

색인 속도
검색 속도
복잡한 쿼리의 처리
컬렉션의 크기

대부분의 기준들은 수치적으로 측정이 가능하기 때문에, 비교적 평가를 명확하게 할 수 있습니다.

2) 사용자 유용도

사용자의 유용도의 측정은 목적에 따라 조금씩 다를 수 있습니다. 일반적인 검색엔진에 대한 유용도는 재방문률로 측정할 수 있고, 다른 검색엔진 대비 방문률도 유용도의 척도가 될 수 있습니다.

3) 배치된 시스템의 정제

시스템을 업데이트 하고싶다면, 기존 시스템 대비 사용자의 만족도가 높은지를 알 수 있어야 합니다.

가장 일반적으로는 A/B 테스트 를 사용합니다. 기존 시스템과 제안 시스템에 한 가지의 차이를 두고 사용량을 조사하는 것입니다.

사용량을 조사하는 방법에는 최상위 결과나 첫 페이지의 결과를 얼마나 클릭했는지 분석하기 등이 있습니다. 이런 방법을 클릭 로그 분석, 클릭 스트림 마이닝 이라고 합니다.

[최신 정보검색론] 지지 벡터 기계와 기계 학습

Thu, 11 Apr 2019 17:30:00 +0900

Chapter 15 지지 벡터 기계와 기계 학습

이 글은 최신 정보검색론 을 읽고 정리 한 내용입니다.

Chapter 15 에서는 분류 모델 중 하나인 지지 벡터 기계 (SVM) 에 대해 알아보겠습니다.

SVM 의 기본적인 아이디어는 두 범주의 경계를 가장 넓게 하는 경계를 찾는 것 입니다. 주로 2-Class 분류에 많이 쓰이며, 필요에 따라 회귀나 다범주 분류에도 쓰입니다.

15.1 선형 분류 문제

선형분류란 위의 별과 동그라미 자료를 구분하는 선을 찾는 문제로 볼 수 있습니다.

A 와 B 가 둘 다 선형 분류인데, 이 중 어떤 선이 더 좋은 분류기일까요?

답은 B입니다. SVM 은 두 범주의 경계를 가장 넓게, 즉 가장 확실하게 분류하는 분류기를 찾는 것이 목적이기 때문입니다.

여기서 분류기를 결정하는 점 (노란색으로 표시된 점) 을 Support Vector 라고 합니다.

15.2 SVM 의 확장

1) soft margin SVM

SVM 분류기는 B’ 나 B’’ 선 바깥쪽으로 어떠한 데이터가 추가되어도 분류기가 바뀌지 않습니다. Support Vector 만이 분류기를 결정하기 때문입니다.

문제는 B’ 와 B’’ 사이나 근처에 데이터가 추가되는 경우입니다. 그 사이에 데이터가 추가되면 분류기가 바뀔 수도 있고, 만약의 경우 이상치가 들어온다면 이상치에 의해 분류기가 결정될 수 있기 때문입니다.

이런 이상치에 대비하기 위해서 우리는 보다 유연한 모델이 필요합니다. 선형 SVM 모델 보다 이상치에 유연한 모델을 soft margin모델 이라고 합니다. (수식은 뒤에서 설명하겠습니다.)

앞의 기본 SVM 모델 (hard margin) 에서 파라미터 $C$를 추가하면 soft margin 모델을 고려할 수 있는데, 이 $C$값에 따라 이상치를 얼마나 허용할 지 결정하게 됩니다.

$C$ 값이 작을수록 이상치를 많이 허용하고, $C$ 값이 클수록 이상치를 적게 허용합니다. 즉, $C$ 가 작을수록 과소적합, $C$ 가 클수록 과대적합이 될 위험이 높기 때문에 적절한 파라미터 값을 찾는 과정이 필요합니다.

2) 비선형 SVM

이제까지는 선형 SVM 모델만 보았습니다. 하지만 실제 데이터에서는 아무리 선형으로 분류하려고 해도 되지 않는 경우가 더 많습니다. 이런 경우에도 우리는 커널 이라는 개념을 통해 선형 분류기를 사용할 수 있습니다.

좌측의 Input Space 에서는 선형 분류기를 사용할 수 없지만, 차원을 높여 우측의 모양으로 만들어 선형 분류기 (초평면) 을 정의할 수 있습니다.

이처럼 저차원 공간을 고차원 공간으로 사상하는 방법을 커널 이라고 합니다.

이 커널에는 많은 종류가 있지만, 많이 사용하는 가우시안 RBF 커널의 개념에 대해서 주로 설명을 하겠습니다.

RBF 커널은 gamma 를 파라미터로 사용합니다. 위의 그림은 gamma 값에 따른 RBF 커널의 표준편차 를 나타냅니다. gamma 가 클수록 표준편차가 작습니다. 즉, gamma가 클수록 한 데이터 포인터들이 영향력을 행사하는 거리가 짧아지는 반면, gamma가 낮을수록 커진다고 볼 수 있습니다.

soft margin SVM 모델에 RBF 커널을 사용한다고 하면, C와 gamma 총 두 개의 파라미터를 최적화 하는 작업이 필요합니다.

C 값이 커질수록 이상치를 적게 허용 하고 있는 것을 확인할 수 있고, gamma 값이 커질수록 경계가 더 구체적으로 변하는 것을 확인할 수 있습니다. 이러한 성질들을 고려해 적절한 파라미터를 정하는 것이 중요합니다.

+) 수식

수식적으로 분류기를 구하면 다음과 같습니다.

초평면의 절편을 $b$, 초평면에 직교하는 법선 벡터 (가중치 벡터) 를 $ \vec{w} $ 라고 하면, 초평면 상의 모든 점 $\vec{x}$는

$\vec{w}^T\vec{x} = -b$를 만족합니다.

[최신 정보검색론] 점수 계산, 용어 가중치, 벡터 공간 모델

Thu, 11 Apr 2019 13:50:00 +0900

Chapter 6. 점수 계산, 용어 가중치, 벡터 공간 모델

이 글은 최신 정보검색론 을 읽고 정리 한 내용입니다.

Boolean 질의로 매칭되는 문헌들을 찾았을 때, 그 문헌들에 점수를 부여해 순서를 정하는 과정이 필요합니다.

Chapter 6 에서는 그 방법들에 대해 다루겠습니다.

6.1 인수 색인과 구역 색인

문헌은 용어 뿐 아니라 메타 데이터 를 포함한 구조입니다. 메타 데이터란 저자, 제목, 출판일 등 문헌의 기본 정보를 의미합니다.

검색 결과에 점수를 부여할 때, 이 메타 데이터를 활용할 수 있습니다. 메타 데이터 중 값이 작은것을 필드, 값이 비교적 큰 것을 구역이라고 하는데 주로 구역에 대해 살펴보겠습니다.

1) 가중치 구역 점수 계산

메타 데이터의 각 구역에 가중치를 부여해 매칭 정도를 계산하면, 점수를 매길 수 있는 형태가 됩니다.

예를 들어,

문헌 ID	저자	제목	본문
1	현경	고양이 좋아	고양이가 최고야
2	고양이	고양이가 좋아하는 것	츄르가 최고야

위의 자료에서 저자, 제목, 본문에 각각 가중치 $ 0.2 , 0.3, 0.5$ 를 부여한다고 합시다.

쿼리가 ‘고양이’ 일 때, 문헌 1의 점수는 $ 0.2 * 0 + 0.3 * 1 + 0.5*1 = 0.8 $ 이고, 문헌 2의 점수는 $ 0.5 $ 입니다.

두 문헌 모두 ‘고양이’ 라는 단어를 두번씩 포함하지만, 본문에 가중치를 높게 주었기 때문에 문헌1의 점수가 더 높습니다.

이렇게 더 중요하다고 생각하는 구역에 가중치를 높게 줌으로써 순위를 정할 수 있었습니다.

그렇다면 이 가중치는 어떻게 구할까요?

위의 예제처럼 값을 지정해 사용할 수도 있지만, 일반적으로는 최적의 값을 찾기 위해 학습 을 합니다.

학습을 위한 데이터셋은 보통 (질의 q, 문헌 d, 적합성여부) 로 구성 됩니다. 가중치는 g 입니다.

제목(T)와 본문(B)에 대한 가중치를 구하는 경우를 생각해 보면,

$ score(d_j, q_j) = g * s_T(d_j, q_j) + (1-g) * s_B(d_j, q_j) $ 인 식을 생각할 수 있습니다.

모든 구역에 대한 가중치 합은 1이고, $ s_T $와 $ s_B $는 각각 쿼리와 제목,본문의 일치 여부에 대한 Boolean값입니다.

이 score 값을 데이터셋의 적합성 여부와 비교해, 다음과 같이 오차함수를 정의할 수 있습니다.

$ \epsilon(d_j, q_j) = (r(d_j, q_j) - score(d_j, q_j))^2 $

그렇다면 총 오류는 모든 데이터 쌍에 대한 $ \epsilon $ 값의 합이 됩니다.

결과적으로, 총 오류를 최소로 만드는 가중치 g의 값을 찾는 것이 최적의 가중치를 찾는 것임을 알 수 있습니다.

이 문제는 g 에 대한 이차식이 최소가 되는 점, 즉 미분해서 0이 되는 점을 찾으면 되는 문제입니다.

6.2 용어 빈도와 가중치

1) 에서는 구역에 가중치를 부여했다면, 2)에서는 문헌 내 용어에 가중치를 부여합니다.

문헌1과 2에 동일한 단어가 있는데, 그 단어의 중요성이 문헌1보다 2에서 크다면 문헌2의 단어에 높은 점수를 주는 것입니다. 즉, 문헌에서 중요한 단어를 포함하는지를 살펴보는 것입니다.

이 절에서는 빈도 관련 용어가 많이 나오기 때문에 용어를 정리해 보겠습니다.

용어 빈도 (tf) : 문헌 d 내에서 용어 t의 빈도
문헌 빈도 (df) : 컬렉션 c 내에서 용어 t를 포함하는 문헌의 수
역문헌 빈도 (idf) : $ log(\frac {N} {df}) $

용어에 가중치를 주는 가장 간단한 방법은 문헌 내 용어의 빈도 (tf) 를 세는 것 입니다.

하지만 이 방법은 문제가 있습니다. 예를 들어 고양이 서적 관련 컬렉션에서 용어 ‘고양이 화장실’를 찾는 경우를 생각해봅시다. ~~너무 극단적이네요…~~

문헌 1	문헌 2	문헌 3
고양이 … 고양이 … 고양이 … 고양이 … 고양이	고양이 고양이 화장실	화장실

문헌 1 에서 고양이의 빈도는 5, 문헌 2 에서 고양이의 빈도는 2 이므로 빈도 수만 생각해본다면 ‘고양이 화장실’의 검색결과는 문헌 1로 잘못 나오게 됩니다.

고양이 서적 관련 컬렉션에서는 모든 문헌이 대체적으로 ‘고양이’를 많이 포함하고 있기 때문에 ‘고양이’보다는 ‘화장실’에 집중하는 것이 좋습니다. 그러기 위해서는 ‘고양이’의 많은 빈도를 조절해 중요도를 낮추어 주어야 합니다.

빈도 조절을 위해 컬렉션 내에서 ‘고양이’를 포함하는 문헌의 수 (df) 를 세어줍니다. 위의 예에서는 2 입니다.

‘고양이’를 포함하는 문헌이 많을 수록 그 용어를 덜 중요하게 보고 싶기 때문에, 전체 문헌 수 (N) 를 df 로 나누어 줍니다. 이 값을 역문헌 빈도 (idf) 라고 하고, $ idf = log(\frac {N} {df}) $ 로 정의해 줍니다. (log 는 계산량을 줄이기 위해 사용합니다.)

이제 빈도 조절까지 완료했으므로, tf 와 idf를 결합한 tf-idf 를 문헌 내 용어의 가중치로 사용할 것이며, 식은 $ {tf-idf}{t,d} = tf{t,d} * idf_t$ 입니다.

결과적으로 tf-idf 값은

적은 수의 문헌에 용어 t가 많이 있으면 가장 높은 값을 가짐
문헌들에 그 용어가 적게 있으면 적은 값을 가짐
모든 문헌 안에 용어가 존재할 경우 가장 낮은 값을 가짐

으로 생각할 수 있겠습니다.

6.3 점수 계산을 위한 벡터 공간 모델

위에서는 문헌을 용어들의 집합으로 생각했습니다. 이번 절에서는 문헌을 벡터 공간 안에 있는것으로 생각해 보겠습니다.

[Sorting #6] Quick Sort

Thu, 29 Nov 2018 12:45:00 +0900

Quick Sort

Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다.

quick sort 는 추가적인 메모리 사용 없이 Divide and Conquer 를 사용할 수 있습니다.
pivot 을 이용해 divide 될 지점을 찾아주는 것이 핵심입니다.

그림으로 예를 들어 설명해보겠습니다.

이 리스트에서 첫번째 pivot 을 54 라고 합시다.
( pivot 을 정하는 방법은 여러가지가 있지만, 예제에서는 첫번째 원소를 pivot 으로 하는 방법을 선택하고 있습니다.)

이제 이 pivot 을 기준으로 하고, 나머지 리스트 에 대해 leftmartk 와 rightmark 를 정합니다.
leftmark 와 rightmark 는 서로의 방향으로 한 칸씩 이동을 하는데
leftmark > pivot 이고 rightmark < pivot 인 시점에서 두 값을 swap 합니다.

이런 과정을 거치면서 leftmark 와 rightmark 를 이동하다 보면 둘이 교차하는 지점을 찾을 수 있는데,
그 지점에서 rightmark 의 값과 pivot 의 값을 swap 해 줍니다.
( 아래 그림에서는 31과 54 를 swap 해 주어야 합니다. )

이렇게 한 pivot 에 대해 완료하고 나면 리스트를 분할할 수 있습니다.

이미 정렬이 된 pivot 인 54 를 기준으로 앞과 뒤의 원소들로 리스트를 분할합니다.
각 리스트에 대해 다시 quicksort 를 실행해 주면 정렬이 완료됩니다.

구현하기

pivot , leftmark, rightmark 를 정해 한번의 quick sort 과정을 거치기
분할된 리스트에 대해 quicksort 하기

~~quicksort 를 재귀로 계속 하면 좋을것 같은데, base case 가 무엇일지 잘 생각이 안나 일단은 구현한 대로 포스팅 합니다..ㅠ~~

def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
    if first < last:

        splitpoint = partition(alist,first,last)

        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
    pivotvalue = alist[first]

    leftmark = first+1
    rightmark = last

    done = False
    while not done:

        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            done = True
        
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp

    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

    return rightmark

분석하기

길이가 $n$ 인 리스트에 대해, 파티션이 항상 리스트의 중간에 있다면 binary search 와 마찬가지로 $\log n$ 만큼의 시간이 소요됩니다.
또한 분할지점을 찾기 위해 pivot 과 값을 비교하는 과정은 최대 $n$ 만큼 소요되므로 Quick Sort 는 $O(n\log n)$ 인 알고리즘 입니다. $n-1$ 개의 값을 피벗과 비교해야 합니다.

Merge Sort 와 실행시간은 비슷하지만, 추가적인 메모리를 필요로 하지 않는다는 장점이 있습니다.

하지만 파티션이 왼쪽이나 오른쪽으로 치우쳐 있는 경우에는 문제가 될 수 있습니다.
예를 들어 파티션이 계속해서 맨 앞쪽에 나온다고 하면 의미없는 분할을 계속 해야 하기 때문입니다.
이 경우 길이가 $n$ 인 리스트를 처음 분할 했을 때 $0$ , $n-1$ 인 리스트로 분할이 되고 그 다음에는 $0$, $n-2$ 인 리스트 로 분할이 됩니다.
즉 worst case 의 실행시간은 $O(n^{2})$ 이 되어버립니다.

위와 같은 worst case 는 항상 pivot 을 맨 앞의 원소로 할 때에 발생합니다.
이를 해결하기 위해 pivot 을 결정하는 많은 방법들이 존재합니다.
그 중 median of three 라는 방법이 있는데, 리스트의 처음,중간,끝 값 중 중위수를 pivot 으로 사용하는 방법입니다.
리스트가 어느 정도 정렬되어 있을 때 median of three 를 사용하면 리스트가 거의 반으로 분할 되기 때문에 유용합니다.

[Sorting #5] Merge Sort

Thu, 29 Nov 2018 10:30:00 +0900

Merge Sort

Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다.

sorting 알고리즘의 성능을 높이기 위해 Dived and Conquer 전략을 사용할 수 있습니다.

Merge Sort 는 리스트를 재귀적으로 두개로 나누어 정렬 후 정렬된 부분들을 다시 합치는 방식입니다.
base case는 merge 를 수행하는 부분이 되겠고, 그 조건은 리스트의 값이 하나 이하일 경우 입니다.

그림으로 예를 들어보겠습니다.

위의 그림은 Merge Sort 를 위해 리스트를 분할하는 과정을 나타냅니다.
리스트의 원소가 하나 이하가 될 때 까지 계속 분할하는 것을 볼 수 있습니다.

이렇게 분할된 리스트는

위와같이 다시 합치는 과정을 거치게 되는데, 이 때 합치는 과정은 정렬된 부분에서 가장 작은 값을 원래 리스트의 맨 앞으로 가져오는 형식으로 진행됩니다.

구현하기

길이가 1 이하가 될 때 까지 입력리스트를 반으로 나누기 (Python 의 slicing 방법을 사용)
반으로 나눈 리스트에 대해 각각 mergerSort 하기
입력리스트, 왼쪽리스트, 오른쪽리스트 의 값을 비교하며 가장 작은 값부터 앞쪽에 넣어주기

def mergeSort(alist):
    print('Splitting {}'.format(alist))
    if len(alist) > 1:
        mid = len(alist) // 2
        leftList = alist[:mid]
        rightList = alist[mid:]
        
        mergeSort(leftList)
        mergeSort(rightList)
        
        leftIdx = 0
        rightIdx = 0
        originIdx = 0
        
        while leftIdx < len(leftList) and rightIdx < len(rightList):
            if leftList[leftIdx] < rightList[rightIdx]:
                alist[originIdx] = leftList[leftIdx]
                leftIdx = leftIdx + 1
            else:
                alist[originIdx] = rightList[rightIdx]
                rightIdx = rightIdx + 1
            originIdx = originIdx + 1
            
        while leftIdx < len(leftList):
            alist[originIdx] = leftList[leftIdx]
            leftIdx = leftIdx + 1
            originIdx = originIdx + 1
            
        while rightIdx < len(rightList):
            alist[originIdx] = rightList[rightIdx]
            rightIdx = rightIdx + 1
            originIdx = originIdx + 1
            
        print('Mergeing {}'.format(alist))

실행결과를 보면, 재귀적으로 구현되었기 때문에 왼쪽리스트부터 base case 까지 나눈 후 merge 하고
그 다음에 오른쪽리스트를 merge 하고 있는것을 확인할 수 있습니다.

mergeSort([54,26,93,17,77,31,44,55,20])

Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting [54, 26, 93, 17]
Splitting [54, 26]
Splitting [54]
Splitting [26]
Mergeing [26, 54]
Splitting [93, 17]
Splitting [93]
Splitting [17]
Mergeing [17, 93]
Mergeing [17, 26, 54, 93]
Splitting [77, 31, 44, 55, 20]
Splitting [77, 31]
Splitting [77]
Splitting [31]
Mergeing [31, 77]
Splitting [44, 55, 20]
Splitting [44]
Splitting [55, 20]
Splitting [55]
Splitting [20]
Mergeing [20, 55]
Mergeing [20, 44, 55]
Mergeing [20, 31, 44, 55, 77]
Mergeing [17, 20, 26, 31, 44, 54, 55, 77, 93]

분석하기

Merge Sort 는 크게 두 가지의 과정으로 나뉘므로, 각 과정에 대해 생각해 볼 필요가 있습니다.

먼저 Split 의 과정을 생각해보면 Binary Search 와 같은 과정임을 알 수 있습니다.
n개의 값을 반으로 나눠가는 과정을 생각해 보면,
첫번째 과정을 거쳤을 때에는 $\frac {n}{2}$, 두번째는 $\frac {n}{4}$ , … , $k$ 번째에는 $\frac {n}{2^k}$ 개의 값이 남는 것을 알 수 있습니다.
우리는 $\frac {n}{2^k}$ (맨 마지막으로 남은 원소의 수) 가 1인 경우까지 split 하는 것이기 때문에, $\frac {n}{2^k} = 1$ 인 k 를 계산하면 됩니다.
$k=\log n$ 이므로 반으로 나눠가는 과정의 실행 시간은 $O(\log n)$ 만큼이 걸리는 것을 알 수 있습니다.

다음으로 Merge 의 과정은 각 값당 최대 n 번의 비교를 거쳐야 하기 때문에 $n$ 만큼의 시간이 걸립니다.

그래서 Merge Sort 알고리즘은 $O(n\log n)$ 알고리즘 입니다.

추가중

그런데 slicing 방법의 실행시간은 무시해도 되는걸까 하는 의문이 생겼습니다.
검색결과 slicing 은 $k$ 개의 slicing 을 할 때에 $O(k)$ 만큼의 실행시간이 필요하다고 합니다.

Merge Sort 의 이론적인 분석시간인 $O(n\log n)$ 을 맞춰주기 위해서는 이 slicing 방법을 제거해야 합니다.

[Sorting #4] Shell Sort

Wed, 28 Nov 2018 15:00:00 +0900

Shell Sort

Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다.

shell sort 는 조금 생소할 수도 있는 소팅 방법입니다.
insertion sort 방식을 조금 개선한 방법인데, insertion sort 가 두 연속된 sublist 로 나누어 정렬하는 방식이었다면
shell sort 는 일정 gap 을 가진 sublist 로 나누어 정렬하는 방식입니다.

그림을 보면서 설명하겠습니다.

이 그림은 gap 이 2 인 sublist 로 나누어 정렬한 예시입니다.
그림처럼 일정한 gap 만큼 떨어진 값들을 하나의 sublist 로 묶어서 생각해 정렬하면 됩니다.

각 sublist 를 정렬한 후 의 그림은 다음과 같습니다.

각 sublist 를 정렬했지만 전체 리스트에서 보았을 때 정렬이 완료되지 않은것을 알 수 있습니다.
이때는 2를 반으로 나눈 1을 gap 으로 가지는 sublist 를 만들어 다시 정렬합니다.

구현하기

[Sorting #3] Insertion Sort

Tue, 27 Nov 2018 15:00:00 +0900

Insertion Sort

Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다.

insertion sort 는 한 리스트 내에서 두 부분으로 리스트를 나누고, 뒤의 리스트의 값들을 하나씩 앞의 리스트에 정렬해서 넣는 방식입니다.

결론부터 말하자면 bubble sort 와 마찬가지로 성능이 좋지 않은 방법입니다.

그림으로 예를 들어보겠습니다.

편의상 앞의 list 를 sorted sublist , 뒤의 list 를 unsorted sublist 라고 이름붙여 보겠습니다.

unsorted sublist 에 있는 값들을 차례로 sorted sublist 로 가져오는데, 이 때 가져오는 값과 sorted sublist 의 값을 하나씩 비교하며 삽입합니다.

위의 그림에서 31 을 sorted sublist 에 삽입하는 과정을 자세히 보겠습니다.

31 과 sorted sublist 의 값을 비교하며 31 보다 작은 값이 나올 때 까지 계속 shift 하는 것을 볼 수 있습니다.
early stop rule 이 없다고 가정했을 때 한 원소를 삽입하기 위해 검사해야 하는 횟수는 최대 $n-1$ 번 입니다.

구현하기

현재 값, 현재 인덱스 저장
sorted sublist 와 비교 후 shift

def insertionSort(alist):
    for temp in range(len(alist)):
        tempValue = alist[temp]
        tempIdx = temp
        print('\n tempValue : {}'.format(tempValue))
        while tempIdx > 0 and alist[tempIdx-1] > tempValue:
            print('shift {} -> {}'.format(alist[tempIdx-1], alist[tempIdx]))
            alist[tempIdx] = alist[tempIdx-1]
            tempIdx = tempIdx-1
            
        alist[tempIdx] = tempValue
    return alist

shift 하면서 찾은 인덱스에 현재 값을 넣어주면 됩니다.

위의 코드를 실행한 결과는 다음과 같습니다.

insertionSort([54, 26, 93, 17, 77, 31, 44, 55, 20])

tempValue : 54

tempValue : 26
shift 54 -> 26

tempValue : 93

tempValue : 17
shift 93 -> 17
shift 54 -> 93
shift 26 -> 54

tempValue : 77
shift 93 -> 77

tempValue : 31
shift 93 -> 31
shift 77 -> 93
shift 54 -> 77

tempValue : 44
shift 93 -> 44
shift 77 -> 93
shift 54 -> 77

tempValue : 55
shift 93 -> 55
shift 77 -> 93

tempValue : 20
shift 93 -> 20
shift 77 -> 93
shift 55 -> 77
shift 54 -> 55
shift 44 -> 54
shift 31 -> 44
shift 26 -> 31

분석하기

worst case 의 경우는 완전 역순으로 정렬된 리스트가 들어오는 경우입니다.
이 경우 최대 $n-1$ 번의 비교를 하게 되고, bubble sort 와 마찬가지로 $\frac{1}{2}n^{2} + \frac{1}{2}n - n$ 의 연산을 하게 됩니다.

따라서 $O(n^{2})$ 만큼 시간이 걸린다고 볼 수 있습니다.

bubble sort 와 차이점은 swap 이 아닌 shift 연산을 한다는 것입니다.
shift 연산은 swap 보다 가벼운 연산이기 때문에 bubble sort 보다는 좀 더 나은 알고리즘으로 볼 수 있습니다.