最近在看機器學習疗杉。想著這那的機器學習算法不就是一個個分類判別算法嗎？蚕礼！但它們大多沒能描述清楚內(nèi)在的結構烟具。就想著，從描述內(nèi)在結構的角度能不能搞出套算法來奠蹬。拿二維坐標上的點集分類練練手吧朝聋。
首先，看到一堆點集囤躁，人是怎么分類的呢玖翅？人看到的并不是各個點的坐標，而是它們之間的相互關系（遠近）割以。一個理想的分類算法結束的時候，內(nèi)部應該有一個結構對應這種關系应媚。
理想的劃分至少應該滿足這兩個條件吧：
- 群落之間的距離應該盡可能大严沥；
- 群落內(nèi)部的距離應該盡可能小中姜；
那么消玄，我們?nèi)绾味x這些個距離呢？「群落之間的距離」可以定義為：分屬不同群落的結點的最短距離丢胚。
而「群落內(nèi)部的距離」暫且先定義為：
我們先只考慮二分的情況翩瓜，一組劃分的得分可以這么定義：
得分越高，應該越接近人的直覺携龟。
但這個問題存在一個問題：當某個集合只有一個點時兔跌，根據(jù)d_in(S)的定義，其值為零峡蟋，則V()的值為∞坟桅。這里先略過吧
我們先隨機生成 10 個點測試一下：
| num. | x | y |
|---|---|---|
| 0 | 0.7250072248113352 | 0.6918674556852833 |
| 1 | 0.8848755951652081 | 0.46103430800321377 |
| 2 | 0.25686934593051614 | 0.3654236509121931 |
| 3 | 0.14727023823421648 | 0.6484006308621074 |
| 4 | 0.7204948792044977 | 0.17961644632138496 |
| 5 | 0.8945877982332864 | 0.4176191979853947 |
| 6 | 0.20413783912899097 | 0.3999350169560174 |
| 7 | 0.013751428920831588 | 0.2286960623435942 |
| 8 | 0.9593664284715295 | 0.5913802576287239 |
| 9 | 0.19519850392723048 | 0.7646584504057086 |
反正我一眼看上去覺得應該是從中間剖開：(0, 1, 4, 5, 8)一組华望，(2, 3, 6, 7, 9)一組。
然后我就把這 10 個點所有二分的情況算了一遍仅乓，MB! 前五結果如下：
排名 | 得分 | 分組1 | 分組2
-----|----------------------|------------------------
1 | 1.3655563661214813 | 2, 6 | 0, 1, 3, 4, 5, 7, 8, 9
2 | 1.041780761128343 | 1, 5 | 0, 2, 3, 4, 6, 7, 8, 9
3 | 0.9991390772630108 | 0, 1, 4, 5, 8 | 2, 3, 6, 7, 9
4 | 0.8654202725096181 | 3, 9 | 0, 1, 2, 4, 5, 6, 7, 8
5 | 0.6481575237761811 | 1, 5, 8 | 0, 2, 3, 4, 6, 7, 9
你知道我的內(nèi)心有多么崩潰嗎赖舟？！？溟埂宾抓！
然后，我又試了下用「各點到質(zhì)心的距離之和」來替代「群落內(nèi)部的距離」豫喧。結果一個球樣
我什么也不想說了……
我怎么會告訴大家之前「想用最小生成樹來組織石洗，切掉最遠的邊」，結果失敗了這種事情嘿棘。
我怎么會告訴大家我連「羅列所有的二分可能」都想了好久劲腿，還復習了好一會排列組合這種事情。
我怎么會告訴大家 Ruby 語法忘得干干鸟妙，各種百度這種事情焦人。
……
手好生啊~~
