K-means Algorithm

在监督学习中，有标签信息协助机器学习同类样本之间存在的共性，在预测时只需判定给定样本与哪个类别的训练样本最相似即可。在非监督学习中，不再有标签信息的指导，遇到一维或二维数据的划分问题，人用肉眼就很容易完成，可机器就傻眼了，图(1)描述得很形象。

但处理高维度的数据，人脑也无能为力了，最终还是得设计算法让机器来完成。如何将所有样本分成若干个类簇(cluster)，并且每个类簇中的样本具有更高的相似度，这就是聚类分析算法的终极目标。这里以最经典的K-means算法为切入点进行说明。 K-means算法的目标是将m个样本组成的集合X={x(1),x(2),⋯,x(m)|x(i)∈Rn}划分成k个类簇(k≤m)，其准则函数形式如下：

J (c, μ) = \sum i = 1 m ∥ x (i) - μ (i) c ∥ 2

其中c为样本的类簇分配情况，μ为类簇中心点，μ(i)c为样本x(i)对应的类簇中心。准则函数计算的是所有样本点与其对应的类簇中心的距离平方和。使准则函数最小的类簇划分极为最优的聚类。K-means算法描述请下图。

算法的内层循环完成两个工作：一是将每个样本划分到与其最近的类簇中心；二是将属于同一个类簇的样本均值作为新的类簇中心。算法的终止条件可以有三种：1)准则函数值的变化小于一个阈值；2)类簇中心在一定范围内不再变化；3)达到指定的迭代次数T。K-means的执行步骤如图(2)所示：(a)随机初始化的样本点；(b)随机设置类簇中心；(c)给样本点分配与之最近的类簇中心；(d)类簇中心更新为类簇中所有样本的均值；重复(c)和(d)直到收敛。

这里的准则函数不是凸函数，找到全局最优解是不可能的，但是能保证它收敛到局部最优解，分析如下：

更新样本x(i)所属的类簇时，总是选择与其最近的类簇中心，所以∥x(i)−μ(i)c∥2在每次迭代过程都是非递增的，那么能保证准则函数J也是非递增的；
类簇中心被更新为类簇中所有样本的均值也能保证J非递增。准则函数对类簇中心求偏导，并令偏导为0即可求得类簇中心的更新规则 $\partial J \partial μ j = \partial \partial μ j \sum i = 1 m 1 {c (i) = j} ∥ x (i) - μ (i) c ∥ 2 = 2 \sum i = 1 m 1 {c (i) = j} (μ (i) c - x (i)) = 0 \Rightarrow μ j = \sum m i = 1 1 { c ( i ) = j } x ( i ) \sum m i = 1 1 { c ( i ) = j }$

图(3)左侧是在随机生成的四组服从正态分布的数据上跑完K-means后的聚类结果；右侧则为每次迭代过程中准则函数值的变化曲线图，经过16次迭代后算法就收敛了，这也从实验角度验证了算法的收敛性。因为给定的不同类簇的数据间分得比较开，最后的聚类分析结果堪称完美。由于这次随机初始化的类簇中心情况很糟糕，算法经过16次迭代后才收敛，一般在8次以内就稳定了。

如果样本有多个属性，而且属性不在同一个定义域内，则有必要对样本数据进行预处理，防止某些值很大的属性在计算距离时占主导优势。最常用的就是标准化处理，使得每个属性均值为0，方差为1。 K-means算法对类簇中心的初始化非常敏感，如图(4)所示，我在图中示意性标出了6个可能的初始点，算法会收敛到对应的6个局部最优解，然而只有第2个才是全局最优解。为了避免陷入很差的局部最优解(如第1个局部最优解)，常用的策略就是多跑几次K-means，每次都将类簇中心随机初始化，最后选取使准则函数最小的聚类情况。

聚类的最终目的是使同一个类簇中的数据尽可能相似，而不同类簇间的样本彼此离得越远越好。如果我们在初始化类簇中心的时候就遵循这条原则，则可以大大减少收敛所需的迭代次数。下面给出了类簇中心初始化的算法(2)描述，该算法的时间复杂度为O(m2+km)。我们可以想象到，该初始化算法实际上是从样本分布的最边缘开始选取类簇中心的，以避免类簇中心被初始化到数据较为密集的地方，大大降低算法收敛需要的迭代次数。有收获必然也要付出代价，这是永恒的真理，这么做是否值还得视情况而定。

