改进的内容相似性（精选10篇）
改进的内容相似性 篇1
时间序列是指按时间顺序排列的一种数据,在“时间序列”这一学科所研究的范围内,广义地指组有序的随机数据[1]。一般来说,时间序列的相似性搜索可以分为两类:全序列搜索和子序列搜索[2]。
在判定两时序的相似度上还会遇到一些问题,如高频噪声、时间轴上伸缩等,对于这些问题已提出很多算法,如离散傅立叶变换[3],离散小波变换[4],滑动平均聚集近似方法[5]等。笔者引用时间序列分段表示思想,以某省电力公司ERP系统业务量统计数据为研究对象,提出一种快速相似性搜索的优化算法。
1 时间序列相似性度量
相似性度量是衡量两个序列相似性的依据,是相似性查找的基础,下面分别从时间序列距离度量和时间序列分段表示来介绍。
1.1 时间序列距离度量
1.1.1 欧式类距离
给定两个时间序列,X(X=n),Y(Y=m),当n=m的,它们之间的Euclidean距离定义为
1.1.2 PLR常用距离
一个时间序列,将其线性分割为K段,用大写字母A来表示:A={AXL,AXR,AYL,AYR,AW}。对于第i段Ai,Ai=(AXLi,AXRi,AYLi,AYRi,AWi)分别为第i段的起点横坐标,起点纵坐标,终点横坐标,终点纵坐标,第i段的权重。则距离D(A,B)定义为
1.2 时间序列分段线性表示
时间序列分段线性表示(PLR)是将时间序列数据基于时间表示成多段相邻的近似直线。在数据挖掘领域,PLR表示已经在下面一些领域得到应用:一是支持快速相似性搜索;二是支持时间序列新的距离度量,包括模糊查找、加权序列、DTW距离、信息反馈等;三是支持文本和数据序列。
2 算法描述
2.1 S7算法及其改进算法
基本搜素算法的本质就是搜索时序Q沿着被搜索时序R滑动,当Q与R中子序列相匹配时计算其相似距离。Eamonn Keogh曾提出的S7算法,有效地解决了效率和时间轴方向的伸缩问题。但是,S7算法的执行效率较低,大部分时间都在构造表,因此,王晓晔等人在其基础上提出了计算两个不等长序列相似性算法,但该算法在排列组合时间序列倾角上花费了大量时间,为此笔者在降低此算法的时间复杂度方面作了一些研究,提出了一种快速搜索算法。
2.2 快速搜索算法
输入数据。时间序列S1和S2,伸长和收缩范围ε≧0,相似性距离§≧0。
输出数据。若相似,则输出相似子序列的起始点和相似性距离。
算法描述。步骤1:比较S1和S2的长度,较长的标记为R(长度为M),较短的标记为Q(长度为N);R和Q的倾角相应地标记为r和q。步骤2:标记出Q两端的端点位置,左端子段记作QL,右端子段记作QR,计算RR和RL的时间差,当两者的时间差刚好等于N时,记录此子时间序列为Rs。步骤3:计算最大伸长和收缩角QL和QR,基于以下公式:θmin=θ-ε,θmax=θ-ε;标记其为(q Lmin,q Lmax)和(q Rmin,q Rmax)。将Rs中满足此范围的记作Rm。步骤4:计算Q和Rm的相似性距离,如果相似性距离小于§,则输出D及R中Rm的起点,否则输出“NULL”。算法示意图见图1。
3 应用实例
以某省电力公司下属各供电及超高压公司ERP系统的人力资源模块维护员工工资业务的业务量统计数据为例,使用ABAP开发平台,采用本文提出的算法进行相似性搜索数据挖掘。该实验中记录业务量数据482个,经分段处理,划分成31个子段,所有子段直线的倾斜角集合为R;搜索时序Q有5个子段,直线倾斜角集合为Q。设ε=3,§=5,实验结果见表1。
表1中C1,C2,C3,C4,C5指该电力公司下属的5家公司,由表1可以看出,C2和C3的业务统计数据和C1相似,C4与C5相似。由于C1和C2这两个公司的业务发生时间及业务量的起伏相似,可以认为其在人力资源管理上的管理方式也是类似的。这样,当其中一家公司改进业务管理方法,就可以被与其他相似的公司所借鉴。
4 结束语
对时间序列数据挖掘的研究越来越受到重视,其在金融分析和科学实验分析等方面的应用也越来越广泛。笔者基于S7算法的思想,对时间序列的相似性搜索算法提出改进,克服了以前此类方法在时间复杂度上的不足,实验过程中表现比较好的性能。
摘要：针对时序数据进行相似性挖掘方法的研究,提出一种寻找已知序列的所有相似性子序列的方法,用该方法对数据模拟,结果表明该算法提高了查询性能。
关键词：相似性挖掘,时间序列,数据挖掘
参考文献
[1]杨叔子,吴雅.时间序列分析的工程应用[M[.武汉:华中理工大学出版社,1991.
[2]FaloutsosC,Ranganathan M,ManolopoulosY.Fast Subse-quence Matching in Time SeriesDatabases[C]//Proceedings of ACM SIGMOD,1994.
[3]Agrawal R,FaloutsosC,Swamia.Efficient similarity search in sequence databases[C]//Proceedings of4th International Conference on Foundations of Data Organiza-tion and Algorithms.Berlin:Sp ringer2Verlag,1993:69-84.
[4]Chakrabarti K,Ortega-Binderberger M,Porkaew K,et al.Similar Shape Retrieval in MARS[C]//Proceedings of IEEE International Conference on Multimedia and Expo.Berlin:Springer-Verlag,2000:709-712.
[5]Yib K,FaloutsosC.Fast TimeSequenceIndexing for Arbi-trary LP Norms[C]//Proceedingsof the26th International Conference on Very Large Databases(VLDB).Cairo,Egypt:Morgan Kaufmann,2000:385-394.
改进的内容相似性 篇2
职业院校开展教学工作诊断与改进既是深化落实《决定》的重要举措，也是新形势下加快发展现代职业教育的战略选择。“通知”从战略高度阐述了开展教学诊断与改进的原因、内容和流程设计，为职业院校教学诊断与改进工作指明了方向。
职业院校教学工作诊断与改进的内容，“通知”明确了10大要素。一是办学方向，这是人才培养工作的前提；二是办学定位，这是人才培养工作的指南；三是人才培养目标，这是人才培养工作的依据；四是专业设置与条件，这是人才培养工作的基础；五是教师队伍与建设，这是人才培养工作的条件；六是课程体系与改革，这是人才培养工作的抓手；七是课堂教学与实践，这是人才培养工作的重点；八是学校管理与制度，这是人才培养工作的保证；九是校企合作和创新，这是人才培养工作的关键；十是质量监控与成效，这是人才培养工作的保障。
（一）诊断与改进须完成的五项任务 1.理顺工作机制
“通知”要求依据一个方针，建构包括三项具体内容的工作机制。一个方针就是“需求导向、自我保证，多元诊断、重在改进”的工作方针；三项内容就是职业院校人才培养工作状态数据，学校自主诊断与改进，教育行政部门根据需要抽样复核；工作机制就职业院校持续提高人才培养质量的机制。2.落实主体责任
“通知”要求职业院校要切实履行好人才培养工作质量保证主体责任，为此要做好三项工作。一是建立常态化周期性的教学工作诊断与改进制度，为职业院校人才培养主体责任的落实奠定制度基础；二是开展多层面多维度的诊断与改进工作，为主体责任的落实奠定工作基础；三是构建校内“三全”（全员、全过程、全方位）质量保证制度体系，为主体责任的落实奠定组织基础。3.分类指导推进
“通知”从提高教学工作诊断与改进的针对性和实施效果出发，分别明确了中等职业学校和高等职业技术学院各自的诊断重点。对于中等职业技术学校来说，因为统一的国家层面上推进人才培养质量提升的具体措施尚属首次，故其教学工作诊断与改进的重点是保证学校的“三个基本”，即基本办学方向、基本办学条件、基本管理规范。高等职业技术学院可根据发展的不同阶段所面临的不同任务，确立不同层面的诊断重点，一是保证履行办学主体责任，建立和完善学校内部质量保证制度体系；二是集聚优势、凝练方向、提高发展能力。4.数据支撑系统
为提高教学诊断与改进的科学性和准确性，“通知”要求职业院校要充分利用信息技术，做好三方面工作，一是建立校本人才培养工作状态数据管理系统，为教学工作的诊断与改进建构技术基础；二是及时掌握和分析人才培养工作状态，为教学工作的诊断与改进建构工作基础；三是依法依规发布社会关注的人才培养核心数据，为教学工作的诊断与改进建构动力基础。5.试行专业诊改
由于专业教学诊断与改进，涉及面比较广，且不同的专业有其不同的特质要求，故“通知”提出试行要求，鼓励相关行业与院校联手进行试点，同时对试行提出了五点要求，一是要求由对企业有较大影响力的行业牵头；二是以行业企业用人标准为依据，设计诊断项目；三是以院校自愿为原则，不强求所有职业院校都参加；四是要求通过反馈诊断报告和改进建议的方式，反映专业机构和社会组织对职业院校教学质量的认可程度；五是形成倒逼机制，即职业院校依据社会对其教学质量的认可程度，进行专业改革与建设。
（二）诊断与改进的三项工作要求 1.完善组织保证
为将教学诊断与改进工作落到实处，“通知”要求建构部、省两级教学工作诊断与改进专家委员会。一是部级专家委员会，主要任务是研制指导方案、政策咨询、业务指导，另外还负责教育部委托的相关工作；二是省级专家指导委员会，负责本省教学诊断与改进工作。2.加强省级统筹
“通知”明确提出职业院校教学工作诊断与改进的主体是省级教育行政部门，其工作职责主要是三点。一是制定本省教学诊断与改进工作规划；二是根据教育部总体指导方案制定本省（区、市）工作方案、细则和实施规划；三是组织和检查本省区域内职业院校诊断后的改进情况。另外，由于中等职业学校数量众多，而且办学情况比较复杂，故“通知”提出可由省级教育行政部门委托地（市）级教育行政部门组织实施。3.确保公开透明 为保证职业院校教学工作诊断与改进能取得实效，在推进职业院校人才培养质量提升工作中发挥应有的作用，“通知”提出加强管理的要求。一是要求相关组织机构、职业院校和专家要增强责任感、使命感，自觉遵守工作规则规程，规范工作行为；二要建立职业院校教学工作诊断与改进的信息公告制度，要求提高工作的透明度，将相关政策、文件、方案、标准、程序以及结论等均在适当范围内公开，接受教师、学生和社会各界的监督。
二、职业院校如何积极参与教学工作诊断与改进
职业院校教学工作诊断与改进是新形势下促进人才培养质量提升的新举措，是职业院校建构人才培养质量自主保证制度的新尝试。职业院校是教学工作诊断与改进的主体，良好的顶层制度设计能否得到贯彻，意图能否得到实现，效果能否得到体现，处于一线的职业院校具有决定性的作用。职业院校对教学工作诊断与改进的认知、态度和实践情况，决定了职业教育顶层设计的制度能否得到落实以及落实的程度，理性的职业院校必须做好充分准备。
第一 认真学习深刻认知教学工作诊断与改进对促进职业院校可持续发展的积极作用。第二 更新理念牢固建构职业教育教学工作的问题意识。所谓问题就是理想与现实、目标与结果之间的差距。第三 夯实基础建构教学工作诊断与改进的校本制度和工作机制。第四 培养队伍夯实教学诊断与改进工作的人力基础，队伍是教学工作诊断的前提，也是教学工作诊断能够取得成效的保证。职业院校只有做好上述四方面工作，才能使教学工作诊断与改进做到常态化和周期性，才能真正发挥教学诊断与改进在提升教学质量、提高人才培养质量中的积极作用，才能实现自己的可持续发展。
改进的内容相似性 篇3
[关键词] 电子商務 推荐系统 协同过滤 相似度计算 数据挖掘
一、引言
电子商务推荐系统是模拟销售人员向网络客户推荐商品的系统，推荐精度的高低直接影响了用户的购买量，也影响着用户对该系统的信任度，信任程度的高低决定了用户对该系统的使用率，从而影响用户浏览实现了推荐功能的网站进行物品购买的次数。
当前的信息推荐技术主要有：协同过滤推荐、基于内容推荐、基于人口统计信息推荐、基于效用推荐、基于知识推荐、基于规则推荐。
二、协同过滤算法介绍
1.基于项的协同过滤算法介绍
基于项的协同过滤是通过相似度的计算，找出当前用户未评分项目的前k个相似项目，根据用户对这k个项目的评分预测当前用户对未评分项目的评分值,按照评分值大小进行推荐。推荐分为两个步骤:①找出当前用户（这里指系统进行项目推荐的对象）的未评分项目的相似项目;②根据每个未评分项目的相似项目评分预测当前用户对未评分项目的评分，根据预测评分的高低，推荐前N个评分较高的项目给用户。
（1）项目相似度的计算
计算方法主要包括三种方法:
①基于余弦的相似度计算
(1)
其中，表示项目i，j的相似性，和表示对于项目i和j存在有共同用户对此两项评分的分别的评分集合。
实际应用中，该公式存在如下问题：因为，数据稀疏性是协同过滤使用中遇到的一个问题， 尤其是推荐系统初次使用时，数据库中的用户评分极其稀少，所以在这种情况下，存在两个项目之间只有1～2个共同的用户，如果这1～2个共同用户对这两个项目的品质认为是无差异的，则用余弦相似性进行计算时得出的结果也是认为两者很相似。事实上，基于项目的协同过滤算法是认为如果绝大多数用户对两项目的感觉是无差异的，则证明这两项目具有相同的品质，那么具有相同品质的两项目对于待推荐用户来说也是无差异的。可是，当两项目只有一两个共同评分用户，项目相似性的计算仅仅是反映了这一两个用户所关注的项目特征在这两个项目中是否相同，而这一两个用户所关注的项目特征并不一定是待推荐用户所关注的特征，并且一两个特征的相似也不能真正反映两个项目之间的相似性。
②基于相关性的相似度计算
(2)
其中，U表示对项目i和j都有评分的用户集合，和分别表示用户u对i与j的评分，和表示集合U中所有用户对i和j评分的平均值。
相关性的相似度计算是将用户对项目i、j的打分看作是一个两个随机变量，通过计算两个随机变量分布的相似性得出两项目的相似性。
③调整余弦的相似度计算
(3）
其与余弦相似性不同在于：将不同用户的打分规模考虑进去，其中表示用户u的平均打分。余弦相似性没有考虑不同用户的打分规模会造成平均打分较高的用户对相似度计算作用大于其余用户，使得每个用户的打分对相似度计算的贡献率不相等，造成相似度计算不如调整余弦相似度的计算精确。
在实际应用中，在数据库中打分数据分布极其稀疏的情况下，调整余弦的相似度的度量也会遇到在余弦相似性计算中所遇到的情况，即当项目只有一两个共同评分用户，项目相似性的计算仅仅是反映了这一两个用户所关注的项目特征在这两个项目中是否相同，而这一两个用户所关注的项目特征并不一定是待推荐用户所关注的特征，并且一两个特征的相似也不能真正反映两个项目之间的相似性。另外，在进行算法精度测试试验中，发现调整余弦的相似度计算有出现分母为0的情况。在程序测试过程中发现，分母为0有两种情况：
a)两项目只有一个共同打分的用户，该用户对很少的项目打分且打分值相同，即且。这种情况，按照余弦相似性的思想，可以认为两项目的相似度值为1。
b)两项目有为数很少的共同评分用户,且出现或的情况。在这种情况下，调整余弦无法正确计算出两项目之间的相似度，因此在数据极其稀疏的条件下，不宜采用调整余弦相似度进行度量。
2.评分预测公式
（1）权重和法
(4）
其中，表示项目i和j的相似度，表示用户u对项目j的评分，n表示选出n个数目的最近邻项目。该预测公式适用于用户评分数目相当大的情况。（基于项目相似度计算经典算法）当用户评分数目较少的情形下，相似度的计算本身就不精确，而该公式对未评分项目的预测，完全依赖于不精确的相似度值选择的相似项目的打分进行预测，精度很低。
（2）线性回归法
目标项目i对应向量为，相似项目N对应向量为，则线性回归模型为(5)
其中，的值由目标向量与相似向量确定，为误差项。
三、基于项目相似度计算改进算法
在第2节中，提到余弦相似度和调整余弦相似度都会碰到的问题：当两项目只有一两个共同评分用户，项目相似性的计算仅仅是反映了这一两个用户所关注的项目特征在这两个项目中是否相同，而这一两个用户所关注的项目特征并不一定是待推荐用户所关注的特征，并且一两个特征的相似也不能真正反映两个项目之间的相似性。
基于上述问题，本节提出了对这两种相似度计算的改进公式。本节认为，两项目分别的评分用户越多，则这两项目的共同评分项目也应该越多，因为一用户对一个项目感兴趣且有打分，则他对该项目的相似项目也应感兴趣且应有打分。基于这种观点，本节对余弦相似度和调整余弦相似度公式进行改进，并用基于改进的余弦相似度公式和传统余弦相似度公式计算项目间相似性来进行实验。由于在第2节中提到在数据稀疏的条件下，调整余弦相似度公式计算中会遇到分母为零的可能，且对调整余弦相似度公式的改进与余弦相似度公式改进方式是相同，故可以认为基于余弦相似度公式和改进公式的对比试验结果可以代表调整余弦改进公式的改进效果。
1.改进的相似度计算公式
（1）改进的余弦相似度计算公式
(6）
其中，mutual_num为对项目i、j都评分的用户数目，item_num表示对项目i、j中任何一个有评分的用户集合的数目。
（2）改进的调整余弦相似度计算
(7)
2.本文提出的对基于项的评分预测的公式
（1）提出的评分预测公式
(8）
其中，为用户u所有评分的平均值，为i和j项目的相似度，n为选择前n个最近邻。当时，令。
（2）说明
①从用户对相似项目评分的相似性考虑，相似项目评分与该用户平均评分的偏差和预测项目的评分与该用户平均评分的偏差也相似。
②与基于向量评分不同在于：基于向量的评分只适合于评分数目十分大的用户，当用户评分数量小时，最相似的几个项目可能用户没有评分，因此导致预测精度降低；另外，当每个项目的评分数量很少时，项目相似性预测精度下降，使得预测精度降低，而本文提出的预测公式可以降低相似项目对预测项目评分的贡献率。
③在计算中若，即当用户u对相似项目j没有评分时，令，消除没评分时，的影响。
实验证明，在数据极其稀疏条件下，本文提出的预测公式有很好的预测效果。
四、实验过程及结果分析
1.数据来源
本文采用Movielens站点提供的数据集，该数据集包括943个用户对1682部电影的100000条评分，评分取值为（1，2，3，4，5）中任一个数，值越大说明用户喜好程度越高，每个用户至少评价了20部电影。
2.测试方法
本文随机抽取其中80000条评分作为训练集，剩余20000条数据作为测试集，分别采用余弦相似性（公式1）和本文提出的改进地余弦相似性（公式6）进行相似度度量，并都采用本文提出的评分预测公式进行预测。
3.评测标准
本文采用平均绝对误差MAE作为评测标准，它是常用的推荐算法质量评价标准。
(9）
num为算法评分项目数目，为基于算法预测的评分，测试集中用户原始打分。
4.试验结果
图
五、结论
从上图可以看到，本文提出的改进算法的精度明显优于传统算法，这证明改进的余弦相似度计算方法比传统余弦相似度算法准确度高，因为它将每个项目的被评分规模考虑进去，排除了传统余弦相似度算法因为某些项目的打分用户数目大导致与其他并非很相似的项目计算结果很相似的可能。图中显示，当最近邻数目为10时，改进算法的精度最高；当最近数目大于10时，随着最近邻数目的增多，预测精度反而降低，从10以后的最近邻的相似度开始降低。在传统算法中，最近邻数目从40到50之间时，预测精度反而上升，这说明最近邻从40到50之间的存在着可能更相似的用户。通过这些对比，证明了本文的改进算法的有效性。
参考文献:
[1]刘玮:电子商务系统中的信息推荐方法研究.情报科学.2006,2
[2]Badrul Sarwar,George Karypis,Joseph Konstan,etc.Item-Based Collabrative Filtering Recommendation Algorithms.WWW10.2001
不同的形式相似的内容 篇4
一.相似的社会背景
“无知山谷”, 四周是“永恒的山脉”, 与外界隔离, 自然形势封闭, 只有一条“知识的小溪”沿着“深邃破败的溪谷缓缓流着”, 保持着与外界的联系。保守势力强大而坚固, 有“神秘莫测的古书”束缚着人们的思想, 有“守旧老人”的“叨唠”蒙蔽着人们的视听。山民狭隘保守, 愚昧无知, 他们安于“饮毕牲口, 灌满木桶, 便心满意足地坐下来, 尽享天伦之乐”, “和睦相处”, 过着所谓的“幸福的生活”。
《药》中有不少的描写渲染了那个时代特有的气息。如:点油灯, 用洋钱, 士兵衣服上的大白圈, 上坟摆饭菜烧纸钱。刑场上围观杀人的看客, 茶馆里为革命者挨打叫好的茶客, 共同组成了社会背景。这一切反映了辛亥革命前后中国的社会现实。自鸦片战争后, 闭关锁国的中国逐渐沦为半封建半殖民地社会, 腐败无能的清政府对外勾结帝国主义, 投降卖国;对内加强反动统治, 残酷镇压革命运动, 另一方面又在思想上愚弄和麻痹人民, 使人民任其宰割, 劳苦大众处于极端的悲苦之中。
二.相同的麻木的民众
对于“守旧老人”和他们的“古书”, “无知山谷”里的众人是敬畏的;正如茶馆里华老栓和众茶客对康大叔“恭恭敬敬”一样。
而怀疑者会受到“正人君子”真心的“冷落”;就像夏瑜被打, 而茶客们却叫好。
“无知山谷”的人们吼叫着, 举起沉重的石块杀死了先驱者, 把他的尸体扔到山崖脚下;夏瑜被杀时, 人们“潮一般”地赶去, “颈项都伸得很长”地看热闹, 鲜血被当作“药”吃了。
三.同样孤独的先驱者
先驱者是山谷里多少代人试图找到通往外界出路的探索者, 他冒着死亡的威胁走出了无知山谷, 然后又爬着回来。他外出是为大家寻找出路, 他回来是给大家引路走出无知山谷, 可他得到的是法律的严惩和山民的误解, 他试图对他们传播新知新见, 但山民还是用乱石砸死了他。
初中课间操内容与形式的改进研究 篇5
摘要：课间操作为学校教育的重要组成部分，已经有将近五十年的历史。它的存在不仅仅是让学生强身健体，还培养了学生的团队精神和组织意识。但是，长期以来，课间操在教育中更多扮演的是“鸡肋”的角色。尽管国家提出了大课间的活动概念，尽管广播体操已经改进和完善到了第十套，尽管个别学校为此推出了更富特色的课间操，但是，学校思想重视不足，教师组织力度不大，学生参与热情不高，使得课间操尴尬的地位多年得不到改变。本文针对课间操的现状，希望通过对课间操的内容和形式的尝试性改进和研究，摸索出一套从根本上改变课间操质量的方法。关键词：课间操 内容 形式 改进 研究
正文：随着新课程改革标准的推出，课堂教学的改革步伐与改革力度逐渐加大和深入。相较于硕果累累的课程教育，课间操作为学校教育的重要组成部分却一直处在被遗忘的角落。在国家提出大课间概念后，一些地方和学校也尝试着进行了课间操的改革，但却总是“水过地皮干，治标不治本”，长此以往，课间操对于调节学生身心，增健强魄的作用就形同虚设了，而对学生组织纪律的培养、集体意识的增强和集体荣誉感的形成也就丧失了一个有效的途径。因而，对课间操内容和形式的改进与研究已经成为当前学校教育工作的当务之急。
一、课间操现状与成因
1、内容单调贫乏
课间操恰如它的名字是课间的广播操，也就是说，这是课间的唯一活动形式。而广播操常年没有变化，学生日复一日、年复一年的在同一个时间重复做着相同的动作，导致做操的兴趣完全丧失，只为了应付差事，锻炼的目的与价值无从谈起。
2、组织形式直接刻板
课间操是几十年如一日的组织形式：“一听(听音乐)、二做(做广播操)、三评(教师评价质量)、四散(学生解散休息)”。这种刻板的方式对正处在青春叛逆期的学生来说，无疑是一种桎梏，十分钟的课间操对学生们来说就是割舍掉十分钟的自由。
3、管理方法陈旧
课间操的直接管理者是体育老师，管理方式是站在主席台上对各班学生的做操情况进行点评。学生们在熟悉了这套管理模式后，就会对教师的点评产生免疫，很难起到管理想要达到的效果。
二、课间操的改革途径
1、加长课间操时间
《中小学锻炼指南》中明确指出：学生每天至少要有一小时的户外锻炼时间。学校是学生学习活动的主要场所，相较于不是每天都有的体育课，课间操是学生的每日常规。可以考虑将每天的课间操从十分钟延长到三十分钟，使学生有足够的时间进行身体锻炼，这样的话，指南中的每天一小时就不再是纸上谈兵了。
2、开展丰富多彩的课间活动。
课间操的时间增加到三十分钟后，只运用广播操这一种形式显然是远远不能满足了。因此要积极开展多种多样的课间活动形式（1）自创操
所谓的自创操其核心意义在于将课间活动的自主权还给学生。这样会大大激发学生的参与兴趣，对学生创新精神与创新能力的培养也是一种有效的途径。自创操的形式与风格可以是多种多样的，比如健美操、韵律操、器械操，只要是在保证学生安全的基础上，可以鼓励学生进行大胆的创造。学生在自创的过程中会充分感受到自己是自己的主人，满足了初中生的心理特点，张扬了他们的个性。有些学校自创的课间操还因为引领潮流、新颖独特而迅速风靡全国。比如雾霾严重时，四川的中学生创造了一套在室内就可以完成的课间操，因为音乐动感、节奏鲜明、动作简单易学，成为当时国内大部分学校雾霾天的主要锻炼方式。学生进行课间操的创作大大激发了学生的参与兴趣，使他们认识到了体育的魅力，主动通过体育锻炼增强自己的体质，在增强体质的过程中意志品质得到提升。（2）自选操 课间操已经进行了三十余年，到现在为止是第十套，也就是说一套操的平均寿命是三年，这正好是一个初中的学段。学生在三年里面日复一日的做着相同的动作，其枯燥乏味的程度可想而知。这时候，学校可以掌握课间操的主动权，将我国传统体育项目发扬光大。比如武术、五禽戏、太极拳等等。这些体育项目在锻炼身心的效果上远胜于重在普及的广播操。学校还可以通过这些体育项目进行潜移默化的爱国主义教育，完成体育运动中“育”的目标。
3、改善完善课间操的组织形式（1）改变做操队伍
现在大课间的做操多数是以班级为单位，男生一排，女生一排。改革后的课间操可以按照实际内容打乱班级排列，在秩序不变的基础上做出大幅度的调整，也可以遵循一定的规律，定期变换队伍，使学生们常常保持着新鲜感，对课间操有所期待。（2）改变入场和退场形式
传统的课间操以铃声为信号，铃响上操，做完之后解散。改革后的课间操可以以音乐为信号，音乐安排成三段式，第一段音乐是让学生下课做好上操准备，第二段音乐是学生们走上操场整理队伍，保持秩序，第三段音乐放在课间操结束后，学生们解散回班时播放。三段音乐的播放形式丰富，内容各有侧重，符合学生的认知特点，还使学校的安全教育和纪律教育润物细无声的进入到学生的心中。（3）改变课间操节奏
在经过一段时间的训练后，我们常常说文体不分家，这句话在广播操中同样适用。在学生做操动作质量达到一定水平时，教师可以根据学生的实际情况在节拍节奏上做一些大胆的尝试。让学生用肢体语言展示节奏的快慢与节拍的强弱，甚至可以在播放音乐时让学生按照自己的理解进行表达，全身心的投入到广播操带来的快乐中。当然，要想达到这样的效果，非得是循序渐进，长期坚持才可以。首先，在初期要降低传统间操中口令的指挥力度，使学生对口令口哨的固有印象逐渐祛除；其次，用音乐指挥学生，要求学生分辨不同的音乐下自己所要达到的要求，这需要学生保持高度集中的注意力，并且能够积极的参与到音乐中去；在经过一段时间的训练后，音乐就可以进行富有韵律的变化，这种变化不应该是体育老师一个人的决定，更好的是体育老师和音乐老师一起合作在各自的领域中发挥，再结合，会起到更好的效果。环环相扣是为了不断刺激学生的神经系统，使学生对课间操的注意力和兴趣始终高亢，从而提高课间操的质量。（4）改变管理模式
传统课间操，体育老师会站在主席台上看着各个班的做操情况，随时进行点评。这种方式的确能够将情况及时的反馈给学生，但是从另一个方面来说，学生们每天听到的几乎都是相同的话，不仅起不到好的效果，久而久之还会让学生感到厌烦，而且点到的班级的班主任也会因为影响到集体荣誉而不配合课间操工作的开展，因此可以把管理变成软性模式，用做游戏的方式管理学生，比如可以把操随机分成几个部分，体育老师在前面说第几节到第几节初一年级做，第几节到第几节初二年级做，第几节到第几节初三年级做，一个年级做，其他两个年级在旁边观看点评，互相监督，以学生的点评替代教师的点评。做操质量的高低以衔接情况和动作标准程度来判定，队形的设置可以更加灵活，学生的主人翁意识也会越来越强烈。（5）利用榜样力量，做好宣传工作
“榜样的力量是无穷的。”任何工作的开展都不能眉毛胡子一把抓，教师在定好总的基调后，可以把自主权完全下放到学生手中，在经过一段时间的考察后，教师可以从中优选出一些学生，让他们担任领操员的工作，每次做操时，让领操员在前面带领大家做，为大家充分展示课间操带来的形体美与韵律美。也可以让领操员走到班级里去进行一对一的指导，领操员采取责任制的方法，每人负责一班，纠正指导，观察督促，在月评中选出比较好的班级，给予领操员和班集体表彰。另外，要对学校的宣传途径进行充分的利用，比如校广播站、简报、大厅展示橱窗、黑板报等等，进行课间操知识的传播，每个学期开展广播操的比赛，选取优胜班。这种示范加宣传的工作可以帮助学生体验到成功的快乐，还可以培养学生的审美。
三、关于课间操的另一些建议
目前,课间操在学校的教育工作中是一个非常明显的薄弱环节，不仅仅是体育老师，从事教育工作的人对此都深有体会，有些地方和学校也进行了一些尝试与改革，措施定的很细致，建设性的意见也采纳了很多。但是，改革不是一朝一夕一己之力，没有自上而下的支持与协作，这项工作很难长效的开展下去。因此，要想让课间操有根本的改观，国家的教育主管部门应该把它当作一项重要的改革内容来进行，首先要进行广泛而深入的调查研究，收集上来详实的数据；其次要对数据进行本质性的分析，找到真正的核心原因去治标治本；再有，支持的措施要具体，无论是地方教育行政机构还是学校都要从意识上重视，行动上落实。比如适当延长课间操的时间，将运动负荷设计安排的合理适量，真正达到强身健体、益趣身心的目的。当改革开始时，一定要坚持下去，不要说是一变就停，实质上，真正的问题都是在改革的过程中不断出现的。这个时候，如何解决改革遇到的困阻，就是需要运用教育智慧的地方了。
另外，建议学校可以专门成立负责课间操的组织管理机构，对课间操的内容与形式结合本校的实际，具体情况具体分析，制度上墙，有人执行，有人监督，教师可以和学生共同参与，切忌把自己变成学生的对立面、学生的监视器。当学生在自创操需要指导时，教师要给予细致的指导，当学生在口令改革后不知所措时，教师要稍微放缓速度，给学生适应的时间。不要把课间操变成某个群体的专利，只有教师真正的热爱，学生才会被感染，热爱上课间操。有的时候，课间操的改善会带动其他方面的教育，而这样的教育是学生主动积极参与，主动积极改善的，其效果自然比强制的要好上几倍。综上所述，课间操是一个协调多方面关系，综合多方面力量的工作，响应国家的大课间，将大课间做好、做活、做强，学生身心康健的目标才能落实到地，学生的阳光与自信会成为教育中亮丽的风景线，使国家的体育事业打下扎实的基础，增强国民的身体素质。参考文献：
[1]周登嵩主编.学校体育学[M].人民体育出版社,2004
[2]姚蕾著.体育隐蔽课程的基本理论与实践[M].人民体育出版社,2002 [3]任秀红.课间操存立之辨析[D].北京师范大学,2005
[4]曲宗湖.构建大课间体育活动课程[N].中国教育报.2001(003)
改进的内容相似性 篇6
微博客,又称微博,作为一种新的传播载体,包含了大量用户针对人物、事件等的评论信息,因此在网络舆情发起和传播中起着重要作用,并成为网络舆情浏览和分析的重要数据源之一。
但是,在微博空间,便捷的“转发”操作以及快速增长的“网络水军”,使得大量相同或相似的数据在微博空间内迅速传播。同时,噪音微博作为一种宣传手段也迅猛蔓延到微博空间的各个角落。对于网络舆情分析而言,噪音微博通常没有意义,相同或相似的微博也只具有一定的统计意义。对于微博用户的浏览而言,用户会发现自己看到的微博数据很多,但真正得到的有意义的信息量却很有限,浪费了时间和精力。同时,这类微博的存在也严重影响到了信息检索的准确性,大大降低了分析的可信性。因此,对微博客文本信息进行过滤提纯,对于减轻用户浏览理解和系统存储的负担,提高文本内容检索、网络舆情分析的效率等都具有十分重要的意义。
基于此,本文分析了微博客文本流中噪音微博和相似微博的特点,提出一种针对微博文本流的噪音判别和内容相似性双重检测的过滤方法。通过URL、字符率、高频词等特征判别,过滤噪音微博。通过分段过滤和索引过滤的双重内容过滤,检测和剔除相似微博。实验表明了这些方法能有效的对海量中文微博数据进行提纯,准确地过滤掉其中的噪音微博和相似微博。
1 相关工作
微博客近年来已经成为相关领域的研究热点。Sakaki等利用微博数据的实时性特征,将Twitter[1]中的用户看作“社会信息传感器”,并以此来对地震、台风等自然灾害信息进行跟踪与预警[2]。Weng等研究微博空间中关键用户发现问题,考虑用户间的话题相似性和链接结构,设计新的排序算法Twitter Rank来发现Twitter中有影响力的用户[3]。在文献[4]中,作者利用Twitter中蕴含的情感信息来对竞选结果进行预测。除此之外,在热点话题发现[5]、短文本分类[6]、虚拟社群挖掘[7]都是微博研究中的热点问题。
文本过滤是指依据一定的标准和运用一定的工具从大量的文本数据流中选取用户需要的信息或剔除用户不需要的信息的方法[8]。在微博文本过滤的研究方面,文献[9]对微博数据进行训练,利用半监督的机器学习支持向量机的方法发现微博上的噪音制造者。文献[10]提出了统计字符种类和最短编辑距离计算方法来判定Twitter中近似重复的消息。
虽然微博的研究目前已成为一个热点,但总体上,针对微博的文本过滤技术还处于起步阶段。中文微博考虑到“微博文本流”这一特点,以上过滤方法并不适用。因此,本文在分析了中文微博文本流中噪音微博和相似微博特点的基础上,提出了针对微博文本流的噪音判别和内容相似性双重检测的过滤方法,通过对微博数据实时抓取后再进行过滤,实现了保留高质量微博数据的目标。
2 中文微博客噪音文本、相似文本的特点
2.1 噪音微博文本的特点
目前针对微博的工作主要为舆情分析、观点挖掘等,因此我们将微博中对这类应用没有实际意义的微博数据定义为噪音微博,本文将其分为以下两类:广告型噪音微博和字符型噪音微博。
(1)广告型噪音微博
广告型噪音微博是指为达到宣传、增加点击率的目的而在微博客中有意加入的URL链接。为了分析该类噪音微博的特征,我们取不同时间段随机下载了1000条微博数据,并进行人工标注,统计发现其中噪音微博的覆盖率高达29.9%。进一步分析发现噪音微博中含有URL链接的信息约占85%,说明广告型噪音微博占有相当高的比例,同时说明了链接特征是广告型噪音微博最根本特点。噪音散布者通常利用链接的特性,人为地发表指向其他网站的链接,旨在宣传产品或者提升网站权威性。表1给出一些广告型噪音微博例子,其中都含有链接。
(2)字符型噪音微博
字符型噪音微博包括纯数字、纯英文等对中文微博分析和舆情分析无意义的字符型消息,以及用户分享视频、图片的文本保存形式,例如“分享图片”代表了用户在微博上分享的图片格式的文本保存信息。表2给出一些字符型噪音微博的例子。
我们分别统计了500条噪音微博和500条正常微博的文本字数,平均值为66和44,噪音文本的字数大于正常微博。图1显示了正常微博和噪音微博不同字数所占有的比率,噪音微博字数较为平均,长消息和短消息覆盖率相差不大,而普通用户发表的微博主要以少于40字的短消息为主,这是因为微博用户通常用简短的文字发表自己的观点和心情。图2显示了不同字数的正常微博和噪音微博消息中非汉字字符所占比率,发现噪音微博中所含有的无意义字符占有非常高的比率,例如在小于20字的噪音消息中,90%是非汉字字符,在这样的微博中通常只有URL链接的信息。同时我们统计了10万条微博信息的平均非汉字字符率,约为30%,而这500条噪音微博的平均字符率约为50%,因此本文将微博的字符率作为噪音微博判定的依据之一。
(3)噪音微博中的高频词
本文在人工标注的过程中发现噪音微博中大多含有URL,而在含有URL的噪音微博中用词相对集中,普通微博用词分散。这样,利用大量的含有URL的微博,可以找到噪音微博中的常用词。我们利用这一特点,从大量微博中提取出含有URL的微博消息作为训练集,对微博进行分词,去除停用词后作为噪音微博高频词的词库。统计发现词库中词的出现频率范围较大,本文保留了高于某一合适频率的词语作为高频词匹配词典。含有高频词的微博实例如表3所示。通过构建噪音微博高频词词典,累加高频词的频率计算权值,作为噪音微博判定的参考。同时,本文采用人工分析的方法修正了普通微博也会出现的高频词语,例如“微博”。
综上分析可见,噪音微博的3个主要特点是:(1)字符率较高;(2)URL较多;(3)噪音微博的高频词。其中(1)、(2)是显著特点,而(3)的检测则需要对内容进行分析,第3节将基于这3个特点检测噪音微博。
2.2 相似微博文本的特点
本文在对新浪微博平台的观察中发现,用户在发送消息时经常会复制别人的消息,或者直接转发好友的消息,或者经过少量的添加、删除、修改部分原始微博后作为新的消息再发送。同时,微博客空间内存在一定数量的“网络水军”,不断发布重复的微博数据。这些都是相似微博产生的原因,表4给出了一些例子。
可见,相同或相似微博本身并非噪音微博那样具有明显特点,只有通过内容相似性分析予以检测。
3 微博文本流中噪音微博和相似微博的过滤
我们利用API对微博进行实时抓取,首先基于噪音微博特征的判定方法,通过URL链接、字符率、高频词特征判别,过滤噪音微博。对文本进行预处理工作后,去掉微博本身特有的符号特征,然后基于VSM模型描述微博并采用向量夹角的余弦计算两微博间相似度,通过分段过滤和索引过滤的双重内容过滤,检测和剔除相似微博。第一重过滤基于时间分段,段内的微博之间进行相似度比较。第二重过滤时,考虑“微博文本流”的特点,将第一重过滤输出的微博集在缓冲池中构建索引,以提高搜索和比较的性能。微博文本流的过滤方法如图3所示。
3.1 基于特征判别的噪音微博检测与过滤
结合2.1节介绍的三个典型的噪音微博特征,即字符率较高、URL较多、以及噪音微博的高频词,首先以微博的字符率作为基础权值,对含有URL这种最为典型的噪音微博文本加上较高的权值,最后匹配高频词,本文对高频词的频率扩大了5倍。基于此,本文提出了算法1计算出微博的噪音权值,若大于所设定的阈值则过滤掉该条微博。
算法1 Spam microblog filter based on feature judgment
Input:microblogs mbs,spam weightβ,high frequency word lexicon HF,total thresholdθ;
Output:result without spam microblog result Set;
Method:
算法1中,第2)行是对字符率的处理,第3)行是对URL链接的处理,第6)~7)行是借助于2.1.3中所述的高频词典HF对高频词的处理。这三个特征的判别均以对β加权的形式统一到一个权重上,最后在第8)~9)行,判断该权重是否满足阈值θ,满足则视为噪音微博予以剔除。
3.2 特殊类型微博文本的预处理
微博中转发回复以及提到某一用户都有一定特征,系统会给消息加上一些固定模式的特殊字符(如//@),这类字符对转发回复消息的识别提供了可靠条件。微博中还包括“@”加上用户名,表示该微博是针对这一用户。由于本文仅考虑“原始消息”,在进行相似文本判断前对这类消息进行预处理,把特殊字符过滤掉。经过基于微博特殊规则的字符串匹配算法,使微博消息缩短,利于进一步的相似文本判断。预处理前后的微博文本对比如表5所示。
3.3 基于内容计算的相似微博双重检测与过滤
微博数据流属于海量数据,如果在整个数据集中去重,需要花费很多时间,也不能及时的得到处理结果,难以应用到实际中。而且,研究发现大量的转发微博更多地出现在相近时间里,重复率随着发表时间差距的增大而减小。为了证明这一规律,本文对各个时间段的总共800条话题微博计算重复率,利用VSM模型表达、向量夹角的余弦计算两条微博的相似值,该值高于所设阈值则定义为重复,重复率即为重复微博占段内总微博数的比例。如图4所示,在短时间内微博的重复率较高,随着相隔时间的加大,微博重复率迅速减少到很小值。
为了在尽量不降低召回率的前提下提高准确率,改善文本过滤性能,本文根据微博重复率随时间递减的特性,提出基于内容相似性计算的双重过滤法:首先对抓取的一个时间段内微博进行第一重过滤———分段过滤,再对相近时间发表的微博进行第二重过滤———索引过滤,达到微博文本流整体上的过滤,这样对发表时间相隔较短的微博去重,即能保证准确率,同时极大地减少处理时间,提高可用性。
(1)第一重内容过滤———分段过滤
首先,对噪音微博过滤以及文本预处理后的微博集分词,过滤停用词。然后构建向量空间模型,将每一条微博转换为一个文本向量,通过计算每两个文本向量的余弦值作为相似度,将相似度存在矩阵中,最后得到一个上三角相似度矩阵。遍历矩阵,查找相似的微博,如果相似值大于设定的阈值,则将其中一条过滤掉,如算法2所示。
算法2 Subsection-based similar microblogs filter
Input:microblogs subsection mbs,thresholdγ;
Output:result with less similar microblog in the subsection result Set;
Method:
(2)第二重内容过滤———索引过滤
经过算法2对微博进行一重过滤后,这里再对输出结果进行第二重过滤。本文使用索引查找相似微博的算法。首先构建一个微博缓冲池,存放最近发表的微博。由于微博的重复率随发表时间的递增而递减,因此本文只对最新一批微博构建索引。算法的基本原理如图5所示。图中的数据集经过了噪音微博过滤、微博预处理以及相似微博的一重过滤。图中(a)表示data5尚未加入缓冲池的状态,(b)表示data1数据集从缓冲池中移除后,data5加入缓冲池的状态。
算法3说明了将一重过滤后的微博集进行二重过滤的过程。首先对该微博集中的每一条进行分词处理,去除停用词。然后使用该条微博的分词结果集作为检索关键词,即可在构建的缓冲池索引中检索出最相关的一条微博。同样VSM模型表达、向量夹角的余弦计算两条微博的相似值。如果相似度值大于设定的阈值,则表示该微博与检索出的微博相似,过滤掉该微博。这样循环,对第一重过滤后的每一条微博再过滤后,将剩余微博集加入缓冲池进行更新,同时对缓冲池里的微博重新构建索引,该索引将作为下一批微博集进行二重过滤时所使用的新索引。
算法3 Index-based similar microblogs filter
Input:microblogs from first-level filter mbs,thresholdγ;
Output:result without similar microblog result Set;Method:
4 实验
4.1 实验数据与评价标准
目前在微博客过滤领域,尚无国际公认的标准测试语料库,本文从国内用户最多的新浪微博下载了公共大厅微博和话题微博作为实验数据源。本文的评价指标采用正确率(Precision)、召回率(Recall)及微F测度(F-score)来衡量算法性能的高低[11]。计算如式(1)、式(2)和式(3)所示。对于噪音微博分类,其中S为噪音微博分类算法检测为噪音微博结果中判断正确的数量,C是分类算法检测为噪音微博的数量,R是人工标注测试数据集中噪音微博的总数量。同样,对于相似微博过滤方法,其中S为相似微博检测算法检测为相似微博结果中判断正确的数量,C是算法检测为相似微博的数量,R是人工标注测试数据集中相似微博的总数量。实验中,程序找出的相似微博与人工标注的这组相似微博完全相同则为正确。
4.2 数据集大小对噪音微博过滤效果的影响
由于不同的数据集大小产生不同的噪音微博高频词,进而会影响到噪音微博过滤的效果,本文在阈值β为1的情况下,增加数据集的大小做了多组实验。首先从3000万微博中提取出含有URL的微博共700万作为总的噪音微博高频词训练集,然后取10万、50万、100万、200万、300万、400万、500万7组不同大小的数据集提取高频词,实验结果如图6所示,当数据量较小时,噪音高频词的覆盖面太窄,过滤效率不理想。随着数据量的增加,过滤的效率得到提升。但是当数据量足够大时,过滤的效率趋于平缓。当数据集选取100万时F值达到了峰值,本文选取这100万含有URL的数据集提取高频词,最终保留了含有5000词的噪音微博高频词词典。
4.3 噪音微博阈值β对判别性能的影响
在噪音微博判别算法中,判断是否为噪音微博的阈值β是一个很重要的参数,它会影响分类器的性能。本文标注了1000篇公共大厅微博作为检测噪音微博分类的数据集,利用上文确定的高频词词典,对该参数进行了多组实验。为了平衡准确率和召回率,以F值作为分类算法的评判标准,同时作为参数选取的标准。实验结果如图7所示,当β取值范围在0.8-1.0时,都取得了较好的分类效果;其中β在取值为0.9时,分类器具有最好的性能,此时F值达到峰值0.90,准确率P为0.84,召回率R为0.97。说明本文的判定方法能够较准确地过滤掉噪音微博,简单实用高效。由于阈值β的大小决定了分类效果,因此,若β取值过小,分类器则会过度拟合为噪音微博,从而导致分类准确率下降;若β取值过大,会导致分类的召回率下降。当β取0.9时,最好地平衡了准确率和召回率。
4.4 阈值γ和双重过滤对相似微博判断算法性能影响
在相似微博判断算法中,阈值γ也是一个很重要的参数,γ的取值将会影响过滤的性能。本文将经过了噪音微博过滤后人工发现的相似微博进行标注,其中含有大于或等于2个的多种相似微博,将标注的600多条相似微博加入不含相似微博的普通微博中,约2000条微博作为检测实验效果的数据集,针对不同参数进行了多组实验,同样以F值的大小作为算法的评判标准和参数选取标准。实验如图8所示,三条曲线分别表示进行双重过滤和仅第一重过滤、仅第二重过滤时F值的对比,其中双重过滤的算法性能明显较高,充分说明了本文提出的双重过滤法的必要性、准确性和实用性。双重过滤在γ等于0.5时F值取得最高值0.72,召回率为0.78,准确率为0.66,说明该算法判断较为准确、性能较高;当γ大于0.5的时候,F值开始出现下降现象。这是因为,随着γ的增加,被归类到相似微博的条件越高,被判为相似的文本越少,因此导致召回率大大下降。
4.5 相似微博双重过滤的时间性能
本文设计双重过滤法主要考虑到微博数据流属于海量数据,如果在整个数据集中进行去重,时间效率较低,难以达到实时应用的目的。因此本文首先对抓取的一个时间段内微博进行一重过滤,然后再对相近时间发表的微博进行二重过滤,达到微博文本流整体上的过滤目的。本文下载了2000条公共大厅微博,仅使用一重过滤处理的时间为90秒,使用二重过滤时处理时间仅为44秒,同时过滤掉了约20%的相似微博。实验说明本文提出的双重过滤法即能保证有效地过滤掉相似微博,同时极大地减少了处理时间,增加了处理效率。
5 结语
本文分析了中文微博数据的特点,针对其中的相似消息和噪音消息提出了一种面向微博客文本流的噪音判别与内容相似性双重检测的过滤方法。本方法实现效率较高,效果理想,实验证明了该方法能有效的对海量中文微博数据进行提纯,高效准确地过滤掉其中的噪音微博和相似微博,较好地保留下了高质量数据。同时该数据也可用于今后对微博数据的进一步分析,包括话题检测、情感倾向性分析等方面。
然而,这些工作尚需进一步深入和完善,主要包括以下几个方面:随着噪音微博的种类特征变化,还需根据新规则新特点进行过滤;在微博相似性计算方面可以选择其他更合理的方法进行比较。
参考文献
[1]Twitter[EB/OL].2011-3-16.http://twitter.com.
[2]Sakaki T,Okazaki M,Matsuo Y.Earthquake shakes Twitter users:real-time event detection by social sensors[C]//Proceedings of the 19th International Conference on World Wide Web,WWW2010,Ra-leigh,North Carolina,USA,April26-30,2010.ACM2010,2010:851-860.
[3]Weng J,Lim E,Jiang J,et al.TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the Third International Con-ference on Web Search and Web Data Mining,WSDM2010,New York,USA,February4-6,2010.ACM2010,2010:261-270.
[4]Tumasjan A,Sprenger T,Sandner P,et al.Predicting elections with Twitter:what140characters reveal about political sentiment[C]//Proceedings of the Fourth International Conference on Weblogs and So-cial Media,ICWSM2010,Washington,DC,USA,May23-26,2010.The AAAI Press2010,2010:178-185.
[5]Goorha S,Ungar L.Discovery of significant emerging trends[C]//Proceedings of the16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,July 25-28,2010.ACM2010,2010:57-64.
[6]Sriram B,Fuhry D,Demirbas M.Short text classification in Twitter to improve information filtering[C]//Proceeding of the33rd Interna-tional ACM SIGIR Conference on Research and Development in Infor-mation Retrieval,SIGIR2010,Geneva,Switzerland,July19-23,2010.ACM2010,2010:841-842.
[7]Kamath K,Caverlee J.Identifying hotspots on the real-time web[C]//Proceedings of the19th ACM Conference on Information and Knowl-edge Management,CIKM2010,Toronto,Ontario,Canada,October 26-30,2010.ACM2010,2010:1837-1840.
[8]黄晓斌.网络信息过滤原理与应用[M].北京:北京大学出版社,2005.
[9]Benevenuto F,Magno G.Detecting spammers on Twitter[EB/OL].http://ceas.cc/2010/papers/Paper%2021.pdf.
[10]曹鹏,李静远.Twitter中近似重复的消息的判定方法研究[J].中文信息学报,2011,25(1):20-27.
旅游本体的概念相似度算法改进 篇7
语义相似度是用来衡量文档或术语的语义内容或涵义间的相似程度的概念[1]，目前相似度计算已广泛应用于本体学习与合并、语义标注、知识管理中的信息抽取及自然语言理解等相关领域。与依赖关键词的检索相比，基于语义的检索能大幅度提高信息检索的查准率和查全率[2]。而概念的相似度计算决定了语义匹配的精确度，是语义检索的基础，因此提高概念相似度计算的精确度成为本体应用的关键。
目前，国内外学者已经对概念相似度计算进行了广泛的探索和研究，提出了很多计算相似度的方法。根据所使用的数据源及数据源的使用方式，相似度算法大致可分为基于路径的方法、基于特征的方法、基于信息内容IC(Information Content)的方法。基于路径的方法把概念相似性度量建立在本体中分割两个概念的语义连接数目上[3,4]。基于特征的方法根据本体概念描述模型中相同和不同的概念属性来估计概念间的相似度[6]。基于信息内容的相似性度量方法把概念信息量与本体知识相结合[7,8,9]。传统的信息内容求解方法是基于统计方法，统计给定语料库中的概念出现的次数，求得其出现的概率，从而得到信息内容值。但是基于统计的方法会受语料库内容的影响，工作量较大。
本文结合Word Net词典本身结构，综合考虑概念在分类树中的子节点信息、深度信息、公共父节点信息，提出了一个新的基于信息内容的概念语义相似度算法，这种基于Word Net本身结构的求解方法不需要其他语料库的参与，简单易行。同时本文利用Word Net词典，构建了旅游领域本体，通过实例证明该算法有效地提高了概念间语义相似度计算的准确度。
1 信息内容
1.1 信息内容算法概述
用数学语言去描述Word Net中的概念的信息内容参数，P(c)表示遇到概念c的实例的概率。根据信息理论中的定义，信息内容表示为-log P(c)，即IC(c)=-log P(c)，含义是一个概念的出现的概率越大，则该概念的自信息量就越小。其中，c是指某一具体概念，IC(c)指概念c的信息内容值。在Resnik的实验中，求解P(c)的方法是统计布朗语料库中名词出现的频率，计算方法可以形式化表示为:
其中，count(w)表示单词w在语料库中的个数，N表示语料库中的名词个数。
由式(1)可以看出，对于不同的语料库，则有可能得到不同的IC(c)。这是因为语料库中的概念是有限的。不同的语料库概念的数量也不同，出现的频率也不一定相同。由此可见，基于语料库进行词频统计有着不足之处。
Seco的IC计算模型是基于Word Net自身分类树结构来求解[10]。Seco发现子节点越多的概念所包含的信息量越少，而那些叶子节点的信息量最大。Seco的计算模型形式化表示为:
其中，hypo(c)返回值为概念的所有子节点数，max_node是一个常量，表示存在于分类树的所有概念的数目。
然而，该模型只考虑了概念的子节点数。如果在本体树中两个概念的子节点个数相同，则IC值相同。为此，Zhou在此算法基础上加入了概念深度因素[11]:
其中，depth(c)是概念深度，max_depth是本体树的最大深度。虽然上述算法较之Seco算法有所改进，但该模型仍无法区分概念子节点数相同、深度相同时的IC值。
1.2 信息内容算法改进
通常我们用Sim(A,B)来表示概念A和B间的相似度。概念信息内容的精确与否直接影响到概念间相似度的比较。经过分析，本文认为影响概念信息内容及概念间相似度的因素有:
(1)被比较概念在本体树中的深度。根据Resnik[7]和Seco[10]理论，概念深度越小，说明出现频率越高，则该概念越抽象，所涵盖的信息内容也就越少。反之，底层概念更为具体，所继承的信息内容也越多，概念间所共享的上层信息概率越大，因此底层概念间的语义相似度一般大于高层概念间的相似度。如IC(水果)
(2)被比较概念在本体树中所在簇的密度(簇:在语义树中，从根节点分出的树枝[12])。簇中概念节点越多，密度越大，说明对该簇根节点概念的细化程度越大，所对应的子节点所代表的概念也就更为具体，信息内容也就越大，所共享信息的概率也就越大，因此相似度越高。如第2节的图1中Activity簇的细化程度比Accommodation簇高，IC(Relaxation)>IC(Hotel)。
(3)被比较概念在本体树中相隔的路径长度。在密度及路径类型相同的情况下，概念间路径长度越长，相似度越小。如图1中Sim(Luxury Hotel,Hotel)>Sim(Luxury Hotel,Accommodation)。
(4)被比较概念最近祖先节点LCS(Least Common Subsumer)的信息内容。在密度、深度及路径长度相同的情况下，被比较概念最近祖先节点的信息内容越大，概念的信息内容也就越大。如第2节的图1中，IC(Sports)>IC(Rural Area)，则IC(Climbing)>IC(Countryside)。
基于以上分析，提出了基于信息内容特征参数求解的新模型，如式(4)所示:
其中，Cnode_max是概念C所在簇的概念节点总个数，Tnode_max是本体树所有概念节点的个数，AIC是概念C最近公共祖先节点的IC值，Hnode是概念C最近祖先节点拥有的与C深度相同的子节点个数，hypo(c)是概念C的所有子节点，depth(c)是概念C的深度，Tdepth_max是本体树的最大深度。
上述算式中的分母把信息内容值约束在[0,1]之间，本体树中顶层概念节点信息内容值为0，底层概念节点信息内容值为1，如此规律递增。概念节点越向上，说明概念出现的频率越高，所包含的信息内容越少，反之亦然。同样，概念节点所包含的子节点越多，则出现的频率越高，涵盖的信息内容也少。在深度、密度、子节点数都相同的情况下，如果父节点的信息内容值越大，则子节点的信息内容值也越大。
2 实例与仿真
2.1 实例
在研究与旅游有关的知识体系时，我们利用Word Net把有关的本体分成了Activity、Way、Accommodation和Destination四大类。图1为利用Protégé4.1创建的本体库片段。
2.2 实验仿真
为了验证旅游本体库的合理性，以及检验本文算法的实用性和有效性，我们使用MyEclipse 6.5、JDK 1.6.0等开发工具实现了本文中的算法。同时用基于路径的方法(Wu&Palmer[1])、基于特征的方法(David&Montserrat[6])、基于信息内容的方法(Resnik[7]、Jiang&Conrath[9]、Lin[8])对图1中部分本体概念进行了相似度求解并与人工打分进行了比较，结果见表1、表2。其中，基于信息内容的方法分别使用了Seco[10]、Zhou[11]及本文模型进行了结果对比。
本文采用皮尔森相关系数作为评价本文相似度计算公式的标准，如式(5)所示:
其中，xi表示相似度计算公式计算出来第i对概念的相似度值;yi表示由专家判定的第i对概念的相似度值;分别表示它们的平均值;σx和σy分别表示它们的方差。
不同相似度算法和不同信息内容算法对相同概念进行相似度求解的结果。其中，方法1为基于路径算法，方法2为基于特征算法，方法3-方法5为信息内容算法。所对应的具体算法名称详见表3。
从表2中的数据可以看出:本文的算法计算结果比较精确，更为接近人类专家的判断结果。
同时，为了更进一步验证本文算法的本体适用性，将该算法应用于文献[12]的基因本体中，对基因本体的部分概念节点进行了相似度求解，并把该结果与文献[13]中的算法结果进行对比，结果如表4所示。
3 结语
本文给出了概念的信息内容参数模型，该参数可以广泛应用到基于信息内容相似度算法当中。相对比其他模型，该模型不仅考虑了概念的子节点的个数，而且将概念所处于树中最近公共祖先节点、簇中同深度的节点数等纳入模型当中，使得概念的IC值更为精确。通过与其他相似度算法进行比较，结果表明本文算法求得与人工判别得到的相似度值的相关系数更高，同时把该算法用于基因本体，更进一步证明本文中新的IC模型的本体适用性。
摘要：传统的基于信息内容的概念相似度算法在计算信息内容值时过于依赖语料库,给出一个新的只通过WordNet结构计算概念语义相似度的信息内容模型。该模型以WordNet的is-a关系为基础,不仅考虑了概念所包含的子节点个数和所处深度,而且将该概念所处的簇及父节点的信息内容值引入到模型中,使得概念的信息内容值更为精确。实验结果显示将该模型应用到领域本体的概念相似度计算中,可以明显提高现有相似度算法的性能。
改进的内容相似性 篇8
词语相似度是一个主观性相当强的词语，对于不同的应用词语的相似度也不同。词语之间的关系非常复杂，其相似之处很难用一个简单的数值来进行度量。从某一角度看非常相似的词语，从另一个角度看，很可能差异非常大。在基于实例的机器翻译中，词语相似度主要用于衡量文本中词语的可替换程度；而在信息检索中，相似度更多的要反映文本或者用户查询在意义上的符合程度。
目前，对于语义相似度的计算主要分为两种:1) 词语信息量法, 该方法充分利用了信息论和概率统计的相关知识, 但计算的词语间语义相似度不能更细致地区分词语间语义的差别；2) 词语距离法，先计算两词语的语义距离，然后转化为语义相似度。本文在研究了大量文献后，提出了综合利用现代汉语语义分类词典的类层次关系中的多种影响因素来计算词语间的相似度的方法。文中词语间相似度的计算，主要是基于按照词语间结构层次关系组织的语义词典的方法，根据在这类语言学资源中词语之间的上下位关系以及其它一些因素，如语义重合度、语义距离、层次深度、调节因子等多种因素，来计算领域内部词语之间的语义相似度。
1、词语语义相似度的计算
与传统的语义词典不同，《知网》采用了1500多个义原，通过一种知识描述语言来对每个词语进行描述。义原一方面作为描述词语的最基本单位，另一方面，义原之间又存在复杂的关系。在《知网》中，一共描述了义原之间的8种关系：上下位关系、同义关系、反义关系、对义关系、属性-宿主关系、部件-整体关系、材料-成品关系、事件-角色关系。可以看出，义原之间组成的是一个复杂的网状结构，而不是一个单纯的树状结构。不过，义原关系中最重要的还是的上下位关系。根据义原的上下位关系，所有的"基本义原"组成了一个义原层次体系，这个义原层次体系是一个树状结构，可以得到一棵义原词语树，这也是我们进行语义相似度计算的基础。
1.1 词语语义相似度的概念
词语语义相似度是两个词语内在含义之间的相似程度，它在信息检索、信息推荐和过滤、数据挖掘、机器翻译等领域有着广泛的应用，成为当今信息技术研究的一个热点。
定义1当两个词语x、y满足某些共同特征时，用[0, 1]中的一个实数值来表示词语x、y之间的语义相似程度，记为sim (x, y) 。
有定义，易知词语语义相似度具有如下性质：
(1) 词语语义相似度是0和1中的一个实数值，即sim (x, y) ∈[0, 1];
(2) 如果两个词语完全相同，则语义相似度为1，即sim (x, y) =1当且仅当x=y;
(3) 如果两个词语没有任何共有的特征，则语义相似度为0，即sim (x, y) =0ㄢ
(4) 词语语义相似度具有对称性，即sim (x, y) =sim (y, x) 。
1.2 词语相似度的计算
目前，国内外对概念间语义相似度的研究大致可分为两类[3]:
(1) 利用语义词典如WordNet、HowNet中的同义词或义原组成的树状层次体系结构，通过计算两个概念之间的信息熵或语义距离，计算概念间语义相似度；
(2) 利用语料库统计的方法，根据两概念在上下文中出现的频率，计算概念间语义相似度。
在知网的相似度计算中，词语描述式的首义原对语义计算有着十分重要的作用，因此有的研究者将词语词语的首义原抽取出来，放在义原层次结构中计算它们的语义距离，然后用公式转换为相似度值，从而计算词语词语的相似度。
1.2.1 义原距离
两个义原之间的语义距离，是指在义原树中连接这两个节点的最短路径的长度。语言学研究认为，两个义原的语义距离越大，其相似度越低；反之，两个词语的语义距离越小，其相似度越大。
设义原集合为M，义原数量表示为|M|，义原用pi表示，i=1, 2，…，|M|。
设Li为义原pi在词语树中的深度，y为距离初始阈值，x为满足不等式max (L）<y/x成立的一个正实数，则pi与其父结点的距离定义为：
任意两个义原pi、pj之间的距离定义为：
其中ωk表示第k种关系对应的权重，通常取ωk≥1ㄢ
易验证，该定义符合对距离函数的数学要求。
1.2.2 词语相似度的改进
文献[4]中，董振东先生在描述《知网》的结构时，并不是将每一个词语概念对应于一个树状概念层次体系中的一个结点，而是通过用一系列的义原，利用某种知识描述语言来描述一个词语概念。而这些义原通过上下位关系组织成一个树状义原层次体系。因此词语语义相似度的计算我们可以是基于义原间的相似度计算。本文在公式 (2) 基础上考虑如下几个方面：
1) 节点的深度：节点的深度是指义原与树根的最短路径中所包括的边数。因为在义原树中，每一层都是对上一层概念的细化，由此可见，在语义距离相同的前提下，两个节点的深度差越小，概念之间的相似度越大。本文用Dep (p) 表示义原p的深度。
2) 节点密度：节点的密度是指两个义原最近共同祖先的子节点的密度。义原树中不同地方节点的密度是不同的，有的节点可能有几十个子结点，而有的节点可能只有几个子节点。一般来说，某个节点的子节点密度越大，说明细化的概念越具体。这些子节点间的语义相似度也就越小；反之越大。本文用den (p1, p2) 表示义原p1和p2与最近共同祖先的子节点密度。
3) 调节参数：语义相似度是一个主观性相当强的概念，对于不同的应用词语的相似度也不同。调节参数正是根据系统应用的不同来设计的，这里用α来表示调节参数。
综合上面提出的各方面的因素，可以得到以下词语S1和S2的相似度计算公式：
在式 (3) 的三项中，第一项表示语义距离对相似度的影响；第二项表示节点深度对相似度的影响；第三项表示节点密度对相似度的影响；α, β, γ表示语义距离、节点深度、节点密度对语义相似度影响的权重且α+β+γ=1，由于语义距离在相似度计算中占主导地位，而节点密度和节点深度只是起辅助作用，所以α的权重相对较大，β、γ的权重相对较小。
这里考虑的是孤立的两个词语的相似度。如果是在一定上下文之中的两个词语，最好是先进行词义排岐[4]，将词语标注为概念，然后再对概念计算相似度。
2、语义相似度的应用
传统的搜索引擎都是基于关键字进行搜索的。搜索引擎本身并不理解用户所要检索内容的真正含义，只是严格地按照用户所提供的关键字进行匹配。这样很容易出现漏查、错查的现象，搜索的查准率和查全率都不能得到保证。例如：要查找以"计算机"为主题的网页，于是在搜索界面中输入检索词"计算机"，搜索引擎响应用户的请求，然后把含有关键字"计算机"的网页信息返还给信息用户。然而，可能有一些网页的主题并不含有"计算机"这个词，含有的却是"电脑"这个关键字，虽然大家都知道"计算机"和"电脑"在很多情况下表达相同的意思，但由于基于关键词匹配的搜索机制，这些含有"电脑"的网页资源就被轻易地漏掉了，从而降低了搜索的查全率。在搜索引擎中加入语义相似度计算模块就可以很好的解决这一问题，在输入搜索关键字后，利用词语之间的语义相似度，根据实际应用的需要设定相似度的阈值，从而得到与输入关键词语义接近的概念扩充集，最后利用该概念扩充集中的概念, 进行信息搜索, 找到符合要求的页面[5]。
在实际计算中，假设图1中的词语集合{0, 1, 2, 3, 4, 5, 6, 7, 8, 910, 11, 12, 13}分别为{"电脑", "计算机", "软件", "硬件", "主机", "外设", "应用软件", "系统软件", "主板", "芯片", "内存", "windows", "linux"}，如图1所示。
首先分析词语的语义关系，由于词语"计算机"和"电脑"属同义关系，它们的相似度为1，可以把它们等同对待。然后对余下的概念进行处理，这里取权值全为1, a=2，α=0.9，β=0.05，γ=0.05，经过计算得到各个节点之间的相似度如表1所示。
表1反映了人们对词语之间相关联程度的主观认识，在搜索"计算机"时，如果设定阈值为0.9，可以得到的扩展集为{"计算机"，"电脑"}；若设定阈值为0.5，得到的扩展集为{"计算机"，"电脑"，"硬件"，"软件"}，再利用这些扩充集进行搜索，可以大大提高搜索的查准率和查全率。
3、结束语
本文对目前词语的语义相似度研究进行了综合分析，提出了一种基于《知网》的词语语义相似度的计算方法。本文通过搜索引擎实例，分析了利用词语语义可以改善搜索引擎的功能，实现一定程度上的智能化。
参考文献
[1]朱礼军, 陶兰, 刘慧.领域本体中的词语相似度计算[J].华南理工大学学报 (自然科学版) , 2004, 32 (z1) :147-150.
[2]刘金岭.一种基于语义的中文短信文本高质量聚类算法[J].计算机工程, 2009, 35 (10)
[3]张承立, 陈剑波.基于语义网的语义相似度算法改进[J].计算机工程与应用, 2006, 42 (17)
[4]http://www.keenage.com, 2008.1.18
改进的内容相似性 篇9
实际工作生活中,各类信息构成不同的网络,如微博社交网络,蛋白质网络,疾病网络等。根据网络节点的连接关系可以将其划分为若干社区,社区内部节点连接相对紧密,社区间连接则较为稀疏。社区发现对于网络舆情监测、安全预警、电子商务等有非常重要的应用价值。如聊天软件推荐的好友都归属同一社区,购物网站向不同社区的用户推荐不同风格的商品,公安系统监测邪教社区“游行”等词语频率升高时立即采取行动。对社区发现的研究,可以获取大量可靠有价值的信息。
社区发现的研究近年来取得了相当大的进展,很多学者提出了新理论和新方法。这些方法主要可以分为四类:图分割方法、W-H算法、层次聚类法以及标签传播算法。图分割方法通常应用于计算机领域,它基于迭代对分技术:每次划分都将网络分为最优的两个子图,子图再继续迭代对分,直至数量达到要求。图分割法大体可以分为两类:基于拉普拉斯矩阵的谱平分法[5,6]和Kerninghan-Lin算法[4]。其缺点是每次只能将网络对分,为了获取结果需要不断迭代。为解决这一问题,Wu和Huberman提出了W-H算法[7]:选取不同社区的两个节点,分别设为电压为1的初始点和电压为0的终结点,将每条边阻值设为1,其他节点会得到不同的电压值。将电压值相似的节点划分到同一社区。W-H算法缺点是在划分前必须知道社区结构的部分先验信息,以保证初始点和终结点不在同一社区。层次聚类法是根据节点间的连接关系和相似程度来划分社区,该方法又可以分为凝聚法和分裂法。代表算法分别为G-N算法[8]和Newman快速算法[9],但由于社区中存在很多相似度极低的点,层次聚类法往往忽略这些节点,最终结果难以令人满意。标签传播算法LPA(Label Propagation Algorithm)[10]与前几类方法相比,不需要知道网络结构或者先验社区结构,仅依赖于网络的传播特性,具有线形的时间复杂度,社区划分效率很高。引起了国内外学者的广泛关注。
标签传播算法准确高效,但传播过程中,当节点邻居中标签出现频率存在多个最高时,会平等的对待每一个节点,随机选取一个最高标签,这种随机性导致标签在不同社区之间的传播,针对标签传播算法的缺点,国内外学者提出了许多改进方法。文献[11]通过计算节点潜在影响力,生成一个具有k个强影响力节点的初始集合,为集合中节点赋予初始标签,节点的影响力越强,标签的传播速度越快。但该算法无法准确界定k值,如果k取值少于实际社区数目,算法无论如何运算都不会得到正确的社区划分。Lin等依据节点的权重排序,按照先后顺序依次更新节点标签[1]。康旭彬和贾彩燕通过分析节点之间的拓扑关系为节点赋予权值[12],打破节点原本的平等关系。Zhang等提出了基于边聚集系数的标签算法[2]。另外还有基于反馈控制[3]、目标函数[13]、LeaderRank[14]、圈子[21]等进行标签传播的社区发现改进算法。
本文从抑制标签传播的随机性入手,引入随机游走思想,基于随机游走的距离公式定义了一种新的相似度计算方法,构建节点间的相似度矩阵。在标签传播的过程中,当节点邻居中标签频率出现多个最高时,不再随机选定,而是选择最相似的节点所拥有的标签进行更新,有效防止了节点在社区之间的任意传播,提高了社区划分的准确度。
1 标签传播算法
1.1 标签传播算法描述
将网络视为一个有n个节点的无向图G={V,E},V表示节点的集合,E表示节点间联系的集合。标签传播算法可简述如下:
(1)初始化社区,为图中的每个节点随机分配唯一的标签,用标签代表节点所在社区。
(2)标签更新,计算节点x的邻接节点中各标签出现频率,将x的标签更新为:出现频率最高的标签,若标签频率存在多个最高,则随机选取一个。
(3)判断是否满足停止条件:达到规定的迭代次数或者若干次迭代后标签值达到稳定。
(4)划分社区,标签相同的节点归属同一社区。
图1为单个社区标签传播的过程,首先为4个节点分配a、b、c、d四个不同的标签,而后随机选取节点3进行更新,节点3在3个邻居标签中随机更新为标签b。继续选择节点4,节点4的邻居节点中只有一个频率最高的标签b,其标签更新为b,随后节点1也更新为标签b。所有节点属于同一社区,划分结束。
1.2 标签传播算法存在的问题
标签传播算法简单、高效,但准确率还有待提高。其最大的原因是平等的对待了每一个节点,导致标签在社区之间很容易传播,在更大范围上形成了社区的吞并,如图2所示,该图原本应当划分为两个社区。但若节点3更新标签时,在四个相邻标签中,随机的选择了节点4的标签,随后上半部分3个节点都将拥有节点4的标签,上社区被吞并,整个网络最终将划分为同一个社区。这是标签算法所暴露出的最大缺点:节点邻居中标签出现频率存在多个最高时做出的选择是随机的。
2 基于随机游走相似度矩阵的标签传播算法
标签传播算法最大的缺点是其随机选择标签而导致结果不稳定,为解决这一问题,我们提出基于随机游走[19]相似度矩阵的改进标签传播算法RWLPA(Label Propagation Algorithm Based on the Similarity Matrix Using Random Walk)。
2.1 随机游走相似度矩阵的计算
改进的标签传播算法在社区划分过程中,当节点的邻居节点中标签频率存在多个最高时,能作出正确的选择,更新为最有可能处于同一社区的节点拥有的标签。为控制选择方向,引入基于随机游走的相似度矩阵。节点每次更新标签都选择与自己相似度最大的节点所拥有的标签。
借助相似度矩阵,我们可以很好对标签传播方向进行选择,对于图3中节点4来说,共有4个邻接节点,即4个更新时可选择的标签。查找图4的相似度矩阵,节点4与节点1,2,3的相似度为4.189,与节点5的相似度为1.791,因此节点4应当在节点1,2,3中选择标签更新,实际上无论选择这三个中的哪个节点,左社区都会得到正确划分。
目前对于随机游走相似度的衡量有几种不同的标准。最先得到使用的是平均通勤时间ACT[15]和平均首次穿越时间MFTP[16]。这两种衡量方式易于理解,但是复杂度高。本文基于文献[17]中介绍的方法,定义一种新的距离进行衡量。算法初始时将随机游走的walker放置在图中任选的节点,使其按照马尔科夫性质[20]随机选择下一个位置。随机游走可以用递推的方式来描述。用Pxy表示一步之内walker从节点x走到y的概率。πxy(t)表示walker行走t步时,从节点x出发到达y的概率。πx(t)是π(t)矩阵第x列的列矩阵。
如果节点x与y之间有连接,则axy=1,若二者无连接则axy=0,kx表示节点x的出度。PT是矩阵P的转置。
用sxyLRW表示节点x和y之间的相似度。计算公式如下:
其中|E|是网络中节点间的连接总数。
但随机游走同样存在问题。其缺点在于walker的行走遵循马尔科夫性质。假如x和y是同一社区中相近的两个节点,相似度很高,而walker却可能游走到距离较远的节点或者到其他社区中,从而测定的x和y之间的相似度很低。为了解决这一问题,可以连续多次释放walker,降低这种可能对算法的影响,然后对LRW相似度进行叠加,这样就降低了在某次游走时可能出现的特殊情况对算法造成的影响。叠加后距离公式为:
对于一个固定的网络来说,其总边数,即|E|是固定的,因此在计算过程中,2|E|被忽略。产生一种新的相似度,称其为OLRW相似度(Omitted Similarity Based on Local Random Walk)。
以Δt=1连续不停释放t个walker,直至最后一个walker步数为1,此时首次开始行走的walker步数为t。相应的OSRW相似度(Omitted Similarity Based on Superposed Random Walk)计算公式为:
计算过程中,使用新的OSRW相似度计算节点之间的相关程度,生成相似度矩阵,图3为具有8个节点的简单网络图,图4为释放4个walker计算得到的该图OSRW相似度矩阵。
在随机游走的过程中,依次释放walker。步数t不同,walker数量也就不同,求得的相似度矩阵也不同。步数t的选取对于算法效果十分重要,我们通过实验确定t的取值。试验中选取节点数为500的基准网络为数据集,采用准确度NMI作为评价值。混合参数μ表示社区之间的混合程度(μ取值为0到1),μ取值较小时,社区结构清晰,容易划分,算法准确度接近于1;μ取值较大时,社区结构不明显,准确度为0。因此我们取准确度变化幅度较大的μ=0.6和0.65进行测试。
这里仅对较少步数(t≤10)进行试验。当步数过高时,算法过于复杂,且相似度会逐渐趋向于一种稳定状态[17],取极限(t→+∞),此时节点x与y之间的相似度不依赖于其他参数,仅与节点x的度相关,即:πxy(t)=kx/2|E|。因此并非t取值越高,相似度矩阵越精确。通过图5和图6,我们可以看出3≤t≤8时,实验结果更为精确,所求得社区的NMI更高。这是由于t过小,walker数量少、行走步数小,求得矩阵的准确率不高,而t过大,相似度则趋于稳定。本文选取步数t=4计算相似度矩阵。
2.2 改进算法描述
依据前文对标签算法的介绍,结合随机游走算法,RWLPA算法过程表述如下:
(1)初始化社区,为图中的每个节点随机分配唯一的标签,用标签代表节点所在社区。
(2)标签更新,计算节点x的邻接节点中各标签出现频率,将x的标签更新为:出现频率最高的标签,若标签频率存在多个最高,则选取相似度最高的节点所拥有的标签,若存在多个相似度最高的节点,则随机选取一个。
(3)判断是否满足停止条件:达到规定的迭代次数或者若干次迭代后标签值达到稳定。
(4)划分社区,标签相同的节点归属同一社区。
3 实验及分析
为验证算法的准确性,本文采用Zachary's karate club、Lusseau’s Dolphin、Pol Books等广泛应用于社区发现评价体系的数据集进行测试。每次实验运行100次,以尽量消除算法的随机性。下面以Zachary's karate club数据集[3]为例,进行介绍。该数据集包括美国一个空手道俱乐部中的34个成员,78个成员联系。这34个成员由于两位领导相互之间的矛盾产生了分裂,成为两个派别。图7为原始LPA算法划分结果,从图中可以看出,LPA算法对小社区很敏感。比较LPA算法与RWLPA算法,可以看到图8中RWLPA算法中节点5与节点26被划分到大社区中,从直观上来看,节点5与大社区中1、11有连接,小社区中仅与7有连接。节点26的邻接节点24、25,24与大社区的联系也远多于25与小社区的联系。直观上来说,5、26应当划分到大社区中。
为了更好的证明,使用Newman提出的社区发现模块度Q[18]作为实验的评价指标。
式中|E|代表无向图总边数,Aij为邻接矩阵,ki为节点i的度数,节点i与j在同一社区时δ=1,反之δ=0。
表1中模块度计算的结果,证明针对Zachary's karate club数据集,RWLPA算法的结果优于LPA算法。为了更好的验证,我们同时选取Lusseau’s Dolphin、Pol Books等公开测试数据集对进行实验。为提高实验结果的可靠性,对每个数据集分别用两个算法各运行100次求得平均值,如表1所示。表中数据表明,对于4个真实数据集,RWLPA算法划分的社区模块度均高于LPA算法。这主要是因为在标签传播的过程中,相似度矩阵很好地抑制了传播过程中的随机性,节点每次都选择最可能与自身处于同一社区的节点标签进行更新,使社区划分结果更稳定、更接近于真实情况。
4 结语
本文对社区发现的常用算法进行了介绍,并基于随机游走的相似度矩阵对标签算法做出改进。实验证明,RWLPA的效果优于原始LPA算法。但算法对重叠社区考虑不足,同时矩阵的计算占用较多的资源,在未来可以对重叠社区进行研究,改进矩阵运算方法,适应现实网络大规模重叠社区的发现需要。
摘要：基于标签传播的社区发现算法因其时间效率高而得到广泛关注。针对该算法因标签传播的随机性导致其社区划分准确度难以保证的问题,提出一种基于随机游走的改进算法。首先,引入随机游走思想,计算得到一种衡量网络节点间相似度的矩阵;其次,在标签传播过程中,当邻居节点中标签出现频率存在多个最高时,不是随机选择一个,而是选择相似度最高的邻居节点所拥有的标签来更新,避免了标签在社区之间的任意传播;最后,用不同的真实网络进行测试,结果表明在社区发现中该算法比原始标签传播算法取得更好的表现。
改进的内容相似性 篇10
1 模糊C均值聚类算法描述
FCM聚类由Bezdek[3]提出的一种基于迭代的优化算法。该算法是一种基于划分的聚类算法,用隶属度来确定每个数据点属于某个聚类的程度,其思想是把相似度最大的对象划分为同一类,而不同类之间的相似度最小。它可以描述如下: 假设FCM把n个向量xi( i = 1,2,…,n) 分类为c个模糊组,其分类过程是通过求取每组的聚类中心,来使非相似性指标的目标函数达到最小值,从而实现把相似度最高的向量分为同一类。FCM算法最小化目标函数定义为
式中: uij表示xj属于第i类的隶属度,其大小为uij∈[0,1]; vi为第i个聚类中心; D为第i个聚类中心与第j个像素点间的欧氏距离,是表达相似性度量的规范,具体描述为D( xj,vi) = ‖vi- xj‖2; m∈[1,+ ∞) 是一个加权指数,控制聚类结果的模糊程度,m越大聚类的结果越模糊。
对所有输入参量求导,使式( 1) 达到最小的必要条件如式( 2) 所示
换言之,要使目标函数递减的隶属度和聚类中心的迭代式如下
为了满足上述条件,模糊C均值需要进行多次迭代,最终可使目标函数最小化。
FCM算法进行图像分割可以归纳为以下步骤[7,9,10]:
步骤1,输入图像Y,确定分割数目i( 2 < i < n) ,加权指数m,终止阈值;
步骤2,初始化中心点集,随机生成隶属度矩阵u;
步骤3,使用式(3)更新隶属度uij;
步骤4,使用式(4)更新聚类中心vi;
步骤5,根据式(1)计算目标函数J;
步骤6,转到步骤3,对该目标函数进行迭代运算,直到它小于某个确定的阈值时算法终止,转到步骤7;
步骤7,依据隶属度矩阵u分割图像。
2 模糊C均值聚类算法的不足
FCM聚类算法虽然已经成功的应用在图像分割中[11],然而传统的FCM算法将灰度级作为图像分割的单一特征,没有考虑像素的空间信息或不同样本向量对它的影响,因此,它对噪声非常敏感,计算结果会受到分属于不同区域的向量的影响。针对上述问题,DZUNG提出了一种包含像素空间信息的FCM算法[12],它在原来的目标函数上加入了包含像素空间领域信息的惩罚项,这需要几种统计估计来完成这个效果。本文工作中,选择了空间特征: 算术平均估计( 用μ 表示) 来实现,这样的应用可以对正常像素和噪声像素都进行较好的聚类,但是边界区域的分割不平滑。表1 显示使用空间特征和传统灰度级特征对噪声和边界像素聚类的优点和不足。
3 本文算法描述
利用空间特征与灰度特征的互补性,本文的图像分割算法将联合使用这两种特征来进行FCM聚类。该算法是一种新的自适应相似度距离FCM ( ADFCM)算法,它的优势就是通过对每个像素点的空间配置来避免只使用一种特征所带来的不足。
3. 1 空间配置规范
3. 1. 1 空间配置分类方法
本文要求每个像素都有特定的聚类判据选择,将空间像素分为4 类,如图1 所示。具体分类如下: 区域像素( PR) ,边缘像素( PE) ,噪声像素( NP) 和邻近噪声像素( NN) 。窗口大小为3 × 3。
3. 1. 2 空间配置的表征
一般来讲,空间配置是由两个统计描述符来表征的,具体如下:
1) 标准偏差 σ 表示待聚类像素周围的像素的动态分布。该特征定义为
2) KNN表示某个像素点的所有邻近点中灰度级与该像素点一致的点的数目。KNN特征定义为
式中: S阈值的确定通常是凭经验来选择。
根据这2 个特征可以表征各种可能的空间配置。对于PR,标准偏差 σ 普遍较低,正常像素区域基本为零。然而,对于PE,NP和NN,σ 就变得较高了,要区别这三种空间配置就需要采用KNN特征。NP类像素的KNN数值一般较低,而PE类则中等,NN类较高。
3. 1. 3 根据空间配置的聚类判据选择
对于PR或NP聚类,要优先考虑空间特征,这是因为这一决定取决于邻近像素的信息( 如邻近像素都与它相同或者都与它不同) 。而对于PE和NN聚类就要优先考虑像素的灰度级特征,以更好地保护轮廓,避免噪声的影响。表2 总结了聚类判据的选择和空间配置的特点。
3. 2 新相似度距离定义
标准的FCM算法使用对象xj和类中心vi的欧氏距离来表征相似度距离。本文为了自适应的选择优先特征,采用一种基于欧氏距离的动态加权距离来来表征相似度距离。这个新的距离由式( 7) 给出
式中: D是一个同时基于空间特征和灰度级特征的二维距离。在式( 7) 中,加权系数pj控制像素xj聚类时每种特征的重要度。即: 如果pj高那么优先考虑空间特征,否则就偏向于灰度级特征。pj系数由每一个待聚类的像素点根据它在图像中的空间配置来进行计算。由表2 的配置特点可以看出,当像素的空间配置是PR或NP时,pj系数必须最大化,因为决定它的隶属度的是空间特征。反之,当像素的空间配置是PE或NN时,pj系数必须最小化,因为灰度级特征这时是最好的聚类判据。
3. 3 空间加权系数的估计
选择空间加权系数pj计算新的距离是非常重要的。本文采用了一个模糊的方法估计pj。为此,使用一个模糊系统[8,14]来实现,该系统具有两项输入语言变量 σ 和KNN和给出结果的输出语言变量p。根据上节内容,p是根据空间配置来选择,可以用一个模糊规则If-Then( 用Ri表示) 来定义每一种空间配置。由此,可以用四种规则来表征输入变量 σ、KNN与输出变量p之间的关系,利用该关系可以确定所有必要的结果,以便计算出p的值[14]。语法规则定义如下:
这里,σ 的阈值设为Tσ; KNN的阈值设为T1,T2; p的阈值设为T3,T4; 都由经验方式获得。
4 实验结果分析
为验证算法的有效性,本文采用改进的FCM算法对混入高斯噪声的人工合成图像进行了实验。其中,对“Lena”图像混入了7% 高斯噪声,对磁共振脑图像混入了5% 的高斯噪声。所有测试都是在相同的条件下进行( 加权指数m = 2,收敛误差= 0. 001) 。本文ADFCM算法采用由3 × 3 窗口计算得到的均值 μ 作为空间特征,采用的聚类数为3。ADFCM( σ 的阈值Tσ=55) 实验分割结果对比如图2 所示。
图2c为聚类数为3 的FCM标准算法对图2b的图像分割结果,这个结果清楚地说明了标准FCM算法在区分噪声像素上的局限性。图2d采用均值 μ 空间特征可以解决噪声点问题,但是它会产生不准确的边界分割。图2e为采用本文ADFCM算法进行分割的结果,边界分割更为准确,噪点也明显减少。显然,实验结果表明本文算法的性能要优于标准FCM算法。
脑图像分割由3 种脑结构组成: 灰质( GM) 、白质( WM) 和脑脊液( CSF) 。本文算法对图3b进行了测试试验。图3c为采用基于灰度级特征的标准FCM算法分割结果,图像有明显的噪点和边界重叠问题( 特别是在灰质和白质之间) 。图3d为采用基于空间特征的标准FCM算法分割结果,它降低了边缘划分的质量。而图3e采用本文ADFCM算法进行分割后,极大地降低噪声像素而获得良好的确定区域和具有连续的边缘,更加接近于现实。
最后,为了和文献[5]算法比较,本文采用文献算法及本文ADFCM算法对图4a原始图像进行分割并与Ground truth图像( 图4b) 对比。为了量化评估两种算法的分割效果,采用了文献[15]定义的分割正确率( CCR) 作为分割结果的评价测度。表3 给出了两种方法的CCR值。通过对比可知,本文方法略优于文献[5]的算法,如图4c和图4d所示。
5 结论