Method and system for clustering datasets
View Patent ↗A method and system for clustering a plurality of data elements is provided. According to embodiments of the present invention, a bit vector is generated based on each of the data elements. Bit operations are used to group each data element into a cluster. Clustering may be performed by partition clustering or hierarchical clustering. Embodiments of the present invention cluster data elements such as text documents, audio files, video files, photos, or other data files.
1. A computer-implemented method for clustering a plurality of data elements, the method comprising:
generating, by a computer, a bit vector for each of the plurality of data elements based on vector of reals associated with a data element of the plurality of data elements and a plurality of random vectors, thereby generating a plurality of bit vectors;
creating, by the computer, a histogram based on the plurality of bit vectors;
partitioning, by the computer, the histogram into a plurality of regions;
creating, by the computer, a bit mask for each of the plurality of regions; and
clustering, by the computer, each of the plurality of data elements into one of a plurality of clusters by comparing the bit vector for each of the plurality of data elements with each of the bit masks, wherein the comparing comprises processing the bit vector and each of the bit masks using a bit operation and assigning each of the plurality of data elements associated with the bit vector to the cluster with the corresponding bit mask generating greatest number of ones in the bit operation.
2. The computer-implemented method of claim 1 , wherein generating the vector of reals comprises:
extracting, by the computer, a feature set from the plurality of data elements, and
generating, by the computer, a vector of reals for each the plurality of data elements based on the feature set.
3. The computer-implemented method of claim 1 , wherein partitioning the histogram comprises identifying at least one deepest valley within the histogram.
4. The computer-implemented method of claim 3 wherein the identifying at least one deepest valley within the histogram comprises:
creating a queue data structure having as entries pairs representing left-position and right-position;
determining a mid-point between the left-position and the right-position of the entries pairs; and
comparing depth of the valley identified nearest to left of the mid-point to the depth of the valley nearest to right of the mid-point.
5. The computer-implemented method of claim 3 wherein the identifying at least one deepest valley within the histogram is repeated until a specific number of clusters are generated.
6. The computer-implemented method of claim 1 , wherein the plurality of data elements comprises one of image files, audio files or text files.
7. The computer-implemented method of claim 1 wherein the generating a bit vector for each of the plurality of vectors comprises executing a dot product operation between the vectors of reals and the plurality of random vectors.
8. A computer-implemented method for clustering a plurality of data elements, the method comprising:
generating, by a computer, a bit vector for each of the plurality of data elements based on vector of reals associated with a data element of the plurality of data elements and a plurality of random vectors, thereby generating a plurality of bit vectors;
creating, by the computer, a histogram based on the plurality of bit vectors;
creating, by the computer, a hierarchical set of bit masks according to the histogram; and
clustering, by the computer, each of the plurality of data elements into one of a plurality of clusters by comparing the bit vector for each of the plurality of data elements with the hierarchical set of bit masks, wherein the comparing comprises processing the bit vector and each of the bit masks using a bit operation and assigning each of the plurality of data elements associated with the bit vector to the cluster with the corresponding bit mask generating greatest number of ones in the bit operation.
9. The computer-implemented method of claim 8 , wherein generating a vector of reals comprises:
extracting, by the computer, a feature set from the plurality of data elements, and
generating, by the computer, a vector of reals for each the plurality of data elements based on the feature set.
10. The computer-implemented method of claim 8 , wherein the plurality of data elements comprises one of image files, audio files or text files.
11. The computer-implemented method of claim 8 wherein the generating a bit vector for each of the plurality of vectors comprises executing a dot product operation between the vectors of reals and the plurality of random vectors.
12. A system for clustering a plurality of data elements, comprising:
a data processing device;
a database coupled to the data processing device;
a bit vector creation module coupled to the data processing device and the database, the bit vector creation module configured to:
generate a bit vector for each of the plurality of data elements based on vector of reals associated with a data element of the plurality of data elements and a plurality of random vectors, thereby generating a plurality of bit vectors;
and
a clustering module coupled to the data processing device and the database, the clustering module configured to:
create a histogram based on the plurality of bit vectors,
partition the histogram into a plurality of regions,
create a bit mask for each of the plurality of regions, and
cluster each of the plurality of data elements into one of a plurality of clusters by comparing the bit vector for each of the plurality of data elements with each of the bit masks, wherein the comparing comprises processing the bit vector and each of the bit masks using a bit operation and assigning each of the plurality of data elements associated with the bit vector to the cluster with the corresponding bit mask generating greatest number of ones in the bit operation.
13. The system of claim 12 , wherein the bit vector creation module is further configured to:
extract a feature set from the plurality of data elements, and
generate a vector of reals for each the plurality of data elements based on the feature set.
14. The system of claim 12 , wherein clustering module is configured to partition the histogram comprises identifying an at least one deepest valley within the histogram.
15. The system of claim 12 , wherein the plurality of data elements comprises one of image files, audio files or text files.
16. The system of claim 12 wherein the generate a bit vector for each of the plurality of vectors comprises execute a dot product operation between the vectors of reals and the plurality of random vectors.
17. A system for clustering a plurality of data elements, comprising:
a data processing device;
a database coupled to the data processing device;
a bit vector creation module coupled to the data processing device and the database, the bit vector creation module configured to:
generate a bit vector for each of the plurality of data elements based on vector of reals associated with a data element of the plurality of data elements and a plurality of random vectors, thereby generating a plurality of bit vectors;
and
a clustering module coupled to the data processing device and the database, the clustering module configured to:
create a histogram based on the plurality of bit vectors,
create a hierarchical set of bit masks according to the histogram, and
cluster each of the plurality of data elements into one of a plurality of clusters by comparing the bit vector for each of the plurality of data elements with the hierarchical set of bit masks, wherein the comparing comprises processing the bit vector and each of the bit masks using a bit operation and assigning each of the plurality of data elements associated with the bit vector to the cluster with the corresponding bit mask generating greatest number of ones in the bit operation.
18. The system of claim 17 , wherein the bit vector creation module is further configured to:
extract a feature set from the plurality of data elements, and
generate a vector of reals for each the plurality of data elements based on the feature set.
19. The system of claim 17 , wherein the plurality of data elements comprises one of image files, audio files or text files.
20. The system of claim 17 wherein the generate a bit vector for each of the plurality of vectors comprises execute a dot product operation between the vectors of reals and the plurality of random vectors.