From issues-return-23865-apmail-spark-issues-archive=spark.apache.org@spark.apache.org Fri Jan 16 19:52:33 2015 Return-Path: X-Original-To: apmail-spark-issues-archive@minotaur.apache.org Delivered-To: apmail-spark-issues-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 2013B10A9A for ; Fri, 16 Jan 2015 19:52:33 +0000 (UTC) Received: (qmail 41526 invoked by uid 500); 16 Jan 2015 19:52:35 -0000 Delivered-To: apmail-spark-issues-archive@spark.apache.org Received: (qmail 41493 invoked by uid 500); 16 Jan 2015 19:52:35 -0000 Mailing-List: contact issues-help@spark.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Delivered-To: mailing list issues@spark.apache.org Received: (qmail 41483 invoked by uid 99); 16 Jan 2015 19:52:34 -0000 Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 16 Jan 2015 19:52:34 +0000 Date: Fri, 16 Jan 2015 19:52:34 +0000 (UTC) From: "Andrew Musselman (JIRA)" To: issues@spark.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Commented] (SPARK-4259) Add Spectral Clustering Algorithm with Gaussian Similarity Function MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/SPARK-4259?page=3Dcom.atlassian= .jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=3D1428= 0731#comment-14280731 ]=20 Andrew Musselman commented on SPARK-4259: ----------------------------------------- Thinking of picking this up; has there been any work on this already? > Add Spectral Clustering Algorithm with Gaussian Similarity Function > ------------------------------------------------------------------- > > Key: SPARK-4259 > URL: https://issues.apache.org/jira/browse/SPARK-4259 > Project: Spark > Issue Type: New Feature > Components: MLlib > Reporter: Fan Jiang > Assignee: Fan Jiang > Labels: features > > In recent years, spectral clustering has become one of the most popular m= odern clustering algorithms. It is simple to implement, can be solved effic= iently by standard linear algebra software, and very often outperforms trad= itional clustering algorithms such as the k-means algorithm. > We implemented the unnormalized graph Laplacian matrix by Gaussian simila= rity function. A brief design looks like below: > Unnormalized spectral clustering > Input: raw data points, number k of clusters to construct:=20 > =E2=80=A2 Comupte Similarity matrix S =E2=88=88 Rn=C3=97n, . > =E2=80=A2 Construct a similarity graph. Let W be its weighted adjacency m= atrix. > =E2=80=A2 Compute the unnormalized Laplacian L =3D D - W. where D is the = Degree diagonal matrix > =E2=80=A2 Compute the first k eigenvectors u1, . . . , uk of L. > =E2=80=A2 Let U =E2=88=88 Rn=C3=97k be the matrix containing the vectors = u1, . . . , uk as columns. > =E2=80=A2 For i =3D 1, . . . , n, let yi =E2=88=88 Rk be the vector corre= sponding to the i-th row of U. > =E2=80=A2 Cluster the points (yi)i=3D1,...,n in Rk with the k-means algor= ithm into clusters C1, . . . , Ck. > Output: Clusters A1, . . . , Ak with Ai =3D { j | yj =E2=88=88 Ci }. -- This message was sent by Atlassian JIRA (v6.3.4#6332) --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org For additional commands, e-mail: issues-help@spark.apache.org