[Journal] 제2코사인법칙 응용 - 뉴스 분류 알고리즘

서론

 

웹페이지에 무언가를 검색하고, 그것과 관련된 기사를 제공하는 것이 검색엔진의 역할이다. 여기서 생기는 합당한 의문점은 ‘어떻게 관련된 기사를 찾는가?’이다. 도서 ‘수학의 아름다움’의 내용 중, 코사인법칙과 벡터 연산을 응용하여 텍스트끼리의 유사성을 비교할 수 있다는 내용이 들어있다. 이것에 대해 추가적으로 조사하고 직접 구현해보고자 한다.

 

 

 

---

 

 

 

기본 원리

 

 무언가를 검색하면 그것과 관련된 기사를 제공하는 것이 검색엔진의 역할이다. 여기서 생기는 합당한 의문점은 ‘어떻게 관련된 기사를 찾는가?’이다.

 먼저 사용자가 검색한 문장의 각 단어들에게 가중치를 매긴다. 이후 가중치를 이용해 임의의 뉴스가 얼마나 검색한 문장과 관련되었는지 연산한다. 이 과정에서 코사인법칙과 벡터 연산을 응용하는 것이다.

 

 

 

TF – IDF

 

(1)   IDF

 ‘How to repair chair’라는 문장과 관련된 웹페이지를 찾을 것이다. 우리는 이 단어를 검색할 때, 직감적으로 to보다는 how의 중요도가 높고, how보다는 chair의 중요도가 높다는 사실을 알 수 있다. 이 중요도의 차이를 가중치로 계산한다.

 키워드 w에 대한 가중치의 크기는 아래의 수식(또는 용도에 맞게 이것을 응용한 수식)으로 구한다.

IDF 공식

 The, to, a 같은 단어는 대부분의 웹페이지에 포함되어있다. 이 단어들의 IDF를 계산하면 0에 수렴할 것이다.

 

(2)   TF

 TF란 단어의 빈도수를 의미한다. 1000단어로 이루어진 웹페이지에 ‘how’, ‘repair’, ‘chair’가 각각 0, 5, 35회 등장한다면, TF는 각각 0, 0.005, 0.035이다. 따라서, 검색한 단어 w에 대한 가중치의 크기는 다음과 같다.

TF-IDF 공식

 

 

 

코사인법칙의 응용

 

(1)   웹페이지의 단어 빈도 수를 벡터로 표현하기

 사이트 내 전체 웹페이지에서 사용되는 단어의 종류가 10000가지라고 가정하자. 이때 우리는 한 웹페이지의 단어 빈도수(TF-IDF)들을 모아 하나의 벡터로 표현할 수 있다.

 

(2)   제2 코사인법칙으로 연관성 계산

 삼각형에서 각 A의 코사인은 다음과 같다.

b와 c를 벡터로 보면 각 A의 코사인은 다음과 같다. 단, 여기서 점 곱( • )은 스칼라 곱이다.

 두 웹사이트를 각각 10000차원의 벡터 b와 c로 변환한다. 두 벡터의 사잇각은 A가 된다. 따라서, cosA가 1에 가까울수록 두 웹사이트가 유사하고, 0에 가까울수록 두 웹사이트가 유사하지 않다는 사실을 알 수 있다. 이것이 뉴스 분류 알고리즘의 기본 원리이다.

 사이트 내 전체 웹페이지에서 사용되는 단어의 종류가 10000가지일 때, 두 단어의 연관성(0~1)은 다음과 같이 나타낼 수 있다.

 

 

 

---

 

 

 

