Posts tagged with K-means

20070921 ~dokumenttien luokittelu

早上七點多時爬回床,睡了回籠覺,於是下午兩點的課就遲到了,我想說應該會自己醒來所以沒設鬧鐘…

今天的電子商務由勝凱報告第一章,他製作了約 30 多張投影片,除了課本以外,還自己找了很多例子,報告超過三小時。同學們的發言,不論是補充說明或是提出不同的意見,都很踴躍,整堂課洋溢在熱情的學術氣息中,真是讓我倍感壓力呀~ 我怕得回房間後便趕快先搜尋一下我負責章節——《顧客介面》的相關資訊 XD 課程後半段我拼命想找可以發言的點,但是實在對於這個議題不怎麼瞭解,找不到可以提建設性意見的地方,雖然對某些部份覺得好奇,但又不想提無聊的問題,最後只在 eDistribution 的部份試圖舉了一個例子。今天這一堂課,讓我突然有了身為研究生的自覺 orz

晚上閒著沒事,打掃了一下房間。用的是前住戶留下的 3M 魔布拖把1,不過我不太懂用法,不知道前住戶是怎麼拖到讓上面佈滿灰塵的… 我拖的時候都吸不起來這麼多耶~


前天去圖書館時,我稍微看了一下認知心理學學的是什麼,看起來它的理論要套用到使用者介面設計上還是有些距離2,不知道對使用者經驗有興趣的話應該要看哪些書?

最近在想我的研究方向,堅哥給的大方向是網頁文件自動分類,這個好像沒有選擇的餘地。至於要採用什麼技術就比較好通融,這個主題我覺得跟搜尋引擎 refine 搜尋結果的技術相當類似,是不是應該找陳教授討教一下? XD

看了兩篇論文比較 SVMk-NN 演算法的結果3, SVM 看起來是一個相當適合處理 Text Mining 的演算法,而且可以套用在 K-means 上(眼睛一亮),融合兩者的演算法有人稱為 KMSVM ,不過這應該不是大家公認的名稱。還有 Bayes’ theorem4 也可以參考看看,不知道為什麼國內研究很少使用這個演算法,它不是滿有名的嗎?

如果要作 KMSVM 的話,就跟熊的研究性質滿像的,都是為 K-means 加入新的元素,可是這個主題不是沒人作過,再重新作一次好像不太好?因此融合 Bayes’ theorem 和 K-means 可能是更好的選擇,只是不知道是不是真能融合起來就是 XD

斷詞直接用 Bigram 就可以有不錯的結果,根據我看見的一篇論文,對於 SVM 和 k-NN 來說,用 Bigram 斷詞甚至會有更精確的分群效果,真是奇怪 XD


  1. 此時我突然覺得前住戶真是 3M 的忠實愛用者啊… 

  2. 雖然有關聯,但是要融會貫通才能應用在 UX Design 上… 

  3. 其中一篇還多比較了 VSM , VSM 的效果又比 k-NN 更差一點。 

  4. Wikipedia 這頁直接拿文件分類作為範例耶~ 

google://K-means

因為從流量統計上看到,所以我也試了一下——

目前在 Google 台灣搜尋 K-means,我在第 30、44 個;如果限定繁體中文的話,我在第 15、25 個 XD

所以只要 PageRank 高,內容沒價值也是可以排名倒滿前面的耶 >///<

20070728 ~K-means

Screenshot - 2007_7_28 , 下午 08_10_53

今日進度:

  1. 修復特殊檔名導致無法讀取的問題,作法只是在 SQL 裡面將檔名用引號包起來…… 突然才想到這件事,平常寫 PHP 時明明很在意這個的,改用 OLE DB 就忘了。
  2. 用滑鼠可以拖曳圖形,這樣就能看見畫布以外的點了,不過圖片重繪同時也會變色,這是 feature ,不是 bug 喔! XD
  3. 本來我也想作滑鼠滾輪放大點的功能,但是 PictureBox 元件不支援滑鼠滾輪事件。
  4. 支援多維資料,因為多維圖形畫不出來,因此只取 x, y 兩點座標來畫。繪圖結果如上圖,群重疊在一起,有種朦朧美的感覺。但是如果太多維的話,可能結果就全部疊在一起 XD
  5. 儲存分群結果圖片的功能,同時解決了圖片會因為其他視窗遮蔽而消失的問題,不過缺點是現在看不見一個一個點上去的動畫效果了 XD

20070727 ~K-means

Screenshot - 2007_7_27 , 下午 10_49_06

醒來後的第一件事便是繼續改程式,首先我將原始資料改用二維陣列(2-dimensional Array)儲存,因為突然發現其實這個資料並不需要動用到動態陣列(ArrayList,為了 Array 特化過的 Linked List)。原來的方式有以下缺點:

  1. 必須以 Push 的方式一個一個將數值塞進 ArrayList ,感覺效率會差……
  2. ArrayList 不支援多維,所以必須於 ArrayList 裡面再放一維陣列。
  3. ArrayList 每個元素的型態為 object ,雖然我實際上存的是一個一維陣列,但只要放進 ArrayList 裡,它就會自動變成 object 型態。但讀出來時可沒有這麼自動,必須使用相當暴力的方式強制轉換型態回來。

因此如果使用 ArrayList 的話,我就會有一大堆的 Push 和強制轉換型態,所以我決定多花一個 SELECT 計算出資料列數,然後改用固定大小的二維陣列1,不但看起來開心,操作起來也較簡單。

接下來我才開始寫 K-means 演算法,一氣呵成的寫完一長串,然後 debug 得很難過… 因為一氣呵成的結果就是很難找出源頭…… orz 最後發現兩個滿囧的 bug:

  1. 隨機選取起始點的 function 發生怪事,必須在這裡寫個彈出對話方塊顯示目前取了哪一點,才能正確的取到三個隨機的座標。這個部份我在之後寫隨機產生顏色的 function 時,才知道問題出在哪裡——原來 C# 的 Random Class 必須先有個 instance ,才能開始產生正確的亂數。
  2. 另一個相當令我無言, K-means 演算法的原理有一個重要的步驟,是要反覆的取群中心點,直到群中心點不再變動,稱為收斂。而我的程式一執行便陷入無限迴圈,檢查到最後才發現原來我忘了更新群中心點,當然不管怎麼比對都不一樣。

接下來到了10點多時完成了隨便配色的功能, K-means 該有的東西大概都已經完成了!不過有點奇怪的就是… 聽說 K-means 應該會有標準答案,但我的程式每次計算都有不同結果耶~ 如果這是 bug 的話我想我會 de 得相當難過……


  1. C# 的陣列有多維陣列和不規則陣列(Jagged array)兩種用法,其中不規則陣列就像其他語言中的多維陣列作法,也就是陣列中的陣列(Array of arrays),因此每列長度可以不同;多維陣列則像是表格,每列長度都相同,我的資料都是平面座標,因此選用這種就好。 

 1