MDL原理在二元关系可视化中的应用

主持人:景波

参会老师:安宁、杨矫云

参会学生:赵春阳,韩鹏,贵芳,李雨龙,刘硕,明鉷,肖勇博,江思源,程坤

时间:2018年11月21日

本次例会学习讨论了以下文章:VIBR: Visualizing Bipartite Relations at Scale with the Minimum Description Length Principle

对于两个集合,如果一个集合中点和另一个结合中的点有连接,而集合内的点之间没有连接,那么这样的数据称为二分关系数据。通常这样的数据通过图模型来描述,这类特殊的图称为二分图(图1)。生活中存在大量这样的二分关系数据,比如顾客购买商品,议员投票议案等。

庞大数据量带来的挑战,一是人的认知能力的限制,二是噪声数据。因此需要一种可靠的数据可视化技术来提供数据的概览,需要在概览包含的内容量与简洁程度上进行平衡

采用MDL准则构造了一种新的二元关系模型

图片1

 

模型的长度计算公式为:

图片2

采用BM_MDL算法提取出最小的模型,算法伪码描述如下

图片3

 

为了提升算法性能,引入lsh算法提高算法性能,算法性能改善如图

图片4

 

anyShare分享到:
This entry was posted in 例会. Bookmark the permalink.

发表评论