人工智能：基于抽样的不确定图k最近邻搜索算法

《人工智能：基于抽样的不确定图k最近邻搜索算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第３４卷第６期计算机应用与软件Ｖｏｌ３４Ｎｏ．６２０１７年６月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＪｕｎ．２０１７基于抽样的不确定图ｋ最近邻搜索算法张伟（东北大学计算机科学与工程学院辽宁沈阳１１０８１９）摘要在诸如生物网络或社交网络等各种由不确定数据组成的网络中，不确定图是一种十分重要和普遍使用的数学模型。由于不确定图中计算两点连通概率问题是＃Ｐ完全问题，其ｋ最近邻查询问题要比确定图复杂得多，并且与“距离”的定义相关。采用“最短距离”作为距离定义，讨论了在不确定图是加权图的情况下，求解ｋ最近邻搜索问题（ｋＮＮ问题）

2、。为了克服计算两点连通概率带来的时间指数爆炸问题，提出了一个基于Ｄｉｊｋｓｔｒａ算法的抽样ｋＮＮ查询算法，研究了其收敛性和收敛速度，同时通过实验验证了所提出的方法效率优于ｋＭｉｎＤｉｓｔ方法并且具有很高的查全率。关键词人工智能不确定图概率图生物网络ｋＮＮ抽样技术中图分类号ＴＰ３１１．１３ＴＰ３９２文献标识码ＡＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１７．０６．０３３ＫＮＥＡＲＥＳＴＮＥＩＧＨＢＯＲＳＥＡＲＣＨＡＬＧＯＲＩＴＨＭＦＯＲＵＮＣＥＲＴＡＩＮＧＲＡＰＨＳＢＡＳＥＤＯＮＳＡＭＰＬＩＮＧＺｈａｎｇＷｅｉ（Ｃｏｌｌ

3、ｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ１１０８１９，Ｌｉａｏｎｉｎｇ，Ｃｈｉｎａ）ＡｂｓｔｒａｃｔＵｎｃｅｒｔａｉｎｇｒａｐｈｓａｒｅａｖｅｒｙｉｍｐｏｒｔａｎｔａｎｄｗｉｄｅｌｙｕｓｅｄｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｉｎｎｅｔｗｏｒｋｓｃｏｍｐｏｓｅｄｏｆｕｎｃｅｒｔａｉｎｄａｔａｓｕｃｈａｓｂｉｏｌｏｇｉｃａｌｎｅｔｗｏｒｋｓｏｒｓｏｃｉａｌｎｅｔｗｏｒｋｓ．Ｓｉｎｃｅｔｈｅｔｗｏｐｏｉｎｔｃｏｎｎｅｃｔｉｖｉｔｙｐｒｏｂａｂｉｌｉｔｙｐｒｏ

4、ｂｌｅｍｉｎｔｈｅｇｒａｐｈｉｓａｃｏｍｐｌｅｔｅｐｒｏｂｌｅｍ，ｔｈｅｋｎｅａｒｅｓｔｎｅｉｇｈｂｏｒｑｕｅｒｙｐｒｏｂｌｅｍｉｓｍｕｃｈｍｏｒｅｃｏｍｐｌｅｘｔｈａｎｔｈｅｎｏｒｍａｌｇｒａｐｈａｎｄｉｓｒｅｌａｔｅｄｔｏｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆ＂ｄｉｓｔａｎｃｅ＂．Ｕｓｉｎｇｔｈｅｓｈｏｒｔｅｓｔｄｉｓｔａｎｃｅａｓｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆｄｉｓｔａｎｃｅ，ｗｅｄｉｓｃｕｓｓｔｈｅｋｎｅａｒｅｓｔｎｅｉｇｈｂｏｒｓｅａｒｃｈｐｒｏｂｌｅｍ（ｋＮＮ）ｕｎｄｅｒｔｈｅｃｏｎｄｉｔｉｏｎｔｈａｔｔｈｅｕｎｃｅｒｔａｉｎｇｒａｐ

5、ｈｉｓａｗｅｉｇｈｔｅｄｇｒａｐｈ．Ｉｎｏｒｄｅｒｔｏｏｖｅｒｃｏｍｅｔｈｅｐｒｏｂｌｅｍｏｆｔｉｍｅｅｘｐｏｎｅｎｔｉａｌｅｘｐｌｏｓｉｏｎｃａｕｓｅｄｂｙｃｏｍｐｕｔｉｎｇｔｗｏｐｏｉｎｔｃｏｎｎｅｃｔｉｖｉｔｙｐｒｏｂａｂｉｌｉｔｙ，ａｓａｍｐｌｉｎｇｋＮＮｑｕｅｒｙａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｃｏｎｖｅｒｇｅｎｃｅｒａｔｅａｎｄｃｏｎｖｅｒｇｅｎｃｅｒａｔｅａｒｅｓｔｕｄｉｅｄ．Ｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｉｓｐｒｏｖｅｄｔｏｂｅｍｏｒｅｅｆｆｉｃｉｅｎｔｔｈａ

6、ｎｋＭｉｎＤｉｓｔｍｅｔｈｏｄａｎｄｈａｓｈｉｇｈｒｅｃａｌｌｒａｔｅ．ＫｅｙｗｏｒｄｓＡｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅＵｎｃｅｒｔａｉｎｇｒａｐｈｓＰｒｏｂａｂｉｌｉｔｙｇｒａｐｈＢｉｏｌｏｇｉｃａｌｎｅｔｗｏｒｋｋＮＮＳａｍｐｌｉｎｇｔｅｃｈｎｉｑｕｅ［１－３］当前大数据研究当中的一个研究热点。０引言在实际应用中，不确定图搜索问题十分常见。例如，在社交网络中，用节点表示用户，用边表示好友关随着云计算和大数据时代的到来，由于数据获取系，则好友之间的影响程度就可由边上的概率来表示，存在噪声、网络传送存在误差、数据使用颗粒度差异等从

7、而构成一个不确定图；在城市的路网中，用节点表示各种原因，使得我们面临大量不确定数据的处理问题。地点，用边表示街道，则街道是否拥堵就可由边上的概在各种不确定数据组成的网络（诸如生物网络、社交率来表示，亦构成不确定图。不确定图的搜索问题，通网络）中，不确定图（或称概率图）是一种十分重要和常是“在社交网络中，与张三关系最密切的三个人是普遍使用的数学模型，对不确定图的搜索问题，也成为谁？”、“在城市路网中，从地点Ａ到地点Ｂ最通畅的三收稿日期：２０１６－０７－０７。国家科技支撑计划项目（２０１４ＢＡＩ１７Ｂ０１）；软件开发环境国家重点实验室开放课题（ＳＫ

8、ＬＳＤＥ－万方数据２０１２ＫＦ－０２）。张伟，教授，主研领域：人工智能，机器学习。第６期张伟：基于抽样的不确定图ｋ最近邻搜索算法１８１条路径是哪些路径