在标准的K-means算法中，每个样本点都要和更新后的类簇中心计算距离欧氏距离，如果样本维度较高的话，算法的时间复杂度会非常高。有些大牛们提出用三角不等式或树形结构等对K-means进行加速的算法，以减少不必要的距离计算。建议参考2003年Elkan发表在ICML上的论文《Using the triangle inequality to accelerate k-means》，以及《A generalized optimization of the k-d tree for fast nearest neighbour search》。开源项目VLFeat中就使用了k-d树加速K-means。在批量版本K-means算法中，我们用所有数据一次性更新类簇中心。但遇到需要在线处理的应用时，处理时间是关键，另外一个挑战就是数据的动态输入，因此有必要为K-means设计一个在线算法。在时间允许的范围内，我们可以一次值处理一条数据，也可以等收集到几条数据后一起处理。在前面证明K-means算法的收敛性过程中，我们求出了准则函数对类簇中心μj的偏导，我们很容易将其改造成利用随机梯度下降的online版本算法(3)，其中学习率参数α应该随处理数据的增多而逐渐减小。

K-means算法的一大特点是每个样本只能被硬性分配(hard assignment)到一个类簇中，这种方法不一定是最合理的。但聚类本身就是一个具有不确定性的问题，如图(5)所示，实际情况中的类簇很可能存在重叠的情况，那么重叠的部分的归属就颇具争议了；给定一个新样本，正好它与所有类簇中心的聚类是相等的，我们又该怎么办？如果我们采用概率的方法，像高斯混合模型(Gauss Mixture Model,GMM)那样给出样本属于每个类簇的概率值，能从一定程度上反映聚类的不确定性就更合理了。

下面介绍K-means算法的两个简单应用：图像分割和数据压缩。图像分割的目标是将图像划分成若个区域，每个区域内有相似的视觉效果。K-means用于图像分割，实际上就是将图像中的所有像素点当成样本点，将相似的像素点尽可能划分到同一个类簇中，最后就形成了k个区域，在展示分割情况时以类簇中心代替该类簇中的所有样本。如图(6)所示，我选择了经典的Lena图像和一只小鸟图像进行分割，每次聚类的中心数目k从左到右依次为3,6,12，最右侧围原图。Lena图像的颜色种类较少，所有$k=3$时的效果也还行；但是小鸟图像颜色复杂很多，直到k=12时图像的分割效果才略微令人满意。图像分割其实是个相当有难度的问题，K-means算法在这个领域还是太弱了...

数据压缩分为无损压缩和有损压缩两大类，无损压缩要求数据还原后要和元素数据一模一样，而有损压缩可以容忍重构数据与元素数据存在一定程度的偏差。K-means算法用于数据压缩只能是有损压缩了，k越小数据失真越厉害。主要思想是在N个样本集合中用于K-means算法得到k个类簇中心和N个类簇的分配情况，最终我们只需存储类簇中心和每个样本的类簇分配情况即可。假设每个样本的存储空间为a字节，则k各类簇中心需要的存储空间为ka字节，类簇分配情况耗费存储空间为N⌈log2k⌉字节，压缩比为Na/(ka+N⌈log2k⌉)。

整个K-means实验的Matlab代码在这里下载！

分类: Machine Learning

标签: Machine Learning, K-means, clustering

打造一套UI与后台并重.net通用权限管理系统

2013-11-15 19:43 by 微软高级php工程师, 3559 阅读, 79 评论, 收藏, 编辑

一、前言

从进行到软件开发这个行业现在已经有几年了，在整理出这个套开发框架之前自己做了不少重复造轮子的事。每次有新的项目总是要耗费不少时间在UI、权限和系统通用模块上面，自己累得要死，老板还骂没效率。为了能提高开发效率，同时也多拿拿奖金、多存点私房钱，我就着手做了一套以权限管理为主的快速开发框架。不求功能在所有项目中都得到使用，至少要大大提高开发效率。

二、需求分析

根据《那些年我们一起做过的项目》中各类客户对权限模块和通用模块以及UI的要求，我明确了这个系统中要实现的东西。

1、组织机构 多级树型显示，各级部门从属关系一目了然操作便捷

2、用户 所有的权限最终分配给用户，如果按用户去分配权限会把系统管理员给累死，系统中先建立角色，角色中再分配权限，在角色的成员中加入用户。当然会有一些用户的权限大同小异，如果不想在系统中创建太多角色可以给用户分配权限。用户最终的权限取角色权限和用户权限的集合。

3、角色 一组权限的集合。

4、模块 也可以称之为菜单，可以是系统中的页面，也可以是其它系统的页面地址统一纳入到同一套权限系统中维护。

5、按钮

6、权限 权限分配模式：1）角色权限分配，权限分配的便捷性。

