# US 11,442,978 B2 · Heuristic for the data clustering problem

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,442,978 B2
- Document ID: US11442978B2
- Status: Granted
- Kind: B2
- Application number: 15/909,328
- Filed: 2018-03-01
- Published: 2019-09-05
- Granted: 2022-09-13
- Earliest claimed: 2018-03-01
- Assignees: King Fahd University of Petroleum and Minerals
- Applicants: King Fahd University of Petroleum and Minerals
- Inventors: Umair F. Siddiqi; Sadiq M. Sait
- Web page: https://patentgrep.com/patent/US11442978B2

## CPC

- G06V 10/761: {Proximity, similarity or dissimilarity measures}
- G06F 16/2228: {Indexing structures}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/287: {Visualization; Browsing}
- G06F 16/51: Indexing; Data structures therefor; Storage structures
- G06F 16/5838: {using colour}
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06F 18/23213: with fixed number of clusters, e.g. K-means clustering
- G06F 18/24137: {Distances to cluster centroïds}
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A heuristic method for the data clustering problem includes a greedy algorithm, which selects the centroids of well-separated clusters, and a single-solution-based heuristic, which performs clustering with the objective of optimizing a cluster validity index. The attributes of the centroids of clusters are genes and a fitness is determined for each gene. A mutation operation changes the values of the genes of low fitness values and creates a mutant solution. The values of genes of the mutant can replace the values of the genes of the parent if they are better than the genes of the parent. Diversification in the search process is maintained by allowing, with a small probability, the genes of the mutant to replace the genes of the parent even if they are not better than them.

## Claims

### Claim 1

A computer system comprising:
a display; and
one or more processors configured to execute a computer program stored in a memory,
the computer program when executed performs inputting, to the computer system, a color image having a plurality of pixels and a number of clusters;
maximizing distances between centroids of the clusters using greedy search, including selecting new centroids that have maximum distance from the centroids of others of the clusters and that improve a value of a cluster validity index;
using an evolutionary-type search, adjust the new centroids of the clusters with respect to the cluster validity index that considers compactness of the clusters as well as separation between the clusters;
using the adjusted centroids, assign each pixel to the cluster whose centroid has the smallest Euclidean distance from the pixel;
storing, in the memory, a compressed image in which each pixel is stored with the assigned cluster, and the centroids of all clusters; and
displaying, by the display, the compressed image in which each pixel is displayed with the centroid of the assigned cluster,
wherein attributes of the centroids represent genes and the evolutionary-type search adjusts the centroids by
selecting a subset of the genes;
performing a mutation operation on the selected genes to obtain a mutant solution;
determining the validity index based on a ratio of separation between clusters to the compactness of the clusters for the clusters before the mutation operation and after the mutation operation; and
replacing a value of an attribute in a solution with the value of same attribute in the mutant solution if the determined validity index after the mutation operation is greater than or equal to the validity index before the mutation operation.

### Claim 2 (depends on 1)

The computer system of claim 1, wherein the greedy search determines centroids of clusters that maximize inter-cluster separation.

### Claim 3 (depends on 2)

The computer system of claim 2, wherein the greedy search selects a candidate centroid which has a maximum distance from determined centroids of the clusters and adds the candidate centroid to the determined centroid if the value of the validity index is improved.

### Claim 4 (depends on 3)

The computer system of claim 3, wherein the greedy search discards the candidate centroid if the candidate worsens the value of the validity index.

### Claim 5 (depends on 1)

The computer system of claim 1, wherein the value of the attribute in the solution is replaced with the value of the same attribute in the mutant solution if the determined validity index after the mutation operation is less that the validity index before the mutation operation, when the difference in validity index is below a predetermined threshold and a probability of acceptance is greater than a predetermined probability.

### Claim 6 (depends on 5)

The computer system of claim 5, wherein the predetermined threshold and the predetermined probability are greater than 0 and less than or equal to 0.1.

### Claim 7 (depends on 1)

The computer system of claim 1, wherein the evolutionary-type search includes a selection function that is based on a fitness value, wherein the fitness value is determined based on the number of times the attribute has previously been mutated, and wherein the mutation operation is performed on attributes selected by the selection function.

### Claim 8 (depends on 7)

The computer system of claim 7, wherein the evolutionary-type search uses a measure of similarity between pixels that is performed using Euclidean distance.

### Claim 9 (depends on 1)

The computer system of claim 1, wherein each pixel comprises a plurality of attributes.

### Claim 10

A method, in a computer system comprising a display, one or more processors and a memory storing a program, the program when executed performs the method comprising:
inputting, to the computer system, a color image having a plurality of pixels and a number of clusters;
distances between centroids of the clusters using greedy search, including selecting new centroids that have maximum distance from the centroids of others of the clusters and that improve a value of a cluster validity index;
performing an evolutionary-type search to adjust the new centroids of the clusters with respect to the validity index that considers compactness of the clusters as well as separation between clusters;
using the adjusted centroids, assign each pixel to the cluster whose centroid has the minimum Euclidean distance between the pixel and the centroid of the cluster;
storing, in a storage device, a compressed image in which each pixel is stored with the assigned cluster, and the centroids of all clusters; and
displaying, by the display, a compressed image in which each pixel is displayed with the centroid of the assigned cluster,
wherein the centroids include attributes representing genes and the evolutionary-type search adjusts the centroids by
selecting a subset of the genes;
performing a mutation operation on a selected subset of genes to obtain a mutant solution;
determining the validity index based on a ratio of separation between clusters to the compactness of the clusters for the clusters before the mutation operation and after the mutation operation and
replacing a value of an attribute of a solution with the value of the mutant solution in response to a determination that the determined validity index after the mutation operation is greater than or equal to the validity index before the mutation operation.

### Claim 11 (depends on 10)

The method of claim 10, wherein the greedy search determines centroids that maximize inter-cluster separation.

### Claim 12 (depends on 11)

The method of claim 11, wherein the greedy search selects a candidate centroid which has a maximum distance from determined centroids of the clusters and adds the candidate center to the determined centroids in response to a determination that the value of the validity index is improved.

### Claim 13 (depends on 12)

The method of claim 12, wherein the greedy search discards the candidate center in response to a determination that the candidate worsens the value of the validity index.

### Claim 14 (depends on 10)

The method of claim 10, wherein the value of the attribute in the solution is replaced with the value of the mutant solution if the determined validity index after the mutation operation is less than the validity index before the mutation operation, when the difference in validity index is below a predetermined threshold and a probability of acceptance is greater than a predetermined probability.

### Claim 15 (depends on 14)

The method of claim 14, wherein the predetermined threshold and the predetermined probability are greater than 0 and less than or equal to 0.1.

### Claim 16 (depends on 10)

The method of claim 10, wherein the evolutionary-type search includes a selection function that incorporates a fitness value, wherein the fitness value is determined based on the number of times that the attribute has previously been mutated, and wherein the mutation operation is performed on genes selected by the selection function.

### Claim 17 (depends on 10)

The method of claim 10, wherein the evolutionary-type search uses a measure of similarity between pixels that is performed using Euclidean distance.

### Claim 18 (depends on 10)

The method of claim 10, wherein each pixel comprises a plurality of attributes.