属性相似度（精选7篇）
属性相似度 篇1
0 引言
云技术的快速发展和大数据时代的来临, 导致网络中的数据量以指数级趋势膨胀, 用户不得不面对浩如烟海的网络信息, 加大了在其中寻找对用户有益信息的难度, 这就是信息过载。作为一种信息过滤手段, 推荐系统可以根据每个用户的兴趣给用户提供个性化推荐, 是当前有效解决上述问题的方法[1]。在网络时代之前, 人们往往会从与自己有相同喜好的同伴那里获得各种建议以帮助自己决策, 这就是协同过滤的出发点。协同过滤通过计算用户或项目间的相似性, 找出有相似偏好的用户或相似的项目, 根据相似用户的偏好预测目标用户的喜好, 或者根据相似项目的受欢迎情况预测用户对目标项目的倾向程度, 进而作出推荐, 独立于项目本身的内容, 且易于实现, 目前已取得广泛应用。条件概率[2], 贝叶斯方法[3], 图论[4]等方法也被应用于推荐系统。与此同时, 云环境下网络中的数据不断增长, 每一个用户不可能对众多的项目都有评分信息, 进而使用户对项目的评分矩阵高度稀疏, 传统协同过滤相似性计算方法也逐渐暴露了其局限性, 无法适应在大数据时代下的要求, 在数据稀疏情况下推荐效果不佳, 我们在后面的介绍中会分析传统相似性计算方法存在的弊端。另外, 对于新加入系统的用户, 其对项目的评分太少, 以至于无法提供使推荐系统分析出该用户的偏好情况的信息, 系统不能对该用户做出准确的推荐, 这种情况被称为新用户问题。对于新加入系统的项目, 用户对该项目评分太少, 系统也不能将这个项目推荐给用户, 这种情况被称为新项目问题[10]。新用户和新项目问题都属于冷启动问题[10]。针对用户评分数据高度稀疏的情况, 一些学者提出种种改进措施, 文献[5]提出基于项目的项目评分相似性和项目属性相似性自适应权值加权结合, 以解决新项目问题, 但不能解决新用户问题。文献[6]提出基于阈值的对余弦相似性的改进, 该方法可以提高推荐的多样性, 但不能保证推荐准确度。文献[7]提出基于交叠的邻居集选择方法, 该方法要求设置合适的参数。文献[8]提出基于用户的项目评分池方法, 根据用户对项目的评分将用户分成多个独立子集分别对总评分做出贡献, 该方法一定程度上提高了推荐准确度, 但并不能解决数据稀疏问题, 而且需要调整的参数较多。
因此, 本文提出一种基于多向测度和项目属性的相似性计算方法, 利用用户对项目属性的偏好程度和多向测度相似性计算方法加权结合, 得到用户间相似性, 最后生成推荐。实验表明该方法较传统相似性计算方法具有了更好的准确度, 在数据稀疏的情况下, 结果仍较好。
1 传统相似性计算方法分析
基于用户的协同过滤推荐技术利用某种相似性计算方法计算所有用户与目标用户的相似性。取前k个相似性最大用户的组成目标用户的最近邻居集, 由于当前用户的最近邻居对当前项目的评分与目标用户的评分比较类似, 所以可以根据近邻用户对当前项目的评分预测目标用户对当前项目的评分, 然后选择预测评分最高的前若干项目作为推荐结果反馈给用户, 作出推荐。可见, 相似性计算的准确与否, 将影响最终做出的推荐。
1.1 数据表示
推荐系统存储的信息一般包括用户ID, 项目ID以及用户对项目的评分等。设m表示用户数, n表示项目数, 则U={u1, u2, …, um}表示用户集合, I={i1, i2, …, in}表示项目集合, 用ru, i表示用户u对项目i的评分, 取值在1~5之间, 反映了用户对项目的倾向程度, 评分越高表明用户对该项目越倾向。如果用户对项目没有评分, 则其相应评分为0。也有的推荐系统用0表示用户不喜欢该项目或未对该项目评分, 1表示用户喜欢该项目。如表1所示。可用评分矩阵中值为0的项所占的比例来反映数据稀疏度, 比例越大, 数据越稀疏。
1.2 相似性计算
传统的相似性计算方法主要有皮尔逊相似性、余弦相似性和修正的余弦相似性。皮尔逊相似性是依据用户间的共同评分项计算相似性来度量。其计算公式如下:
其中ru, i, rv, i分别表示用户u对项目i的评分和用户v对项目i的评分, 珋ru, 珋rv分别表示用户u和用户v的平均评分, Iu, v表示用户u, v共同评分的项目集。
皮尔逊相似性仍有许多不足之处, 其计算的是两个用户间的线性相关度, 而非相似性, 当两用户的评分向量线性匹配时, 由该公式计算的相似性较高, 但用户在共同评分项上的评分局部不完全匹配时, 其相似性低, 不能反映出用户局部相似的事实。当用户间共同评分项过少时, 该计算方法的结果往往具有误导性, 不能反映用户间真实相似性, 极端情况下, 用户间共同评分项为1个, 则不能用皮尔逊方法计算相似性。当用户评分是形如{2, 2, 2, …}这样平整的情况时, 平均分与评分相等, 也不能用该方法计算。
余弦相似性中用户相似性通过计算向量间夹角的余弦值反映, 余弦值越大, 用户相似性越大。其计算公式如下:
由于余弦相似性没有考虑用户个人的评分尺度, 修正的余弦相似性则引入用户平均评分来反映用户的评分尺度。其公式如下:
2 多向测度结合项目属性相似性计算方法
由于传统相似性计算方法仅从向量角度考虑用户或项目间的相似性, 结果反映的是向量间的整体相关性, 抹煞了评分向量中包含的局部信息, 所以我们从单个评分的角度出发, 使每个共同评分得以反映出更多信息。
2.1 多向测度的相似性计算方法
众所周知, 对一个封闭系统, 外界掌握的信息越多, 就越能反映该系统的实际情况。传统相似性计算方法考虑的是用户评分向量的整体匹配程度, 从用户-项目评分矩阵这个系统中获得的信息较少, 不能很好地反映用户间的真实相似性。本文提出多向测度的相似性度量方法, 综合考虑用户评分在三种距离上的表现。通过对用户间评分在绝对距离, 用户相对距离, 项目相对距离三个方面的综合情况, 反映用户的相似度。
设两用户u, v以及他们的共同评分项目i, u和v的平均评分分别是, 项目i的平均评分是, 用户u, v对项目i的评分分别是ru, i, rv, i。对于项目i, 若两用户对其评分同时大于或小于各自的平均评分, 即, 就认为用户u和v对项目i持相同的偏好, 即同时喜欢或同时不喜欢, 否则, 视为偏好不同。
下面给出多向测度中绝对距离, 用户相对距离, 项目相对距离的定义:
(1) 绝对距离:偏好相同时, AD=ru, i+rv, i;否则AD=|ru, i-rv, i|+1。
(2) 用户相对距离:偏好相同时, , 以各用户的平均评分划分用户的偏好区间, 则用户相对距离反映了当前项目在用户偏好区间的位置, 以此反映用户对前项目的偏好情况。
(3) 项目相对距离:偏好相同时, ;以项目的平均评分划分当前项目的用户偏好区间, 则项目相对距离反映了用户在当前项目的喜好区间的相对位置。
则ru, i, rv, i间的相似性计算如下:
用户u和用户v的相似性计算如下:
其中, Iu, v表示用户u, v共同评分的项目集。
2.2 项目属性相似性
通常, 推荐系统至少保存了三部分数据信息, 即用户-项目评分信息、项目属性信息、用户信息。传统的协同过滤算法是通过用户对项目评分信息计算相似性, 而项目的属性相似性则是利用项目属性信息进行计算的。文献[9]提出项目属性偏好相似度作为相似性度量的一部分, 取得了较好效果, 该方法中用户u对项目属性j偏好程度的计算方法如下:
其中sum (u, j) 表示用户u对具有属性j的项目的总评分, sum (u) 表示用户u的总评分。
该方法反映的是用户总评分在项目属性上的分布情况, 并不能反映用户对项目属性的偏好情况。若某用户评分如表2, 其中i1, i2, i3, i4, i5有属性A, i6, i7, i8有属性B。
则由上式计算得到pref (u, A) =0.53, pref (u, B) =0.47, 用户对属性A更加偏好, 但由表2可知用户对属性B更偏爱。故本文中用户对项目属性偏好程度用式 (7) 计算:
其中num (u, j) 表示用户u对有属性j的项目的评分次数, 该式反映了用户对该项目属性的平均评分。由该式得pref (u, A) =1.6, pref (u, B) =4, 由表2可知反映了实际情况。
2.3 算法描述
Step1 读入用户-项目评分矩阵和项目属性矩阵。项目属性矩阵是n×k矩阵, n是项目数, k是属性数, 元素s (i, j) =1表示项目i有属性j, s (i, j) =0表示项目i没有属性j。
Step2 计算每个用户的平均评分和每个项目的平均评分。
Step3 按式 (7) 计算用户对项目属性的评分, 并计算出每个用户对项目属性的平均评分和每个属性的平均评分。
Step4 按式 (5) 计算用户间对项目评分的多向测度相似度, 结果是m×m矩阵, 用simi表示;计算用户对项目属性的多向测度相似度, 结果是m×m矩阵, 用sims表示。simi中元素simi (u, v) 表示用户u和用户v间的项目评分相似性, sims中元素sims (u, v) 表示用户u和用户v间的项目属性相似性。
Step5 将simi和sims中相应元素simi (u, v) , sims (u, v) 加权结合, 权重为E。由于simi和sims计算的维度不同, 故要先对simi和sims进行归一化, 其公式如下:
max, min分别是simi中的最大相似度, 最小相似度。归一化后simi (u, v) ∈[0, 1], 值越大, 表示对应用户间越相似。同理, 对sims归一化, 最后得到混合相似度sim。
Step6 获得近邻。采用Top-k方法选择前k个与目标用户相似度最大的用户作为目标用户近邻, 组成近邻集。
Step7 预测评分。按式 (10) 计算用户u对待测项目评分i的预测评分:
其中分别是用户u, v的平均分, rv, i表示用户v对项目i的评分, Pu, i是用户u对项目i的预测评分, Neighbor (u) 表示用户u的近邻集合。
3 实验分析
3.1 实验数据集
本文实验中采用的数据集是Grouplens (http://movielens.umn.edu) 工作组提供的公开数据集, 该数据集包含的信息有用户数:943, 电影项目:1682, 用户对项目的评价数据:100 000, 评分值:1~5。可知该数据集用户对项目评分的稀疏性为1-100 000/ (943×1682) =0.936953。实验中将用户对项目的100 000条评分记录按照4∶1的比例划分成训练集和测试集。
3.2 度量标准
实验各相似性计算方法的度量效果采用平均绝对误差MAE (Mean Absolute Error) 来衡量, 通过计算预测的用户评分与用户实际评分之间的差值来衡量预测的准确性, MAE越小, 相似性计算方法的度量准确度越高。假设预测的用户评分集为P={p, p2, …, pn}, 相应的实际评分集合为Q={q1, q2, …, qn}, 则:
其中n表示预测评分集P中的元素个数。
3.3 实验结果
实验先对皮尔逊相似性和多向测度相似性作比较。我们分别在基于用户和基于项目的情况下, 将多向测度与UBPS做了比较, 近邻数依次取为5、10、20、30、40、50, 图1显示了实验结果, 多向测度相似性准确度更好, 并在N=20左右效果最好, 同时在近邻数大于20后, MAE有上升趋势也反映多向测度相似性计算公式仍可以改进, 以提取出更多信息, 准确反映用户间真正相似性。在基于项目的情况下, 多向测度推荐精度较基于用户多向测度有一定提高, 尤其在小邻居集下, 效果提升明显。
接着, 对多向测度相似性和属性偏好相似性加权结合, 为确定混合过滤效果最好时的权值, 对E从0到1, 以0.1为间隔, 依次计算近邻数为5、10、20、30、40、50的MAE, 结果如图2所示, 除了近邻数为5时MAE在0.2时取最小值, 其他情况当E=0.1时MAE最小, 效果最好, 故选用E=0.1。
最后将基于用户的混合过滤与其他方法做了比较, 由图3可知, 基于用户的混合相似性小幅提高了推荐准确度, 并在用户近邻数较少时, 提升效果明显, 说明该方法对缓解数据稀疏有帮助。
4 结语
本文提出基于多向测度和属性偏好相似性的混合过滤方法, 以更好地度量相似性。本文在基于用户和基于项目的情况下, 对皮尔逊相似性和多项测度相似性做了对比, 多向测度相似性的结果比皮尔逊相似性有显著提高, 取得了更好的推荐精度。接着, 在基于用户多向测度相似性的基础上, 进一步考虑用户对属性的偏好作为相似性的一部分, 推荐精度有小幅提高。下一步工作可以考虑对多向测度相似性进行改进, 对项目属性的主成分提取, 以更好地描述用户或项目信息, 还可以考虑从用户文件中提取有效信息。
摘要：传统协同过滤算法中相似性度量方法存在度量不准确, 不能如实反映信息的问题, 导致推荐质量不高。针对这一问题, 提出一种新的基于多向测度和项目属性的相似性计算方法。利用多向测度方法计算用户对项目的评分相似性, 同时结合项目属性计算用户对项目属性的偏好相似度, 通过加权因子得到用户间的最终相似性。实验结果表明该方法较传统方法显著提高了推荐精度。
关键词：协同过滤,属性偏好,相似性度量
参考文献
[1]刘建国, 周涛, 汪秉宏.个性化推荐系统的研究进展[J].自然科学进展, 2009, 19 (1) :1-15.
[2]Iguchi M.Anonymous P2P web browse history sharing for web page recommendation[J].IEICE TRANSACTIONS on Information and Systems, 2007, 90 (9) :1343-1353.
[3]Velasquez J D, Palade V.Building a knowledge base for implementing a web-based computerized recommendation system[J].International Journal on Artificial Intelligence Tools, 2007, 16 (5) :793-828.
[4]Segrera Saddys, Moreno Maria.Application of multiclassifiers in web mining for a recommender system[J].Maria N.WSEAS Transactions on Information Science and Applications, 2006, 3 (12) :2471-2476.
[5]Wu Y, Zheng J.A collaborative filtering recommendation algorithm based on improved similarity measure method[C]//Progress in Informatics and Computing (PIC) , 2010 IEEE International Conference on.IEEE, 2010, 1:246-249.
[6]Feng Xie Zhen, Chen Hongfeng, Xu Xiwei, et al.TST:Threshold Based Similarity Transitivity Method in Collaborative Filtering with Cloud Computing[J].Tsinghua Science and Technology, 2013, 3:318-327.
[7]Bellogín A, Castells P, Cantador I.Improving memory-based collaborative filtering by neighbour selection based on user preference overlap[C]//Proceedings of the 10th Conference on Open Research Areas in Information Retrieval.LE CENTRE DE HAUTES ETUDES INTERNATIONALES D’INFORMATIQUE DOCUMENTAIRE, 2013:145-148.
[8]Sobhanam H, Mariappan A K.Addressing cold start problem in recommender systems using association rules and clustering technique[C]//Computer Communication and Informatics (ICCCI) , 2013 International Conference on.IEEE, 2013:1-5.
[9]夏培勇.个性化推荐技术中的协同过滤算法研究[D].中国海洋大学, 2011.
[10]Su X, Khoshgoftaar T M.A survey of collaborative filtering techniques[J].Advances in artificial intelligence, 2009:4.
属性相似度 篇2
入侵检测系统 (Intrusion Detection System, IDS) 是网络安全防卫体系中的关键部件。为了提高检测率, 在一个实际的分布式网络系统中往往需要配置多套IDS设备。由于网络上不同的IDS针对同一个安全事件都可能分别发出警报, 即使是同一个IDS也可能对某个安全事件发出多个警报。多个异类IDS的协同配置在有效增强网络系统安全性的同时, 会产生大量的重复报警或警报冗余, 从而给安全分析与管理工作造成沉重负担。警报聚合是对冗余警报进行聚类、合并处理的必要过程。目前常用的警报聚合方法主要是通过直接判断警报的攻击类型、源宿地址、时戳信息等特征属性是否完全相同 (精确匹配法) , 或者基于概率与统计分析的相似度算法 (可能性理论) [1,2]。本文认为模糊理论比精确匹配法和可能性理论更适合于处理入侵警报信息在雷同或相似“程度”上的不确定性, 因此本文算法基于模糊逻辑, 综合分析警报的攻击类型特征、时间特征、空间特征三维属性, 通过分别定义具体的隶属函数, 按照模糊相似度对入侵警报进行聚合。
2 算法基本原理
本算法的基本思想是依据如下经验知识:两个警报的攻击类型特征相同程度越高, 越有可能属于同一个攻击过程;两个警报的时间间隔越短, 越有可能属于同一个攻击过程;两个警报的源地址相近程度越高, 越有可能属于同一个攻击过程。
首先, 对于攻击类型特征属性, 从抽象到具体 (如attack-class, attack-type, sub-type, …, name) , 建立攻击特征类属Classification层次关系。文献[3指出网络攻击可按攻击意图划分为四类:发现类 (Discover) 、扫描类 (Scan) 、拒绝服务类 (DoS) 、权限提升 (Escalation) 。例如IP-Sweep属于发现类, PortScan属于扫描类, SYN-Flood属于拒绝服务类, Buffer-Overflow属于权限提升类。警报属性分类简化了聚合算法, 并提高了警报聚合效率, 因为只有从属于同一类别的警报才有可能被聚合在一起。
在不同的警报分类下, 时间、空间属性相似度有不同的考虑方法和侧重点, 讨论如下:
1) 发现类攻击警报主要是攻击者要探询某些IP、域名或者网络是否存在, 通常会在较短时间内发出大量查询信息, 因此源IP地址需要较大程度上精确匹配, 目标IP至少需要网络地址匹配, 查询时间间隔比较短, 因此对于发现类警报主要考虑这三种属性值, 另外还可以通过字符串属性来判断其查询的域名是否类似等;
2) 扫描类警报往往通过端口扫描和漏洞扫描工具进行, 因此此类警报主要是目标IP地址精确匹配, 源IP地址网络匹配 (因为有时其会发出一些伪造的IP地址包) , 格式串也很重要, 因为同一种工具发出的数据包往往有一些相同的特征在里面, 时间属性也需要重视, 有的扫描会在短时间内发出大量包, 但是有的扫描比较隐蔽, 比如可能隔几分钟或者发出一个包, 可以把时间间隔设置得比较大来聚合这类扫描警报, 这就需要动态调节时间;
3) 拒绝服务类警报通常由大量主机协同进行, 因此对源IP地址的匹配并无多大意义, 主要考虑的是目标IP和端口精确匹配, 时间间隔很短, 攻击数据包通常也是类似的, 因此数据包大小和格式串的匹配有时也可占一定权重;
4) 权限提升类警报一般是针对某一网络内所有主机或者单个目标主机以自动方式运行远程攻击程序, 因此主要考虑目标网络和目标端口的精确匹配, 通常源IP地址即为攻击者IP, 因为攻击程序相同, 因此数据报特征必然相同, 同时时间间隔也很小。
本算法的基本步骤为:首先根据警报中的攻击类型信息进行分类, 然后根据攻击源地址、目标地址、端口和时间信息合并重复警报或由同一攻击引起的多条警报, 融合警报信息, 消除冗余信息, 减少警报数量。每条原始警报均为已经后台信息转换模块转换后的标准入侵检测消息交换格式 (Intrusion Detection Message Exchange Format, IDMEF) 警报, 警报聚合的结果将产生若干超警报。超警报代表了一类原始警报, 每当有新警报idmef_newalert来临时, 警报聚合模块将idmef_newalert与已经存在的超警报比较, 通过相似度比较算法判决该警报是否与某超警报相似, 如是则加入该超警报, 否则自行成为一条新的超警报。
3 特征属性相似度的计算
对于攻击类型属性, 由于警报聚合的目的是尽可能地合并一次攻击产生的多个原始警报信息, 因此合并的这些原始警报必然具有相似的攻击类型, 可以将具有相似类型的多条警报合并为一条单一的聚合警报。文献[4,5]从多个阶段讨论和总结了多种分类策略与方法。警报聚合时按照设定的分类抽象粒度, 只需要对从属于同一类别的警报进行属性聚合即可。
定义攻击类型属性相似度:
对于某些攻击, 如类型未知的攻击或基于异常检测到的攻击, 还需要定义特征属性 (数据包、格式串等属性) 相似度:
对于空间特征属性, 分析不同类型攻击的源地址、宿地址、源端口、宿端口所具有的特性。由于攻击者通常会选择随机的源端口, 因此警报的空间特征主要针对源地址、宿地址及宿端口。表1列举了几种常见攻击的空间特征, 其中“/”表示无意义 (基于传输层以下协议的攻击, 宿端口是无意义的) 。对于不同类型的攻击具有不同的空间特征, 在警报聚合时, 需要为每类攻击指定空间特征。
定义IP地址属性相似度:
IP地址的比较基于无类别域间路由 (Classless Inter-Domain Routing, CIDR) 格式分析, IPv4地址由32位二进制数组成, r表示两IP地址从高位开始相等的位数。
定义端口属性相似度:
对于时间特征属性, 不同类型的攻击通常具有不同的时间特性。一次持续性攻击具有连续性, 并且由于这种攻击通常都是由攻击工具自动完成, 因此攻击进行的速度比较稳定。对不同的攻击事件给出不同的时间间隔阈值, 这个阈值由统计时间间隔的均值决定。注意到IDMEF定义了DetectTime、CreateTime、AnalyzerTime、StartTime、EndTime等多个时间属性, 为方便起见, 本文使用TimeStamp (或ntpstamp) 来描述, 而不涉及具体的时戳算法细节。
定义时间属性相似度:
4 基于多属性相似度的聚合算法
警报间的冗余关系包括重复关系和并发关系, 通过对多个冗余警报的聚合得到超警报 (Hyper-Alert, Meta-Alert) 。对于并发警报, 通过警报聚合, 同时得到攻击次数、攻击频度等信息。
定义1 (重复关系) 对于任意两个警报信息和, 除时间属性之外, 其它属性值均相同, 并且满足
则称和满足重复关系。其中, 为指定的时间间隔阈值。
定义2 (并发关系) 对于任意两个警报信息和, 除AgentId、时间属性之外, 其它属性值均相同, 并且满足
则称和满足并发关系。其中, 为指定的时间间隔阈值) 。
每类超警报由一张链表维护, 超警报链表按照某ntpstamp时间戳属性值递增排序。超警报与原始警报的唯一区别在于AdditionalData子类中的alertset属性, 而警报的类别由Classification子类的category属性标识。对于每条原始警报idmef_newalert, 判决算法如下:
从Classification子类中的category属性得知其所在警报类别, 对相应超警报链表中每条超警报Idmef_MetaAlert, 应用相似度比较算法:
1) 与每条超警报的比较是通过与超警报中包含的原始警报进行相似度比较, 本文的算法取其中五条ntpstamp属性值与Idmef_newalert最接近的原始警报, 然后取五个相似度值的平均值作为Idmef_newalert与Idmef_MetaAlert的相似度;
2) 取相似度最大的超警报作为最终判决的超警报, 如相似度低于预先设定的阈值, 则该警报成为一条新的超警报, 新的超警报通过复制该原始警报而成, 唯一的变化在于alertset属性, 将包含自身的警报消息标识;如果大于阈值, 则其属于该超警报, 只需要将自身的警报ID加入到该超警报的alertset属性中, 并保持alertset中的警报消息依然按ntpstamp时间递增排序。
5 结语
分布式IDS的协同配置在有效增强网络系统安全性的同时, 会产生大量的重复报警或警报冗余, 从而给安全分析与管理工作造成沉重负担。入侵警报聚合主要利用初级警报间的类型特征和时空属性相似性关系归并重复警报和并发警报, 是降低警报数量、提升警报质量的必要技术手段。为有效消除警报冗余、改善入侵检测的效果和性能, 本文提出了一种基于特征属性模糊相似度的入侵警报聚合算法。该算法基于模糊逻辑综合分析警报的攻击类型特征、时间特征、空间特征三维属性, 通过分别定义具体的隶属函数, 按照攻击类型和时空特征属性模糊相似度对入侵警报进行聚合, 并可通过设定不同的相似度阈值来调节聚合结果, 比传统的精确匹配法和概率统计方法更适合于处理入侵警报冗余信息的相似性。
摘要：分布式入侵检测系统的一个显著缺陷是会产生大量的重复警报。为有效消除警报冗余, 改善入侵检测的效果和性能, 本文提出了一种基于特征属性模糊相似度的入侵警报聚合算法。该算法基于模糊逻辑, 综合分析警报的攻击类型特征、时间特征、空间特征三维属性, 通过分别定义具体的隶属函数, 按照攻击类型和时空特征属性模糊相似度对入侵警报进行聚合, 比传统的精确匹配法和概率统计方法更适合于处理入侵警报信息的相似性。
关键词：警报聚合,入侵检测,模糊逻辑
参考文献
[1]Valdes A, Skinner K.Probabilistic Alert Correlation[A].Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection[C].Berlin:Springer-Verlag, 2001:54-68.
[2]龚俭, 梅海彬, 丁勇, 等.多特征关联的入侵事件冗余消除[J].东南大学学报, 2005, 35 (3) :366～371.
[3]DainOM, Cunningham RK.Fusinga Heterogeneous Alert Streamin to Scenarios[EB/OL].http://www.ll.mit.edu/mission/communications/ist/publications/acm_02_omd_rkc.pdf.
[4]王晓程, 刘恩德, 谢小权.攻击分类研究与分布式网络入侵检测系统[J].计算机研究与发展, 2001, 38 (6) :727-734.
疾病相似度方法研究 篇3
近年来, 相似度的研究在生物医学领域正受到各方的高度关注, 如:基因序列相似度[1]、生物本体术语的相似度[2]、药物相似度[3]等。而相似度就是指定量估算事物的相似性, 事物间的相似性则主要由事物之间的共同属性进行决定并确定。一个具体的事物, 总是有许许多多的性质与关系, 在此即将一个事物的性质与关系都称做该事物的属性。事物的形状、颜色、气味、美丑、善恶、优劣、用途等都是事物的性质;而包含、被包含、整体、部分、大于、小于、压迫、反抗、朋友、热爱、同盟、矛盾等, 则都是事物的关系。并且任何属性都是属于某种对象的。比较事物的相似度就是定量评估事物间的共同属性。
疾病相似度则是对疾病与疾病之间相似性的量化过程。疾病相似性是疾病与疾病之间的共同属性。疾病的属性包括:疾病与疾病之间的共同关系、疾病与疾病之间共同的关联因素。疾病与疾病之间的共同关系又包括:疾病与疾病之间的包含关系, 如:‘乳腺癌’包含‘男性乳腺癌’和‘女性乳腺癌’。‘乳腺癌’与‘男性乳腺癌’及‘女性乳腺癌’的关系是包含与被包含的关系。‘男性乳腺癌’与‘女性乳腺癌’即通过‘乳腺癌’得到了关联。疾病与疾病之间共同的关联因素包括:共同的致病基因、共同的治疗药物、共同的代谢产物等。例如, 基因‘NOS3’和‘AGTR2’是疾病‘乳腺癌’和‘糖尿病’的共同的致病基因;药物‘caffeine’和‘cisplatin’都是疾病‘乳腺癌’和‘卵巢癌’的治疗药物;代谢产物‘D-Glucose’和‘3-Methylhistidine’都是疾病‘类型2糖尿病’和‘阿尔茨海默氏病’共同相关的代谢产物。
1 疾病相似度发展现状
如图1所示, 计算疾病相似度的方法通常可以从两个角度考虑:基于语义关联计算疾病相似度、基于疾病相关的基因计算疾病相似度。生物医学领域经常利用本体计算术语的语义相似度, 如:基因本体[4]、人类表型本体[5]等。尽管如此, 这些方法中却只有很少一部分已用于计算疾病相似度。Resnik设计的方法即是其中最为常见的方法[6], 该方法更多是应用于基因本体计算基因功能、细胞构成、生物学过程术语的相似度, 而且若与其它多种方法 (union-intersection、longest shared path、JC) [7]相比, 则具有明显的优势[8]。Resnik的方法是利用本体中的‘is_a’关系计算术语相似度, 该方法计算疾病对之间的相似度主要依赖于疾病对信息量最大的共同祖先节点。而Lin的方法[9]则改进了Resnik的方法中对信息熵的比较方法, 从理论角度对Resnik的方法进行了一定的完善。Resnik和Lin的方法最近已由研究人员写入R包[10], 以方便计算疾病的相似度。Wang等人提出的方法对Resnik的方法进行了更深层的优化[11]。该方法在计算疾病对相似度时, 不仅考虑了疾病对的信息量最大的共同祖先节点, 还考虑了疾病对其它的共同祖先节点。该方法的优越性在基因本体中得到了更好的体现, 并且已用于计算医学主题词中的疾病术语语义相似度。
疾病的关联不仅体现在疾病相关的本体上, 而且体现在共同的致病基因上。因此, 研究人员同样关注如何基于疾病的致病基因计算疾病的相似度。目前存在两种基于基因计算疾病相似度的方法。第一种是基于共同的疾病基因 (based on overlapping gene set-BOG) 的方法[12]。该方法比较疾病之间共同相关的基因数目, 由此而获取疾病相似度。若与基于语义的角度计算相似度相比, 该法则从一个全新的角度发现相似的疾病对。因此, 该方法能发现新的未知疾病关联。尽管如此, 在计算疾病相似度时, 该方法却未考虑疾病基因之间的功能关联, 而显然可见的是这种关联对疾病相似度却有着一定影响。第二种方法即基于过程相似性 (process similarity based-PSB) 计算疾病相似度[13], 其中, 过程指的是致病基因相关的基因本体的生物学过程术语。该方法考虑了疾病基因的功能关联, 因此对BOG方法有了很大的提高。PSB与Resnik、Lin、LC和JC的方法相比, 也呈现了良好的性能。基因间的功能关联包含很多方面, 如:基因共表达、蛋白质相互作用、基因本体术语等。另外, 为了提高疾病相似度方法的性能, Fun Sim方法利用综合加权的人类基因关联网络[14]计算疾病相似度。
2 集成的疾病相似度算法
本文集成了疾病之间的基因关联和语义关联, 提出了集成的疾病相似度算法Fun Sim Wang, 计算公式如下:
其中, d1和d2是一对疾病, G1和G2分别是d1和d2相关的基因集, |G1|和|G2|则分别是G1和G2包含的基因数;GA1表示G1和G2信息量最小的共同祖先节点, GAi表示GA1的第i个祖先节点, Fun Sim (d1, d2) 表示了d1和d2之间的功能相似度, 而α表示的是‘is_a’关系表达的语义关联参数。基于Wang等人的研究, α=0.8。
3 验证过程
在图2中, 圆圈表示疾病本体[15]中的疾病术语, 圆圈之间的联系表示疾病术语之间的‘is_a’关系, 其中箭头指向为父节点, 另外一个则是子节点。相似的疾病基准集包括两个疾病集, 并分别来自于两篇文献。具体地, 一个疾病集来自于Suthram等人的研究[16]。该研究利用表达谱数据设计算法寻找到相似的疾病对, 再利用药物进行验证。另外一个疾病集则来自于Pakhomov等人的研究[15], 该数据集通过两个医学专家的联合验证而最终得到[17]。在此将这两部分疾病集合并为基准集, 共有47个疾病, 70个疾病对。以基准集作为正例, 同时从疾病本体中随机地抽取700个疾病对作为反例。更利用五种相似度算法计算相似度, 比较得到的相似度接受者操作特性曲线 (receiver operating characteristic curve–ROC curve) [18]。该验证方法共产生了100个随机的疾病对, 分别实验了100次, 以提高实验的真实可靠性。
4 实验结果与分析
图3 (a) 给出了通过每种方法得到的ROC曲线, 图的横坐标表示特异性, 图的纵坐标表示敏感性。由图可知, 通过每种方法得到的ROC曲线下方的面积分别为:Resnik (63.14%) 、Lin (66.17%) 、Wang (68.04%) 、BOG (78.10%) 、PSB (89.52%) 、Fun Sim (94.37) 、Fun Sim Wang (95.36%) 。对于每种方法而言, ROC曲线下方的面积 (AUC) 越大, 表明方法性能越好。而由图3中ROC曲线下方的面积清楚显示了Wang的方法比Resnik的方法有了一点提高, 且Wang的方法和Resnik方法得到的面积非常接近。显而易见, 在基于基因的方法中, BOG方法的性能是最差的。尽管通过PSB方法得到了很高的性能, Fun Sim仍然将PSB方法的性能提高了5%左右。在融合了基因功能和语义关联后, Fun Sim Wang方法已将性能提高到接近100%。
为了避免实现结果由于偶然的因素造成, 研究随机生成了100份疾病对集合, 并进行了100次实验。实验结果如图3 (b) 所示。图中横坐标是疾病相似度方法, 纵坐标是平均的AUC值。由该图可知, 平均的AUC值分别为:Resnik (63.45%) 、Wang (67.84%) 、BOG (76.57%) 、PSB (89.84%) 、Fun Sim (94.15%) 、Fun Sim Wang (95.56%) 。所得结果与图3 (a) 的结论亦保持了一致。
在七种疾病相似度方法中, Resnik的方法利用最大信息量共同祖先的信息熵识别疾病间的语义关联。在基准集中, 有一些疾病对仅存一个共同的祖先节点 (根节点) 。因此, 根据Resnik方法, 这些疾病对的疾病相似度即为0。例如:疾病对‘diabetes mellitus (DOID:9351) ’和‘Alzheimer’s disease (DOID:10652) ’的相似度为0, 因为在疾病本体中, 该疾病对的最大信息量共同祖先是根节点, 而根节点的信息量为0。为了避免错误地理解相似的疾病对, Sem Sim中就没有使用信息量。如此一来, 发生以上的情况时, 疾病相关的基因功能关联就能发挥应有作用。图3中的ROC曲线表明SemFun Sim方法取得了最高的AUC值, 这即充分验证了被集成进来的语义关联对识别真阳性率和减少假阴性率已获明显提高。
5 结束语
本文提出了一种新的疾病相似度算法。该算法融合了语义关联与基因功能关联。语义关联是指疾病与疾病之间通过疾病本体的‘is_a’关系建立的关联。基因功能关联指的是疾病相关的基因之间存在的功能关联, 包括:基因本体术语关联、蛋白质相互作用关联、共表达关联等。本文利用基准集 (70个相似的疾病对) 及100个来自疾病本体的随机集 (700个疾病对) , 对Fun Sim Wang方法进行了性能评估。而且, 在ROC曲线之下的面积已经达到了95.56%, 该结果表明Fun Sim Wang获得了一个非常高的真阳性率和非常低的假阴性率。
摘要：本文研究了集成语义与基因功能关联的疾病相似度方法。综合的加权的人类基因关联网络可用于衡量疾病相关的基因集之间的关联分值;疾病术语对以及其在疾病本体中的共同祖先相关的基因数可用于计算疾病术语的语义关联分值。这两类关联被用于计算集成的疾病相似度。通过从文献中搜集相似的疾病对作为基准集, 对疾病相似度算法的性能进行了有效的评价, 证实了集成的疾病相似度方法优于已有的其他方法。
词语相似度计算方法分析 篇4
词语相似度计算研究的是用什么样的方法来计算或比较两个词语的相似性。词语相似度计算在自然语言处理、智能检索、文本聚类、文本分类、自动应答、词义排歧和机器翻译等领域都有广泛的应用,它是一个基础研究课题,正在为越来越多的研究人员所关注。笔者对词语相似度计算的应用背景、研究成果进行了归纳和总结,包括每种策略的基本思想、依赖的工具和主要的方法等,以供自然语言处理、智能检索、文本聚类、文本分类、数据挖掘、信息提取、自动应答、词义排歧和机器翻译等领域的研究人员参考和应用。词语相似度计算的应用主要有以下几点:
(1)在基于实例的机器翻译中,词语相似度主要用于衡量文本中词语的可替换程度。
(2)在信息检索中,相似度更多的是反映文本与用户查询在意义上的符合程度。
(3)在多文档文摘系统中,相似度可以反映出局部主题信息的拟合程度。
(4)在自动应答系统领域,相似度的计算主要体现在计算用户问句和领域文本内容的相似度上。
(5)在文本分类研究中,相似度可以反映文本与给定的分类体系中某类别的相关程度。
(6)相似度计算是文本聚类的基础,通过相似度计算,把文档集合按照文档间的相似度大小分成更小的文本簇。
1 基于语料库的词语相似度计算方法
基于统计方法计算词语相似度通常是利用词语的相关性来计算词语的相似度。其理论假设凡是语义相近的词,它们的上下文也应该相似。因此统计的方法对于两个词的相似度算建立在计算它们的相关词向量相似度基础上。首先要选择一组特征词,然后计算这一组特征词与每一个词的相关性(一般用这组词在实际的大规模语料中在该词的上下文中出现的频率来度量),于是,对于每一个词都可以得到一个相关性的特征词向量,然后计算这些向量之间的相似度,一般用向量夹角余弦的计算结果作为这两个词的相似度。
Lee利用相关熵,Brown采用平均互信息来计算词语之间的相似度。李涓子(1999)利用这种思想来实现语义的自动排歧;鲁松(2001)研究了如何利用词语的相关性来计算词语的相似度。PBrownetc采用平均互信息来计算词语之间的相似度。基于统计的定量分析方法能够对词汇间的语义相似性进行比较精确和有效的度量。基于大规模语料库进行的获取受制于所采用的语料库,难以避免数据稀疏问题,由于汉语的一词多义现象,统计的方法得到的结果中含有的噪声是相当大的,常常会出现明显的错误。
2 基于本体库的词语相似度计算方法
2.1 常用本体库
关于Ontology的定义有许多,目前获得较多认同的是R.Studer的解释:“Ontology是对概念体系的明确的、形式化的、可共享的规范说明”。在最简单的情况下,本体只描述概念的分类层次结构;在复杂的情况下,本体可以在概念分类层次的基础上,加入一组合适的关系、公理、规则来表示概念间的其它关系,约束概念的内涵解释。
Word Net是一个联机英语词汇检索系统,由Prince-ton大学研制。它作为语言学本体库同时又是一部语义词典,在自然语言处理研究方面应用很广。它采用语义网络作为其词汇本体的基本表示形式。在Word Net中,网络节点由字形(Wordform)标识,分为名词、动词、形容词、副词和功能词等5种。节点之间的关系分为同义关系(Synonymy)、反义关系(Antonymy)、继承关系(Hypony-my)、部分/整体关系(Meronymy)、形态关系(Morpholog-icalrelation)等。Word Net提供了很好的概念层次结构。
知网是一个以汉语和英语词语所代表的概念为描述对象、以揭示概念与概念之间以及概念所具有属性之间的关系为基本内容的常识库和知识库。其中包含丰富的词汇语义知识和本体知识,这些关系都隐含在知网的知识词典和义原的特征文件中。知网中有以下两个主要的概念:
(1)义项。它是对词汇语义的一种描述,每一个词可以表达为几个义项。义项是用一种知识表示语言来描述的,这种知识表示语言所用的词汇叫做义原。
(2)义原。它是用于描述一个概念的最小意义单位,从所有词汇中提炼出的可以用来描述其他词汇的不可再分的基本元素。
与一般的语义词典(如同义词、词林或Word Net)不同,知网并不是简单地将所有的概念归结到一个树状的概念层次体系中,而是试图用一系列的义原来对每一个概念进行描述。
知网的汉语知识库中每个词汇由一个四元组表示:
DEF部分是表示词与义原的关系,也是词汇描述中最重要的部分,可以简单地认为词是由义原通过某种关系构成的。
2.2 相似度计算方法分析
根据本体知识来计算。主要是基于按照概念间结构层次关系组织的语义词典方法,根据概念之间的关系来计算词语的相似度。这类方法通常依赖于比较完备的大型语义词典,一般词典都是将所有的词组织在一棵或几棵树状的层次结构中,在一棵树型图中,任何两个节点之间有且只有一条路径,这条路径的长度就可以作为这两个概念的语义距离的一种度量。
传统基于本体的概念之间相似度计算模型主要有基于距离的语义相似度计算模型、基内容的语义相似度计算模型和基于属性的语义相似度计算模型3种。
刘群等人利用知网作为语义词典计算汉语词汇的相似度;Rada等人和Lee等人通过计算在Word Net中词节点之间上下位关系构成的最短路径来计算词语之间的相似度。许多学者考虑到其他因素对语义距离的影响,如Resnik根据两个词的公共祖先节点的最大信息量来衡量两个词的语义相似度;Agirre等人在计算词语的语义相似度时,除了节点间的路径长度外,还考虑到概念层次树的深度和区域密度的影响。张瑞霞等人提出了一种基于知识图的汉语词汇相似度计算方法,该方法以知识图为知识表示方法,在构造词图的基础上对词汇概念中的义原进行分类,通过计算不同类型义的相似度得到概念的相似度。
3 比较与总结
这两种方法各有特点。基于世界知识的方法简单有效,无需用语料库进行训练,也比较直观,易于理解,但这种方法得到的结果受人的主观意识影响较大,有时并不能准确反映客观事实。另外,这种方法比较准确地反映了词语之间语义方面的相似性和差异,而对于词语之间的句法和语用特点考虑得比较少。基于语料库的方法比较客观,综合反映了词语在句法、语义、语用等方面的相似性和差异。但是,这种方法比较依赖于训练所用的语料库,计算量大,计算方法复杂,另外,受资料稀疏和资料噪声的干扰较大。
参考文献
[1]秦春秀,赵捧未,刘怀亮.词语相似度计算研究[J].信息系统.2007.
[2]余超.基于知网的词汇语义计算研究及应用[D].辽宁:沈阳航空工业学院.2007.
[3]刘紫玉,黄磊.基于领域本体模型的概念语义相似度计算研究[J].计算机技术与发展.2010.
[4]http://wordnet.princeton.edu/.
[5]http://www.keenage.com/.
[6]孙海霞,钱庆,成颖.基于本体的语义相似度计算方法研究综述[J].知识组织与知识管理.2010.
[7]刘群,李素建.基于《知网》的词汇语义相似度计算[J].计算语言学及中文信息处理.2002.
本体相似度计算方法研究 篇5
本体映射算法以两个本体作为输入, 然后为这两个本体的各个元素 (概念、属性或者关系) 建立相应的语义关系。相似性提取是本体映射的一个重要步骤, 它主要是进行概念相似度的计算, 提高语义相似度计算精度成为提高语义信息检索质量的关键之一。语义相似度一般是指计算本体概念间的相似度, 多数方法所考虑的概念是基于一个本体的, 跨本体概念间的方法比较少。MD3模型是一种典型的计算跨本体概念间相似度的方法。
1 MD3模型
Triple Matching-Distance Model (MD3) 模型是一种跨本体概念间相似度计算框架。计算实体类a和b之间的相似度通过计算同义词集、特征属性和语义邻居之间的加权和, 公式如下:
其中w, u, v表示了各组成部分的重要性。特征属性细化为组成部分、功能以及其他属性。概念a和b的语义邻居及其特征属性 (即概念的部分、功能及其他属性) 也通过同义词集合描述, 每一个相似度的计算都通过Tversky公式:
其中A, B分别表示概念a和b的描述集合, A-B表示属于A但不属于B的术语集 (B-A相反) 。参数 (a, b) 由概念a和b和在各自层次结构中的深度确定。
2 EMD3模型
MD3模型的不足在于没有考虑对象实例对概念的影响, 同时其语义邻居只考虑语义关系中层次之间的相似度, 没有考虑非层次之间的相似度。本文在MD3模型的基础上, 参考了其概念名称相似度、特征属性, 对本体的结构以及概念描述两方面做了扩充, 重点讨论了跨本体概念间非层次关系的相似度的比较和实例对概念相似度的影响, 把MD3模型扩展到Extension of Triple Mapping Distance model (EMD3) 模型。
2.1 概念属性的相似度
属性有属性名称、属性数据类型、属性实例数据等要素, 因此判断两个属性是否相似主要从这三个要素来考虑。属性名称、属性类型本身是文本类型, 是字符串, 因此可以采用字符串相似度计算方法进行判定。例如用Humming distance来比较两字符串。设两字符串s和t, 则它们之间的相似度可由下式给出:
其中:若s[i]=t[i], 则f (i) =0;否则f (i) =1。由于每个概念的实例对该概念的每个属性都分配了一个相应的值, 对于其他类型的数据, 可以采用下面介绍的方法进行计算。
设概念A的属性为ai, 概念B的属性为bj, 两个属性之间的相似度的计算公式为:
其中wi是权重, 代表属性名称、数据类型、属性实例数据对属性相似度计算的重要程度, 且和为1。设概念A, B之间总共计算出m个sim (ai, bj) , 并设置相应的权值kl, 则概念之间基于属性的相似度为:
2.2 概念名称相似度
知网中概念的语义用义原来描述, 义原是描述概念语义的最小单位, 一共有1500多个义原。由于所有义原根据上下位关系构成了一个树状的层次体系, 所有可以用语义距离计算相似度。假设两个义原在该层次体系中的路径为d, 可以得到两个义原之间的语义相似度如下:式中a是一个可以调节大小的因子。在知网中一个概念由多个义原描述, 所以我们只要计算每个义原的相似度来考虑其重要性, 就可以得到概念之间的名称相似度。计算方法如下:, 其中m, n为概念c1, c2的义原数, wi为第i个义原所占的权重。
2.3 语义关系的相似度
语义关系包括层次语义关系和非层次语义关系, 层次语义关系具有有向传递性, 非层次关系不具有传递性 (如关联关系) 。
(1) 层次语义关系的计算
本文借鉴参考文献[1]中的方法来计算层次语义关系, 利用语义邻居的概念, 以实体为中心向周围辐射, 设定一个语义半径, 半径取值的大小反映与实体之间的亲疏关系。划定语义邻居的范围集合进行匹配, 取集合中的最大值作为语义邻居之间的相似度。语义邻居计算公式如下:
层次语义关系相似度计算:其中A, B分别代表实体a, b的语义邻居集合。
(2) 非层次语义关系的计算
上位词:定义概念的上位词为概念所有父类的集合, 公式如下:UC (Ci, H) ={CjC|H (Ci, Cj) }
基于概念上位词的定义, 定义概念的匹配公式:
与概念相关的非层次关系:如果关系的定义域或值域是概念c, 则称这些关系为与概念c相关的非层次关系, 公式如下:
还可以进一步把非层次关系细化为概念的In关系和Out关系 (可以认为非层次关系的方向是从定义域到值域, 凭此来定义In和Out的关系) , In关系指概念c是非层次关系的值域, 公式如下:。而Out关系指的是概念c是非层次关系的定义域, 公式如下:
比较概念的非层次关系, 首先应该找出两个本体中与这两个概念相关的同类非层次关系 (无需考虑不同类的非层次关系) , 进而比较这些同类非层次关系的另外一项之间的相似度 (如果要比较的概念是非层次关系的定义域, 分别找出这个关系的值域, 通过概念匹配公式对其进行比较, 反之亦然) 。
下面以In关系为例描述比较的过程:其中RaP-I表示本体p中与概念a相关的In关系, 而Rqb-I表示本体q中与概念b相关的In关系, 所以其交集RI表示本体p, q中与概念a, b相关的公共In关系集合。如果概念a, b没有公共的In关系, 则RI为空, 无需下面的计算。对于公共In关系集合, 公式如下:对In关系和Out关系进行加权综合, 得到非层次关系相似度的公式如下:
其中i, o为权值, 反映的是非层次关系的值域与定义域对概念相似度的影响程度。对层次关系和非层次关系计算结果进行综合, 得到概念语义环境的相似度计算公式如下:
其中t, u分别是层次关系和非层次关系的权重, 因为在本体中层次关系要比非层次关系的重要性高, 所以在计算中应该赋以较大的值, 即t>0.5>u, 且t+u=1。
2.4 概念实例特征的相似度
基于实例特征计算相似度的理论依据是, 如果概念所具有的实例全部都相同, 那么这两个概念是相同的;如果两个概念具有相同实例的比重是相同的, 那么这两个概念是相似的。对于概念A, B的具体实例, 可以用Jaccard系数来计算相似度:
其中P (A, B) 表示一个实例既属于概念A又属于概念B的概率, 表示一个实例属于概念A但不属于B的概率。
2.5 结论
由上面的分析, 综合了各个部分相似度的值, 得到跨本体概念间相似度的综合公式如下:
其中m, n, r, t为各个部分所占的权重, 根据各个部分重要性的不同m, n, r, t分别被赋以不同的值, 并且m+n+r+t=1。
3 结语
本文扩展的模型充分继承了MD3模型的优点, 并对MD3模型进行了优化。在选择了适当权重的前提下, EMD3模型能够确保语义相似度的计算更准确, 更全面。但是在语义相似度计算过程中存在着大量权重的设定问题, 对模型的性能有一定的影响。如何准确高效地设定权重是未来值得深入研究的问题。
摘要：MD3模型是一种系统的跨本体概念间相似度的计算方法, 这种方法无需建立一个集成的共享本体。本文在MD3模型的基础上, 充分利用本体对概念的描述信息, 重点讨论了跨本体概念间非层次关系相似度的计算, 把MD3模型扩展到EMD3模型, 使得概念间相似度的计算理论上更全面、更精确。
关键词：本体,元数据模型,语义相似度,MD3模型
参考文献
[1]Rodriguez M A, Egenhofer M J.Determining Semantic SimilarityAmong Entity Classes from Different Ontologies.IEEE Trans.onKnowledge and Data Engineering.2003.
[2]徐德智, 肖文芳, 王怀民.本体映射过程中的概念相似度计算[J].计算机工程与应用.2007.
[3]陈杰, 蒋祖华.领域本体的概念相似度计算[J].计算机工程与应用.2006.
[4]李鹏, 陶兰, 王弼佐.一种改进的本体语义相似度计算及其应用[J].计算机工程与设计.2007.
[5]Alexander Budanitsky, Graeme Hirst.Evaluating WordNet-basedMeasures of Lexical Semantic Relatedness[J].Computational Linguis2tics.2006.
Java错误堆栈相似度计算 篇6
在服务器端运行的java程序会产生java错误报告,在这些错误报告中包含了大量的java错误堆栈。程序的维护人员会根据这些java错误堆栈对程序进行修改。为了提高解决问题的效率,人们希望能够自动地对错误堆栈进行分类,根据错误堆栈的类别,采取相应的方法解决问题。在这个过程中,会比较错误堆栈之间的相似度。
Jav的错误堆栈是由一系列的字符串组成,因此在比较Jav错误堆栈之间相似度的时候,往往会用到字符串相似度比较算法。现在字符串相似度方法有很多,比如最长公共子串算法(Longest Common Subsequence缩写为LCS)[1],它是根据两个字符串之间最长的公共子串的长度来计算字符串之间的相似度,此算法的算法复杂度为,其中m,n,是两个字符串之间的长度。LeveinshteinDistance也被称作编辑距离[2],它是根据由一个字符串变成另外一个字符串所需要的操作数来衡量字符串之间的相似度,这些操作包括插入、删除、更改字符。该算法的算法复杂度也是,其中m,n,是两个字符串之间的长度。汉明距离(Hamming Distance )[3]也是一种计算字符串相似度的算法。该算法是根据两个相同长度字符串之间对应位置的不同字符的个数来计算字符串之间的相似度。此算法的算法复杂度是,其中m是字符串的长度,但是该算法只适用于两个相同长度字符串之间相似度的比较。这些字符串相似度比较算法广泛地应用于和字符串相关的领域中,但是这些算法并不是针对Java错误堆栈而设计的,java错误堆栈有其自身的特点,以上的字符串相似度比较算法不能很好地衡量错误堆栈之间的相似度。
图1是Java错误堆栈的一个例子,一个java错误堆栈里面包含了很多的字符串,在这里我们称每一行字符串为error trace。在错误堆栈分类的过程中,其实比较的是error trace之间的相似度。在比较error trace相似度的过程中,如果使用最长公共子串算法或者Levenshtein Distance, 那么这只能比较它们最大的公共部分,并不有很好地说服性,另外在java程序中,如果使用的包的名字或者类的名字更改的话,这会对算法的效果产生很大的影响,并且这些算法的算法复杂度过高,随着error trace的长度的增加,算法的效率会下降很多,所以这些算法并不能很好地适用java error trace的相似度比较。因此我们提出了一种新的java错误堆栈相似度比较的算法。
2方法说明
在我们的算法中,我们首先对Hamming Distance进行了改良,使其适用于不同长度字符串之间的相计算。我们称新的算法是Length Adapted Hamming Distance (简称LA Hamming Distance或者LAHD)。
2.1 LAHD
LAHD算法的核心思想是把两个长度不同的字符串中的长度较长的字符串进行修改,把多余的部分删除掉,然后利用Ham.ming Distance计算剩余的字符串之间的相似度,然后再加上删除部分的长度,这样就计算出了两个长度不同的字符串之间的相似度。
在图2中详细地描述了LAHD算法的过程。我们用A,B代表两个字符串,其中A的长度要大于B,我们用C代表字符串A除去比字符串B长的那一部分后的子串。那么在图2的例子中,A代表的是org.hibernate.persister.entity, B代表的是org.apache.struts.ac.ion, C代表的是rg.hibernate.persister. .那么字符串A和B之间的LAHD距离为:
其中代表的是字符串B和字符串C之间的Hamming Distance. 代表的是字符串A和字符串B的长度。在图二的例子中是M与N的和,是用P表示。那么A与B之间的相似度:
2.2三段法
Java错误堆栈中包含了很多的error trace,文章上文中提到的算法在计算error trace相似度的时候把error trace当成一个整体而我们设计的算法并不是这样的,一个error trace中包含了包的名字、类的名字以及函数的名字,根据error trace的特点,我们设计出了我们的算法,我们称之为三段法。
在图3中详细说明了我们算法的基本原理。首先我们根据errotrac的特点,把errotrac进行划分,分为三部分:包名、类名、函数名。然后分别计算这三部分的相似度,每一部分用不同的算法来计算,其中包名之间的相似度是使用Length Adapted Ham.ming Distance (简称为LA Hamming Distance)来计算的,因为在整个java error trace中包的名字最长,如果使用其它的两种方法会使算法的效率下降很多。类名和函数名都是使用最长公共子串算法来计算的(原因我们会在实验中说明)。最后对这三部分的相似度进行加权求和(关于各个部分的权值是根据实验得来的,我们会在试验中说明)。这样就可以计算出相似度。
3实验结果
首先,我们在错误堆栈中提取了100条数据,然后请熟悉堆栈分类的人对这些数据进分类,然后我们利用K-means[4]算法对这些算法进行聚类,在聚类的过程中我们要计算不同类别之间的距离,我们在这个过程中使用了三种方法来衡量这些类别之间的距离,这三中方法是Single-Linkage[5],Complete-Linkage[6], Average-Linkage[6]。最后机器分类的结果与人工分类的结果进行比较,得到机器分类的准确率
我们通过实验,得到了在包名,类名以及函数名的权值分别取0.35,0.40,0.25的情况下,准确率的值最高。
表一中列出了在不同聚类算法的情况下,我们的算法和其它算法的准确率的信息。通过上表可以看出,我们算法的准确率要明显高于Hamming以及levenshtein距离。而且我们的算法和LCS算法的准确率的差距并不大。这也是我们使用LCS算法而不使用Levenshtein Distance来计算类名以及函数名相似度的原因。
通过实验,我们得出Levenshtein Distance, Hamming Distance, LCS以及我们算法所花费的时间分别为38.5464ms,0.1661ms,21.5883ms,7.5089ms。可以看出,我们的算法要比Levenshtein Distance以及LCS要高很多。但是要比Hamming Distance要低。
旅游本体的概念相似度算法改进 篇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关系为基础,不仅考虑了概念所包含的子节点个数和所处深度,而且将该概念所处的簇及父节点的信息内容值引入到模型中,使得概念的信息内容值更为精确。实验结果显示将该模型应用到领域本体的概念相似度计算中,可以明显提高现有相似度算法的性能。