2）用户权限分配，权限分配的灵活性。

权限控制类型：1）模块权限采购员有采购模块权限和库存查看模块权限。

2）按钮权限采购员能点击新增按钮新增采购单，采购经理能点击审核按钮审核采购单。

3）数据权限每个业务员只能看到属于自己的客户资料。

4）字段权限会计可以看到库存报表中的所有字段，仓库管理员不能看到报表中的金额字段。

5）文件权限采购部的文件只有总经理和采购部成员有权限

7、日志 登陆日志、操作日志、系统异常日志

8、数据库管理 在前端页面查看数据库信息，数据库备份

9、访问控制

10、动态接口 这里说的接口是与其它系统或设备的通信接口，一般以Webservice、WCF、Webapi的形式提供。在系统中对外只暴露一个接口。增加接口、修改接口都不用修改程序。

11、UI 前端框架：采用Jquery UI,功能强大扩展灵活，不用担心版权问题。

多种风格界面：手风琴导航风格、desktop风格、触摸屏风格

12、系统参数

13、代码生成器 根据需要生成界面和后台代码

三、设计实现

2、程序设计

程序基本以Jquery+Ajax+工厂模式实现，接近10万行的代码量，后续分模块详细讲解

3、用户体验UI设计

UI对于一个软件来说就像女人那张脸，别人最先看到的就是你的脸。人再好，脸长得丑肯定还是要经常过光棍节。一套程序UI漂亮程序的档次自然也就上去了。无图无真相，下面给出一些主要界面，详细实现也会在后面的博客中给出。

1）系统风格

a)desktop风格

b)手风琴风格

c）触摸屏风格

2、员工管理

左边展开组织机构，右边员工管理

3、组织机构管理

树型组织机构，组织架构一目了然

4、组织架构图

根据组织机构自动生成的组织架构图

5、角色权限控制

角色成员：拥有该角色的用户。

模块权限：该角色能操作哪些模块。

按钮权限：角色能操作指这模块中哪些按钮。

数据权限：角色对哪些数据有操作权限。

文件权限：角色对哪些文件有操作权限。

6、模块按钮管理

拖动按钮位置能改变按钮在模块中的显示位置。

勾选状态的按钮会在模块中显示。

当然图片就先晒到这边啦！如果你觉得可以把这些图片的设计思路理解，并且觉得以后会用的话，请收藏一下，推荐一下啦!

对于一些界面看完让我内心想对他说三个字"毁三观"的界面，我只能说你的审美水平一定要提高的，IT这是一个潮流的行业，如果你不潮，那就无法与众不同，机遇往往会给你留个位置的！大家说呢？

Asp.net Mvc4 基于Authorize实现的模块权限验证方式

在MVC中，我们可以通过在action或者controller上设置Authorize[Role="xxx"] 的方式来设置用户对action的访问权限。显然，这样并不能满足我们的需求，

对于一般的MVC系统来说，如果我们定义一个controller来处理一个模块的话，我们大致有以下需求：

　　一，单个action的访问权限。如果删除，列表action

　　二，一个action两种权限，如edit(int? id)如果id为null则添加，或者修改

　　三，在此cotroller验证其它模块权限，比如，我们要在新闻模块获取新闻列表

　　四，对于某些通过模块，如分类，我们希望通过传入不同的参数可以验证不同模块的权限

对于四种情况，我理想的想法是：

对于第一种，直接制定controller的moduleid和action的权限

 [Module(ModuleId=6)]
public class Controller: Controller{
        [SysAuthorize(Permission.List)] //设置action要验证的权限
        public ActionResult List()
 }

对于第二种情况，我们希望通过参数来达到验证那个权限的目的：

 [Module(ModuleId=6)]
 public class Controller: Controller{
        //如果参数为null是将验证添加权限否则验证修改权限
        [SysAuthorize(Permission.Add,Permission.Edit,"id",null)]       
        public ActionResult Edit(int? id)
  }

对于第三种情况，我们可以为action验证指定单独的模块id

    [Module(ModuleId=6)]
    public class Controller: Controller{
        [SysAuthorize(9,Permission.List)] //此方面验证模块9的列表权限
        public ActionResult List(int CType)
    }

对于第四种情况，我们可以为模块添加不同的参数module对应关系

    [Module(ModuleId=5,"CType",1)]
    [Module(ModuleId=6,"CType",2)]
    public class Controller: Controller{
         如果当前传入CType为1则验证ModuleId=5,等于2是验证ModuleId=6
        [SysAuthorize(Permission.List)]
        public ActionResult List(int CType)
    }