预测传播概率与传播规模

已有很多学者在研究复杂网络上的传播动力学问题,并取得了一系列的研究成果。是否能够以及如何才能利用某时刻传播的瞬间状态,预测传播的演化过程呢?这一基本问题,目前还很少有学者进行深入研究。而这一问题本身对信息传播与控制有着重要的理论和现实意义。

针对这一基本问题,大数据研究中心,数据挖掘与推理研究所的陈端兵副教授和瑞士弗里堡大学曾安、肖锐两位博士一起提出了一种简单而有效的传播概率与传播规模的预测方法。基于被学术界广泛接受的“易感-染病-免疫”动力学模型,陈端兵等人提出了一种迭代计算方法,能够有效估计特定节点在被感染之前,已被感染的邻居数量。陈端兵等人在此之上发展出了一套传播概率的预测方法。在小世界和无标度网络模型以及真实网络中的实验结果表明,该方法能够很好地预测传播概率。在预测的传播概率基础上,采用平均场模型进一步对传播规模进行了预测,也取得了很好的结果。

论文信息:

D.-B Chen(陈端兵), R. Xiao, A. Zeng, Predicting the evolution of spreading on complex networks. Scientific Reports 4 (2014) 6108.

论文链接: http://www.nature.com/srep/2014/140818/srep06108/full/srep06108.html

从官僚主义到平等主义:大数据揭示鸽子群集运动的复杂策略

从慌乱的人群,到椋鸟、海洋鱼类,再到蝗虫乃至细菌,不同尺度的生命体都可以自组织,形成模式各异的群集运动。20年前,匈牙利科学院院士TamasVicsek教授就提出了著名的Vicsek模型[PRL 75 (1995) 1226, 引用3000+次],其中个体下一时刻将选择周围邻居的平均方向作为自己的运动方向——这种简单规则可以再现某些复杂的自然群集运动的统计规律。

几年前,Vicsek小组的一篇实验论文对自己的模型提出了挑战[Nature 464 (2010) 890]。他们通过对十几只鸽子的精密飞行轨迹(通过在鸽子脚上捆绑GPS设备)进行跟踪,发现鸽子在飞行的时候存在一种“领导-被领导”的层次网络结构,这可能是形成高效集群的原因。

大数据研究中心,数据挖掘与推理研究所周涛教授和Vicsek小组及其他合作团队一起,对鸽子飞行数据进行了进一步地分析。他们发现鸽子在飞行中实际上混合了“听领导的”和“听周围朋友的”这两种策略。就运行方向而言,当飞行轨迹平滑的时候,鸽子尽力与周围邻居的平均方向保持一致;而当出现突然的急转弯变向的时候,鸽子迅速和领导保持一致。在决定飞行速度的时候,周围邻居对鸽子的影响一直都比领导大。数据显示,鸽子的运动策略并不简单,随着环境的改变,需要不停在官僚主义和平等主义之间切换。

论文信息:

H. T. Zhang, Z. Chen,T. Vicsek, G. Feng, L. Sun, R. Su, T. Zhou(周涛), Route-dependent switch between hierarchical and egalitarian strategies in pigeon flocks. Scientific Reports 4 (2014) 5805.

论文链接: http://www.nature.com/srep/2014/140724/srep05805/full/srep05805.html

大数据帮助你寻找感兴趣的地点

当我们来到一个陌生的城市,总是希望能够尽快找到喜欢的地方。而当我们在一个城市居住一段时间以后,也希望能够在重复的生活娱乐场所之外,探索到一些新奇而又符合自己兴趣的地方。一个重要而又被所有以前的研究工作所忽略的特征是,当人们经常光顾一个地点而很少光顾这个地点周围的其他地点的时候,那么他们就有可能对周围的地点没有太大兴趣,而且这个对周围不感兴趣的程度和人们光顾那个地点的次数是正相关的。也就是说,当你注意到两家紧邻的餐馆A和B,目标用户经常去A而从不去B,那么即便很多去过A的其他用户都常常光顾B,也不要轻易给目标用户推荐B——如果他喜欢B,不用你推荐,早就去了。

大数据研究中心,教育大数据研究所的连德富博士敏锐注意到了这些地理和兴趣交织的复杂心理,提出了一个混合模型来无缝地结合协同过滤技术和地理建模技术。协同过滤可以帮助人们找到符合人们兴趣的地点,而地理建模技术可以过滤那些距离人们活动区域过远的地点,并通过将位于常去地点附近又从未被光顾之处看作负例,来进一步提高地点推荐被接纳的可能性。这个混合方法不仅能够大幅提高地点推荐的精确性,还能克服因人们访问地点过少而导致的数据过于稀疏的问题——数据稀疏是推荐技术面对的最为严峻的问题之一!

论文信息:

