基于kNN完善digit recognition(kaggle)精度(0.95-->1)[進行中]

背景

一直在搞高維資料檢索，研究成果沒出多少，愛鑽牛角尖。時間長了，發現連基本的解決問題的能力都沒有了。視野太狹窄，是以決定到kaggle上惡補一番。

Digit Recognition是一個最基本的手寫識别問題，是對數字[0-9]手寫的識别。共有42000份訓練樣本，28000份待識别樣本。

kNN初步嘗試

先送出第一份結果建立自信吧。感謝wepon_的kaggle入門帖的啟發。原來自己一直在研究的k近鄰(k nearest neighbor, kNN)查詢技術竟然可以直接用于解該問題。

原理：

- 将每個28 x 28的圖像轉化成784維的向量，直接作為該圖像的特征向量，這是最簡單的特征向量建構方案

- 如果兩份圖像表示的内容相似，則兩幅圖像特征向量的距離（我用的是歐式距離）就會很小

- 是以，将42000份訓練圖像作為kNN查詢的基本資料集(baseset)，28000份圖像作為kNN的查詢集合(queryset)，為每個查詢向量在baseset中搜尋 k 個最近鄰，采用某種政策融合查詢結果的标簽資料，作為該查詢圖像的識别結果。

這麼簡單的思路，我竟然都沒轉過彎來，看來真是鑽牛角尖鑽得夠深了啊。

思路有了，二話不說開始實施，很快在matlab裡實作了（其實花了1個多小時）。不過用的是brute-force查詢。等會，28000個查詢點，尼瑪，那得跑多久啊，不過幸好計算機核心比較多（12核），還能跑并行，而且baseset四萬多的體量也太小了。不夠跑下來就蒙了，還是太慢。

幸好自己平時積累了一些c/c++實作的kNN算法，直接取來。我用的是[Sharadh Ramaswamy 2011年TKDE上的一篇文章][1]，簡稱HB。

“` python

./main -ds digit -K 50 -h 1 -nq 28000 -k 20

花了24分鐘生成kNN查詢結果，到matlab翻譯成識别結果（每個查詢點取得票最多的标簽值），送出，0.95857，排名1081。乍一看準确度還挺高的95%，不過是1161個誤判呀。還是可怕。感覺是k取大了。

細化提升

• Markdown和擴充Markdown簡潔的文法
• 代碼塊高亮
• 圖檔連結和圖檔上傳
• LaTex數學公式
• UML序列圖和流程圖
• 離線寫部落格
• 導入導出Markdown檔案
• 豐富的快捷鍵

表格

Markdown　Extra　表格文法：

項目	價格
Computer	$1600
Phone	$12
Pipe	$1

可以使用冒号來定義對齊方式：

項目	價格	數量
Computer	1600 元	5
Phone	12 元	12
Pipe	1 元	234

定義清單

Markdown　Extra　定義清單文法： 項目１ 項目２

定義 A

定義 B

項目３

定義 C

定義 D

定義D内容

代碼塊

代碼塊文法遵循标準markdown代碼，例如：

“` python

@requires_authorization

def somefunc(param1=”, param2=0):

”’A docstring”’

if param1 > param2: # interesting

print ‘Greater’

return (param2 - param1 + 1) or None

class SomeClass:

pass

message = ”’interpreter

… prompt”’

離線寫部落格

即使使用者在沒有網絡的情況下，也可以通過本編輯器離線寫部落格（直接在曾經使用過的浏覽器中輸入write.blog.csdn.net/mdeditor即可。Markdown編輯器使用浏覽器離線存儲将内容儲存在本地。

使用者寫部落格的過程中，内容實時儲存在浏覽器緩存中，在使用者關閉浏覽器或者其它異常情況下，内容不會丢失。使用者再次打開浏覽器時，會顯示上次使用者正在編輯的沒有發表的内容。

部落格發表後，本地緩存将被删除。　

使用者可以選擇 把正在寫的部落格儲存到伺服器草稿箱，即使換浏覽器或者清除緩存，内容也不會丢失。

注意：雖然浏覽器存儲大部分時候都比較可靠，但為了您的資料安全，在聯網後，請務必及時發表或者儲存到伺服器草稿箱。

浏覽器相容

1. 目前，本編輯器對Chrome浏覽器支援最為完整。建議大家使用較新版本的Chrome。
2. IE９以下不支援
3. IE９，１０，１１存在以下問題
   1. 不支援離線功能
   2. IE9不支援檔案導入導出
   3. IE10不支援拖拽檔案導入

[1]: Ramaswamy S, Rose K. Adaptive cluster distance bounding for high-dimensional indexing[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(6): 815-830.