사능이

Spearman's rank correlation coefficient 은 Pearson correlation coefficient에 rank를 적용한 것이다. object가 n개이고 각각 점수를 Xi, Yi를 가질 때, 점수를 xi, yi의 순위로 바꾸어 구한다. Pearson correlation coefficient는 다음과 같이 구한다.

Spearman's rank correlation coefficient에서는 xi, yi가 rank이므로

이고, 이를 ⓐ에 적용하면 다음과 같다.

 

… ⓑ

ⓑ를 보면 Spearman's rank correlation coefficient는 object의 개수와 각 rank의 차에 의해 결정이 된다. rank의 차가 전혀 없는 경우 최대 1을 가지고, , 가 완전히 반비례 할 때,최소 -1을 가진다.

(x1 , y1), (x2 , y2), …, (xn , yn)의 set이 있다고 하자(xi, yi는 중복 없이 유일하다). (xa , ya), (xb , yb)가 xa>xb , ya>yb 이거나 xa<xb , ya<yb일 때 concordant라고 한다. 그 외의 경우에는 discordant라고 한다. Keandall tau rank correlation coefficient는 다음과 같이 정의된다.

tau는 -1 ~ 1 사이의 값을 가지는데 두 rank가 일치하면 1의 값을, 두 rank가 완전히 불일치 (예를 들어 한 rank가 다른 rank의 역순)하면 -1의 값을 가진다. 두 rank가 서로 독립적이면 0에 근접한다.

Microsoft Visual Studio 2010

C#

password : 제 학번입니다.

m : # of dimension, evaluation items

L : sorted list by each evaluation item

F(x) : aggregation function

Repeat until return top-k or access all the list L.

FOR i=0; i<m; i++

Do sorted access in sorted list Li. as each object represents R.

Find all of R fields x1, ... , xm by random access.

Compute F(R) = F(x1, ... , xm)

If R is one of the top k, then remember it.

Each list Li, let yi be the grade of the last object seen under sorted access.

Do the threshold value t to be F(y1, ... , ym).

IF top-k values are higher or equal than t, THEN return top-k.

T : top-k objects

C : objects that have possibility of top-k

Tk : the minimum value of T

W(x) : the worst value of candidates that object(x) can have

B(x) : the best value of cadidates that object(x) can have

T = 0, C = 0

Repeat the following

Do the sorted access in parallel to all sources

For every object X seen under sorted access do

If |T} < k then put X to T

Else If W(X) > W(Tk) then move Tk to C, put X to T

Else put X to C

For every object Y ε C, compute B(Y)

If Y is no more relevant(i.e. B(Y) ≤ W(Tk)) then remove Y from C

If |C| = 0 then return T and exit