跳到主要內容

KNN Text Classification

KNN Text Classification

Simplified Data Set

Assume terms a document are unique (tag-like dataset).

doc terms
d0 [ t0, t2, t3 ]
d1 [ t1, t3 ]
d2 [ t0, t2 ]

and

docs = [ d0, d1, d2 ]
d0.terms = [ t0, t2, t3 ]

Weight of Terms

Represent weight of terms with a term-by-document Matrix, A,
where ti denotes term i and dj denotes document j.
Entry A(i, j) is computed by TF-IDF. For example:

A(0, 0) = 
	(1 / # of terms of d0) * 
	log2(# of docs / t0 occurrences for all docs)
	= (1/3) * log2(3/2)
	~= 0.195

Hence A of the dataset is

term\doc d0 d1 d2
t0 0.195 0 0.292
t1 0 0.792 0
t2 0.195 0 0.292
t3 0.195 0.292 0

Note: t0 … t3 can be viewed as a multi-dimension space such that d0 is a point
(0.195, 0, 0.195, 0.195) of the space.

Document Similarity

Per the weight matrix we can compute document-to-document similarities matrix, S, by cosine-similarity. For example:

intersect(d0.terms, d0.terms) = [ t3 ]

S(0, 1) = 
    sum([ A(i, 0) * A(i, 1)) | ti is shared by d0 and d1 ]) /
    [ sqrt(sum( A(i, 0)^2 ) for all i) + 
      sqrt(sum( A(i, 1)^2 ) for all i) ]
      
    = [ A(3,0) * A(3, 1) ]  / [
	    sqrt(0.195^2 + 0^2 + 0.195^2 + 0.195^2) +
	    sqrt(0^2 + 0.792^2 + 0^2 + 0.292^2)
	    ]
	= 0.199
doc\doc d0 d1 d2
d0 1 0.199 0.81
d1 1 0.0
d2 1

As one can see, documents have more terms in common will have higher similarity score.
e.g. S(0, 1) = 0.199 represents 1 common term. S(0, 2) = 0.81 represents 2 common terms.

Nearest Neighbor

Given a new document, d3, and its term list [t2, t3], we can compute the nearest neighbor of it.
First we compute weight of terms of d3, which is

term\doc d3 w/upd d3 wo/upd
t0 0 0
t1 0 0
t2 0.292 0.792
t3 0.499 0.792

Note: Among calculation of weight, only log2(# of docs / term occurrences for all docs) need to be updated. In practice, within large enough dataset, I think it should be fine to eliminate the updating. Above table shows both weight values with/without updating.

Then we compute similarity score for d3 to other documents.

doc\doc d0 d1 d2
d3 w/upd 0.789 0.299 0.5
d3 wo/upd 0.816 0.245 0.5

The nearest neighbor, i.e. 1-NN, of d3 is d0.

Written with StackEdit.

標籤：

留言

張貼留言

這個網誌中的熱門文章

得利油漆色卡編碼方式

得利油漆色卡編碼方式 類似 Munsell 色彩系統 ，編碼方式為 HUE LRV/CHROMA 例如 10GY 61/449 ( 色卡 ) 編碼數值 描述 10GY hue ，色輪上從 Y(ellow) 到 G(reen) 區分為 0 ~ 99 ，數值越小越靠近 Y，越大越靠近 G 61 LRV (Light Reflectance Value) 塗料反射光源的比率，數值從 0% ~ 100% ，越高越亮，反之越暗，也可理解為明度 449 chroma 可理解為彩度，數值沒有上限，越高顏色純度 (濃度) 越高 取決於測量儀器，對應至 RGB 並不保證視覺感受相同。 參考資料： 色卡對照網站 e-paint.co.uk Written with StackEdit .
張貼留言
閱讀完整內容

C++17 新功能 try_emplace

C++17 新功能 try_emplace 回顧 emplace 大家的好朋友 Standard Template Library (STL) 容器提供如 push_back , insert 等介面，讓我們塞東西進去； C++11 之後，新增了 emplace 系列的介面，如 std::vector::emplace_back , std::map::emplace 等，差異在於 emplace 是在容器內 in-place 直接建構新元素，而不像 push_back 在傳遞參數前建構，下面用實例來說明： struct Value { // ctor1 Value ( int size ) : array ( new char [ size ] ) , size ( size ) { printf ( "ctor1: %d\n" , size ) ; } // ctor2 Value ( const Value & v ) : array ( new char [ v . size ] ) , size ( v . size ) { printf ( "ctor2: %d\n" , size ) ; memcpy ( array . get ( ) , v . array . get ( ) , size ) ; } private : std :: unique_ptr < char [ ] > array ; int size = 0 ; } ; struct Value 定義了自訂建構子 (ctor1)，以指定大小 size 配置陣列，複製建構子 (ctor2) 則會配置與來源相同大小及內容的陣列，為了方便觀察加了一些 printf 。當我們如下使用 std::vector::push_back 時 std :: vector < Value > v ; v . push_back ( Value ( 2048 ) ) ; 首先 Value 會先呼叫 ctor1，傳給 push_ba...
張貼留言
閱讀完整內容

Notes for C/C++ Programming

Notes for C/C++ Programming Notes for C/C++ Programming Off by One Error Prone # define LEN 128 char buf [ LEN ] = { 0 } ; // -1 for prevent missing NULL terminator // since strncpy doesn't preserve it for us. strncpy ( buf , something , sizeof ( buf ) - 1 ) ; // snprintf does preserve NULL terminator for us // i.e. actual size for placing characters is sizeof(buf) - 1 // but it takes extra time to parsing format snprintf ( buf , sizeof ( buf ) , something ) ; Bad things often happen when we mess with -1 or +1 to pointers point to continuous elements. Absorber # define LEN 128 char buf [ LEN + 1 ] = { 0 } ; // ^^^^ Always preserve 1 byte strncpy ( buf , somethin , sizeof ( buf ) ) ; Constant Correctness (C/C++) Bad void do_something ( char * dest , char * src ) ; struct MyList { void do_something ( std :: string & name ) ; } ; Reason : Will the name be modified by the lookup method? Will stat...
張貼留言
閱讀完整內容