有关照片聚类算法的思考

作者：俞尚

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

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

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

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

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

[1498532499147_5536_1498532499323.png]

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

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

4.简单算法的尝试

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

[1498532511692_8433_1498532511839.png]

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

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

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

[1498532529573_6340_1498532529568.png]

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

[1498532548233_805_1498532548238.png]

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

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

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

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

优化后的规则如下:

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

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

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

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

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

[1498532571409_7583_1498532571401.png]

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

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

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

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

[1498532583314_8998_1498532583300.png]

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

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

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

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

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

4.基于网格的聚类。

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

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

7.层次聚类法

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

1.把所有照片聚成一个类（考虑到算法效率，先按天聚类）；

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

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

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

[1498532594547_6934_1498532594798.png]

8.照片聚类的其它问题

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

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

2.飞机上快速运动时，怎么处理？

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

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

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