最近一直在完善一个视频人脸聚类的算法，开始时一直使用DBSCAN算法，不过视频测试的时候，发现该算法对参数的依赖太过严重，有些视频的人脸阀值很难去界定。
对于某个点A，判断它是否是核心点的依据是：在给定的半径（邻域半径）内的样本点的数量大于等于给定的最小点数。例如以A点为圆心，半径为2的圆内包含的样本点的数量超过3个就算核心点。注意：（1）这里的半径范围内的点包含A点本身。（2）这里的半径是一个经验值，通常可以取值大一些，当然取值越大计算量也越大，不过这个不是关键问题。相对于DBSCAN算，该参数的影响弱很多。
例如，以点A为圆心，包含3个点的圆里，最小半径即为核心距离。这样，每个点都能计算出一个核心距离（如果该点是一个核心点的话），理解也不难，不过这个距离的作用更多只是用来引入可达距离。
例如计算B点和核心点A的可达距离：
对于B点自身的可达距离，实际上是会随着核心点的发现而更新的，例如当出现另一个核心点C的时候，也会有一个计算一个B到C的可达距离：rd(B, C)，那么这时B点的可达距离为：
每个点都有一个可达距离（该值需要小于给定的半径），称为密度可达；当然如果没有邻居点，则是不可达的。所以，可达距离实际上是每个点到其他核心点的可达距离。每个点的可达距离是OPTICS算法输出的主要结果，在实际聚类的时候，传递一个可达距离的阀值，就能将样本点聚类了。
核心算法部分如下：
简述一下其算法步骤：
完整的代码见这里。
以及初始化半径R和最小点数为3，即在半径R内，如果有3个或者3个以上的点，即为核心点。
我们选择第一个点，如下图黑色的点，并以它为圆心作一个半径为R的圆，如下图（左图）：
在该圆内，共有4个点，所以该点为核心点。该核心点有三个邻居点，如上右图的淡红色的点。
计算该核心点的核心距离，如下图：
就是以该核心点为圆心，找到一个最小半径的圆，使得该圆内至少包含3个点，则该半径则为该核心点的核心距离。有了核心距离之后，计算这三个邻居点的可达距离。
根据可达距离，对三个邻居点进行排序，优先选择可达距离最小的点进行处理。如下左图：
上左图，该点（灰色点）在半径R内的点数也达到3个（阀值），所以该点也是核心点，这时需要更新该点的邻居点的可达距离。同理最左上角的点也类似，也是核心点。但是对于第3个邻居点，即上右图所示的粉色的点，在半径R内，只有2个点，不满足核心点的要求，故该点不是核心点。
核心点的邻居点（黑色点）都处理完之后，开始寻找下一个未处理的点，如下图：
显然，该点不满足核心点的条件。至此，所有点都已经处理完毕，OPTICS算法完成。
sklearn里有现成的OPTICS算法，不过可惜不能自定义距离函数，而在我们的场景下，自定义距离函数确是需要的，所以才重新造了一个轮子。例如视频人脸聚类，同一帧里的人脸肯定都是不同的人，那么我们就可以定义同一帧内的人脸距离无限大，这是非常重要的。
聚类结果
OPTICS算法输出其实并不是最终的聚类类别，只是各个点的最小可达距离，如果需要聚类结果，只需要一个距离阀值，如下图：
如上图，横轴是OPTICS输出的排序好的样本点，纵轴是每个样本点的可达距离，我们需要定义一个阀值（如上图中的红线），在阀值之上的可以定义为异常点，这样之下的样本点就被分成了3块，也就聚类成了3类。
该图来自sklearn官方文档，显示了OPTICS和DBSCAN两种算法的聚类结果的对比。