문제 설정

 

 위 내용을 바탕으로 뉴스 분류 알고리즘을 구현하려고 하였으나, 뉴스에 실사용 되는 단어의 개수가 너무 많아 제한된 컴퓨터 메모리 내에서 구현이 불가능할 것으로 판단했다. 따라서 비교적 실사용 단어가 적은 c언어 코드를 분류하는 알고리즘을 제작하고자 했다.

 임의의 두 c언어 코드를 입력 받았을 때, 두 코드가 얼마나 유사한지 계산하고 분류하는 알고리즘을 제작한다. 정확도를 높이기 위해 모든 코드는 블로그 [얍문’s Coding World]에서 가져왔다. (https://yabmoons.tistory.com/)

 

 

 

코드 구상

 

(1)   Get_TF_IDF.py 작동 과정

①    웹페이지의 개수를 입력한다.

②    웹페이지 본문을 @ 간격으로 입력한다.

③    웹페이지의 단어들을 리스트로 만든 뒤 AllList에 이차원 배열로 저장한다.

④    AllList를 활용해 TF, IDF를 각각 구하고 TF – IDF를 출력한다.

 

(2)   Get_cos.py 작동 과정

①    Get_TF_IDF.py에서 구한 TF – IDF 배열 두 개를 각각 입력한다.

②    두 배열을 벡터 값으로 인식하여 코사인을 계산한다.

③    임의 기준(0.5)을 설정하여, 코사인 값으로 두 코드의 유사성을 판단한다.

 

 

 

코드 전문

 

(1)   Get_TF_IDF.py

import math

def word_removing(tmp):  # 불필요한 단어 제거
    RemoveList = [",", ".", ";", "(", ")", "{", "}", "<", ">"]
    for k in RemoveList:
        tmp = tmp.replace(k, " ")
    return tmp


D = int(input("사이트 내 웹페이지 개수를 입력하세요 : "))  
# 사이트 내 전체 웹페이지 수
print("@ 간격으로 웹페이지 본문을 입력하세요 : ")

AllList = []  # 웹페이지별 단어를 2차원 배열로 저장한 것
AllDict = {}  # 모든 웹페이지에 존재하는 단어 목록
TFDict = {}   # TF를 저장할 Dictionary
IDFDict = {}  # IDF를 저장할 Dictionary

for cnt in range(D):
    dic = {}
    while True:
        WordList = str(input())
        ProcessedWL = word_removing(WordList)
        ProcessedWL = ProcessedWL.split()
        if ProcessedWL == ['@']:
            break
        for i in ProcessedWL:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1

            if cnt == 0:
                if i in TFDict:
                    TFDict[i] += 1
                else:
                    TFDict[i] = 1
            else:
                if i not in TFDict:
                    TFDict[i] = 0

            IDFDict[i] = 0.0  # key값만 삽입

    OneList = list(dic.keys())  
    AllList.append(OneList)  # AllList에 2차원 배열로 append

# IDF

wList = AllList[0]
for w in wList:
    Dw = 0
    for i in AllList:  # i는 한 사이트 내의 모든 단어 목록
        if w in i:
            Dw += 1
    IDF = math.log10(D/Dw)
    IDFDict[w] = IDF

print("TF     : {}".format(TFDict))
print("IDF    : {}".format(IDFDict))
TFList = list(TFDict.values())
IDFList = list(IDFDict.values())
TF_IDF_List = [x * y for x, y in zip(TFList, IDFList)]
print("TF-IDF : {}".format(TF_IDF_List))

 

(2)   Get_cos.py

import math

TF_IDF_1 = list(map(float, input("TF_IDF_1 : ").split(", ")))
TF_IDF_2 = list(map(float, input("TF_IDF_2 : ").split(", ")))
# 입력 형식 : 0, 0, 0, ... , 0

scalar_bc = sum(x * y for x, y in zip(TF_IDF_1, TF_IDF_2))
size_b = math.sqrt(sum([x ** 2 for x in TF_IDF_1]))
size_c = math.sqrt(sum([x ** 2 for x in TF_IDF_2]))

cos = scalar_bc / (size_b * size_c)

print(cos)

if cos > 0.5:
    print("두 코드는 높은 유사성을 가지고 있습니다.")
else:
    print("두 코드의 유사성이 낮습니다.")

 

 

 

 

실행

 

처음 입력한 코드와 두번째로 입력한 코드의 유사성을 비교할 수 있도록 살짝 변형된 코드를 사용하였다. 입력값은 블로그 [얍문’s Coding World]에서 임의로 10개를 선정했다.

  유사성이 높은 두 코드를 비교 해 보았다. 두 코드는 백준 문제 토마토(7576)와 적록색약(10026)이다. 두 문제 모두 너비우선탐색을 사용하여 해결하였기 때문에 유사성이 높을 것이라 예상했다. 실행 결과 실제로 두 코드의 유사성이 높다는 결과가 출력되었다.

 유사성이 낮은 두 코드도 비교 해 보았다. 백준 문제 피보나치 함수(1003)와 단지 번호 붙이기(2667)는 각각 동적계획법과 너비우선탐색을 사용했다. 따라서 유사성이 낮을 것이라 예상했다. 실행 결과 실제로 두 코드의 유사성이 낮다는 결과가 출력되었다.

 

 

 

참고 문헌

© 우쥔 (2014). 수학의 아름다움 (한수희 옮김). 세종서적.