精华内容
下载资源
问答
  • 聚类算法之k-均值,k-中心点

    千次阅读 2018-10-11 19:23:19
    k-means和k-中心点算法是属于简单的迭代型聚类算法,它将一个给定的数据集分为用户指定的k个聚簇。实现和运行该算法都很简单,它的速度比较快,同时又易于修改,所以在实际应用中使用非常广泛。 K-means算法 k-...

    k-means和k-中心点算法是属于简单的迭代型聚类算法,它将一个给定的数据集分为用户指定的k个聚簇。实现和运行该算法都很简单,它的速度比较快,同时又易于修改,所以在实际应用中使用非常广泛。

    K-means算法

    k-means算法是硬聚类算法,是典型的基于原型的目标函数聚类算法的代表。它是数据点到原型的某种距离作为相似性的评价指标,即两个对象的距离越接近,其相似度就越大。算法采用误差平方和准侧函数作为聚类准则函数。

    算法实现

        输入:

           k:簇的数目

           D:包含n个对象的数据集

       输出:k个簇的集合

       方法:

        (1):从D中任意选择k个对象作为初始簇中心

        (2):repeat

        (3):    根据簇中的对象的均值,将每个对象分配到最相似的簇

        (4):    更新簇均值,即重新计算每个簇中对象的均值

        (5):util不再发生变化

    k-means方法是不保证收敛于全局最优解,并且它通常终止于一个局部最优解。结果可能依赖于初始簇中心的随机选取。

    k-means算法的优点:

    1:是聚类算法中的一种经典,快速,简单的算法

    2:对处理大数据集,该算法保持可伸缩性和可扩展性

    3:当簇接近高斯分布时,结果较好

    k-means算法的缺点:

    1:在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用,比如说标量数据

    2:在 K-means 算法中 K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。

    3:在 K-means 算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果。

    4:该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的。

    5:若簇中含有异常点,将导致均值偏离严重(即:对噪声和孤立点数据敏感)。

    6:不适用于发现非凸形状的簇或者大小差别很大的簇。

    k-means算法的改进

    1、很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。通过类的自动合并和分裂,得到较为合理的类型数目 K,例如 ISODATA 算法。

    2、针对上述3,可选用二分K-均值聚类;或者多设置一些不同的初值,对比最后的运算结果,一直到结果趋于稳定结束。

    3、针对上述第5点,改成求点的中位数,这种聚类方式即K-Mediods聚类(K中值)

    k-means算法的实现

    def readfile(filename):
        lines=[line for line in open(filename)]
    
        #第一行是列标题
        colnames=lines[0].strip().split('\t')[1:]
        rownames=[]
        data=[]
        for line in lines[1:]:
            p=line.strip().split('\t')
            #每一行的第一列是行名
            rownames.append(p[0])
            #剩余部分就是行对应的数据
            onerow = [float(x) for x in p[1:]]
            data.append(onerow)
        return rownames,colnames,data
    
    #计算两行的皮尔逊相似度
    def pearson(v1,v2):
        #简单求和
        sum1=sum(v1)
        sum2=sum(v2)
    
        #求平方和
        sum1Sq=sum([pow(v,2) for v in v1])
        sum2Sq=sum([pow(v,2) for v in v2])
    
        #求乘积之和
        Psum=sum([v1[i]*v2[i] for i in range(len(v1))])
    
        #计算r
        num=Psum-(sum1*sum2/len(v1))
        den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))
        if den == 0:
            return 0
        return 1.0-num/den
    
    #每个点表示一行,每个聚类点表示一类。rows数据集,distance距离计算方法,k聚类的数目
    def kcluster(rows,distance=pearson,k=4):
        #确定每个点的特征的最小值和最大值--->每一列的最大值和最小值
        ranges = [(min([row[i] for row in rows]), max([row[i] for row in rows])) for i in range(len(rows[0]))]
    
        #为每一列生成一个随机聚类点
        clusters = [[random.random() * (ranges[i][1] - ranges[i][0]) + ranges[i][0]
                     for i in range(len(rows[0]))] for j in range(k)]
    
        lastmatches = None
        for t in range(100): #默认迭代一百次
            print("迭代 %d" % t)
            # 生成k个空数组,用于存储k个聚类点包含的成员
            bestmatches = [[] for i in range(k)]
    
            #在每一行中寻找距离最近的点
            for j in range(len(rows)):
                row = rows[j]
                bestmatchIndex = 0
                for i in range(k):
                    d = distance(clusters[i], row)
                    if d < distance(clusters[bestmatchIndex], row):
                        bestmatchIndex = i
                bestmatches[bestmatchIndex].append(j) #每个聚类点记录它包含的成员
    
            #如果结果与上次一样,则整个过程结束
            if bestmatches == lastmatches:
                break
            lastmatches = bestmatches
    
            #把中心点移到成员的平均位置处
            for i in range(k):
                avgs = [0.0]*len(rows[0])
                if len(bestmatches[i]) > 0:
                    for rowid in bestmatches[i]:
                        for m in range(len(rows[rowid])):
                            avgs[m] += rows[rowid][m]
                    for j in range(len(avgs)):
                        avgs[j] /= len(bestmatches[i])
                    clusters[i] = avgs
        return bestmatches
    
    if __name__ == '__main__':
        blognames,words,data = readfile('blogdata.txt')
        kclust = kcluster(data,k=4)
        print([blognames[r] for r in kclust[0]])

    k-中心点算法

    k-means算法对离群点敏感,因为这种对象远离大多数数据,因此分配到一个簇时,他们可能严重地扭曲簇的均值。我们可以不采用簇中对象的均值作为参考点,而是挑选实际对象来代表簇。k-中心点使用了一个绝对误差标准。典型的算法为PAM

    PAM实现过程

        输入:

         k:结果簇的个数

         D:包含n个对象的数据集合

        输出:k个簇的集合

        方法:

            1:从D中随即选择k个对象作为初始的代表对象或种子

            2:repeat

            3:    将每个剩余的对象分配到最近的代表对象所代表的簇

            4:    随即地算则一个非代表对象O

            5:    计算用O代替代表对象的总代价S

            6:    if S<0,then O代替代表对象,形成新的k个代表对象的集合

            7:util不再发生变化。

    PAM这样的典型k-中心点算法在小型数据集上运行良好,但是不能很好地用于大数据集,为了处理大数据集,可以使用一种称为CLARA(Clustering LARge Applications,大型应用聚类)的基于抽样的方法。

    PAM(partitioning around medoid,围绕中心点的划分)是具有代表性的k-medoids算法。
    它最初随机选择k个对象作为中心点,该算法反复的用非代表对象(非中心点)代替代表对象,试图找出更好的中心点,以改进聚类的质量。 
    例子: 
    空间有5点{A,B,C,D,E}, 各点之间距离关系如表,根据pam算法进行聚类分析。

    样本点ABCDE
    A01223
    B10243
    C22015
    D24103
    E33530

    假设分为2类,以A,B为中心点,初始聚类为{A,C,D}和{B,E}。接下来进行交换(以非代表对象代替代表对象),我们需要计算TCac、TCad、TCae、TCbc、TCbd、TCbe。 
    TCij表示用非中心点j替换中心点i所产生的代价。 
    计算TCAC:当A被C替换后,设一指针p遍历所有对象,判断他们是否聚到别的类里。

    1:先看A是否变化:C成为中心点后,A离B比A离C近,故A被划分到B簇里。所产生的代价为d(A,B)-d(A,A)=1(d(i,j)表示i划分到中心点j的距离;差值表示属于新的中心点-属于旧的中心点产生的代价。)
    2:看B是否变化:C成为中心点后,B当然离自己是最近的,不变
    3:看C是否变化:C成为中心点后,C划分到C簇里,代价为d(C,C)-d(C,A)=-2
    4:看D是否变化:C成为中心点后,D离C最近,故划分到C里,代价为d(D,C)-d(D,A)=-1;
    5:看E是否变化:C成为中心点后,E离B最近,为0 
        TCac就等于上述的代价之和,为1+0-2-1+0=-2。 
        同理需要计算TCAD=-2、TCAE=-1、TCBC=-2、TCBD=-2、TCBE=-2 
        然后选取代价最小的替换,这里有多个选择,随便选择一个就行。选C的话,新的簇为{C,D}和{A,B,E}。新的簇中心为C,B,继续迭代计算直到收敛。
    为了判定一个非代表对象orandom是否是当前一个代表对象oi的好的替代,对于每一个非中心点p,需要考虑下面4中情况:

    第一种情况:p当前隶属于代表对象oj(A类中心点),如果oj被orandom所代替作为代表对象,并且p离其他代表对象oi(B类的中心点)最近,则p重新分配给oi。(i!=j)

    第二种情况:p当前隶属于代表对象oj(A类中心点),如果oj被orandom所代替作为代表对象,并且p离orandom(新的中心点)最近,则p重新分配给orandom。(i!=j)

    第三种情况:p当前隶属于代表对象oi(B类中心点),如果oj被orandom所代替作为代表对象,并且p仍然离oi最近,则p不发生变化。(i!=j)

    第四种情况:p当前隶属于代表对象oi(B类中心点),如果oj被orandom所代替作为代表对象,并且p离orandom最近,则p重新分配给orandom。(i!=j)

    参考文献:

    数据挖掘概念与技术

    k-means算法的优缺点

    https://blog.csdn.net/shuaishuai3409/article/details/50016013

    展开全文
  • K-means和K-中心点算法

    万次阅读 2019-01-05 15:15:53
    K-means和K-中心点算法 k-means算法 在聚类的算法中这个算法比较常用,首先是将数据集中的每一条数据想象称为超空间中的一个点,因为通常数据不只是只有三个特征属性,当超过三个特征属性之后就难以在坐标空间中进行...

    K-means和K-中心点算法

    k-means算法

    在聚类的算法中这个算法比较常用,首先是将数据集中的每一条数据想象称为超空间中的一个点,因为通常数据不只是只有三个特征属性,当超过三个特征属性之后就难以在坐标空间中进行表示,所以这里统一的称为超空间

    先确立一些比较重要的思想:

    距离的概念,如果每一个点都有坐标,不管是5维还是6维,反正存在j个属性,每个属性的值进行归一化处理之后得到一个比较干净的数据,关于数据的前期处理不是这里的重点,所以这里默认的认为所有数据已经清洗好了

    使用欧式距离作为这里判定两个点之间的距离度量,放在超空间中无非就是两个点做差后进行距离化

    度量和算法逻辑分离:

    算法逻辑是一种执行方式,算法是一种方法,这种方法并不是说必须要用谁谁谁作为损失函数,比如决策树中的CART算法是用Gini系数作为度量,采用的是二叉树的方式,但是这里并不代表只能用Gini系数作为特征提取的度量,我们完全可以使用信息熵,只是使用信息熵如果效果比Gini效果还要好,那为啥一定要用Gini系数呢?

    度量只是一种衡量方式,说白了就是我们自己构造的比较方式而已,我们认为这么计算能够区分这两个点是否相近,但是并不代表说这是唯一评判标准

    使用不同的度量可能会带来意外的收获,如果使用体重作为度量我们能区分胖瘦,如果使用身高进行度量,我们能区分高矮,聚类中经常采用的是欧式距离进行度量两个对象(数据点)是否相似,那么难道只有欧式距离这种度量么?

    不逼逼了,直接说这个算法

    1 随机的在数据集中进行选择k个点作为种子点,记作{A,B,C,D,E…}

    注意这里k是人为设定的,这里的k代表我要把这个数据集分成k类,聚类本身就是无监督的学习算法,事先我们并不知道这一堆数据到底应该有几个类,因此我们这里随机的给一个k很可能就是一个错误的,比如本来别人有3个类,你给了一个10让别人分,别人怎么分?

    因为是无监督学习,所以没有办法,这里只能先给一个k,用测试集看看效果,在给k+i个,用测试集看看效果,再用k+2i个看看效果,统计每次k的变化和测试的准确率之间的关系,画出一个图像,多做几次就看到趋势了,下面就是人为的根据趋势去试,找出最合适的k值,先假设我们运气很好,第一次就给对了k

    2 以种子点为均值点,将空间中其他的点分别与这些种子点做距离计算,并归簇

    比如一个点p,在与A点作计算后得到距离d1,与B点作距离计算得到距离d2,对所有的点都做完计算得到一组距离值,选出最小的那对,如果d1是最小的,那么就把p这个点归到A簇中,空间中除了种子点之外的所有点都这么来一遍,那么就能够找到每一个种子点所具有的簇.

    这里同样会有一些问题,比如最小的距离如果不唯一呢?换句话说如果正好有一个p距离其中的某几个种子点的距离都相同,而且都是最小值,这种可能也是存在的,怎么办?此时其实大可不必担心,无所谓的,随便给一个最近距离的簇就行了,因为这个算法在后面的均值点移动的过程中会打破之中相等的情况

    当然也有人认为假如本身已经完全分好了,比如只有两个簇,连个簇的均值点连线的中垂面上的所有点不都是距离这两个均值点距离相等么.对,确实会有这种情况,那么这些点本身就很难分类到任何一个簇,这些点就是临界点,难以区分的点,你无法说它一定属于左边的簇还是右边的簇,这里的做法在于看看哪个簇所具有的点数量多分给谁,这是一种比较贪心的做法,就像一个中等身材的人,你一定要区分是高大还是矮小的话,那为了不得罪人我就说分到高大里面

    有人继续较真,如果两边簇的个数相等咋办?好吧,这种都被你遇到也是牛皮,那么就随机分

    3 每一个种子点都对应有簇之后,下面进行针对每个簇进行取均值动作

    一堆点取均值其实难度不大,这一堆点取了均值之后的均值点并不一定是在给的数据集中的某个点上,这一点要明确,也许这个均值点上就没有对应的数据,但是这并不影响

    4 以均值点为新的种子点进行重新划分

    因为第一次选的是随机的种子点,那么归簇之后计算的新均值点虽然不能说一定比随机的那个点好,但是这至少是有个均值作为依据,这里进行重新归簇之后会得到一个新的划分,那么关键来了

    5 比较均值点与原种子点不同划分造成的数据集中所有的误差平方和

    E = ∑ i = 1 k ∑ p ∈ C i d i s t ( p , c i ) 2 E=\sum_{i=1}^k{}\sum_{p\in C_i}dist(p,c_i)^2 E=i=1kpCidist(p,ci)2

    上式为数据集中所有对象的误差的平方和,听起来就绕口,这个公式需要从右边开始往左读

    dist(x,y)表示点x到点y的距离,这里的ci就是种子点,如果变化为均值后,ci表示均值点,距离之后再平方,Ci表示第i个簇,对应我们前面的时候A的代表簇,或者B的代表簇

    第一个求和的意思就是将簇里面的非ci点分别对ci进行距离运算,之后再平方,所有的平方再加起来

    前面的求和变化的是i,从i=1到k,意思就是把所有的簇都运算加起来

    加起来之后就是一个定值,此时整个值里面包含了所有点分别对自己簇的中心点的距离平方和,整个值为E,我们认为这个值能够度量数据的在各自的簇里面的聚程度

    思考一下:

    现在有一个点群,如果这个点非常集中,所有点都一个挨着一个,紧紧包围中心点的,那么这些点到中心点的距离就会很小,平方后还是很小,加起来之后还是小,那么对应的E值就会非常小,E就表示着我们这个点群中其他散点相对于中心的聚集程度,越是聚集越是表示这些点相似性就越高,就意味着这些数据对象就越相似

    那么现在我的中心点找错了,找了个最边缘的点,那么其余的点到这个边缘距离点的平方和会变大,导致E变大,这就意味着我们的中心点选的有问题

    这里不同,本身的随机种子构建的点群划分是一种划分状态,可以计算出E值,当我们计算出簇内所有点的均值后,构建一个新的种子点,对这个点再次构建一个点群划分,新的划分会存在一个新的E值,那么如果新的E值小于原来的E值,那就意味着新的点群划分使得各个簇包含的点更加聚集,我们就有理由认为新的划分更合理,于是就使用均值当做新的种子点

    6 重复2-5,直到新的均值无法再使得E更小为止

    这样就能让本身随机的选点最后一次次迭代成为最优的划分

    收尾工作:

    上面的计算确实能够使得E成为最小,每个簇最紧凑,但是很容易掉进局部最优解,比如数据点群中局部存在两个聚集团,但是实际上这两个团是一个类的,正好随机的点随到里面去了,把这两个团归为两个类,或者出现其他的局部最优解.这种情况确实存在,算法本身的随机选择种子点就已经决定了这个是算法本身没法避免的,那么我们后续可以进行多次计算来弥补这个问题,第一次运气不好正好随机到局部最优解去了,第二次难道还是这么倒霉,多来几次,次次都中奖那就是人品问题了

    算法本身就是人为的设置k值,所以k也会存在好几次尝试

    K-中心点算法

    该算法其实跟k-means非常接近,是用来填补k-means中的离群点干扰问题,这个后面再解释,先看算法逻辑

    1 选择k个随机的点作为初始的种子点

    这个和k-means没啥区别

    2 以种子点为中心点,对空间中的其他点根据距离来划分

    这一步和k-means一样

    3 针对每个簇中,随机在选一个点为新的种子点构建新的划分

    这一步区别就来了,这里不再是对簇中的点求均值,因为均值点大多数情况下是没有实际数据点对应的,这里采用的是在簇中随机的点作为新种子,这个点一定是确实存在并且确实有数据对应的,可以不恰当的比喻为实例.现在以新的种子点划分数据点群

    4 比较前后两次的绝对误差之和进行判断新划分与原划分的优劣

    这里的判定依据是
    E = ∑ i = 1 k ∑ p ∈ C i d i s t ( p , c i ) E=\sum_{i=1}^k{}\sum_{p\in C_i}dist(p,c_i) E=i=1kpCidist(p,ci)
    实际公式中的ci用的是oi来替换的,但是从意义上来说oi就是ci,只是k-means中的ci表示均值点,oi表示中心点,从算法逻辑上来说不都是把它作为中心去划分么,没啥两样,所以这里直接用ci了,注意到跟k-means不同的是这里没有平方了,因为是距离,这里被称作绝对误差之和,E依然能够描述簇的聚集程度

    思考:

    前后两次都是随机的,第一次是随机选种子,第二次是在已经划分好的簇里面再随机选种子,再划分,为了评价两次不同的划分谁更合理,这里引入了E进行度量,根据前面的分析已经知道E值实际就是表现了点群划分后的聚合程度,如果新随机划分的E值更小,我们就有理由认为新随机的划分更合理,因此将中心点移动到新随机点

    5 重复2-4,直到再没有能够使得E值更小的划分为止

    收尾工程:

    和k-means一样,也是不可避免局部最优解和k值的人为给定一样,只能多计算几次

    思考:

    两个算法都是用了距离来度量,而且都是针对所有的点进行计算的,那么一定会有离群点也被计算进去了,从E中的dist(p,ci)就已经包含了离群点,所以两个算法都是没有办法杜绝利群点的,只能尽量减少利群点的影响

    区别

    两个重要的不同

    1 k-中心点中的dist(p,ci)没有平方

    2 k-中心点使用的是真实存在的数据点作为中心来划分

    先说2的好处,以真实存在的数据点作为中心点这比使用均值点作为中心点计算出来的dist通常要大一些.均值中心点是更加对称的结构,均值点并不一定在数据点上,但是这种对称结构更喜欢的是数据均匀分布,如果存在利群点,那么利群点就会干扰均值计算,导致均值偏离实际

    使用簇中的随机来作为中心点,好处在于利群点毕竟是少数,随到的可能性很低,如果真的随到了,那么离群点计算的dist会整体增加,这将导致E变大,那么在步骤4的时候就不会对这个点进行更新,这个离群点不会参与中心点的选择,所以从中心位置选择上就没有离群点的干扰

    再看1,为什么k-means是平方,而k-中心是1次方

    dist都是指距离,那么这个距离谁能保证一定大于1,难道就不能是0.1么,数值越小说明距离中心点越近,如果大量的点的数值都很小则平方后会更小,反而离群点通常都比较大,平方后会被放大,如果某个划分中,中心点距离离群点近了,那么就不会出现大量的短距离数值,虽然距离最大的离群点贡献的E值小了,而大量的聚集点贡献的E值被放大的很明显,从而导致整体E值没有想象中下降的多,因此整个点作为中心点就不适合.

    高指数能够放大离群点对E值的贡献,在k-means里面离群点在中心点选择的时候就干扰过一次,已经造成了均值点比实际中心点偏移,此时对离群点贡献度进行放大,多少有点弥补的意味

    那么k-中心点选择1而不是开根号,为啥不是进行和k-means同样采用平方呢?

    在k-中心点算法中,中心点的选择不受到离群点的影响,但是dist计算则一定会受到离群点的影响,如果指数小于1,比如1/2,就是开根号,那么0.04的距离开根号后就会成为0.2,本身距离短的聚集点结果贡献的E值被放大了,而离群的点本身比较大,开个根号实际上进行了缩小(100开跟也就10),这样计算的dist并不合理.如果本身划分是非常好的,簇中的点非常集中,只有离群点的距离大于1,或者就是1,那么开根号反而使得E值变大,会错误的认为这是个不良的划分

    不选择高指数,高指数确实能够使得离群点的贡献度放大,但是这里也没有这个必要了,因为离群点不能干扰中心的选择,再去放大离群贡献的意义并不是很大,反而增加计算开销

    从来没有人说过dist只能是平方,你变化成10次方都行,这只是一个度量,与算法的逻辑没有任何关系,你甚至可以不用距离作为度量,都行,没有谁规定k-means一定就是平方,k-中心点一定就是一次项

    在实际的工程中,如果用的是k-means,你发现使用一次项在你的这个工程中效果最好,那干嘛非要用平方项

    当实验数据与理论冲突的时候,我们确定数据是真实有效的情况下,那么我们就应该考虑是不是理论不够完善了

    展开全文
  • 一.原理 K均值聚类 最常见的划分方法是K均值聚类分析。... (3) 重新计算每类中的点到该类中心点距离的平均值(也就说,得到长度为p的均值向量,这里的p是变量的个数); (4) 分配每个数据到它最近的中心点;...

    一.原理

     

    K均值聚类
          最常见的划分方法是K均值聚类分析。从概念上讲, K均值算法如下:
           (1) 选择K个中心点(随机选择K行);
           (2) 把每个数据点分配到离它最近的中心点;
           (3) 重新计算每类中的点到该类中心点距离的平均值(也就说,得到长度为p的均值向量,这里的p是变量的个数);
           (4) 分配每个数据到它最近的中心点;
           (5) 重复步骤(3)和步骤(4)直到所有的观测值不再被分配或是达到最大的迭代次数(R把10次作为默认迭代次数)。

           这种算法是把观测值分成k组并使得观测值到其指定的聚类中心的平方的总和为最小。也就是说,在步骤(2)和步骤(4)中,每个观测值被分配到使下式得到最小值的那一类中:

     

            表示第i个观测值中第j个变量的值。表示第k个类中第j个变量的均值,其中p是变量的个数。

     

    PAM聚类算法:

           因为K均值聚类方法是基于均值的,所以它对异常值是敏感的。一个更稳健的方法是围绕中心点的划分(PAM)。与其用质心(变量均值向量)表示类,不如用一个最有代表性的观测值来表示(称为中心点)。 K均值聚类一般使用欧几里得距离,而PAM可以使用任意的距离来计算。因此, PAM可以容纳混合数据类型,并且不仅限于连续变量。

           PAM算法如下:
           (1) 随机选择K个观测值(每个都称为中心点);
           (2) 计算观测值到各个中心的距离/相异性;
           (3) 把每个观测值分配到最近的中心点;
           (4) 计算每个中心点到每个观测值的距离的总和(总成本);
           (5) 选择一个该类中不是中心的点,并和中心点互换;
           (6) 重新把每个点分配到距它最近的中心点;
           (7) 再次计算总成本;
           (8) 如果总成本比步骤(4)计算的总成本少,把新的点作为中心点;
           (9) 重复步骤(5)~(8)直到中心点不再改变。

     

    二、步骤和结果

     

    环境:windows 10 64位系统,R ×64 3.1.2

     K 均值聚类     

           在R中K均值的函数格式是kmeans(x,centers),这里x表示数值数据集(矩阵或数据框),centers是要提取的聚类数目。函数返回类的成员、类中心、平方和(类内平方和、类间平方和、总平方和)和类大小。
          由于K均值聚类在开始要随机选择k个中心点,在每次调用函数时可能获得不同的方案。使用set.seed()函数可以保证结果是可复制的。此外,聚类方法对初始中心值的选择也很敏感。
           kmeans()函数有一个nstart选项尝试多种初始配置并输出最好的一个。例如,加上nstart=25会生成25个初始配置。通常推荐使用这种方法。

            让我们用K均值聚类来处理包含178种意大利葡萄酒中13种化学成分的数据集。该数据最初来自于UCI机器学习库(http://www.ics.uci.edu/~mlearn/MLRepository.html),但是可以通过rattle包获得。在这个数据集里,观测值代表三种葡萄酒的品种,由第一个变量(类型)表示。我们可以放弃这一变量,进行聚类分析,看看是否可以恢复已知的结构。具体实验过程,如下:

     

      

     

     


    因为变量值变化很大,所以在聚类前要将其标准化(1)。下一步,使用wssplot()和Nbclust()函数确定聚类的个数(2) 。图1表示从一类到三类变化时,组内的平方总和有一个明显的下降趋势。三类之后,下降的速度减弱,暗示着聚成三类可能对数据来说是一个很好的拟合。在图2中, NbClust包中的24种指标中有15种建议使用类别数为三的聚类方案。需要注意的是并非30个指标都可以计算每个数据集。

     

     

     

     

    图1 画出组内的平方和和提取的聚类个数的对比。从一类到三类下降得很快           

          (之后下降得很慢),建议选用聚类个数为三的解决方案

     

    图2  使用NbClust包中的26个指标推荐的聚类个数

     

    使用kmeans()函数得到的最终聚类中,聚类中心也被输出了(3)。因为输出的聚类中心是基于标准化的数据,所以可以使用aggregate()函数和类的成员来得到原始矩阵中每一类的变量均值。

              使用Kmeans()函数总的聚类情况如下图3所示。

     

    图3 划分3类的分类情况

     

    PAM聚类算法:

           我们可以使用cluster包中的pam()函数使用基于中心点的划分方法。格式是pam(x, k, metric="euclidean",stand=FALSE),这里的x表示数据矩阵或数据框, k表示聚类的个数,metric表示使用的相似性/相异性的度量,而stand是一个逻辑值,表示是否有变量应该在计算该指标之前被标准化。具体实验过程,如下:

           注意,这里得到的中心点是葡萄酒数据集中实际的观测值。在这种情况下,分别选择36、 107和175个观测值来代表三类。通过从13个测定变量上得到的前两个主成分绘制每个观测的坐标来创建二元图(参见第14章)。每个类用包含其所有点的最小面积的椭圆表示。图4列出了使用PAM方法处理葡萄酒的数据。

     

    图4  基于意大利葡萄酒数据使用PAM算法得到的三组聚类图

     

    相应代码及对用的word文档解释可从以下链接得到:

    划分聚类分析: K均值和基于中心点的划分(PAM) 及相应代码-CSDN下载
    http://download.csdn.net/download/u012711335/10142621

     

    注:本文思想来自《R语言实战》

     

    展开全文
  • 矩本来是个统计学概念,定义为f(x)*P(x)关于x的定积分,在二值化图形中,其零阶矩的定义如下: V(i,j)是(i,j)的灰度值,这个定义的本意是,所有像素的灰度值的总和,但因为在二值化图形中,白色都为1,黑色都为0...

    轮廓面积和中心点的计算(python-opencv)

    1、矩的概念

    矩本来是个统计学概念,定义为f(x)*P(x)关于x的定积分,在二值化图形中,其零阶矩的定义如下:

    在这里插入图片描述
    V(i,j)是(i,j)点的灰度值,这个定义的本意是,所有像素的灰度值的总和,但因为在二值化图形中,白色都为1,黑色都为0,所以M00的结果是所有白色区域的像素值的和,也可以当作白色区域的面积使用。

    其一阶矩定义如下:

    在这里插入图片描述

    i,j分别是每个像素的x,y坐标,这个定义本质所有像素点的x,y坐标分别和像素值相乘的积,然后求和得到的,同样M10的结果就是所有白色区域像素的x坐标的和,M01是所有白色区域y坐标的和。

    利用一阶矩,我们可以求出图形的重心坐标,其公式为:

    在这里插入图片描述

    2、求面积和重心

    如上面所示,利用矩可以求出图形的面积和重心

    opencv提供cv2.moments(轮廓)来求出图形的矩,这个函数只要提供Contours参数就可以。

    例子:

    M= cv2.moments(contours[0]) #求矩
    cx = int(M['m10']/M['m00']) # 求x坐标
    cy = int(M['m01']/M['m00']) # 求y坐标
    img=cv2.circle(img ,(cx,cy),2,(0,0,255),4) #画出重心
    

    对于面积,本来图形的矩里面M00就是表示面积,但opencv同时也提供cv2.ContourArea(轮廓)
    来计算面积,两者并没有什么区别
    例子:

    area = cv2.contourArea(contours[0])
    print  "area = %f"%area
    print   "M00 = %f"%M["m00"]
    

    注:cv2.moments这个函数返回的结果是一个字典类型的数据,零阶矩的键值是m00,一阶矩的键值分别是m10和m01

    展开全文
  • 中心极限定理的基本概念和应用场景

    万次阅读 多人点赞 2019-03-31 19:49:41
    一、中心极限定理的基本概念 中心极限定理是说:样本的平均值约等于总体的平均值。不管总体是什么分布,任意一个总体的样本平均值都会围绕在总体的整体平均值周围,并且呈正态分布。 接下来,我们用通俗易懂的话来...
  • 图论(6)树的概念中心与形心

    千次阅读 2020-04-08 14:00:41
    (一)、树的概念与应用 1.树的概念 不含圈的图称为无圈图,树是连通的无圈图。树的度为1的顶点称为树叶。 定义:称无圈图G为森林。 即无圈图G就是森林,森林可以是不连通的,若森林连通,则该森林为树。即...
  • 因为它们都有一个共同,那就是有着大量的用户需求。当大量用户的需求集中在一处,那这就是入口,也会成为风口。 当前,互联网已经经过数十年的发展,内卷化的平台形态成为了互联网发展的瓶颈,在内容载体、传播...
  • 一、树的概念和性质 首先借助图来阐述几个概念: 树:不含圈的连通图。 森林:不含圈的图。 树叶:度为1的顶点。 \quad由定义可知,树和森林都是简单图,且都是偶图。树有许多特有的性质,接下来我们一一...
  • IM 去中心概念模型与架构设计

    千次阅读 2016-08-01 21:09:28
    今天打算写写关于 IM 去中心化涉及的架构模型变化和设计思路,去中心化的概念就是说用户的访问不是集中在一个数据中心,这里的去中心是针对数据中心而言的。 站在这个角度而言,实际上并非所有的业务都能做去中心化...
  • 线面平面设计的概念是什么,在平面设计的领域里,、线、面有其独特的视觉效果和审美价值,它作为视觉语言,通过一定方式的组合,向人们传达出特定的内涵和信息。线面是平面设计中常用的构成元素,它构建了整个...
  • SAP概念之利润中心(Profit Center)

    千次阅读 2018-11-13 03:23:12
    SAP概念之利润中心(Profit Center)
  • 估计和区间估计——统计学概念

    千次阅读 2021-01-24 15:33:15
    概念简介: 估计和区间估计是通过样本统计量估计总体参数的两种方法。估计是在抽样推断中不考虑抽样误差,直接以抽样指标代替全体指标的一种推断方法。因为个别样本的抽样指标不等于全体指标,所以,用抽样...
  • 本文介绍了图计算中的核心概念与算法,了解这些基本知识可以帮助我们更好更快的探索一个图,找到相应的解决方案,同时也是更深层次研究的基础。
  • 信号滤波器以及中心频率概念

    万次阅读 多人点赞 2018-05-23 21:19:55
    两个半功率,这两中心就称为 中心频率 (Center Frequency) 。合成器中最常见的是低通滤波器,如果一台合成器只有一个滤波器的话,毫无疑问就是低通滤波器。 (4)声音高低主要与频率有关,由于 可听声 的 ...
  • SAP概念之利润中心

    千次阅读 2016-03-15 08:37:21
    1.基本概念 利润中心是出于内部控制目标而设定的反映管理架构的会计组织单位。从管理会计的角度来说,一个利润中心,最终考核的是利润,那么该组织单元就会发生收入,也会发生成本和费用。 SAP中,日常业务...
  • 中心频率和一些概念解释

    千次阅读 2016-06-30 10:31:42
    中心频率是滤波器通频带中间的频率,以中心频率为准,高于中心频率一直到频率电压衰减到0.707倍时为上边频,相反为下边频,上边频和下边频之间为通频带。 从原理上讲,再复杂的声音也可以用傅里叶分析的方法把它最后...
  • 文章目录中心性(degree centrality)中介中心性(betweenness centrality)接近中心性(closeness centrality)特征向量中心性(eigenvector centrality)有向图与PageRank小结 网络由节点(node)和连接它们...
  • 数据库-异地多活多中心概念

    千次阅读 2018-11-24 17:58:26
    数据库-异地多活多中心概念 0x01 摘要 本文简要谈谈我对异地多活多中心浅显理解,以及互相产生的记录不冲突的原因。 0x02 什么是多活 多活就是指业务服务部署在N个机房,那么可以容忍N-1个机房挂掉,还是能正常提供...
  • Elasticsearch最佳实践之核心概念与原理

    万次阅读 多人点赞 2018-12-03 22:29:58
    作为专栏文章的第二篇,本文从数据组织、数据分布、集群角色、数据写入与存储结构多个方面对Elasticsearch的核心概念进行整理,尽可能由浅入深的交代清楚每个概念
  • 一、概念 RectTransform是继承自Transform的组件,专门用于UI,除了显示在表面的一些基础属性,实际内部还有很多隐藏属性未显示在面板上,主要用于对UI做些基础操作 ...
  • SNA社会关系网络分析中,关键的就是通过一些指标的衡量来评价网络结构稳定性、集中趋势等。主要有中心度以及中心势两大类指标。 以下的代码都是igraph包中的。...是最基本的概念,就是在某个上,有多少
  • Eureka中的核心概念

    千次阅读 2017-09-07 10:16:49
    本文是Spring Cloud系列的第四篇,前面三篇文章(使用Spring Cloud搭建服务注册中心...前面的文章我们是以实际代码操作为主,这篇文章我想对前面三篇文章中涉及到的一些知识再进行详细的梳理,对于一些前面未涉及到的
  • 因为对普通用户来说,每一个接入到cas认证中心的子系统都提供特定的服务比如商城、bbs等,大家都听过软件即服务,平台即服务,这样理解service就通顺了  SaaS:Software-as-a-Service,软件即 服务  PaaS:...
  • 服务器基本概念

    千次阅读 多人点赞 2020-04-22 06:38:05
    服务器基本概念
  • CAS单登录-配置中心(三)

    万次阅读 热门讨论 2017-09-09 17:24:50
    CAS单登录-配置中心(三)本章计划及内容计划: 微服务概念 配置中心充当角色 搭建配置中心 cas连接配置中心 内容: 采用 spring cloud Dalston SR3搭建配置中心 采用 spring cloud config 1.3.2.RELEASE版本 采用...
  • 本文将给大家解释他的基本概念,告诉大家无监督学习可以用用到哪些具体场景中。 最后给大家举例说明2类无监督学习的思维:聚类、降维。以及具体的4种算法。 什么是无监督学习? 无监督学习是机器学习中的一种...
  • 云数据中心概述与趋势

    千次阅读 2019-04-12 17:04:14
    数据中心概念 数据中心(Data Center)是企业IT系统的核心,海量数据运算、交换、存储的中心,关键信息业务应用的计算环境,集中管控各种数据、应用程序、物理或虚拟化设备的环境。 数据中心四大焦点:可靠,灵活...
  • 1,WLAN的基本概念

    千次阅读 2021-11-14 10:52:23
    1,基本名称及作用: STA : 无线终端 ...3 中心AP 在集中式网络架构的敏捷分布Wi-Fi方案架构中,中心AP代理AC分担对RU的集中管理和协同功能,如STA上线、配置下发、RU之间的STA漫游。 4 远端单元RU...
  • SNA社会关系网络分析中,关键的就是通过一些指标的衡量来评价网络结构稳定性、集中趋势等。主要有中心度以及中心势两大类指标。 以下的代码都是igraph包中的。 ——————————————...中心度 在某

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 239,779
精华内容 95,911
关键字:

中心点的概念