K-PRSCAN算法实现

66 阅读 0 评论 44 点赞

我是靠谱客的博主内向雪糕，最近开发中收集的这篇文章主要介绍K-PRSCAN算法实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

今天看了一篇论文，K-PRSCAN: A clustering method based on PageRank，基于PageRank的一个聚类算法，该算法前面很简单，就是迭代得到最终的ＰＲ向量，最后对PR向量进行聚类。最后一步相当与对一个double类型的数组进行聚类，本来这个是一个基于距离的聚类问题，作者搞了个scanning factor，其实就是一种knn的变形，其实效果并不是很好，虽然不用给定k值，但是sf值选的不好，效果相差很大，虽然最后作者基于二分查找提出了K-PRSCAN算法，找出合适的sf值使得类簇个数恰好为k，但是这又要logn次运行PRSCAN，虽然不好，但还是写了写最后一步聚类的代码：

package clustering.prscan

/**
  * Created by fhqplzj on 16-12-18 at 下午1:50.
  */
case class Info(index: Int, pr: Double, var cluster: Int) {
  override def toString: String = s"($index,$pr,$cluster)"
}

object PRSCAN {
  def cluster(data: Array[Double]) = {
    /*按照PR值从小到大排序*/
    val corpus = data.zipWithIndex.map {
      case (pr, index) =>
        Info(index, pr, -1)
    }.sortBy(_.pr)
    /*spanning factor*/
    val sf = 3
    /*类簇编号*/
    var count = 0
    corpus.indices.toArray.foreach {
      i =>
        /*当前索引为i，所以维护一个滑动窗口[i-sf+1,i+sf-1]*/
        val low = math.max(i - sf + 1, 0)
        val high = math.min(i + sf - 1, data.length - 1)
        /*索引范围*/
        val indices = Range(low, high + 1).toArray
        /*当前的pr值*/
        val curr = corpus(i).pr
        /*按距离排序，最近的前sf个点的索引*/
        val idx2 = indices.map {
          idx =>
            (idx, math.abs(curr - corpus(idx).pr))
        }.sortBy(_._2).take(sf).map(_._1)
        /*是否全部都没有标签*/
        val b = idx2.forall(idx => corpus(idx).cluster == -1)
        if (b) {
          corpus(i).cluster = count
          count += 1
        } else {
          val k = idx2.find(idx => corpus(idx).cluster != -1).get
          corpus(i).cluster = corpus(k).cluster
        }
    }
    corpus
  }

  def main(args: Array[String]): Unit = {
    val data = Array(0.1, 0.5, 0.9, 0.11, 0.55, 0.99, 0.111, 0.555, 0.999)
    cluster(data).foreach(println)
  }
}