跳到主要內容

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 .
張貼留言
閱讀完整內容

UTF8 與 Unicode 的轉換 (C++)

UTF8 與 Unicode 的轉換 (C++) 先釐清一下這兩者的性質 Unicode: 為世界上所有的文字系統制訂的標準，基本上就是給每個字(letter)一個編號 UTF-8: 為 unicode 的編號制定一個數位編碼方法 UTF-8 是一個長度介於 1~6 byte 的編碼，將 unicode 編號 (code point) 分為六個區間如下表 1 Bits First code point Last code point Bytes Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 7 U+0000 U+007F 1 0xxxxxxx 11 U+0080 U+07FF 2 110xxxxx 10xxxxxx 16 U+0800 U+FFFF 3 1110xxxx 10xxxxxx 10xxxxxx 21 U+10000 U+1FFFFF 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 26 U+200000 U+3FFFFFF 5 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 31 U+4000000 U+7FFFFFFF 6 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 觀察上面的表應該可以發現 除了 7 bits 的區間外，第一個 byte 開頭連續 1 的個數就是長度，例如 110XXXXX 就是 2 byte 長，而 1110xxxx 就是 3 byte 除了第一個 byte 外，之後的 byte 前兩個 bit 一定是 10 開頭，這樣的好處在於確立了編碼的 self-synchronizeing，意即當編碼為多個 byte 時，任取一個 byte 無法正常解碼。 Note 第一點中的例外 (7 bits) 是為了與 ASCII 的相容性，而第二點會影響到 code point 至 UTF-8 的轉換。 為了與 UTF-16 的相容性，在 R...
張貼留言
閱讀完整內容

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...
張貼留言
閱讀完整內容