首页 > 程序开发 > 软件开发 > 其他 >

机器学习实战聚类之k均值聚类算法

2017-02-18

机器学习实战聚类之k均值聚类算法:这两天学习了非监督学习的聚类算法,k均值聚类和优化版二分k均值聚类,最后在地图上实现一个聚类小应用。

机器学习实战聚类之k均值聚类算法:这两天学习了非监督学习的聚类算法,k均值聚类和优化版二分k均值聚类,最后在地图上实现一个聚类小应用。

k均值聚类称为kmeans,是一种非监督学习的算法,下面写一下对监督学习和非监督学习的理解。

监督学习:分为训练集和测试集,每个数据有不同的特性和标签,标签分为连续型或者标称型,我们通过一定的方法对训练集进行训练,总结出数据潜在的规律,对数据进行预测,连续性数据的预测称为回归,标称型数据的预测称为分类,训练出机器用测试集进行误差分析。

非监督学习:这种学习方式没有标签属性,也没有训练集和测试集,我们利用聚类或其他方法找出数据的潜在规律。

聚类的通俗解释:

在美国总统大选中,每1%的投票可能决定最终总统的归属,每个总统竞选人必须把握住每一个人的投票,所以找到没有投自己的人比较关键,利用聚类算法我们可以找到全国不同区域所支持的不同人,比如A州支持候选人a比较多,B州支持候选人b比较多,于是候选人c就要去A和B州进行宣传拉票,让这帮人改投自己的票,这样自己获胜的机会会大一些,这个例子表示了聚类算法就是寻找每个聚堆的数据区,然后利用这些聚在一起的数据,分析这些数据的潜在规律。

接下来看聚类的效果:

step1:

读取数据:

#读取数据函数
def loadDataSet(filename):
    datamat = []
    feanum = len(open(filename).readline().strip().split('\t'))
    f = open(filename)
    for line in f.readlines():
        t = line.strip().split('\t')
        temp = map(float, t)
        datamat.append(temp)
    return datamat
step2:

数据可视化:可以看到数据大致分为4堆

step3:

此处的聚类算法的质心采取的为随机选取,我们先随机选取数据范围内的4个质心,然后聚类算法慢慢调整这些质心,直到质心所含数据不再改变为止。

聚类的距离函数和随机选取质心函数:

#距离函数
def getDistance(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2)))

#kmeans随机选取质心
def randCent(dataset, k):
    n = shape(dataset)[1]
    cent = mat(zeros((k, n)))
    for i in range(n):
        minnum = dataset[ : , i].min()
        rangenum = dataset[ : , i].max() - minnum
        cent[ : , i] = minnum + rangenum * random.rand(k, 1)
    return cent

step4:

kmeans聚类算法慢慢调整这些质心,直到质心所含数据不再改变为止。

调整质心的原理:

开始质心为随机点,每次数据全部循环结束后,质心会偏向离它最近的聚集区域,因为质心的重新定位是取聚类点的平均值,所以聚集区域对离它近的质点有极强的吸引力,经过多次循环后趋于稳定,直到直到质心所含数据不再改变为止。

#keanms算法
def kMeans(data, k, distype = getDistance, centtype = randCent):
    m = shape(data)[0]
    dataset = mat(data)
    cent = centtype(dataset, k)
    disarr = mat(zeros((m, 2)))
    centchange = True
    while centchange:
        centchange = False
        for i in range(m):
            mindis = inf
            minindex = 0
            for j in range(k):
                dis = distype(dataset[i, : ], cent[j])
                if dis < mindis:
                    mindis = dis
                    minindex = j
            if minindex != disarr[i, 0]:
                centchange = True
            disarr[i] = minindex, mindis   
        for temp in range(k):
            distancearr = dataset[nonzero(temp == disarr[ : , 0])[0]][0]
            cent[temp, :] = mean(distancearr, axis = 0)
    return cent, disarr

我们看下聚类的效果:

质心为:

我们看到,&#39;+&#39;号位置为每个聚类的质心,也就是中心位置(基本上是,有误差)。

但是这种算法有缺点为我们刚刚的数据过于简单,如果数据量过大或者维数过多我们没法可视化,这样我们无法确定k值。也有时会出现某个巧合点恰好使质点稳定,但是并不是我们的预期,所以我们进行改进,得到二分k均值聚类算法。

step5:

二分k均值聚类:

这个算法的原理:

