php机器学习算法之kmeans的一个简单的例子

时间:2017-12-15 15:10:14 阅读:508次
php机器学习算法之kmeans

聚类算法有很多种(几十种),K-Means是聚类算法中的最常用的一种,算法最大的特点是简单,好理解,运算速度快,但是只能应用于连续型的数据,并且一定要在聚类前需要手工指定要分成几类。


下面,我们描述一下K-means算法的过程,为了尽量不用数学符号,所以描述的不是很严谨,大概就是这个意思,“物以类聚、人以群分”:


1.首先输入k的值,即我们希望将数据集经过聚类得到k个分组。

2.从数据集中随机选择k个数据点作为初始大哥(质心,Centroid)

3.对集合中每一个小弟,计算与每一个大哥的距离(距离的含义后面会讲),离哪个大哥距离近,就跟定哪个大哥。

4.这时每一个大哥手下都聚集了一票小弟,这时候召开人民代表大会,每一群选出新的大哥(其实是通过算法选出新的质心)。

5.如果新大哥和老大哥之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大,趋于稳定,或者说收敛),可以认为我们进行的聚类已经达到期望的结果,算法终止。

6.如果新大哥和老大哥距离变化很大,需要迭代3~5步骤。

<?php
/*
A1(2, 10)  A2(2, 5) A3(8, 4)  A4(5, 8)  A5(7, 5) A6(6, 4)  A7(1, 2)  A8(4, 9)
*/
$samples = [
	['2', '10'],
	['2', '5'],
	['8', '4'],
	['5', '8'],
	['7', '5'],
	['6', '4'],
	['1', '2'],
	['4', '9'],
];
require_once __DIR__ . '/vendor/autoload.php';
use Phpml\Clustering\KMeans;

$kmeans = new KMeans(3);
$result = $kmeans->cluster($samples);
print_r($result);

/*
Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [0] => 2
                    [1] => 10
                )

            [1] => Array
                (
                    [0] => 5
                    [1] => 8
                )

            [2] => Array
                (
                    [0] => 4
                    [1] => 9
                )

        )

    [1] => Array
        (
            [0] => Array
                (
                    [0] => 2
                    [1] => 5
                )

            [1] => Array
                (
                    [0] => 1
                    [1] => 2
                )

        )

    [2] => Array
        (
            [0] => Array
                (
                    [0] => 8
                    [1] => 4
                )

            [1] => Array
                (
                    [0] => 7
                    [1] => 5
                )

            [2] => Array
                (
                    [0] => 6
                    [1] => 4
                )

        )

)
*/


图示

image.png

运行结果图示

image.png


其中,实验中出现了同一组数据,多次运行结果不一致的问题。


K-Means的细节问题

K值怎么定?我怎么知道应该几类?

答:这个真的没有确定的做法,分几类主要取决于个人的经验与感觉,通常的做法是多尝试几个K值,看分成几类的结果更好解释,更符合分析目的等。或者可以把各种K值算出的SSE做比较,取最小的SSE的K值。

初始的K个质心怎么选?

答:最常用的方法是随机选,初始质心的选取对最终聚类结果有影响,因此算法一定要多执行几次,哪个结果更reasonable,就用哪个结果。 当然也有一些优化的方法,第一种是选择彼此距离最远的点,具体来说就是先选第一个点,然后选离第一个点最远的当第二个点,然后选第三个点,第三个点到第一、第二两点的距离之和最小,以此类推。第二种是先根据其他聚类算法(如层次聚类)得到聚类结果,从结果中每个分类选一个点。

K-Means会不会陷入一直选质心的过程,永远停不下来?

答:不会,有数学证明K-Means一定会收敛,大致思路是利用SSE的概念(也就是误差平方和),即每个点到自身所归属质心的距离的平方和,这个平方和是一个函数,然后能够证明这个函数是可以最终收敛的函数。

扫描二维码关注程序员爱笔记,接收更多资讯

评论

快速评论