Klustering

目前是暑假，而我剛從大學畢業，還沒到研究所辦理入學，研究工作卻已經開始了。最近的 meeting 主要是聽學長報告，我們雖然有一位唯一僅有的學姐，我卻未曾有幸聽過她的報告。

因為暫時還算悠閒，在家沒事很無聊，於是 7/25 決定開始學習 C# 。我也考慮過 Java ，但是我對於 Java Virtual Machine 的印象很差，而且 C# 的 IDE 看起來很方便，就這樣有點隨便的決定了我要學的語言。

第一個程式先從基本的 K-means 演算法寫起（因為我指導教授的研究大致上都關於 K-means ，我想先寫一個來以後一定會用到 XD）。現在還沒有學生身份，不能到學校圖書館借書，只能靠著網路資料學，起初不熟悉時什麼都得查，進度好慢。到了 7/27 才完成基本的讀取 CSV 資料、分群。程式寫完便又開始無聊，就繼續作外觀方面的功能，例如讓點可以放大縮小、改使用者介面之類的。 C# 內建許多控制元件，而且不需要特別設定就會自動套用 XP 風格外觀，調整介面方面做得滿愉快的。

讓我印象比較深刻的，是主要資料的儲存型態我改了兩次，兩次都牽一髮而動全身，要改寫好多地方。 C# 的多維陣列有兩種作法：矩形陣列（Rectangular array）和不規則陣列（Jagged array），其中不規則陣列就像其他語言中的多維陣列作法，也就是陣列中的陣列（Array of arrays），因此每列長度可以不同；矩形陣列則像是表格，每列長度都相同。我的資料是一串座標，座標數量、維度不固定（但是同一份資料中座標維度必相同），起初我想這應該算是「動態陣列」吧！就用了 ArrayList（並不是前面提到的任何一種 XD），後來才發現我不需要動態，又改回矩形陣列，矩形陣列每列長度相同，跟我的資料剛好符合。最後一次則是改成不規則陣列，因為矩形陣列要取出其中一列很麻煩…… 這樣改了一圈感覺滿空虛的，都沒有用到 C# 的特殊功能 orz

7/30 沒事作，便試圖提昇 K-means 效能，第一個想法是最佳化找最近點的演算法，因為 K-means 中不斷的在找最近點。稍微翻了一點資料後，我覺得 kd-tree 看起來好像不錯，而這就是一段悲劇的開始…… kd-tree 其實是一種資料結構，為了將我的資料轉換為這種格式，我花了兩天才完成，主要的困難點在於他必須依照資料的各個軸排序，這不是用 Array.Sort() 就能辦到的事情，而我又不想使用 Wikipedia 上講的 Selection sort（時間複雜度很高耶！），最後把資料型態改成不規則陣列才作出來（這也是最後一次改資料型態的主因），這個部份完成後其他部份便很快也跟著完成了。

不過花了兩天研究 kd-tree 其實也還不算什麼，難過的是我寫完後才發現我不知道這要怎麼應用到 K-means 上…… XD