[
https://issues.apache.org/jira/browse/MAHOUT-1991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16142564#comment-16142564
]
ASF GitHub Bot commented on MAHOUT-1991:
----------------------------------------
Github user AdityaAS commented on a diff in the pull request:
https://github.com/apache/mahout/pull/334#discussion_r135379575
--- 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 --
Updated
> 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)