D. Lian (连德富), C. Zhao, X. Xie, G. Sun,E. Chen, Y. Rui. GeoMF: Joint geographical modeling and matrix factorization for point-of-interest recommendation. ACM SIGKDD, pp. 831-840, 2014.

论文链接: http://dl.acm.org/citation.cfm?id=2623638

距离 vs复杂性:大数据帮你导航!

传统的路径规划算法一般基于最短旅行距离或时间来进行优化。然而空间认知学方面的大量研究已表明,人们在选择路径时,其他的一些因素往往发挥着重要的作用。例如在实际中,当本地人为外地游客指路时,常常舍弃那些难走、难认的道路,而选择给出那些容易走(例如较少转弯)的简单路径,即便距离并非最短。

在空间数据库的研究中,道路网络上最近邻的查找(如“离此处最近的邮局”)是一个重要的研究问题。在给定出发点和多个可能的候选目的地的情况下,当路径选择的标准从旅行距离变为通行复杂度时,“最易到达邻”这个新概念可视为最近邻的自然延伸。它的查找对于在陌生的城市环境中旅行的人们大有帮助。

大数据研究中心,数据挖掘与推理研究所邵杰教授和澳大利亚墨尔本大学的合作者一起,通过融合空间认知学的方法来分析空间簇集的效应和地标物的效应,从而对通行复杂度这一因素加以建模,实现了对道路网络上最易到达邻的高效查询处理。通过对墨尔本市道路网络数据(包括市中心密集网格状区域,以及市郊稀疏道路区域)上的超过1000万条的大量路径测试实验发现,最简单路径的旅行距离平均只比最短路径增长15.8%。邵杰等人进一步用真实用户研究的方式验证了最易到达邻的实际使用效果:83.3%的受访用户表示,偏向于选择去到最易到达邻,而非选择实际旅行距离最短的最近邻作为他们的目的地。该研究还展示了导航系统如何同时兼顾旅行距离以及通行复杂度,为旅行者提供更佳路径建议的可能性。

论文信息:

J. Shao(邵杰), L. Kulik, E. Tanin, L.Guo. Travel distance versus navigation complexity: a study on different spatial queries on road networks. ACM CIKM, pp. 1791-1794, 2014.

论文链接: http://dl.acm.org/citation.cfm?doid=2661829.2661861

实时大规模数据流的新分类算法

哲学告诉我们:“一切事物都是在不断变化和发展的,而科学的目标就是客观地认识这些变化事物中蕴藏的规律”。数据流作为当前大数据的主要形式,定义为随时间动态产生的各种数据(如电力数据、网络数据、传感器数据等),挖掘和预测流数据中隐含的数据模式及演变规律具有重要的理论和现实意义。

目前,数据流分类算法主要采用集成学习策略,然而,该类方法由于其本身的黑箱特性往往带来学习的不准确性。另外,当前数据流挖掘算法往往侧重于对近期数据进行学习,忽略了潜在重要的历史数据。

针对这些问题,大数据研究中心,数据挖掘与推理研究所的邵俊明教授提出了一种全新的基于原型示例的数据流分类算法。其基本思想是从个体分析的新视角出发,通过分类性能启发式地对数据流中每个数据的重要性进行动态甄别和筛选,用以有效捕获当前最新的数据模式(数据中产生的新规律),并用于分类预测。针对数据流的演化特性,邵俊明等人提出了基于主成分分析和统计模型的新方法,来检测数据流中存在的突变概念漂移。此外,针对海量高速的数据流,邵俊明等人提出了基于同步约束聚类的数据压缩方法,从而使得算法不仅具有很高的预测性能,而且具有很低的时间和空间复杂度,为实时进行大规模数据流分析提供了全新的思路和技术方法。

论文信息:

J. Shao(邵俊明), Z. Ahmadi, S. Kramer. Prototype-based learning on concept-drifting data streams. ACM SIGKDD, pp.412-421, 2014.

论文链接: http://dl.acm.org/citation.cfm?id=2623609

图片和视频之间的跨界语义索引

语义视频索引,又称视频标注或视频概念检测,在近些年引起了工业界和学术界的广泛关注。随着呈爆炸式增长的媒体大数据的出现,如何开发快速和有效的语义视频索引技术已经成为新的研究热点。目前,已有的语义视频索引方法主要基于传统机器学习算法,由于缺乏有标签训练数据,大部分方法往往不能获得令人满意的结果。

