最近在看机器学习。想着这那的机器学习算法不就是一个个分类判别算法吗？！但它们大多没能描述清楚内在的结构。就想着，从描述内在结构的角度能不能搞出套算法来。拿二维坐标上的点集分类练练手吧。
首先，看到一堆点集，人是怎么分类的呢？人看到的并不是各个点的坐标，而是它们之间的相互关系（远近）。一个理想的分类算法结束的时候，内部应该有一个结构对应这种关系。
理想的划分至少应该满足这两个条件吧：
- 群落之间的距离应该尽可能大；
- 群落内部的距离应该尽可能小；
那么，我们如何定义这些个距离呢？「群落之间的距离」可以定义为：分属不同群落的结点的最短距离。
而「群落内部的距离」暂且先定义为：
我们先只考虑二分的情况，一组划分的得分可以这么定义：
得分越高，应该越接近人的直觉。
但这个问题存在一个问题：当某个集合只有一个点时，根据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
你知道我的内心有多么崩溃吗？！！！
然后，我又试了下用「各点到质心的距离之和」来替代「群落内部的距离」。结果一个球样
我什么也不想说了……
我怎么会告诉大家之前「想用最小生成树来组织，切掉最远的边」，结果失败了这种事情。
我怎么会告诉大家我连「罗列所有的二分可能」都想了好久，还复习了好一会排列组合这种事情。
我怎么会告诉大家 Ruby 语法忘得干干，各种百度这种事情。
……
手好生啊~~
网友评论