专栏首页QQ空间开发团队的专栏有关照片聚类算法的思考
原创

有关照片聚类算法的思考

作者:俞尚

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 条评论
登录 后参与评论

相关文章

  • React Native For Android 架构初探

    React Native 让开发者使用 JavaScript 和 React 编写应用,利用相同的核心代码就可以创建 基于Web,iOS 和 Android 平...

    QQ空间开发团队
  • iOS 高性能图片架构与设计

    一个优秀的图片组件应该具有这些特性:集并发控制,请求合并,下载,缓存,缓存自动淘汰,图片处理,动画的从数据源到图片显示的一站式解决方案。做到图片加载展示如丝般顺...

    QQ空间开发团队
  • RxJava && Agera 从源码简要分析基本调用流程(1)

    相信很多做Android或是Java研发的同学对RxJava应该都早有耳闻了,尤其是在Android开发的圈子里,RxJava渐渐开始广为流行。同样有很多同学已...

    QQ空间开发团队
  • SAS用K-Means 聚类最优k值的选取和分析

    坐在餐馆的用餐者。假设餐厅中有两个桌子。桌子1中的人可能彼此相关,可能是一组家庭成员或同事。

    拓端
  • 机器学习算法之聚类算法

    "If you set your goals ridiculously high and it's a failure, you will fail above...

    小闫同学啊
  • R语言使用最优聚类簇数k-medoids聚类进行客户细分

    k-medoids是另一种聚类算法,可用于在数据集中查找分组。k-medoids聚类与k-means聚类非常相似,除了一些区别。k-medoids聚类算法的优化...

    拓端
  • 一文详解聚类和降维(附实例、代码)

    来源:机器之心 作者:Vishal Maini 本文长度为3500字,建议阅读6分钟 本文对无监督学习的聚类和降维算法进行介绍,其中包括 K 均值聚类、层次聚类...

    数据派THU
  • 聚类方法的区别解读:各种聚类分析呀呀呀

    k 均值聚类法 快速高效,特别是大量数据时,准确性高一些,但是需要你自己指定聚类的类别数量 系统聚类法则是系统自己根据数据之间的距离来自动列出类别,所以通过系统...

    学到老
  • 一文解读聚类中的两种流行算法

    原作:Anuja Nagpal 谢阳 编译自 Medium 量子位 出品 | 公众号 QbitAI 在这篇文章中,Nagpal以简明易懂的语言解释了无监督学习中...

    量子位
  • 【AIDL专栏】方以类聚,物以群分,吉凶生矣 | 于剑:聚类理论与算法选讲

    聚类的思想起源非常早,中国可以追溯到《周易·系辞上》中的“方以类聚,物以群分,吉凶生矣”。但聚类的算法却是上世纪50年代才出现,这是因为聚类依赖于数据,数据量小...

    马上科普尚尚

扫码关注云+社区

领取腾讯云代金券