上一篇博客里提到了一个简单的聚类算法kmeans。这里是用C语言写的一个命令行的版本,它似乎可以运行,也能产生结果,不过我也没有仔细验证过是否正确 :-)    这里是在GitHub上托管的源代码。

使用方法以Linux环境为例,首先make一下,生成可执行文件kmeans

然后 ./kmeans  input.csv  ouput.csv  3   random  means

input.csv和ouput.csv是输入数据和输出数据文件,CSV文件不神秘,用文本编辑器打开看就是几行点坐标数据。
3是指定要把点集分成几个类。
中心点Center计算有两种方式:1.mean(均值); 2.median(中位数)
初始化方法有以下两种方式:1.random partition(随机初始化); 2.k-means++(Knuth的弟子想出的方法)

其实kmeans原理很简单,但是实现起来还是比较繁琐的,特别是用C语言的时候很多处理过程都要自己写。

一开始我对kmeans算法的复杂度严重估计不足,以为两三百行代码可以搞定,于是打开电脑就开始写,后来越写越复杂,代码行数也越来越多,不得分成多个文件,但定义的一些全局变量就不好用了,于是全部塞进kmeans.h头文件。更坑爹的是程序要求先执行初始化后在调用后续的函数处理,我是上星期先写好了random partition和mean聚类法,然后过了几天又来写kmeans++的,当时也没有考虑周全,直接导致了用两种不同的数据结构保存产生的结果,使得后续的函数无法处理kmeans++的结果,于是创造出了saved这么一个奇葩的数据结构专门转换数据,总之代码是写的一团糟。

所以,写这篇博客的目的还是总结一下失败的经验教训,平时自己写程序习惯打开电脑就写,事先不做好设计,一旦代码量变多或者是遇到复杂一点的算法时总会出现各种各样的问题。

想到了Frederick Brooks大牛在《The Mythical Man-Month(人月神话)》中提到的:

三分之一的时间  Planning
六分之一的时间  Coding
四分之一的时间  Component test and early system test
四分之一的时间  System test,all components in hand

可见,先驱给我们的忠告是花大部分的时间做好整体的设计,设计好了再动手coding。像我写kmeans的时候根本就没有仔细的考虑过算法流程就动手coding,以至于后来发现了BUG想修改时已经有“牵一发动全身”的感觉了,就好像《The Mythical Man-Month》在书开头第一段就描绘的情景那样:

No scene from prehistory is quite so vivid as that of the mortal struggles of great beasts in the tar pits.In the mind’s eye one sees dinosaurs,mammoths,and sabertoothed tigers struggling against the grip of the tar.The fiercer the struggle,the more entagling the tar,and no beast is so strong or so skillful but that he ultimately sinks.

19,552 views
Home

17 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.