SOM算法

无导师学习方法

自组织映射(Self-organizing Maps,SOM)算法是一种无导师学习方法,具有良好的自组织、可视化等特性,已经得到了广泛的应用和研究。

基本原理

SOM网络结构如图 1 所示,它由输入层和竞争层(输出层)组成。输入层神经元数为 n,竞争层由m 个神经元组成的一维或者二维平面阵列,网络是全连接的,即每个输入结点都同所有的输出结点相连接。

SOM 网络能将任意维输入模式在输出层映射成一维或二维图形,并保持其拓扑结构不变;网络通过对输入模式的反复学习可以使权重向量空间与输入模式的概率分布趋于一致,即概率保持性。网络的竞争层各神经元竞争对输入模式的响应机会,获胜神经元有关的各权重朝着更有利于它竞争的方向调整“即以获胜神经元为圆心,对近邻的神经元表现出兴奋性侧反馈,而对远邻的神经元表现出抑制性侧反馈, 近邻者相互激励,远邻者相互抑制”。一般而言,近邻是指从发出信号的神经元为圆心,半径约为 50μm~500μm 左右的神经元;远邻是指半径为 200μm~2mm 左右的神经元。比远邻更远的神经元则表现弱激励作用,如图2所示由于这种交互作用的曲线类似于墨西哥人带的帽子,因此也称这种交互方式为“墨西哥帽”。

记所有输出神经元c组成的集合为，神经元c与输入层神经元之间的连接权向量为Wc。SOM算法作为一种非监督类的方法，理论上可以将人以为的输入模式在输出层映射成一维、二维甚至更高维的离散图形，并保持其拓扑结构不变。

该算法的聚类功能主要是通过以下两个简单的规则实现的。

1.对于提供给对于提供给网络的任一个输入向量, 确定相应的输出层获胜神经元s，其中s=argminc| -Wc|所有的c属于。

2.确定获胜神经元 s 的一个邻域范围, 按如下公式调整，范围内神经元的权向量：。该调整过程使得内神经元的权向量朝着输入向量的方向靠拢。  所有的c属于N。

随着学习的不断进行,学习率将不断减小. 邻域也将不断缩小, 所有权向量将在输入向量空间相互分离 , 各自代表输入空间的一类模式,这就是Koohenn网络特征自动识别的聚类功能。

具体过程

(1)将权值赋予小的随机初始值;设置一个较大的初始邻域,并设置网络的循环次数 T;

(2)给出一个新的输入模式 Xk:Xk={X1k,X2k,...,Xnk},输入到网络上;

(3)计算模式 Xk 和所有的输出神经元的距离 djk,并选择和 Xk 距离最小的神经元 c,即

xk-Wc=minj{ dij }则 c 即为获胜神经元;(4)更新结点 c 及其领域结点的连接权值 wij(t+1)=wij(t)+η(t)(xi-wij(t))

其中 0<η(t)<1 为增益函数,随着时间逐渐减小;

(5)选取另一个学习模式提供给网络的输入层,返回步骤 (3),直到输入模式全部提供给网络;

(6)令 t=t+l,返回步骤(2),直至 t=T 为止。

在自组织映射模型的学习中,通常取 500≤T≤10000。Nc 随着学习次数的增加逐渐减小。增益函数 η(t)也即是学习率。由于学习率 η(t)随时间的增加而渐渐趋向零,因此,保证了学习过程必然是收敛的。

一般要求:η(t+k)=∞

η^2(t+k)<∞

其中:0<η(t+k)<1,k=1,2,...,∞。

在实际的权系数自组织过程中,一般,对于连续系统取: η ( t ) = 1t

对于离散系统,则取:η(t+k)= 1/t+k

局限性

无导师学习现在发展的还不成熟,SOM 算法还存在一些局限性,比如:

(1)网络结构是固定的,不能动态改变;

(2)网络训练时,有些神经元始终不能获胜,成为“死神经元”;

(3)SOM 网络在没有经过完整的重新学习之前,不能加入新的

类别;

(4)当输入数据较少时,训练的结果通常依赖于样本的输入顺序; (5)网络连接权的初始状态、算法中的参数选择对网络的收敛性

能有较大影响。为此,一些学者提出了不同的改进算法,从不同方面不同程度地克服了这些缺点。

SOM 的改进算法

基于动态确定神经元数目的改进

传统 SOM 模型存在着许多的不足,特别是需要预先给定网络单元数目及其结构形状的限制。为此,人们提出了多种在训练过程中动态确定网络形状和单元数目的解决方案, 比较有代表性的有: GSOM(Growing Self-Organizing network ))。该算法的基本思想是把n维空间的单形体, 比如一维空间的线段, 二维空间的三角形, 三维空间的四面体作为基本的构建模块, 随着训练的不断进行，渐进、动态地生成SO M网络。 

右图就是将Growing SOM算法应用于一个圆形概率分布的数据集上所得到的最初几步结果。

由上例可以看出, 随着学习过程的不断进行。SOM网络也在不断“增长” ,平

均每隔200个训练例就有新的单形体(上例为三角形)插入到SOM网络中，那么这些单形体应该在什么位置插入就成 G rowing SOM算法所面临的一个关键问题, 一般而言,可以通过下述方法解决：对于整个SOM网络定义一个可以度量的期望目标；对于每一个输出神经元(比如上例中的三角形的顶点)，估计它们对网络期望目标贡献的大小；在那些对期望目标贡献不大的神经元附近插入新的神经元；Growing SOM与普通的SOM网络的不同点在于：网络结构是动态生成的；持续不变的自适应能力；固定的邻域范围。相同点在于：固定的网络维数；邻域的确定取决于网络的拓扑结构。

