SPECTRAL CLUSTERING USING SEQUENTIAL SHRINKAGE OPTIMIZATION
A clustering system initially applies an eigenvalue decomposition solver for a number of iterations to a clustering objective function. The eigenvalue decomposition solver generates an eigenvector that is an initial approximation of a solution to the objective function. The clustering system fixes the eigenvector values for the identified objects. The clustering system then reformulates the objective function to focus on the objects whose clusters have not yet been determined. The clustering system then applies an eigenvalue decomposition solver for a number of iterations to the reformulated objective function to generate new values for the eigenvector for the objects whose clusters have not yet been determined. The clustering system then repeats the process of identifying objects, reformulating the objective function, and applying an eigenvalue decomposition solver for a number of iterations until a termination criterion is satisfied.
1 . A method in a computing device for clustering objects having relationships, the method comprising:
applying a nonlinear eigenvalue decomposition solver to a clustering objective function for a number of iterations to generate an approximate solution represented by an eigenvector with a value for each object representing the cluster to which the object belongs; and
repeating the following until a termination criterion is satisfied:
identifying objects whose clusters have been determined as indicated by the values of the eigenvector;
reformulating the objective function to focus on the objects whose clusters have not yet been determined; and
applying a nonlinear eigenvalue decomposition solver to the reformulated objective function for a number of iterations to generate an eigenvector representing an approximate solution.
2 . The method of claim 1 wherein the termination criterion is satisfied when the clusters of all the objects have been determined.
3 . The method of claim 1 wherein the objective function is represented by the following:
min
q
T
Lq
q
T
Wq
,
s
.
t
.
q
T
We
=
0
4 . The method of claim 3 wherein the reformulated objective function is represented by the following:
min
[
q
1
q
2
]
T
[
L
1
L
12
L
21
L
2
]
[
q
1
q
2
]
[
q
1
q
2
]
T
[
W
1
W
2
]
[
q
1
q
2
]
,
s
.
t
.
[
q
1
q
2
]
T
[
W
1
W
2
]
[
e
1
e
2
]
=
0
5 . The method of claim 3 wherein the reformulated objective function is represented by the following:
min
T
(
q
2
)
=
q
2
T
L
2
q
2
+
2
q
1
T
L
12
q
2
+
q
1
T
L
1
q
1
q
2
T
W
2
q
2
+
q
1
T
W
1
q
1
s
.
t
.
q
2
T
W
2
e
2
+
q
1
T
W
1
e
1
=
0
6 . The method of claim 1 wherein the eigenvalue decomposition solver is a preconditioned conjugate gradient solver.
7 . The method of claim 1 wherein values of the eigenvector corresponding to the objects whose clusters have been determined are fixed.
8 . The method of claim 7 wherein the values are fixed as represented by the following:
q
1
(
i
)
=
{
+
η
2
η
1
q
1
(
i
)
>
0
-
η
1
η
2
q
1
(
i
)
<
0
9 . The method of claim 1 including outputting an indication of the clusters of the objects.
10 . A method in a computing device for clustering objects having relationships, the objects having object weights and the relationships having relationship weights, the method comprising:
applying a nonlinear eigenvalue decomposition solver to a clustering objective function for a number of iterations to generate an approximate solution represented by an eigenvector with a value for each object representing the cluster to which the object belongs, the objective function factoring in object weights and relationship weights; and
repeating the following until a termination criterion is satisfied:
identifying objects whose clusters have been determined as indicated by the values of the eigenvector;
reformulating the objective function to focus on the objects whose clusters have not yet been determined and so that the object weights dominate the relationship weights; and
applying a linear eigenvalue decomposition solver to the reformulated objective function for a number of iterations to generate an eigenvector representing an approximate solution.
11 . The method of claim 10 wherein the termination criterion is satisfied when the clusters of all the objects have been determined.
12 . The method of claim 10 wherein the objective function is represented by the following:
min
q
T
Lq
q
T
Wq
,
s
.
t
.
q
T
We
=
0
13 . The method of claim 12 wherein the reformulated objective function is represented by the following:
H ( q 2 )= q 2 T L 2 q 2 +2 q 1 T L 12 q 2 +q 1 T L 1 q 1
14 . The method of claim 13 wherein the reformulating of the objective function so that the object weights dominate the relationship weights results in the objective function being linear.
15 . The method of claim 10 including outputting an indication of the clusters of the objects.
16 . The method of claim 10 wherein the reformulating removes a denominator of the objective function.
17 . A computer-readable medium encoded with instructions for controlling a computing device to cluster objects having relationships, by a method comprising:
applying an eigenvalue decomposition solver to a clustering objective function for a number of iterations to generate an approximate solution represented by an eigenvector with a value for each object representing the cluster to which the object belongs; and
repeating the following until a termination criterion is satisfied:
identifying objects whose clusters have been determined as indicated by the values of the eigenvector;
reformulating the objective function to focus on the objects whose clusters have not yet been determined; and
applying an eigenvalue decomposition solver to the reformulated objective function for a number of iterations to generate an eigenvector representing an approximate solution.
18 . The computer-readable medium of claim 17 wherein the objective function is nonlinear and the reformulated objective function is nonlinear with values of the eigenvector being fixed for the objects whose clusters have been determined.
19 . The computer-readable medium of claim 17 wherein the objective function is nonlinear and the reformulated objective function is made linear by removing a denominator of the objective function.
20 . The computer-readable medium of claim 17 wherein the objects have object weights and the relationships have relationship weights and the objective function is reformulated so that object weights dominate relationship weights.