有关照片聚类算法的思考

作者:俞尚

1.聚类的规则是模糊的,无法精确描述的

空间当前聚类的规则是 1KM 或 1 小时内的照片会聚在同一个类中。目前来看规则太简单,也不够准确,容易产生一些错误的聚类。从用户角度来说,照片聚类规则其实也不复杂,只要把时间地点相对接近照片聚在一起。但是具体规则又很难精确描述的,什么情况下算接近,无法用一个具体的数值来衡量。如果 500 米算近,那 501 米为什么又不算呢?聚类规则是一个非常主观,非常模糊概念。

2.怎么人工判断照片聚类效果的好坏

直接查看一个个聚类的照片来判断聚类是否合理、评估效果,是非常低效的也不直观。人类对图象的理解有天然的优势。是否可以用图表来表示照片之间距离和时间的关系,可以比较直观的看出聚类效果的好坏?这的确是好主意,但有个困难,照片地理位置本身是二维,加上时间是第三维。对三维图象理解还是不够直观吧。有个巧妙的办法是计算照片之间距离,把位置信息 XY 坐标变成一个一维的数字。如下图:

X 轴横坐标是时间,Y 轴纵坐标是照片之间的距离。 

3.人对照片拍摄地点远比拍摄时间敏感

我们对用户需求的理解,很容易产生偏差,而不自知。在这里很容易把时间和地点作为同样重要的因素来考虑。事实上人对照片地点记忆深刻得多。你很容易想起,今年或去年到哪些城市,但很难说清楚是哪个月份哪一天。另外近期记忆也是如此,我在办公室上班一整天,然后下班后 20 分钟内在 1.5 公里远处吃饭。也不会愿意把办公室 8 个小时跨度的照片与 20 分钟间隔的吃饭照片聚在一个类当中,尽管时间跨度很小。  

4.简单算法的尝试

刚刚开始聚类规则,仅仅是控制时间和距离来进行聚类。从 1 小时,1km 聚类这个规则开始。 

这个方案,总体还算准确。有以下几个问题:

1.如果有张照片刚是距离 1.01km 或者时间间隔是 1 小时 1 分钟,就会强行分类。

2.某些聚类太离散,包含了多个地点,不符合预期。 

3.某些类有些点距离虽然也小于 1km,但是本身是个不在同一个地点,聚类不对 。

(左上角那个点明显不对)

4.在飞机上,拍摄时间很短,但是距离肯定超过 1km,聚类出错 (高速状态下)。

5.如果某地沙滩上呆上太半天,时间肯定超 1 小时,也会聚类出错。(静止状态)。

所以简单的聚类算法总会有这新或者那样的问题。为了修正上面的一些问题,针对算法做改进。

优化后的规则如下:

1.当时间小于 1 分钟,距离在 200km 以内,聚类;

2.当时间小于 5 分钟,距离在 60km 以内,聚类;

3.当距离小于 0.6km,时间在 90 分钟内,聚类;

4.当距离小于 0.3km,时间在 300 分钟内,聚类;

5.其它情况,1 小时,1km 聚类。

如上图所示,低于这条线的点会被聚在同一个类中。

聚类效果有改善,但仍然有问题。算法指定了太多的魔术数字。对于一些边界处理仍然有问题。如果距离好是 0.31km,时间时 300 分钟,就不会被聚类。如果 299 分钟又会聚在一起。这些奇怪的规则,很难说服自己。

5.聚类规则的进一步讨论

显然指定时间和距离的规则,不可能有完美的解决方案。回到这张图上来,用人类的语言来描述,应该是:时间地点相对较近,而且分布较为均匀的照片,应该聚在一起。但无法说清楚,具体数值是多少。取决照片分布情况。但计算机无法理解人类的思维模式,其实还没有解决方案。

6.通用聚类算法的局限性

很容易想到,有关于聚类的算法的研究已经非常深入了,有多种通用聚类算法可以选择。比如:

1.划分聚类,需要知道要划分的聚类的数目,然后计算各个点距离来聚类。

2.层次聚类,按照某种条件,进行层次分解,直到满足条件。

3.基于密度的聚类,比较容易发现球形的聚类。旅游照片往往是线形。

4.基于网格的聚类。