王莉等提出的树型动态增长模型 TGSOM,它与 GSOM 的不同在于它可以按需要方便地在任意合适位置生成新结点,克服了 GSOM 的缺点;Frltzke 提出了增长细胞结构 (Growing Cell Structure, GCS)算法,GCS 算法从一个由 3 个神经元构成的三角形结构开始,记录下每个神经元获胜的次数,在下一周期开始前,选出获胜次数最多的神经元,在其最大的一边上增加一个含初始权值的新结点,并重新计算新结点及各邻接结点的获胜次数,同时,可根据结点的获胜次数进行结点的删除操作。Choi 等提出了自组织、自创造的神经网络模型 (Self-creating and Organizing Neural Networks,SCONN), SCONN 在初始时存在一个激活水平足够高的根结点,找出输入向量 x 的最佳匹配单元 c,然后比较|x - Wc|与 c的激活水平。若前者大于后者,生成一个 c 的子结点以匹配 x;否则, 修正 c 及邻域结点的权值。 

基于匹配神经元策略的改进

Kohonen 竞争学习机制经常会使得竞争层中有些结点始终不能获胜,尽管 SOM 采用拓扑结构来克服此缺点,但并不是非常有效,为此提出了很多克服此缺点的算法,比较典型的有 : SOFM-CV , SOFM-C , ESOM(Expanding Self- organizing Map),TASOM(Time Adaptive SOM),DSOM。 SOFM-CV 的思想是:把 SOM 网络的权值都初始化为 ( n为输入向量的维数),每个输入向量 x 要经过如下修正后: ( (α 随时间从 0 逐渐增大),再输入网络。SOFM-C 即带“良心”的竞争学习 SOFM,它的基本思想是给每个竞争层结点设置一个阈值,每次使竞争获胜的神经元的阈值增加,使经常获胜的神经元获胜的机会减小。ESOM 的思想是把更新获胜结点 c 及其领域结点的权值公式(2)修改为下式: wij(t+1)=cj(t)(wij(t)+η(t)(xi-wij(t)))

其中 cj(t)≥1,由 wij(t),xi,η(t)确定。在 TASOM 中,每个神经元都有自己的学习率和邻域函数,并且能根据学习时间自动地调整学习率和邻域的大小。DSOM 的思想是把内源性一氧化氮(NO) 的四维动态扩散特性和其在长时间学习过程中的增强作用应用到 SOM 中,输入向量 x 输入网络后,以某种规则(评价函数)确定竞争层中一组获胜神经元,称为亚兴奋神经元簇。并把每一个亚兴奋神经元作为 NO 的扩散源。然后计算各亚兴奋神经元所处位置的 NO 浓度, 则 NO 浓度最高的神经元为最终获胜单元。

SOM 算法和其它算法的组合

比较有代表性的组合算法有:Xiao 等提出了把 SOM和微粒群优化(Particle swarm optimization,PSO)算法结合用来对基因数据进行聚类,先用 SOM 算法对基因数据进行聚类,得到一组权值,然后用此权值初始化 PSO 算法,用 PSO 算法对此聚类结果进行优化。Sankar 等提出了把粗糙集和 SOM 结合的 RSOM 算法,它先用粗糙集理论中的依赖规则获得输入数据的大致聚类情况等知识,然后通过这些知识来确定 SOM 网络的结构,并对 SOM 权值进行初始化,用 SOM 网络对结果进行训练、优化。Hussin 等提出了把 SOM 和自适应共振理论 (Adaptive Resonance Theory,ART)模型相结合用来对文档进行聚类,先用 SOM 算法对文档进行划分, 然后用 ART 对所有的划分进行聚类。孙放等提出了把 SOM 和多层感知器(Multilayer Perceptron, MLP)结合进行语音识别,首先用 SOM 算法进行语音特征矢量量化(VQ),用轨迹图训练 MLP 网络,相当于建立好了参数模板,用此参数模板就可以进行语音识别。

SOM变体

TS-SOM

TS-SOM(Tree Struetured Self一Organzing Maps)是SOM算法的一种快速实现。TS-SOM的网络结构可以用一个图T=(V,El,E2)来表示,其中V是结点(神经元)的集合,E1是用于“纵向”层次连接的边构成的集合, 而E2是用于各层之间“ 横向” 连接的边构成的集合。对于每一个节点i属于V,都存在一个相应的子树Ti(Vi,E1i,E2i),并且满足如下条件：Vi属于V，E1i属于E1,E2i属于E2，Ti与Tj不相交。

图是一维和二维的TS-SOM的拓扑结构。在TS-SOM中,树的每一层都是一个SOM网络,并且每一个结点都会引导出2^n个子结点,其中n为TS一SOM的维数,由此可知TS-SOM的第l层包含(2^n)^l个结点(l=0,1,2...L-1,L为TS-SOM的层数)。

由于树结构本身的递归性在对第l层上的神经元进行匹配运算时, 可以利用前面l-1层网络所提供的信息以减少匹配次数J.H.Friedman等人指出,对于总共含有N个结点的网络和任一输入模式,普通SOM网络需要O(N)的时间以找出对应的获胜神经元,而TS-SOM只需O(logpN)的时间就可以完成匹配, 其中户是TS-SOM中每个神经元子结点的数目,且P=2^n。因此TS-SOM实际上是将树结构有效地应用于SOM算法当中给出了SOM算法的一种快速实现。

SOM 的应用

SOM 算法以其所具有的诸如拓扑结构保持、概率分布保持、无导师学习及可视化等特性吸引了广泛的注意,各种关于SOM 算法应用研究的成果不断涌现,现已被广泛应用于语音识别、图像处理、分类聚类、组合优化(如 TSP 问题)、数据分析和预测等众多信息处理领域。总之,SOM 算法的应用十分广泛,有着较好的发展前景,值得大家作进一步的研究。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省