目前，手機已經成為我們生活的必需品。服務商可以很容易通過手機采集到我們日常生活的GPS軌迹資料，圖1為使用者GPS軌迹資料示例，其采集資料的時間間隔為5秒。直接觀察這些資料，我們隻能發現使用者經過某些地點，卻不能确定使用者是否在這些地點停留過。
圖1使用者GPS軌迹資料示例
那麼，如何通過分析使用者的GPS資料來确定他在哪些地方停留過呢？
解決這一問題用到的算法是CB-SMoT。該算法是密度聚類的一個改進。選擇密度聚類是因為它可以發現任意形狀的簇，這正符合使用者的活動規律。
CB-SMoT算法判斷使用者在哪些地方停留過的依據有兩點，一是使用者在哪些地方的GPS點相對密集，二是使用者在哪些地方的運動速度較慢。從大量點資料中尋找密集點正是密度聚類的功能所在。而CB-SMoT所定義的新鄰域則是尋找速度較慢的點的。
CB-SMoT算法其實是DBSCAN聚類算法的改進，它與DBSCAN的不同之處在于對鄰域的定義不同。CB-SMoT對鄰域定義如下：
下面通過如圖2來舉例說明新鄰域。對于O點鄰域内的點，DBSCAN算法認為以O點為圓心、Eps為半徑的圓内的點都在O點鄰域内，由此可知，A、B、C、D、E、F、G這八個點都在O點鄰域内；而CB-SMoT算法認為，當由O點兩側相鄰的點組成的線段的長度之和小于等于Eps時，這些點才在O點的鄰域内，由此可知，O點鄰域的點隻包含B、C、D、E四個，這是因為 BC+CO=48<Eps,OD+DE=48<Eps B C + C O = 48 < E p s , O D + D E = 48 < E p s
。
圖2 CB-SMoT的鄰域
新鄰域内相鄰的點所組成的線段的長度之和，如圖2，S=BC+CO+OD+DE實際上就是使用者所走的路程。使用者的GPS點是按照一定的時間間隔采集的。假設采集的時間間隔是5秒，由于圖2中新鄰域内共有5個點，是以此時使用者的運動時間為t=25秒。使用者在這一鄰域的速度可以表示為S/t。S最大為2Eps，鄰域内的點越多，則t越大，S/t越小，說明使用者在這一區域的速度越慢，使用者可能在此處停留。
參考文獻
Palma A T, Bogorny V, Kuijpers B, et al. A clustering-based approach for discovering interesting places in trajectories[C]// ACM Symposium on Applied Computing. DBLP, 2008:863-868.