四天数模，做得不好，但收获不小。最后还通宵一宿，多日后得以重获新生，特做个小记，聊记心得。

本次选题为神经元的分类和聚类，前者给定种类，需要通过训练样本找寻分类特征，再用测试样本测试分类方法的正确性。后者未给定种类，需要根据相似度找出分类。分类方法众多，比如PCA，一种简单的线性统计主成分分析方法，见参考文献【1】；又或灰度关联法，不需要任何基础知识的分类法，见参考文献【2】。这里将总结一种基于稀疏表示的分类方法。

本科期间应该很多人都学过线性相关，即若y与x1、x2……xn相关，则必有y能被x1、x2……xn线性表示。稀疏分析即基于此，只需将y看成是测试样本，x1、x2……xn当作是训练样本，如果y能被x1、x2……xn表出，则认为y属于x1、x2……xn所在类型。当然，这仅是理想状况，由于有噪声等干扰因素的存在，要使y能由x1、x2……xn精确表出，要求过于严格，需要做具体的处理，比如寻求最小残差。

因为实际上测试样本y，初始时无法肯定属于哪一个类型，它可能属于n类中的任何一类，因此我们先定义一个矩阵A，A中包含所有类的训练样本信息，A如下：

file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/1OGLU31@8RU[99LB)J`V)RM.jpg

因此对测试样本y可以表示成：

y=A*X0

其中X0是系数向量，

除了与测试样本相关的类外，其余元素均为0。

于是，判断y的所属类型，归结于解方程组y=AX，其中y是测试样本，A是整个训练样本集。

此方程组，往往解并不唯一，按照通常处理方法，我们可以采用取2-范数最小，

该法计算复杂度低，但由于误差等，使得y可以被多个不同训练样本逼近，这时解中会有大量来自不同训练样本类的非零元素，这对最后确定样本y属于哪个样本类的精度造成较大影响。

这时为了寻找哪个才是最优，也就是要满足，分类的组类距离最小，组间距离最大，同时考虑到，解向量中大部分元素为0，属稀疏阵，可以设立要求，定义0-范数，为解向量中非零个数，

显然只有非零个数最少时，其表示最为近似。但如此定义的0-范数求解中，会有NP难问题，不利求解。

于是将其等价为1-范数，

具体等价证明可参考文献【3】。

其几何直观解释如下图：

file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/Z7$}[41S$KIP0Z_J8EE2V}O.jpg

是将1-范数球，映射到1-范数多面体，由于边界点的一一对应关系，可得所定义的0-范数与1-范数等价。

最后用邻接性解决1-范数即可。其计算复杂度低。为多项式复杂度。

当然技术处理上需要考虑到噪声等，所以可以用残差量解决。

基于稀疏表示的分类算法：

Step 1：输入训练样本集：file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/$$)L62W35IB8V(35)NIMRMU.jpg ，k为分类数目；

Step 2：输入测试样本：file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/V$}S5{9V[F{GE3)4YZGTU%V.jpg ，并选择最大误差允许值；

Step 3：解最小 -范数问题：

       或file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/@%D{Z7TIPB682U5@A6TMVFM.jpg ；

Step 4：计算残差量：file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/GV]_8OUQD{[44HPWMKJTE$8.jpg；

Step 5：输出y所属的类型：y所属的类型为file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/GLYGIZ4B1U7VCUU$BIP9A}U.jpg对应的标号i。

参考文献：

【1】主元分析(PCA)理论分析及应用 http://www.cad.zju.edu.cn/home/chenlu/pca.htm

【2】基于matlab的灰度关联分析法 http://blog.sina.com.cn/u/1258373041

【3】D. Donoho, “For Most Large Underdetermined Systems of LinearEquations the Minimal l1-   Norm Solution Is Also the SparsesSolution,” Comm. Pure and Applied Math., vol. 59, no. 6, pp. 797829, 2006