（计算机软件与理论专业论文）一种同调边缘学习算法及其应用研究.pdf

一种同调边缘学习算法及其应用研究中文摘要 一种同调边缘学习算法及其应用研究 中文摘要 针对晶体数据的边缘划分问题，引入同调论的思想，从机器学习角度给出了一种 同调边缘学习算法。主要包括以下几方面内容： 1 给出了上同调边缘算法、胞腔同调边缘算法和正则胞腔同调边缘算法。 2 给出了同调边缘划分算法，并将其应用于鸢尾花分类，实验结果表明该算法是 有优势的。 3 给出了上边缘同调学习算法，通过实验验证，该算法应用于晶体数据分析，取 得了明显的效果。 4 给出了上同调边缘学习算法，将该算法应用于晶体结构预测，为物理学家提供 了新的分析方法。 综上所述，本文给出的这些研究内容不仅对机器学习领域有积极意义，而且通过 实例分析进一步说明其应用领域也是十分广泛的。 关键词：机器学习，同调边缘学习，同调，同伦 + 本文的研究得到国家自然科学基金项目支持( 6 0 7 7 5 0 4 5 ) l 作者：鲜敏 指导老师：李凡长 a b s t r a c t r e s e a r c ha n da p p l i c a t i o no nah o m o l o g yb o u n d a r yl e a r n i n ga l g o r i t h m r e s e a r c ha n d a p p l i c a t i o no nah o m o l o g yb o u n d a r y l e a r n i n ga l g o r i t h m a b s t r a c t a i m e da ts o l v i n gt h ec l a s s i f i c a t i o np r o b l e mo fc r y s t a ld a t a , t h ei d e ao fh o m o l o g y t h e o r yi sp r o p o s e di nt h i st h e s i sa n dah o m o l o g yb o u n d a r yl e a r n i n ga l g o r i t h mb a s e do n m a c h i n el e a r n i n gi sp r e s e n t e d t h ec o n t e n t sa r ea sf o l l o w s ： f i r s t l y , t h ec o h o m o l o g yb o u n d a r ya l g o r i t h m ，c e l l u l a rh o m o l o g yb o u n d a r ya l g o r i t h m a n dr e g u l a rc e l l u l a rh o m o l o g yb o u n d a r ya l g o r i t h ma r ei n t r o d u c e d s e c o n d l y , t h eh o m o l o g yb o u n d a r yd e v i s i o na l g o r i t h mi sg i v e na n da p p l i e dt ot h ei r i s c l a s s i f i c a t i o ne x p e r i m e n t t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mh a sm o r e a d v a n t a g e so v e re x i s t i n ga l g o r i t h m s t h i r d l y , t h ec o b o u n d a r yh o m o l o g yl e a r n i n ga l g o r i t h mi s i n t r o d u c e da n du s e dt o a n a l y z et h ec r y s t a ld a t ae x p e r i m e n t r e m a r k a b l er e s u l t sa r ea c h i e v e di nt h ee x p e r i m e n t l a s t l y , t h ec o h o m o l o g yb o u n d a r yl e a r n i n ga l g o r i t h mi s i n t r o d u c e da n da p p l i e dt o c r y s t a ls t r u c t u r ep r e d i c t i o ne x p e r i m e n t ，t h u sp r o v i d i n gp h y s i c i s t san e wa n a l y s i sm e t h o d i ns u m m a r y , t h ec o n t e n t so ft h e s es t u d i e sn o to n l yh a v ep o s i t i v es i g n i f i c a n c et ot h e m a c h i n el e a r n i n gf i e l d s ，b u ta l s od e m o n s t r a t et h e i re x t e n s i v ea p p l i c a t i o n st h r o u g ha n a l y s i s o ft h ee x a m p l e s k e y w o r d s ：m a c h i n el e a r n i n g ，h o m o l o g yb o u n d a r yl e a r n i n g ，c o h o m o l o g y , h o m o t o p y s u p p o r t e db yn a t i o n a ln a t u r a l s c i e n c ef o u n d a t i o no f e c h i n a ( 6 0 7 7 5 0 4 5 1 i l w r i t t e n b yx i a nm i n s u p e r v i s e db yl if a nz h a n g 机器学习 拓扑 同构 同态 同调 同胚 上同调边缘 上同调正合序列 上同伦 胞腔同调 胞腔同伦 正则胞腔同调 正则胞腔复形 单形 复形 链群 点群 空间群 同伦 流形 上闭链 上边缘链 上同调群 胞腔链群 张量 交链 中英文名词对照 m a c h i n el e a r n i n g t o p o l o g y i s o m o r p h i s m h o m o m o r p h i s m h o m o l o g y h e m e o m o r p h i s m c o h o m o l o g yb o u n d a r y c o h o m o l o g ye x a c ts e q u e n c e c o h o m o t o p y c e l l u l a rh o m o l o g y c e l l u l a rh o m o t o p y r e g u l a r c e l lh o m o l o g y r e g u l a rc e l lc o m p l e x s i m p l e x c o m p l e x c h i ng r o u p p o i n tg r o u p s p a c eg r o u p h o m o t o p y m a i n f o l d c o c y c l e c o b o u n d a r yc h a i n c o h o m o l o g yg r o u p c e l l u l a rc h a i ng r o u p t e n s o r a l t e m a r i as p p 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：台熟日期：望：五：主 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 白期：o z6 弓 一种同调边缘学习算法及其应用研究第一章绪论 第一章绪论弟一早 三百。下匕 在数据分析中，维数约简、边缘划分是人们感到比较棘手的问题。本文主要从晶 体数据方面来研究数据约简和边缘划分问题。下面就这些相关问题的研究进展简述于 下。 1 1 晶体数据分析方法 一二维周期结构是三维晶体结构向低维方向扩展的原子层次的结构。在晶体的内 部结构中必须具有三维空间的周期性，但这是一种理想的晶体结构，实际的晶体，其 内部结构往往含有缺陷，晶体结构与晶体缺陷不可截然分离乃是一个客观事实。针对 晶体数据目前的分析方法主要有：电子衍射强度的经验校正方法与晶体的相位扩展 处理技术【l j ：该方法的核心是借助所对应的高分辨像校正电子衍射强度，并借鉴了x 射线晶体学中的重原子法及w i l s o n 统计分析来进行处理；高分辨像的最大熵解卷 处理技术【2 圳：该方法是将信息论中的最大熵原理引入晶体图像中建立起来的一种晶 体识别技术；晶体学图像处理技术【4 】：该方法是将最大熵解卷处理和电子衍射强度 校正的相位扩展组成的晶体识别技术等。 1 2 维数约简 维数约简可以分为线性维数约简和非线性维数约简。在高维数据中，线性维数约 简体现了其方便易解释和可延展等特点。主要的线性维数约简方法有主成分分析 ( p r i n c i p a lc o m p o n e n ta n a l y s i sp c a ) 5 1 , 独立成分分析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s i c a ) 1 6 】，f i s h e r 判别成分( f i s h e rd i s c r i m i n a n ta n a l y s i sf d a ) 7 1 ，3 ee l i 线( p r i n c i p a lc u r v e s ) t 8 1 ， 投影寻踪( p r o j e c t i o np u r s u i tp p ) 9 1 ，局部线性投影( l o c a ll i n e a rp r o j e c t i o nl l p ) 1 0 1 ，以及神 经网络的自组织映射( s e l f - o r g a n i z a i n gm a ps o m ) 【l l 】。主要的非线性数据约简方法，一 是基于核的方法；二是基于流形的方法。常用的核函数方法有k p c a l l 2 】，k i c a l l 3 1 ， k s o m t l 4 1 ，k f d a ”】等等。基于流形学习的非线性维数约简方法，主要包括多维尺度 第一章绪论一种同调边缘学日算法拉其应用研究 方法，等距映射方法1 1 ”，局部线性嵌入方法，拉普拉斯特征映射方法，局部 切空间排列方法等。 下面就相关算法进行简单介绍。 1 2 1 核主成分分析( k p c a ) k p c a 【l ”的主要思想是通过非线性映射将输入空间映射到一个特征空司，然后在这 个特征空间计算主成分。一般的p c a 只能有效处理线性变化的观测数据，当数据的变 化是非线性时，这些数据必须映射到一个线性的更高维的空问( 即特征空问f ) 。k p c a 通过一个简单的核函数找到一个可计算的可控解，本质上就是构造一个从输入空间到 特征空间的非线性映射。园此k p c a 是在输入空间完成非线性的p c a ，可以捕捉线性 p c a 丢失的非线性数据。 k p c a 算法描述如下 ”! f “一 十r 卜 图卜lk p c a 的主要思想 输入：样本输入乒扛一圹：b d 竹，样本真维数d ，邻域参数k 输出：低维嵌入扣扣 y 2 j “e 砖 1 计算点积k d ：。( o ) ( ) o ) ( x ，) ) - 2 通过对角化来计算m a 口= k a 。 3 通过计算l = ( 矿) 来正规化本征向量展开系数口。 4 为了提取和核k 对应的关于测试点。的主成分，通过方程见：l 屯川j 来计算到本 警 一种同调边缘学习算法及其应用研究第一章绪论 征向量上的映射。 k p c a 的特点是：该算法是针对非线性数据。k p c a 的属性：假定特征向量是在特 征值中是升序排列的。第一个9 主成分元素( g 1 ，m ) ，比其他g 正交方向具有更 多的方差，在通过第g 个主成分元素均方逼近误差在观测值是最小的。主成分元素是 无关联的，表示熵是最小化的。第g 个主成分在关于输入上有最大的相互信息。 1 2 2 核独立成分分析( kic a ) i c a 的出发点非常简单，它假设各成分是统计独立的且是线性的，但由于现实中 很多数据是非线性的。k i c a 不是现有i c a 的核化，而是一种新的i c a 方法。 k i c a 1 3 1 算法描述如下： 输入：样本以r p , k = 1 ，2 ，n ，伊是一个把特征空间r 9 映射到q 维的核空间r 9 的 连续映射 输出：w 1 计算点积用一个核函数表示k ( 薯，_ ) = ( ( ) ，( _ ) ) ，其中k 为满足m e r c e r 条件的核函数。 2 利用满足核条件的核函数来来代替两向量间的内迹运算来实现非线性变换。 3 满足收敛条件可得到矩阵w 。 可以证明映射函数伊把特征向量映射到9 = 0 0 的核空间，因此缈的像空间为无穷 维的h i l b e r t 空间，然而不可能直接实现无穷维的映射，但映射够是存在的，所以 h i l b e r t 空间中向量之间的奠基运算可以通过k ( 誓，一) = ( ( 薯) ，( _ ) ) 在原模式空间 中计算。这样基于内积运算的子空间分类可以在核空间中实现，而无需知道映射妒的 具体表达式。 第一章绪论 一种同调边缘学习算法及其应用研究 1 2 3 核fis h e r 判别分析( k f d a ) k f d a l l 5 】算法通过把非线性数据通过第一映射到一些特征空间，在输入空间详细 地产生非线性的判别。算法描述如下： 输入：特征空间上的非线性映射 输出：低维嵌入y _ 秒j ，y 2 ，m q 时 l 最大伽w ) = 器。 w 6 妒 2 获取训练模式的点积( ( x ) ( y ) ) 。 3 获取w 的扩展形式w 7 矿= 言蔷t 荟1 , 哆尼( t ，) = 口r m 。 4 定义矿和相似的转化，寻找w 7 s w - - 口r n a 。 5 通过最大化， ) = i c t r 巧m 函a 寻找在f 中的f i s h e r 线性判别。 k f d a 不要求数据具有线性特点，所以能解决更广的数据。但是k f d a 在解决问题 时候用到了所有的训练样本，而不是像s u p p o r tv e c t o r s 那样只是最困难的样本。 1 2 4 等距映射( is o m a p ) i s o m a p l l 7 】建立在多维尺度变换( m d s ) 的基础上，力求保持数据点的内在几何性质， 即保持两点间的测地距离。它用流形上的测地距离代替经典m d s 方法中的欧氏距离。 该算法的核心，也就是估计两点间的测地距离的方法是： ( 1 ) 离得很近的点间的测地距离用欧氏距离代替； ( 2 ) 离得较远的点间的测地距离用最短路径来逼近。 如图1 - 2 所示，( a ) 中样本分布于s w i s s - r o l l 上，两点间的欧氏距离( 虚线所示) 不能表征两点间的实际距离，( b ) 中分布于流形面上的曲线是两点的测地距离，( c ) 是i s o m a p 降维后两点和两条路径( 测地线和短程拼接) 的投影结果。 4 一种同i 茸边缘学日算法丑其应用研究第一章绪论 输入：样本输入x ：f x l , x 2 , 一肌e 删，样本真维数d 邻域参数k 输出：低维嵌入y - f y l , y 2 , 一y n c - g d l 计算每个点的近邻点( 用k 最近邻或e 球邻域) 。 2 在样本集上定义一个赋权无向图，如果一，和盯互为近邻点，则边的权值为 d x h ，j j t 3 计算图中两点问的最短距离，记所得的距离矩阵为d 。= d 。( i ，j ) 。 4 用m i ) s 求低维嵌人流形，令 s = ( ) = ( o ；) ，h = ( h 。) = ( 吒一l n ) tr ( d ) = 一h s h 2 ， 低维嵌入是f ( d ) 的第2 小到第d + l 小的特征值所对应的特征向量。 l s o m a p 的特点是：该算法是非线性的，适用于学习内部平坦的低维流形，但不 适于学习有较大内在曲率的流形。i s o m a p 算法中与l l e 算法一样有两个待定参数d 和k 。i s o m a p 算法也存在一些明显的缺陷，该算法需要计算图上两点间的最短距离， 执行起来比较慢；它用于可视化会有不稳定的现象，取较大的邻域会产生短路线现象， 而取较小邻域部分的点投影后，虽然能够保证整体结构的稳定，但低维投影结果会产 生大量“空洞”，或使最短路径算法重构的图不连通。 第一章绪论 种同调边缘学目算法& j 应用研究 1 2 5 局韶线性嵌入( l l e ) l l e 算法【”吼为在局部意义下数据的结构是线性的，或者说局部意义下的点在 一个超平面上。因此任耿一点，可以使用它的邻近点的线性组合来表示。图卜3 中b 的三维数据由a 中的二维流形采样而来，彩色带表明了l l e 映射处理后保留的邻域带 情况。b 与c 中用黑线圈出了单个点的邻域部分。 l l e 算法描述如f 图卜3l l e 的基本思想 输入：样本输入肛血鸩jx n e r d j ，样本真维数d 邻域参数k 输电：低雏赦入y = d 】y 2 y n g r d l 计算每个点的近邻点( 用k 最近邻或e 球邻域) 。 z 眠= 至备谢吼一咿限训吩燃 使得酊把x 用它的个近邻点线性表示的误差晶小，即通过最小化怔一w i x ，0 来 球出i 如 3 保持权值哪不变，求朋在低维空间的象，j ，使得低维重构误差最小。 虽小化嵌入成本函数为y 一、v i 】y j f 。 m = ( i w ) 7 ( i w ) ，低维嵌入是m 的最小的第2 到第d + 1 个特征向量。 l l e 算法可以学习任意维的局部线性的低维流形，它的待定参数很少，只有系数 一种同调边缘学习算法及其应用研究第一章绪论 d 和k 。l l e 算法中每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的，并 且有解析的整体最优解，不需迭代。l l e 算法归结为稀疏矩阵特征值计算，计算复杂 度相对较小，容易执行。但l l e 算法要求所学习的流形只能是不闭合的且在局部是线 性的，要求样本在流形上为稠密采样，参数d ，k 有过多的选择且对样本中的噪音很 敏感。 1 2 6 拉普拉斯特征映射( l a pla cia neig e n m a p ) l a p l a c i a ne i g e n m a p 1 9 】的基本思想是在高维空间中离得很近的点投影到低维空间 中的像也应该离得很近，最终求解归结到拉普拉斯算子的广义特征值问题。其算法描 述如下： 输入：样本输入炸扛l ，x 2 ，粕胪 ，样本真维数d ，邻域参数k 输出：低维嵌入卜钞l ，妮，) 1 计算每个点的近邻点( 用k 最近邻或8 球邻域) 。构建一个近邻图，图的顶点 为样本点，离得很近两点用边相连。 2 给每条边赋予权值。如果第f 个点和第，个点不相连，权值为d ，否则w ：1 。 3 计算图拉普拉斯算子的广义特征向量，求得低维嵌入。 令d 为对角矩阵口。= ，w f i ，l = d - w ，是近邻图上的拉普拉斯算子，求解广 义特征值问题l f = 五d 厂。 ， l a p l a c i a ne i g e n m a p 的特点是：它是局部的非线性方法，与谱图理论有很紧密的 联系。其算法中同样只有两个参数k 和d ，通过求解稀疏矩阵的特征值问题解析地求 出整体最优解。算法使原空间中离得很近的点在低维空间也离得很近，所以可以用于 聚类。 1 2 7 局部切空间排列( l t s a ) l t s a 算法1 2 0 1 的基本思想是利用样本点邻域的切空间来表示局部的几何性质，然 7 第一章绪论一种同调边缘学习算法及其应用研究 后将这些局部切空间排列起来构造流形的全局坐标。其算法描述如下： 输入：样本输入x = x 1 ，x 2 ，x n r d ) ，样本真维数d ，邻域参数k 输出：低维嵌入y = y 1 ，y 2 ，y n r d ) 1 计算每个点的近邻点( 用k 最近邻或球邻域) 。 2 局部线性投影。对每个样本点的邻域，计算中心化矩阵x ；一叉。的最大d 个奇 异值对应的右奇异向量，并将这d 个右奇异向量组成矩阵玎。 3 局部坐标系统的排列。构造排列矩阵i ：l 一。n s i w w t 譬，计算痧的最小d + 1 个特征值对应的特征向量u l ，一，u 。，则t = u ：，ud + l ，t 为计算的嵌入结果。 l t s a 算法能够有效地学习体现数据集低维流形结构的整体嵌入坐标，但也存在 一些不足，算法中的用于特征值分解的矩阵的阶数等于样本数，样本集较大时将无法 处理，且算法不能有效的处理新来的样本点。针对这些缺点，杨剑等提出一种基于划 分的局部切空间排列算法( p a r t i t i o n a ll o c a lt a n g e n ts p a c ea 1 i g n m e n t ，p l t s a ) ， 它建立在v q p c a 算法l t s a 算法基础上，利用x 一均值算法把样本空间划分成一些相互 有重叠的块，通过把样本点投影到他所在的局部切空间上得到其局部低维坐标，对局 部低维坐标施加平移、旋转、伸缩变换，求出整体低维坐标。 p l t s a 算法的基本步骤如下： 输入：样本集x 、低维嵌入空间的维数d 、重叠参数或者1 ，划分块数的上下 界 输出：低维嵌入坐标t 、投影方向q 、选择矩阵s 、权值向量v 、仿射变换矩阵l 、 重叠部分中点的局部坐标 1 用x 一均值找到x 的t 个中心。 2 把x 划分成有重叠的t 块x = m iu m i 。 3 对每一个x i 进行局部主成分分析，求得局部坐标秒。 4 对于重叠部分m i 中的点，其整体坐标t 由属于b 的第2 个到第d + 1 个最小特 征值的特征向量给出。 8 一种同调边缘学习算法及其应用研究第一章绪论 5 对于m7 中的点，其整体坐标为t = t s i v i + t i ( i o ) o ? 饼( x 一誓) 。 6 对于新来的样本点x ，找到离它最近的中心m ，其整体坐标为t = t = t s i v i + t i ( i o ) o j 彰( x 一薯) 。 1 3 边缘学习算法 边缘划分可以分为数据划分和图像划分。目前主要的边缘学习算法有t v q 算法 【2 1 】、c a n n y 算法【2 2 1 、i 也m c 算法【2 3 1 等。 1 3 1 切线矢量量化算法( t v q ) t v q ( t a n g e n tv e c t o rq u a n t i z a t i o n ) 21 1 ，在这个算法中，f a b i oa i o l l i ，a l e s s a n d r o s p e r d u t i 提出了一个对提升边缘问题的很好的方案，这方案是建立在边缘理论原则上。 是基于样本加权策略，基本思想实际是增加训练集的样本新复制，并且样本是在足够 边缘下没有分类。 作为学习例子，f a b i oa i o l l i ，a l e s s a n d r os p e r d u t i 提出了这个算法，也就是预计 划的实例，并且包含了基于1 - n n 分类器的切距离。1 - n n 分类器实现了一种切距离 原型的量子化。用这种方式创造的切距离模型在概化能力上有明显的改进，这概化能 力是源于标准切模型。更进一步，已经获得的模型比其他算法具有更好的优势，比如 在o c r 任务中的s v m 算法。 输入：丁：迭代次数；q ：每类的模式个数；口：边缘临界值 输出：w 1 初始化：w ( 1 ) - n ，以卜万1 ；对任意的y ，g ，在随机模式里， m 7 卜( 。- , ，( q ) ，丁，。 f o rt = l ，t 砂，v q ，肼? = o 9 第一章绪论一种同调边缘学习算法及其应用研究 该方法和s v m 方法进行比较，可以观察到，当此方法和s v m 方法具有从经验 风险到理想风险中一致收敛的统计学习理论概念时，该方法将输入分布直接工作在非 线性模型上而不是采取预定于核。这种方法非常类似于采用b o o s t i n g 算法的方法，然 而，在b o o s t i n g 算法中，更加关注独立假设。因为乘法策略更适合于交换机。 1 3 2 规则化大边缘分类器( r l m c ) 在经典大边缘分类器上的边缘临界值处添加一个规则项( 在类分散中) ，当组类 分散到达最小值时，映射特征矢量能达到最大值2 3 1 。 输入：数据集包含两类样本 x i ，y i ，x j r ”，咒 + l ，- 1 ) ，表示类标记 输出：w 1 根据f i s h e r 判别准则，修正已存在的l m c 的目标函数，通过添加规则项， 组类散射产生新的目标函数。 2 通过添加规则项，将m 砌，( 叻= 扣叫j 2 = 三矿w 。f善咒q = ”q o f = 1 n s f 。l“i 。” 变成 搬觑，( w ) 。圭( 2 + r l w r & 叻 s t 。 y , ( w r x j + 功l i = 1 ，n 3 上面式子将训练样本的两类映射到方向上获得新模式，通过添加规则项， 上式能在组类散射最小的时候，能达到最大边缘。 1 0 一种同调边缘学习算法及其应用研究 第一章绪论 1 芒 确2 万备_ 川，2 4 计算所有的组类散射矩阵和类内的训练样本的平均矢量，特别是当r 0 ，露是 一个权值能控制边缘的平衡和组内离散。 r l m c 方法能在时间变化，光照条件变化的情况下在人脸识别实验中取得不错的 效果。通过已有的分类器将训练样本映射到已经获到的矢量上。 1 3 3 基于边缘马尔可夫随机场和波尔兹曼机的边缘检测算法 一般的边缘检测依据于图像灰度的不连续性，包括表面拟合和边界跟踪等方法， 然而很多边缘检测算法仅仅关心灰度信息，对噪声较为敏感。t a n l 2 4 1 将边缘检测问题 转化为一个全局优化问题，不仅考虑到灰度变化信息，而且考虑到了局部边缘结构。 该算法通过基于边缘检测算子的初始化边缘检测以及基于波尔兹曼机的模型参数估 计，最后利用波尔兹曼机的边缘松弛搜索算法。 输入：数据集包含两类样本 x i ，以) ，毛r ”，只 + 1 ，一1 ) ，表示类标记 输出：形 基于边缘检测算子的初始边缘检测。 p = q 。，if ，三) 表示边缘检测算子根据灰度图像z 获得的响应强度。采用微分算 法，只得到边缘检测只依赖于灰度信息。 。 一f l 若p ( z , j i 西j = 1 ) p ( z j ，j i 再j = o ) ) f ，- ，一i o 若p ( 刁，j i 弓= 1 ) _ p ( 弓i 而，= o ) 基于波尔兹曼机的模型参数估计。 用初始边缘检测结果作为学习样本，根据波尔兹曼机的学习规则，要估计这样的 参数吼使得p ( s ) 达到最大。将参数估计问题转化为一个全局最优化问题。 基于波尔兹曼机的边缘松弛搜索算法。 由于采用2 4 邻域系统，当边缘断裂距离超过5 * 5 邻域算法时候，搜索算法难以 第一章绪论 一种同调边缘学习算法及其应用研究 对其处理，可以采用更大的邻域系统，但是会增加算法复杂度。 该算法的局限性：由于学习算法的学习样本是初始边缘检测结果，虽然具有一定 的容错性，但当噪声过多的时候难以进行。由于学习算法只能获取最主要的局部的边 缘特征，因此该类算法具有一定的局限性，只对边缘具有一定规律性( 指某些局部边 缘特征较为明显) 的图像效果比较好，更适合纹理图像的边缘检测。改进方案是利用 标准学习样本进行参数估计，并且应用于非学习样本，但是学习样本和非学习样本必 须是同一类图像。 1 3 4 基于资格函数的模糊边缘检测算法 传统的图像边缘检测模糊算法，简称为p a l k i n g 算法【2 5 1 。其过程是： ( 1 ) 用隶属度函数将图像f ( x ，y ) 映射成模糊隶属度矩阵g ( i ，歹) 。( 2 ) 对属度矩阵 g ( i ，) 进行多次非线性变换z ，以增强边缘信息，弱化非边缘信息。( 3 ) 对模糊隶属度 矩阵g ( i ，) 进行反变化，从而得到经过增强图像。( 4 ) 用“m i n ”或“m a x ”提取边缘a 但是这类算法存在很多不足之处，因此在此基础上进行改进，在原始图像的基础上引 进资格函数，同时完成从图像到隶属度矩阵的转换以及增强边缘信息的变换，使计算 量大大减少，同时动态调整阀值，以适应不同类型图像及不同用户的要求。 1 阀值口的初始化。 2 调整口值。 口= ：曼署 3 引进资格函数，比如z a d e h 的s 函数，对原图像进行进一步的归化和增强处 理。 进行反模糊变换的公式x m = ，。p p ) 可易, ，z 。，1 0 增强后的图像。 使用“m i n 或“m a x ”提取边缘。 1 2 一种同调边缘学习算法及其应用研究第一章绪论 1 4 问题的提出 综上所述，目前在晶体数据分析方面已有了许多成熟的方法，但从物理学家广泛 使用同调论来分析晶体数据的启发下，针对晶体数据的边缘划分等问题，引进同调论 思想从机器学习角度来研究边缘划分学习新方法，应该是一条行之有效的通路。同调 代数源于代数拓扑学的一个分支。2 0 世纪4 0 年代，代数拓扑学的一些概念和方法被 引进到纯代数的领域，形成了系统的理论，进而发展成为同调代数，它的兴起对群、 李代数等的研究都起了非常重要的作用。关于这方面的工作，李凡长教授及其李群机 器学习研究小组从2 0 0 4 年开始这方面的研究工作，提出了“李群机器学习( l i eg r o u p m a c h i n el e a f i n g ，简记为l m l ) ”的概念并建立了起其本理论框架【2 6 。1 1 ，并取得了一 系列的成绩。因此本文基于这些想法做进一步的研究，提出“一种同调边缘算法及其 应用研究 的硕士论文题目。 1 5 内容安排 本文的研究内容分为六章： 第一章主要介绍晶体数据分析、数据约简和边缘学习划分等方法。介绍了晶体数 据的特点以及研究晶体的重要性。在介绍数据约简方面，着重介绍了核方法和流形方 法，并且给出了每种方法的优缺点。同时对边缘划分方法进行了汇总。 第二章介绍晶体数据结构分析方法，目前的研究晶体识别的处理技术主要有电子 衍射强度的经验校正方法与晶体相位扩展处理技术，以及高分辨像的最大熵解卷处理 技术与晶体学图象处理技术。 第三章给出了同调边缘学习算法，分别是同调边缘划分算法，胞腔同调边缘划分 算法，正则胞腔同调边缘划分算法。 第四章给出同调边缘边缘划分算法和上边缘同调学习算法，上同调边缘学习算 法。 第五章给出了实例应用。分别应用到鸢尾花分类实例、晶体点群分类实例和晶体 结构预测和分类实例中，并和其他算法进行比较分析。 第六章结论与展望。 第二章晶体数据结构分析 一种同调边缘学习算法及其应用研究 第二章晶体数据结构分析 物理学中，晶体主要研究它的宏观物理性质和对称性之间的关系，晶体的宏观物 理性质是以晶体微观物理性质为基础的。理想晶体是晶体研究的入手点，理想晶体中 的全部结构基元在空间上的排列具有周期性。晶体分类的步骤如下：1 晶体观测数据 的选择；2 根据观测数据构造相应的群；3 构造相应的分类器( 范例系统) ；4 。数据测 试；5 结果分析和相关算法比较。 中国科学院物理所李方华院士等提供的v e c ( v i s u a lc o m p u t i n gi ne l e c t r o n c r y s t a l l o g r a p h y ) 系统，对疋0 1 7 脯毫绣、巩( 1 7 5 三嘞彩) 8 白5 9 、恐髑1 7 哦5 、 b i 2 ( s r o 9 上1 ) 2c d q( 确+ 5 虢- 3 c 2 ) 职( c a s r o 4 ) c u 2 q ( t o 6 c a o 4 ) ( s r b a ) ( c u o 5 b o 5 ) 0 7 一，六种晶体进行分类验证3 2 ，3 3 3 引。范海福院士等入对晶体 结构的电子晶体学进行研究3 5 4 2 1 。下面就具体晶体的数据结构介绍如下； 2 1 b i 。( s r o 乃l a 。2 5 ) 。c u s o y 晶体结构的判定 b i 。s r s c u s o y f 4 3 1 是在及q 5 一s r o - c u o 系统中已经发现的三种非超导性相位之一 的晶体。它的空间群是f m m m ，其中z = 8 ，晶胞参数为a = 0 5 3 7 3 ( 2 ) r i m ，b = 2 3 9 6 6 ( 4 ) n m ， 并且c = 3 3 9 0 7 ( 6 ) n m ，这个结构是由于它本身的可公度调制，和超导b i 一2 2 0 1 相位相 比较，这仡合物的主要结构特征是电双层的击穿，这击穿是由钙钛矿层垂直叠加在 艿f d 层。当跏原子部分被l a 原予替代，晶体变成以c 为中心的斜方晶结构，其空 间群是c c c a 。然而，结构仍然保持着可公度调制并且l a t t i c e 参数并没有改变太多， 它们是a - - 0 。5 3 9 n m ，b = 2 ，3 5 n m ，c = 3 。4 0 n m ，在电子显微镜j e m - 1 0 0 0 下操作，加速电 压为1 0 0 0 k v 下，并且f o l d e d 曝光时间，比如l 、2 、4 、6 4 秒。一系列的相应的 高分辨率电子显微镜图像是通过用j e m - 2 0 0 点在显微镜在2 0 0 k v 下操作。其中聚焦距 离大约是1 2 n m 球差( 球面像差) 系数。目标透镜的球面像差系数是0 5 n m ，并且电 子显微镜的分辨率是0 1 9 4 n m 。 1 4 一种同调边缘学目算法其应用研究第二章晶体数据结构分析 将晶体结构检测分为图像卷积和相位扩展两个步骤。在图像卷积中，将用于试验 中的未聚焦的图像在a 轴上进行映射。内集是相应的1 0 0 0 k v 的电子衍射模式。映射 结构的对称性是p 2 m m ，映射单元晶格的大小为23 5 34 0 h m 2 ，并且可以被分为四个相 同大小的亚晶胞，大小为11 8 + 17 0 n m 2 。将原始图像通过傅立叶过滤和对称平均后得 到新的图像。 圈2 一i 两个试验【1oo 】岛分辨阜电子显微镜图像在聚焦差别在 2 4 r m l 内。内集是在加速电压1 0 0 0 k v 下的相应的电子衍射模式。 恻2 - 2 将图2 - 1 进行噪声过滤和对称平均后的亚晶胞 第= 章休数据鲒构分析种q 调边缘学日算往其应用 究 b 圈23 ( a ) 图是乩图22 ( a ) 中在散焦一4 8 n 巾和分辨率在02 r i m 下得到的卷 积。( b ) 图是从2 - 2 ( b ) 图中在散焦? l n m 和分辨率在02 册下得卷积。 其中矩形代表了弧晶胞。 舔j藤i 圈24 投影结构模型表示了重原子的位置。( b ) 幽模仿了重原子的潜在映 射，分辨率为02 r i m 。有白色点的黑色点阵是由于截断效果引起的。 一种同调边缘学习算法及其应用研究 第二章晶体数据结构分析 2 2 机器学习方法的应用 目前用于测试聚合体分子量的方法即】，包括分层聚类，决策树，支持矢量机， b a g g i n g 这些算法都被用来构建模型去预测聚合体的分子量。组合触媒剂聚合体是由 9 6 种齐次触媒剂产生的。学习的目的是发展模型，并且可以被用于过滤很多重要的 触媒剂库以获得将来合成和筛选的候选物。描述符是用来表示那些不需要触媒剂详细 信息的触媒剂。这些描述符可以只用拓扑配基计算。用初始化的五个描述符，模型可 以精确到7 0 ，这个结果是从每个机器学习中发现观察到的。有十个描述符的描述符 集遵循b a g 分类器的可以构造到8 0 的精确度。所有的模型都被精确计算到检测过 渡拟合中，并且举例了过度拟合的例子。因为在这种学习方法中所用到的描述符可以 被迅速的计算，所以模型是有效。这些b a g 分类器非常适应于过滤大型重要数据库。 当选择五个描述符的时候，由触媒剂产生的聚合物的分子量是本文关心的问题， 因为关心的是分类( 相反是回归) 模型。已经观测的m w ( 分子矢量) 值在分界线 1 0 0 k 的地方分成两组。分割让数据集很少平衡，5 3 或者5 5 的配基产生低m v 聚 合物，相比之下4 3 的配基产生高m v 聚合物。 最初的描述符是相对比较小的，只包含五个描述符：g a s t o ，g a s t n ，c h i 3 n ， s u r t 3 o ，s u r f 3 n 。对用描述符集1 的模型进行统计分析，意味着一些配基被一直错 误分类，这些配基的群，他们中的每一个是被多余2 3 的模型忽虑的。毫无惊讶，被 找到的同样的化合物是和不同活性的配基是相似的。被用到的描述符不能充分描述这 些化合物并把它们从相邻化合物中区分出来。 在不同的复杂性中不同的算法比如k n n ，b a g g e d 决策树获得了相同的精确度，有 理由相信，任何学习算法不大可能在描述符集合1 上做的更好，为了更好的提高精确 度，必须扩大描述符去处理现在的描述符不能处理的分类。 当用十个描述符的时候第二组描述符集是从第一组描述符中扩展了额外的五个 描述符：c 1 1 i 4 n ，k a p p a 3 ，e s t a t en ，e s t a t eo ，b e r t z c t 。 1 7 第二章晶体数据结构分析一种同调边缘学习算法及其应用研究 图2 - 5 在簇树中展示有不同活性值的化合物 用一组非常有效的描述符去描述配基，可以构建很多精确的预测化合物分子矢量 的模型。这些化合物是由同质触媒剂产生的，尽管数据集相对比较小，通过精心的分 析，混洗测试的利用，无论是保持数据还是o u t o f - b a g 错误估计，这些决定预测不是 数据过度拟合的结果。描述符是单独从配基的二维结构中导出。毫无疑问，化合物本 身结构的属性是可以用来构造这些方法。 这些数据一旦被训练，b a g 分类器，决策树，k 近邻等方法的速度是非常快。任 意输出可以确保预测模型本身在实际数据库筛选中并不变成瓶颈。在b o x 和d r a p e r 的引用中，尽管设计的很多模型被认定是错误的，b a g 分类器的精确性，以及模型和 描述符的有效性，可以得出结论：这些模型是有效的。因此可以迅速地筛选大型实际 数据库，并且对合成物和筛选提供候选。 2 3 三维不定空间中晶体群的分类 在空间矿中讨论与形关联的晶体群的分类是一个有趣的问题【4 5 】。需要做以下两 个方面的工作：( 1 ) 找出所有的矽不变格a 。( 2 ) 计算第一上同调群胃1 ( 矽，v a ) 。当 矿是一个n 维欧式空间时，点群渺为w e y l 群的晶体群的分类问题已有m a x w e l l 解决； 当v 是一个n 一维不定空间，是某个不可约根系的无限w e y l 群，而且其d y n k i n 图 是单边连接( 即所有子图皆是形如a ，x 4 x 4 ，4 ，呜，皿型的有限型子图) 时， 李解决了这方面的问题；当v 是2 维不定或仿射空间，是某个不可约根系的无限 w e y l 群时，该问题也得到解决。 1 8 一种同调边缘学习算法及其应用研究 2 3 1 形一不变格的确定 第二章晶体数据结构分析 定理2 3 1 设y 是3 一维不定空间，= ，口2 ，口3 ) 是它的一组基。若人是中v 中 w 不变格，则存在唯一的一组正实数 岛) ，便得人