好長時間忙的沒寫博客了。看到有人問spark的knn，想着做推薦入門總用的knn算法，順便寫篇博客。

knn算法的大致如下：
    1）算距離：給定測試對象，計算它與訓練集中的每個對象的距離
    2）找鄰居：圈定距離最近的k個訓練對象，作為測試對象的近鄰
    3）做分類：根據這k個近鄰歸屬的主要類別，來對測試對象分類

 

這次用spark實現knn算法。

首先要加載數據：

實驗就簡單點直接模擬：

List<Node<Integer>> data = new ArrayList<Node<Integer>>();
        for (int i = 0; i < 100; i++) {
            data.add(new Node(String.valueOf(i), i));
        }
JavaRDD<Node<Integer>> nodes = sc.parallelize(data);

 

再設計距離的度量，做一個簡單的實驗如下：

new SimilarityInterface<Integer>() {

            public double similarity(Integer value1, Integer value2) {
                return 1.0 / (1.0 + Math.abs((Integer) value1 - (Integer) value2));
            }
        };

距離度量為一個接口可以實現你自己想要的距離計算方法，如cos，歐幾里德等等。

 

再這要設置你要構建的關聯圖和設置搜索的近鄰k值：

 

NNDescent nndes = new NNDescent<Integer>();
        nndes.setK(30);
        nndes.setMaxIterations(4);
        nndes.setSimilarity(similarity);
        // 構建圖
        JavaPairRDD<Node, NeighborList> graph = nndes.computeGraph(nodes);

// 保存文件中
graph.saveAsTextFile("out/out.txt");


 

結果如下： 編號最近的30個值。


 

 

以上就算把knn算法在spark下完成了，剩下要做的就是根據一個數據點進行搜索最相近的k個值。

 

搜索：

final Node<Integer> query = new Node(String.valueOf(111), 50);
final NeighborList neighborlist_exhaustive
                = exhaustive_search.search(query, 5);

 

這段代碼是搜索 結點id為111，數值為50最近的5個值。

結果如下：


 

代碼很簡單：

 

/**
 * Created by lsy 983068303@qq.com
 * on 2016/12/15.
 */
public class TestKnn {
    public static void main(String[] args) throws Exception {
        SparkConf conf = new SparkConf();
        conf.setMaster("local[4]");
        conf.setAppName("knn");
//        conf.set("spark.executor.memory","1G");
//        conf.set("spark.storage.memoryFraction","1G");
        JavaSparkContext sc = new JavaSparkContext(conf);

        List<Node<Integer>> data = new ArrayList<Node<Integer>>();
        for (int i = 0; i < 100; i++) {
            data.add(new Node(String.valueOf(i), i));
        }
        final SimilarityInterface<Integer> similarity =new SimilarityInterface<Integer>() {
            public double similarity(Integer value1, Integer value2) {
                return 1.0 / (1.0 + Math.abs((Integer) value1 - (Integer) value2));
            }
        };
        JavaRDD<Node<Integer>> nodes = sc.parallelize(data);
        NNDescent nndes = new NNDescent<Integer>();
        nndes.setK(30);
        nndes.setMaxIterations(4);
        nndes.setSimilarity(similarity);
        JavaPairRDD<Node, NeighborList> graph = nndes.computeGraph(nodes);

        graph.saveAsTextFile("out");
        ExhaustiveSearch exhaustive_search
                = new ExhaustiveSearch(graph, similarity);
        graph.cache();
        final Node<Integer> query = new Node(String.valueOf(111), 50);
        final NeighborList neighborlist_exhaustive
                = exhaustive_search.search(query, 5);
         for(Neighbor n:neighborlist_exhaustive){
            System.out.print("id編號："+n.node.id+"==============") ;
            System.out.println("對應的數值："+n.node.id) ;
         }
        sc.stop();
    }