面向LBSN的k-medoids聚类算法

Ak-medoids based clustering algorithm in location based social networks

常用的聚类算法存在诸多不足,为此提出了一种基于初始半径r的k-medoids改进算法,主要针对LBSN中的位置数据进行聚类,改善初始聚类中心敏感对聚类结果的影响,其本质是基于密度聚类,不同之处在于k值的选取是依赖于半径r.通过大量真实签到数据集进行实验,结果显示本文算法聚类结果更稳定.本文算法在基于位置的社交网络应用中获得更好的聚类效果和更快的收敛速度.实验中将距离平方和作为准则函数进行对比,相对于传统k-medoids算法优势明显,对退化的k-medoids算法也能够缩小1.2%到2%.

The commonly-used clustering algorithms have several drawbacks. Aiming to solve the above problems, an improved k-medoids algorithm was proposed based on the initial radius r, which is used for clustering using location data. The algorithm is actually a density-based clustering approach. The difference is that the k value depends on the radius r. Extensive experiments are conducted on real check-in data, and the results show that the improved k-mediods algorithm on the radius r is more stable. In addition, by comparing the sum of the square of distance between objects in the same cluster among different algorithms, the proposed algorithm can obtain better clustering results and convergence speed when applied to location based social networks. Compared to the traditional k medoids algorithm, the cost has obviously reduced, as for and the degraded k-medoids algorithm, the cost can be reduced among 1.20% and 2%.