Methods and systems for extracting and visualizing patterns in large-scale data sets

1. A method comprising:

receiving a data set comprising a plurality of data points;

determining a plurality of connections between the plurality of data points;

generating, based on the plurality of connections, a plurality of groups from the plurality of data points;

generating, based on an inter-group similarity measurement and an intra-group similarity measurement for each group of the plurality of groups, a plurality of merged groups;

determining, for each merged group of the plurality of merged groups, a convex hull, wherein each convex hull comprises a plurality of edges;

determining, for each convex hull of each of the plurality of merged groups, a subset of the plurality of edges to be split; and

generating, at a user interface, based on the subset of the plurality of edges to be split for each convex hull of each of the plurality of merged groups, a visual analytic comprising a plurality of geometrical shapes, wherein each geometrical shape of the plurality of geometrical shapes corresponds to a merged group of the plurality of merged groups, and wherein each geometrical shape of the plurality of geometrical shapes is based on a result of splitting the subset of the plurality of edges for the convex hull of the corresponding merged group.

2. The method of claim 1 , wherein determining the plurality of connections between the plurality of data points comprises determining a Delaunay triangulation from the plurality of data points.

3. The method of claim 2 , wherein determining the plurality of connections between the plurality of data points comprises generating a minimum spanning tree (MST) from the Delaunay triangulation, the MST comprising the plurality of connections.

4. The method of claim 1 , wherein generating the plurality of groups comprises generating a predefined number of groups.

5. The method of claim 4 , wherein generating the predefined number of groups comprises generating a predefined number of longest connections from the plurality of connections.

6. The method of claim 4 , wherein generating the predefined number of groups comprises:

identifying a subset of the plurality of connections having a length meeting a predefined threshold; and

removing the subset of the plurality of connections from the plurality of connections.

7. The method of claim 6 , wherein the predefined threshold is based on an average length of the plurality of connections.

8. The method of claim 1 , wherein generating the plurality of groups comprises:

determining a number of groups based on a distance metric defining a closeness between data points in a respective one of the plurality of groups; and

generating the plurality of groups according to the number of groups.

9. The method of claim 1 , wherein generating the plurality of merged groups comprises:

determining, based on the plurality of groups, at least one criterion associated with the plurality of groups that reduces the intra-group similarity measurement and increases the inter-group similarity measurement for each group of the plurality of groups; and

generating, based on the at least one criterion, the plurality of merged groups.

10. The method of claim 9 , wherein the at least one criterion comprises: a total number of groups, a number of data points within each group of the plurality of groups, or a centroid for each group of the plurality of groups.

11. An apparatus comprising one or more processors and a memory storing processor executable instructions that, when executed by the one or more processors, cause the apparatus to:

receive a data set comprising a plurality of data points;

determine a plurality of connections between the plurality of data points;

generate, based on the plurality of connections, a plurality of groups from the plurality of data points;

generate, based on an inter-group similarity measurement and an intra-group similarity measurement for each group of the plurality of groups, a plurality of merged groups;

determine, for each merged group of the plurality of merged groups, a convex hull, wherein each convex hull comprises a plurality of edges;

determine, for each convex hull of each of the plurality of merged groups, a subset of the plurality of edges to be split; and

generate, at a user interface, based on the subset of the plurality of edges to be split for each convex hull of each of the plurality of merged groups, a visual analytic comprising a plurality of geometrical shapes, wherein each geometrical shape of the plurality of geometrical shapes corresponds to a merged group of the plurality of merged groups, and wherein each geometrical shape of the plurality of geometrical shapes is based on a result of splitting the subset of the plurality of edges for the convex hull of the corresponding merged group.

12. The apparatus of claim 11 , wherein the processor executable instructions that cause the apparatus to determine the plurality of connections between the plurality of data points further cause the apparatus to determine a Delaunay triangulation from the plurality of data points.

13. The apparatus of claim 12 , wherein the processor executable instructions that cause the apparatus to determine the plurality of connections between the plurality of data points further cause the apparatus to generate a minimum spanning tree (MST) from the Delaunay triangulation, the MST comprising the plurality of connections.

14. The apparatus of claim 11 , wherein the processor executable instructions that cause the apparatus to generate the plurality of groups further cause the apparatus to generate a predefined number of groups.

15. The apparatus of claim 14 , wherein the processor executable instructions that cause the apparatus to generate the predefined number of groups further cause the apparatus to generate a predefined number of longest connections from the plurality of connections.

16. The apparatus of claim 14 , wherein the processor executable instructions that cause the apparatus to generate the predefined number of groups further cause the apparatus to:

identify a subset of the plurality of connections having a length meeting a predefined threshold; and

remove the subset of the plurality of connections from the plurality of connections.

17. The apparatus of claim 16 , wherein the predefined threshold is based on an average length of the plurality of connections.

18. The apparatus of claim 11 , wherein the processor executable instructions that cause the apparatus to generate the plurality of groups further cause the apparatus to:

determine a number of groups based on a distance metric defining a closeness between data points in a respective one of the plurality of groups; and

generate the plurality of groups according to the number of groups.

19. The apparatus of claim 11 , wherein the processor executable instructions that cause the apparatus to generate the plurality of merged groups further cause the apparatus to:

determine, based on the plurality of groups, at least one criterion associated with the plurality of groups that reduces the intra-group similarity measurement and increases the inter-group similarity measurement for each group of the plurality of groups; and

generate, based on the at least one criterion, the plurality of merged groups.

20. The apparatus of claim 19 , wherein the at least one criterion comprises: a total number of groups, a number of data points within each group of the plurality of groups, or a centroid for each group of the plurality of groups.