mahout-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MAHOUT-1991) Implement naive DBSCAN Algorithm - O(n^2) complexity
Date Thu, 20 Jul 2017 23:28:00 GMT

    [ https://issues.apache.org/jira/browse/MAHOUT-1991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16095551#comment-16095551
] 

ASF GitHub Bot commented on MAHOUT-1991:
----------------------------------------

Github user dlyubimov commented on a diff in the pull request:

    https://github.com/apache/mahout/pull/334#discussion_r128654179
  
    --- Diff: math-scala/src/main/scala/org/apache/mahout/math/algorithms/clustering/DBSCAN_Incore.scala
---
    @@ -0,0 +1,142 @@
    +/**
    +  * Licensed to the Apache Software Foundation (ASF) under one
    +  * or more contributor license agreements. See the NOTICE file
    +  * distributed with this work for additional information
    +  * regarding copyright ownership. The ASF licenses this file
    +  * to you under the Apache License, Version 2.0 (the
    +  * "License"); you may not use this file except in compliance
    +  * with the License. You may obtain a copy of the License at
    +  *
    +  * http://www.apache.org/licenses/LICENSE-2.0
    +  *
    +  * Unless required by applicable law or agreed to in writing,
    +  * software distributed under the License is distributed on an
    +  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    +  * KIND, either express or implied. See the License for the
    +  * specific language governing permissions and limitations
    +  * under the License.
    +  */
    +package org.apache.mahout.math.algorithms.clustering
    +
    +import scala.collection.JavaConversions.iterableAsScalaIterable
    +import org.apache.mahout.math.scalabindings.::
    +import org.apache.mahout.math.scalabindings.RLikeOps.m2mOps
    +import org.apache.mahout.math.scalabindings.RLikeOps.v2vOps
    +import org.apache.mahout.math.scalabindings.dvec
    +import org.apache.mahout.math._
    +import scalabindings._
    +import scala.collection.mutable.ArrayBuffer
    +import scala.collection.mutable.Queue
    +
    +class DBSCAN_Incore {
    +
    +  def expandCluster(i: Int, data: DenseMatrix, neighbours: DenseVector, clusterId: Int,
Eps: Double, Minpts: Int) = {
    +    data(i, 3) = clusterId.toDouble
    +    var neighbourQueue = new Queue[Int]()
    +    for(index <- 0 until neighbours.length) {
    +      neighbourQueue += neighbours(index).toInt
    +    }
    +
    +    while(neighbourQueue.nonEmpty) {
    +      var curr: Int = neighbourQueue.dequeue()
    +      if(data(curr, 1) == 0) {
    +        var currNeighbours: DenseVector = findNeighbours(curr, data, Eps)
    +        data(curr, 1) = 1
    +        if(currNeighbours.length >= Minpts) {
    +          data(curr, 0) = 1 //coreFlag == True
    +          for (index <- 0 until currNeighbours.length) {
    +            neighbourQueue += currNeighbours(index).toInt
    +          }
    +        }
    +        if(data(curr, 3) == -1) {
    +          data(curr, 3) = clusterId
    +        }
    +      }
    +    }
    +  }
    +
    +  def DBSCAN(data: DenseMatrix, Eps: Double, Minpts: Int): Unit = {
    +
    +    var clusterId: Int = 0
    +    for(i <- 0 until data.nrow) {
    +      if(data(i, 1) != 1) {
    +        //i.e. if notProcessed...
    +        val neighbours: DenseVector = findNeighbours(i, data, Eps)
    +        data(i, 1) = 1.0 // ==> processedFlag = True
    +        if(neighbours.length >= Minpts) {
    +          // ==> i corresponds to a core point.
    +          data(i, 0) = 1 // ==> coreFlag = True
    +          //          data(i, 3) = clusterId
    +          expandCluster(i, data, neighbours, clusterId, Eps, Minpts)
    +          clusterId += 1
    +        }
    +        else {
    +          data(i, 4) = 1.0 // ==> noiseFlag = True
    +        }
    +      }
    +    }
    +  }
    +
    +  /*
    +  @args
    +  point: Int - Id of the point whose neighbours are to be computed
    +  data: DenseMatrix[Double] - The augmented matrix containing all the data points along
with the 4 appended columns
    +  Returns: A DenseVector containing the ID's of all the points that are at an Eps distance
from point.
    +   */
    +  def findNeighbours(point: Int, data: DenseMatrix, Eps: Double) : DenseVector = {
    +    val pointId: Int = data(point, 2).toInt
    +    var neighbours: ArrayBuffer[Int] = new ArrayBuffer[Int]()
    +    val pointData: DenseVector = dvec(data(pointId, ::))
    --- End diff --
    
    redundant dvec (imo), slice is already an `o.a.m.math.Vector` 



> Implement naive DBSCAN Algorithm - O(n^2) complexity
> ----------------------------------------------------
>
>                 Key: MAHOUT-1991
>                 URL: https://issues.apache.org/jira/browse/MAHOUT-1991
>             Project: Mahout
>          Issue Type: New Feature
>          Components: Algorithms
>            Reporter: Aditya AS
>            Assignee: Aditya AS
>
> Implement the naive DBSCAN algorithm in Mahout Samsara, as part of the Algorithms Framework.



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

Mime
View raw message