二分k均值聚类算法衡量聚类的标准为SSE,即误差平方和,就是点和质心距离的平方和,这样距离质心远的点会被更加重视,因为误差会被放大。我们假定质心的最大数量,从第一个开始循环,我们先选一个全局的质心,然后我们对该质心所含数据点进行普通的k均值算法(将数据分成两个簇),现在为两个质心。接下来每次循环我们把每一个质心所含数据点进行普通的k均值算法(将数据分成两个簇),计算SSE,选择SSE最小的质心进行二分,添加一个质心,更新新的数据信息,依次下去,直到质心到达我们设定的最大数量。

#二分kmeans算法
def biKMeans(dataset, k, distype = getDistance):
    data = mat(dataset)
    m = shape(data)[0]
    disarr = mat(zeros((m, 2)))
    firstcent = mean(data, axis = 0).tolist()[0]
    cent = [firstcent]
    for j in range(m):
        disarr[j, 1] = distype(data[j], mat(cent[0])) ** 2
    while (len(cent) < k):
        bestdis = inf
        for i in range(len(cent)):
            temparr = data[nonzero(disarr[ : , 0].A == i)[0], :]        
            tempcent, tempdisarr = kMeans(temparr, 2, distype)
            splitdis = sum(tempdisarr[ : , 1])
            nosplitdis = sum(disarr[nonzero(disarr[ : , 0].A != i)[0], 1])
            if (splitdis + nosplitdis) < bestdis:
                bestsplit = i
                bestcent = tempcent 
                bestarr = tempdisarr.copy()
                bestdis = splitdis + nosplitdis
        bestarr[nonzero(bestarr[ : , 0].A == 1)[0], 0] = len(cent) 
        bestarr[nonzero(bestarr[ : , 0].A == 0)[0], 0] = bestsplit 
        cent[bestsplit] = bestcent[0].A.tolist()[0]
        cent.append(bestcent[1].A.tolist()[0])
        disarr[nonzero(disarr[ : , 0].A == bestsplit)[0], :] = bestarr
    print disarr        
    return cent, disarr        
我们看下二分k均值聚类算法的效果:(这个数据集在k均值聚类算法会出现很大误差)


我们接下来看一个在地图上的应用,里面matplotlib还有几个参数没弄懂,先借鉴一下书上,主要是看一下应用。

step6:

#地球距离函数
def distSLC(vecA, vecB):#Spherical Law of Cosines
    a = sin(vecA[0,1]*pi/180) * sin(vecB[0,1]*pi/180)
    b = cos(vecA[0,1]*pi/180) * cos(vecB[0,1]*pi/180) * \
                      cos(pi * (vecB[0,0]-vecA[0,0]) /180)
    return arccos(a + b)*6371.0 #pi is imported with numpy

#实例
def clusterClubs(numClust=5):
    datList = []
    for line in open(&#39;places.txt&#39;).readlines():
        lineArr = line.split(&#39;\t&#39;)
        datList.append([float(lineArr[4]), float(lineArr[3])])
    datMat = mat(datList)
    myCentroids, clustAssing = biKMeans(datMat, numClust, distype=distSLC)
    fig = plt.figure()
    rect=[0.1,0.1,0.8,0.8]
    scatterMarkers=[&#39;s&#39;, &#39;o&#39;, &#39;^&#39;, &#39;8&#39;, &#39;p&#39;, \
                    &#39;d&#39;, &#39;v&#39;, &#39;h&#39;, &#39;>&#39;, &#39;<&#39;]
    colortype = [&#39;blue&#39;, &#39;green&#39;, &#39;yellow&#39;, &#39;black&#39;, &#39;m&#39;]
    axprops = dict(xticks=[], yticks=[])
    ax0=fig.add_axes(rect, label=&#39;ax0&#39;, **axprops)
    imgP = plt.imread(&#39;Portland.png&#39;)
    ax0.imshow(imgP)
    ax1=fig.add_axes(rect, label=&#39;ax1&#39;, frameon=False)
    for i in range(numClust):
        ptsInCurrCluster = datMat[nonzero(clustAssing[:,0].A==i)[0],:]
        markerStyle = scatterMarkers[i % len(scatterMarkers)]
        ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=90,c = colortype[i%len(colortype)])
    myCentroids = array(myCentroids)
    ax1.scatter(myCentroids[:,0].flatten(), myCentroids[:,1].flatten(), marker=&#39;+&#39;, s=300, c = &#39;red&#39;)
    plt.show()
相关文章
最新文章
热点推荐