Back to results
US 8,363,961 B1Granted
Clustering techniques for large, high-dimensionality data sets
AssigneeAdobe Systems Incorporated
InventorsShmuel Avidan, Lior Shapira
Life of this patent
Estimating the term…
Abstract
A clustering method for high-dimensionality data includes identifying a set of nearest neighbors of a point in a multidimensional space and determining the centroid of the set of nearest neighbors, where the centroid is a member of the set of nearest neighbors. The method is then repeated using the neighbors identified around the computed centroid. In one embodiment, the method may terminate when the computed centroid becomes stationary over successive iterations. The resulting centroid may be returned as a mode of the data set. Points of the data set having common modes may be assigned to the same cluster.
Claims34
A computer-implemented method, comprising:
- generating a mode m of a set P including a plurality of data points defined within a multidimensional space, wherein generating said mode comprises:
- (a) for a point p selected from within set P, identifying a set S including a plurality of points within set P that neighbor point p according to a distance metric defined on the multidimensional space;
- (b) generating a centroid point c of set S, wherein centroid point c is a member of set S, and wherein generating the centroid point c of set S comprises:
- projecting each point in set S onto each of a plurality of vectors v within a set V;
- and
- selecting as centroid point c the point in S that minimizes a total difference, across all of the vectors v in V, between the projection of c onto each given vector v and the median of the projection of S onto the same given vector v;
- (c) determining whether a distance between the centroid point c and the point p satisfies a threshold value;
- (d) in response to determining that the distance between the centroid point c and the point p does satisfy the threshold value, returning centroid point c as a mode m of set P and terminating, or in response to determining that the distance between the centroid point c and the point p does not satisfy a threshold value, assigning centroid point c to point p and repeating (a) through (d);
- wherein each of (a) through (d) is implemented by one or more processors.
6 more elements
A non-transitory computer-readable storage medium that stores instructions, wherein the instructions are executable one or more processors to:
- generate a mode m of a set P including a plurality of data points defined within a multidimensional space, wherein to generate said mode, the instructions are further executable by the one or more processors to:
- (a) for a point p selected from within set P, identify a set S including a plurality of points within set P that neighbor point p according to a distance metric defined on the multidimensional space;
- (b) generate a centroid point c of set S, wherein centroid point c is a member of set S, and wherein to generate the centroid point c of set S, the instructions are further executable by the one or more processors to:
- generate a projection of each point in set S onto each of a plurality of vectors v within a set V;
- and
- select as centroid point c the point in S that minimizes a total difference, across all of the vectors v in V, between the projection of c onto each given vector v and the median of the projection of S onto the same given vector v;
- (c) determine whether a distance between the centroid point c and the point p satisfies a threshold value;
- (d) in response to determining that the distance between the centroid point c and the point p does satisfy the threshold value, return centroid point c as a mode m of set P and terminate, or in response to determining that the distance between the centroid point c and the point p does not satisfy a threshold value, assign centroid point c to point p and repeat (a) through (d).
5 more elements
A system, comprising:
- at least one processor;
- and
- a memory coupled to the at least one processor, wherein the memory stores instructions, wherein the instructions are executable by the at least one processor to:
- generate a mode m of a set P including a plurality of data points defined within a multidimensional space, wherein to generate said mode, the instructions are further executable by the at least one processor to:
- (a) for a point p selected from within set P, identify a set S including a plurality of points within set P that neighbor point p according to a distance metric defined on the multidimensional space;
- (b) generate a centroid point c of set S, wherein centroid point c is a member of set S, and wherein to generate the centroid point c of set S, the instructions are further executable by the at least one processor to:
- generate a projection of each point in set S onto each of a plurality of vectors v within a set V;
- and
- select as centroid point c the point in S that minimizes a total difference, across all of the vectors v in V, between the projection of c onto each given vector v and the median of the projection of S onto the same given vector v;
- (c) determine whether a distance between the centroid point c and the point p satisfies a threshold value;
- (d) in response to determining that the distance between the centroid point c and the point p does satisfy the threshold value, return centroid point c as a mode m of set P and terminate, or in response to determining that the distance between the centroid point c and the point p does not satisfy a threshold value, assign centroid point c to point p and repeat (a) through (d).
8 more elements
A computer-implemented method, comprising:
- (a) executing instructions on a specific apparatus comprising a processor so that binary digital electronic signals representing a set P including a plurality of data points defined within a multidimensional space are evaluated to identify, for a point p selected from within set P, a set S including a plurality of points within set P that neighbor point p according to a distance metric defined on the multidimensional space;
- (b) executing instructions on said specific apparatus so that binary digital signals representing a centroid point c of set S are generated, wherein centroid point c is a member of set S, and wherein executing instructions on said specific apparatus so that binary digital signals representing the centroid point c of set S are generated comprises:
- executing instructions on said specific apparatus so that binary digital signals representing a projection of each point in set S onto each of a plurality of vectors v within a set V are generated;
- and
- executing instructions on said specific apparatus so that binary digital signals are generated that represent a selection as centroid point c the point in S that minimizes a total difference, across all of the vectors v in V, between the projection of c onto each given vector v and the median of the projection of S onto the same given vector v;
- (c) executing instructions on said specific apparatus so that binary digital signals representing a distance between the centroid point c and the point p satisfies a threshold value are generated;
- (d) executing instructions on said specific apparatus so that, if the distance between the centroid point c and the point p satisfies a threshold value, binary digital signals representing centroid point c are returned as a mode m of set P, or if the distance between the centroid point c and the point p does not satisfy the threshold value, binary digital signals representing centroid point c are assigned to represent point p and (a) through (d) are repeated;
- and
- storing the mode m of set P in a memory location of said specific apparatus for later use.
6 more elements
Dependencies are inferred from the claim text.