로키오 알고리즘

Rocchio 알고리즘은 1960-1964년 개발된 SMART 정보 검색 시스템에서 비롯된 정보 검색 시스템에서 발견된 관련성 피드백 방법을 기반으로 한다.다른 많은 검색 시스템과 마찬가지로, 로키오 피드백 접근법은 벡터 스페이스 모델을 사용하여 개발되었다.알고리즘은 대부분의 사용자가 어떤 문서를 관련성이 있거나 관련성이 없는 것으로 표시해야 하는지에 대한 일반적인 개념을 가지고 있다는 가정에 기초한다.^[1]따라서 사용자의 검색 질의를 수정하여 검색 엔진의 리콜을 증가시키는 수단으로서 관련 문서와 관련 없는 문서의 임의 비율을 포함시키고, 또한 정밀도도 또한 포함시킨다.질의에 들어갈 수 있는 관련 문서 및 관련 없는 문서의 수는 알고리즘 섹션에 나열된 a, b, c 변수의 가중치로 지정된다.^[1]

알고리즘.

Rocchio 관련 피드백에 대한 공식 및 변수 정의는 다음과 같다.^[1]

${\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1}{ D_{r} }}\sum _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac {1}{ D_{nr} }}\sum _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}$

변수	가치
${\vec{Q}_{m}$	수정된 쿼리 벡터
${\vec{Q}_{o}$	원본 쿼리 벡터
${\vec{D}_{j}$	관련 문서 벡터
${\vec{D}_{k}$	비관련 문서 벡터
$(\displaystyle a}$	원래 쿼리 무게
$(\displaystyle b)$	관련 문서 무게
$(\displaystyle c})$	비관련 문서 가중치
$D_{r}$	관련 문서 세트
$D_{nr}$	비관련 문서 집합

공식에서 입증된 바와 같이, 관련 가중치(a, b, c)는 원래의 질의, 관련 문서 및 관련 없는 문서에서 더 가깝거나 더 먼 방향으로 수정된 벡터를 형성하는 역할을 한다.특히 b와 c의 값은 사용자가 분류한 문서 집합에 비례하여 증감해야 한다.사용자가 수정된 쿼리에 원래 쿼리, 관련 문서 또는 관련 없는 문서의 용어를 포함하지 않아야 한다고 결정한 경우, 카테고리에 해당하는 가중치(a, b, c) 값은 0으로 설정되어야 한다.

알고리즘의 후반부에서 변수 $D_{r}$ $D_{r}$ ${\$ 및 $D_{nr}$ $D_{nr}$ ${\$ 는 관련 문서와 비관련 문서의 좌표를 포함하는 벡터 집합으로 제시된다 $D_{nr}$ . $D_{r}$ $D_{r}$ ${\$ $D_{nr}$ n $D_{nr}$ ${\$ 는 벡터 자체가 아니지만 $D_{nr}$ , ${\vec {D}}_{j}$ → j ${\vec{D}_{j},$ ${\vec {D}}_{k}$ → ${\vec {D}}_{k}$ ${\$ 는 두 세트와 폼 벡터 합산을 통해 반복하는 데 사용되는 벡터다 ${\vec {D}}_{k}$ .이러한 합계는 각 문서 세트의 크기에 따라 정규화(분할)된다( $D_{r}$ $D_{r}$ ${\$ $D_{nr}$ $D_{nr}$ ${\$

수정된 벡터에서 발생하는 변화를 시각화하려면 아래 이미지를 참조하십시오.^[1]문서의 특정 범주에 대한 가중치가 증가하거나 감소함에 따라 수정된 벡터의 좌표는 문서 수집의 중심에서 더 가깝거나 더 멀리 이동하기 시작한다.따라서 관련 문서에 대한 가중치가 증가하면 수정된 벡터 좌표는 관련 문서의 중심에 더 가깝게 반영될 것이다.

시간 복잡성

변수	가치
$\mathb {D}$	레이블이 지정된 문서 세트
$L_{ave}$	문서당 평균 토큰 수
$\mathb {C}$	클래스 세트
$(\displaystyle V}$	어휘/용어 집합
$L_{a}$	문서의 토큰 수
$M_{a}$	문서 유형 수

알고리즘 훈련과 시험에 대한 시간 복잡성은 아래에 열거되어 있고, 그 뒤에 각 변수의 정의가 따른다.시험 단계에서, 시간 복잡성은 등급 중심과 각 문서 사이의 유클리드 거리를 계산하는 것으로 줄일 수 있다.그림 참조: $\Theta (\vert \mathbb {C} \vert M_{a})$ M $\Theta (\vert \mathbb {C} \vert M_{a})$ ) ${\displaystyle \Teta(\vert \mathb {C} \vert M_{a$

교육 = $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ a $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ e $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ + $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ $\Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )$ ) $\theta(\vert \mathb {D} \vert L_{ave}+\vert \mathb {C} \vert \vert V\vert )$
테스트 = $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ + $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ a $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ ) $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ = $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ M a $\Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})$ ) ${\displaystyle \Theta(L_{a}+\vert \mathb {C} \vert M_{a}=\\$ $Theta(\vert \mathb {C} \vert M_{a})}$

사용법

로키오 분류

문서를 관련 없는 것으로 분류할 경우 이점이 있지만, 관련 문서 등급은 사용자가 보다 정밀한 문서를 사용할 수 있게 된다.따라서 Rocchio 분류에서 알고리즘의 가중치(a, b, c)에 대한 전통적인 값은 일반적으로 a = 1, b = 0.8, c = 0.1 정도 된다.현대적인 정보 검색 시스템은 c = 0을 설정하여 관련 문서만을 회계처리함으로써 비관련 문서를 제거하는 방향으로 나아가고 있다.모든 검색 시스템이 비관련 문서의 필요성을 없앤 것은 아니지만, 대부분은 $D_{nr}$ r ${\$ 집합에서 $D_{nr}$ 가장 강력한 비관련 문서만을 회계처리함으로써 수정된 질의에 대한 영향을 제한했다.

제한 사항

로키오 알고리즘은 종종 다중 계층과 관계를 분류하지 못한다.예를 들어, 1989년에 버마라는 나라는 미얀마로 이름이 바뀌었다.따라서 "버마"와 "미얀마"의 두 질의는 둘 다 비슷한 기원을 가지고 있지만 벡터 우주 모델에서는 훨씬 더 멀리 나타나게 될 것이다.^[1]

참고 항목

가장 가까운 중심 분류기, 로키오 분류기

참조

^ ^a ^b ^c ^d ^e ^f 크리스토퍼 D.매닝, 프라하카르 라그하반, 힌리히 슈트제정보 검색 소개, 163-167페이지.케임브리지 대학 출판부, 2009.

[ir-manning-1] ^ ^a ^b ^c ^d ^e ^f 크리스토퍼 D.매닝, 프라하카르 라그하반, 힌리히 슈트제정보 검색 소개, 163-167페이지.케임브리지 대학 출판부, 2009.

[1]

Search

로키오 알고리즘

네임스페이스

더

목차

알고리즘.

시간 복잡성

사용법

제한 사항

참고 항목

참조