这里 1、3 都不适合用来做照片聚类,我们无法事先知道一批照片应该聚成多少类。照片地点分布,往往是线性的,而不是球形。

另外,网上的资料很多,但基本上都过于理论化,我们可以用指定的算法,指定一个规则来得到聚类结果。但是往往不知道这些规则的对应的现实意义是什么,也就无法优化聚类效果。最终也比较难得到一个非常好聚类模型。

7.层次聚类法

最终我们考虑了采用了层次聚类算法。具体方法如下:

1.把所有照片聚成一个类(考虑到算法效率,先按天聚类);

2.判断一个聚类照片分布情况是是否均匀(方差大于: 0.01 且 照片张数大于 10);

3.不够均匀则找到聚类中间隔最大的位置,分成两个聚类。然后重复第 2 个步骤。

经验证,这种方案聚类效果非常的好。准确率 99%以上,各个聚类都比较准确,没有离散点等错误案例。效果如下图:

8.照片聚类的其它问题

1.照片时间和位置信息丢失

如果时间丢失,应该废弃。如果仅丢失时间,考虑根据时间对位置信息进行差值处理。

2.飞机上快速运动时,怎么处理?

飞机上照片一般张数比较少,同时处于匀速运动状态,方差较小,一般也能聚在一起。

3.照片时间与位置两个因素怎么平衡,目前只考虑了位置信息,后面可以讨论具体算法。

4.聚类也要考虑不同的时间段和场景。比如,对较近时间内,推荐发说说时,聚类应该更加严格。较远时间,一般可以推荐上传到相册,对聚类的要求可以适当宽松。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

超级网络

在这篇文章中,我将介绍一下我们最近的文章[1609.09106] HyperNetworks。我作为Google Brain Resident工作在这篇论文上-...

2067
来自专栏智能算法

(入门)|深度学习通俗理解

1. 深度学习到底是干啥的? 2017年10月18日,《自然》杂志网站公布的论文显示,此前战胜人类围棋世界冠军的电脑程序AlphaGo的开发团队又出力作——新程...

3529
来自专栏人工智能

什么时候强化学习未必好用?

作者 Jason Xie 编译 Erica Yi 编辑 Emily 强化学习(reinforcement learning)描述的是个体(agent)必须...

2278
来自专栏美图数据技术团队

深度模型DNN在个性化推荐场景中的应用

随着深度神经网络在语音和图像识别上取得的巨大成功,AlphaGo 战胜人类围棋顶尖高手,以深度网络为基础的人工智能迎来第三次高潮。与此同时互联网所面临的信息超载...

902
来自专栏AI科技评论

CVPR 2018 中国论文分享会之「分割与检测」

本文为 2018 年 5 月 11 日在微软亚洲研究院进行的 CVPR 2018 中国论文宣讲研讨会中第 5 个 Session ——「Segmentation...

1014
来自专栏大数据文摘

视频回放 | 80分钟公开课:机器学习之数学基础,从梯度分析到回归模型

1302
来自专栏AI科技评论

深度、卷积、和递归三种模型中,哪个将是人类行为识别方面的佼佼者?

导读:2016国际人工智能联合会议(IJCAI2016)于7月9日至7月15日举行,今年会议聚焦于人类意识的人工智能。本文是IJCAI2016接收论文之一,除了...

4329
来自专栏ATYUN订阅号

谷歌:计算机视觉模型可在无监督情况下跟踪对象并对视频着色

视频的对象跟踪是计算机视觉的一个基本问题,对于诸如活动识别,对象交互或视频风格化等应用至关重要。然而,教会一台机器以直观地跟踪物体充满挑战性,部分原因在于它需要...

682
来自专栏AI研习社

2017 知乎看山杯从入门到第二

利用一个暑假的时间,做了研究生生涯中的第一个正式比赛,最终排名第二,有些小遗憾,但收获更多的是成长和经验。我们之前没有参加过机器学习和文本相关的比赛,只是学过一...

2697
来自专栏腾讯技术工程官方号的专栏

NIPS2018 | 腾讯AI Lab入选20篇论文,含2篇Spotlight

? 被誉为神经计算和机器学习领域两大顶级会议之一的NIPS于近日揭晓收录论文名单,此次为第32届会议,将于 12 月 3 日至 8 日在加拿大蒙特利尔举办。 ...

203

扫码关注云+社区