针对这些问题,电子科技大学,大数据研究中心,数据挖掘与推理研究所的杨阳教授提出了一种新颖的语义视频索引方法,能够开发利用海量的用户标注Web图片来辅助学习鲁棒的语义视频索引分类器。然而,这个方法面临两个巨大的挑战:(1)不准确/不完整的标签;(2)视频和图片的域间差异。针对这两个挑战,杨阳等人提出了一种非参数化的方法来估算标签的可信度,然后将可信度整合到一套鲁棒的学习模型中,从而可以使Web图片有效的补充有限的视频训练数据。在这套鲁棒模型中,杨阳等人提出了一种新颖的特定于样本的损失函数,并且整合Web图片的可信度以控制图片在学习过程中的贡献程度。与此同时,图片和视频之间的差异可以通过一个最优核空间的学习得以完善解决。杨阳教授的研究成果,在未来跨媒体的商业化应用中有巨大应用前景。

论文信息:

Y. Yang (杨阳), Z.-J. Zha, Y. Gao, X.Zhu, T.-S. Chua, Exploiting Web Images for Semantic Video Indexing Via Robust Sample-Specific Loss, IEEE Transactions on Multimedia 16 (2014) 1677-1689.

论文链接: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6813690&isnumber=6898894

找出推荐系统中的信息核心

推荐系统可以简单看成一个用户-商品的二部分图,推荐算法要做的就是分析用户浏览、收藏、购买的记录,以及用户和商品的其他辅助信息,自动找到用户喜欢的商品。推荐系统往往规模巨大,以刚刚上市的阿里巴巴为例,其淘宝平台是“10亿用户-10亿商品”的规模。是不是每一个用户都携带了同样价值的信息,对于算法贡献相同呢?

大数据研究中心,数据挖掘与推理研究所尚明生教授、曾伟博士等人最近的研究显示,在推荐系统中存在一个用户的子集,却包含了推荐系统中绝大部分信息,他们形象地将其命名为推荐系统的信息核。尚明生小组设计和比较了多个挖掘信息核的算法,在豆瓣、Flickr、Last.fm等真实数据的实验表明,信息核在包含20%的用户时,有的时候比用所有信息得到的推荐精确度还要高。最差的情况下,也能达到91.4%的精确性,而且对很多方法用这种萃取的核来进行推荐,效果都非常不错。

进一步的统计分析表明,位于信息核心的成员并不是购买商品很多的成员,实际上他们的购买数量还比不上平均值,但是这些人相互之间选择具有多样性,而且倾向于选择流行的商品。这些研究可以帮助我们更深入理解推荐系统的本质和用户选择的行为心理,并降低推荐系统计算的复杂性。

论文信息:

W. Zeng (曾伟), A. Zeng, H. Liu, M.-S.Shang (尚明生), T. Zhou,Uncovering the information core in recommender systems, Scientific Reports 4(2014) 6140.

论文链接: http://www.nature.com/srep/2014/140821/srep06140/full/srep06140.html

徐增林教授在人工智能顶级会议上发表的两篇论文

大数据研究中心,数据挖掘与推理研究所徐增林教授在人工智能领域的顶级国际会议,中国计算机学会(CCF)认可的A类会议,第29届人工智能大会(AAAI)上发表两篇论文。徐教授为两篇论文的通信作者,并将于2015年1月份参加在美国德州奥斯汀召开的会议并做口头报告。

徐教授的第一篇论文是神经信息学与机器学习的交叉研究。在艾滋海默症的诊断过程中,如何更好地利用病人的磁共振图像来对病情进行预测,同时从遗传基因差异方面寻求病理解释是非常重要也是非常具有挑战性的问题。徐教授的论文介绍了如何通过稀疏贝叶斯多视角学习来自动发现基因与脑区之间的相关关系,同时对病情程度进行预测。美国礼来制药公司的神经信息学研究者对论文发现的相关基因进行了分析,验证了其合理性。

徐教授的第二篇论文是关于机器学习中的稀疏核学习的理论研究。核方法是机器学习中一类非常重要的方法,它通过将数据从原始低维空间投影到高维甚至是无限维的空间中,从而实现非线性回归或分类。它的主要瓶颈在于对大规模核矩阵的计算。徐教授使用Nystrom近似算法,用对样本的采样来逼近原有较大核矩阵的性能,从而大大提高核矩阵的计算效率。该论文首次从理论上证明了对于稀疏核学习在采用Nystrom近似后,得到的解是可以恢复原问题的最优解的,并且可以比传统核方法快上千倍。

论文信息:

  1. S.Zhe, Z. Xu(徐增林),Y. Qi, P. Yu. Sparse Bayesian Multiview Learning for Simultaneous Association Discovery and Diagnosis of Alzheimers Disease. In AAAI’15: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2015.

  2. Z.Xu(徐增林),R. Jin, B. Shen, S. Zhu. Nystrom Approximation for Sparse Kernel Methods: Theoretical Analysis and Empirical Evaluation. In AAAI’15: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2015.



Questions & Discussion: ✉️ zjuvis@cad.zju.edu.cn