ADDITIVE ONLINE COMPLETE LINKAGE CLUSTERING

In certain aspects, a computer-implemented method includes receiving an incoming element; determining whether a distance of the incoming element to the nearest existing element that is found is above a clustering threshold; creating, based on determining the distance is above the clustering threshold, a new cluster and associating the new cluster to the incoming element; determining, based on determining the distance is not above the clustering threshold, whether distances from the incoming element to contents of the nearest existing element that is found are all below the clustering threshold; associating, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are all below the clustering threshold, associating the incoming element to the cluster of the nearest existing element that is found; processing, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are not all below the clustering threshold, elements of the cluster of the nearest existing element that is found together with the incoming element using an original complete-linkage algorithm, wherein the processing generates a first cluster and a second cluster, wherein the first cluster is smaller than the second cluster; creating another cluster and re-associating elements of the first cluster into the another cluster.

TECHNICAL FIELD

The present disclosure generally relates to hierarchical clustering, and more specifically relates to additive online complete linkage clustering.

BACKGROUND

Agglomerative hierarchical clustering methods, such as complete-linkage clustering, are commonly utilized in data mining and statistics for cluster analysis. Such cluster analysis methods generally build a hierarchy of clusters. The original method of complete-linkage clustering is limited to working only in an offline mode because of the complex and time intensive methodology involved to process the full set of collected elements at once. While some traditional agglomerative hierarchical clustering methods approximate the complete-linkage clustering method, a desire exists for a complete-linkage clustering method with improved time efficiency that can process elements sequentially as they are entered into a system.

SUMMARY

According to certain aspects of the present disclosure, a computer-implemented method is provided. The method includes receiving an incoming element. The method includes determining whether a distance of the incoming element to the nearest existing element that is found is above a clustering threshold. The method includes creating, based on determining the distance is above the clustering threshold, a new cluster and associating the new cluster to the incoming element. The method includes determining, based on determining the distance is not above the clustering threshold, whether distances from the incoming element to contents of the nearest existing element that is found are all below the clustering threshold. The method includes associating, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are all below the clustering threshold, associating the incoming element to the cluster of the nearest existing element that is found. The method includes processing, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are not all below the clustering threshold, elements of the cluster of the nearest existing element that is found together with the incoming element using an original complete-linkage algorithm, wherein the processing generates a first cluster and a second cluster, wherein the first cluster is smaller than the second cluster. The method includes creating another cluster and re-associating elements of the first cluster into the another cluster.

According to other aspects of the present disclosure, a system is provided. The system includes a memory comprising instructions and a processor configured to execute the instructions which, when executed, cause the processor to receive an incoming element. The processor is configured to execute the instructions which, when executed, cause the processor to search for a nearest existing element with respect to the incoming element. The processor is configured to execute the instructions which, when executed, cause the processor to determine whether a distance of the incoming element to the nearest existing element that is found is above a clustering threshold. The processor is configured to execute the instructions which, when executed, cause the processor to create, based on determining the distance is above the clustering threshold, a new cluster and associating the new cluster to the incoming element. The processor is configured to execute the instructions which, when executed, cause the processor to determine, based on determining the distance is not above the clustering threshold, whether distances from the incoming element to contents of the nearest existing element that is found are all below the clustering threshold. The processor is configured to execute the instructions which, when executed, cause the processor to associate, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are all below the clustering threshold, associating the incoming element to the cluster of the nearest existing element that is found. The processor is configured to execute the instructions which, when executed, cause the processor to process, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are not all below the clustering threshold, elements of the cluster of the nearest existing element that is found together with the incoming element using an original complete-linkage algorithm, wherein the processing generates a first cluster and a second cluster, wherein the first cluster is smaller than the second cluster. The processor is configured to execute the instructions which, when executed, cause the processor to create another cluster. The processor is configured to execute the instructions which, when executed, cause the processor to re-associate elements of the first cluster into the another cluster.

According to other aspects of the present disclosure, a non-transitory machine-readable storage medium comprising machine-readable instructions for causing a processor to execute a method is provided. The method includes receiving an incoming element. The method includes determining whether a distance of the incoming element to the nearest existing element that is found is above a clustering threshold. The method includes creating, based on determining the distance is above the clustering threshold, a new cluster and associating the new cluster to the incoming element. The method includes determining, based on determining the distance is not above the clustering threshold, whether distances from the incoming element to contents of the nearest existing element that is found are all below the clustering threshold. The method includes associating, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are all below the clustering threshold, associating the incoming element to the cluster of the nearest existing element that is found. The method includes processing, based on determining the distances from the incoming element to the contents of the nearest existing element that is found are not all below the clustering threshold, elements of the cluster of the nearest existing element that is found together with the incoming element using an original complete-linkage algorithm, wherein the processing generates a first cluster and a second cluster, wherein the first cluster is smaller than the second cluster. The method includes creating another cluster and re-associating elements of the first cluster into the another cluster.

DETAILED DESCRIPTION

The disclosed technology provides a solution to conventional complete-linkage clustering methods. For example, the disclosed technology advantageously approximates complete-linkage clustering with improved time efficiency by processing elements sequentially as received by a system. The disclosed technology provides improvements over traditional approaches by returning cluster association information for each incoming element just after being received by the system, minimizing elements re-associations, and improving time efficiency. Accordingly, the disclosed system can be utilized online, which is an improvement over existing methods that are limited to working only in an offline mode.

Throughout the specification and claims, the following terms take the meanings explicitly associated herein, unless the context clearly dictates otherwise. “Element” is an entity to be clustered and is, but not limited to being, represented as a numeric vector. “Distance” returns a non-negative real number representing the distance between two elements. For example, a distance of zero means the elements are identical. As the value of the distance increases, the elements are more distant from each other. “Clustering threshold” is a user-defined non-negative real number. “Cluster” is a set of near elements. “Complete linkage clustering” is a method according to which the distance between all elements in a cluster must be below the clustering threshold and the distance between clusters defined as the maximum of all the distances between their components. At a first stage, in “agglomerative hierarchical clustering”, each element is considered as a cluster, and next, pairs of nearest clusters are merged to larger clusters. The “agglomerative hierarchical clustering” continues as long as the distance between the clusters to be merged is below the clustering threshold.

FIG.1illustrates an example architecture100for additive online complete linkage clustering. For example, the architecture100includes at least one computing device10, such as a first computing device10a, second computing device10bto an nth computing device10n, a hierarchical clustering service12, and a database14all connected over a network16.

The hierarchical clustering service12can be any device having an appropriate processor, memory, and communications capability for communicating with at least one computing device10and the database14. For purposes of load balancing, the hierarchical clustering service12may include multiple servers. The at least one computing device10, such as the first computing device10aand the second computing device10b, to which the hierarchical clustering service12communicates with over the network16, can be, for example, a tablet computer, a mobile phone, a mobile computer, a laptop computer, a portable media player, an electronic book (eBook) reader, or any other device having appropriate processor, memory, and communications capabilities. The database14can be any device having an appropriate processor, memory, and communications capability for communicating with the hierarchical clustering service12and the at least one computing device10. In certain aspects, the hierarchical clustering service12can be a cloud computing server of an infrastructure-as-a-service (IaaS) and be able to support a platform-as-a-service (PaaS) and software-as-a-service (SaaS) services.

The network16can include, for example, any one or more of a personal area network (PAN), a local area network (LAN), a campus area network (CAN), a metropolitan area network (MAN), a wide area network (WAN), a broadband network (BBN), the Internet, and the like. Further, the network16can include, but is not limited to, any one or more of the following network topologies, including a bus network, a star network, a ring network, a mesh network, a star-bus network, tree or hierarchical network, and the like.

FIG.2is a block diagram illustrating examples of the hierarchical clustering service12, a first computing device10aof the at least one computing device10, and the database14in the architecture ofFIG.1according to certain aspects of the disclosure.

The hierarchical clustering service12, the first computing device10aof the at least one computing device10, and the database14are connected over the network16via respective communication modules18,20,22. The communication modules18,20,22are configured to interface with the network16to send and receive information, such as data, requests, responses, and commands to devices on the network16. The communications modules18,20,22can be, for example, modems or Ethernet cards.

The hierarchical clustering service12includes a processor24, the communications module18, and a memory26that includes a clustering module28. The processor24of the hierarchical clustering service12is configured to execute instructions, such as instructions physically coded into the processor24, instructions received from software in the memory26, or a combination of both. The processor24of the hierarchical clustering service12is configured to receive a clustering threshold from, but not limited to, the first computing device10aof the at least one computing device10. For each incoming element, the processor24of the hierarchical clustering service12, via the clustering module28, is configured to linearly search for the nearest existing element. If no such element is found within the clustering threshold, the processor24of the hierarchical clustering service12, via the clustering module28, is configured to create a new cluster associated to the incoming element.

On the other hand, if an element is found within the clustering threshold, the processor24of the hierarchical clustering service12, via the clustering module28, is configured to add the incoming element to an existing cluster (e.g., a target cluster) associated with the nearest existing element based on complying with a complete linkage constraint. For example, the complete linkage constraint is that all distances between all elements in a cluster must be below the clustering threshold.

If the complete linkage constraint is violated, however, the hierarchical clustering service12, via the clustering module28, is configured to run a complete-linkage algorithm on the elements of the target cluster together with the incoming element resulting in splitting of the target cluster into two valid clusters with the incoming element in one of the two valid clusters. For example, and with reference toFIG.3, the database14includes an elements table38, which can be organized to include columns associated with element properties such as, but not limited to, vector40, cluster ID42, and other appropriate element properties. The memory36is configured to store a cluster list44of at least one cluster46. Each cluster46includes a cluster ID42, which contains an element list48of at least one element50. Each element50contains a vector40and a cluster reference52, which is a reference to its parent cluster.

In certain aspects, as an optimization, when the data is appropriate (e.g., vectors of discrete values), a hash table54can be utilized in searching for identical existing elements prior to the linear search. In such aspects, when an identical element is found, the incoming element is immediately associated to the cluster of the identical existing element. It is enough to store only unique elements under each cluster in the data structure used for the linear (and hashed) search.

As described above, the hierarchical clustering service12, via the clustering module28, is configured to perform advantages in terms of implementation and memory consumption while also allowing for distributed processing such that it is horizontally scalable. Accordingly, different clusters with their components can reside on different machines. For each incoming element, the nearest element on each machine can be searched concurrently, then the results can be reduced to the nearest-of-nearest. Adding the element and splitting the cluster, if required, continues on the machine where the absolute nearest was found. In certain aspects, hierarchical clustering service12, via the clustering module28, is configured to perform with stack traces data of software crash reports with a measured time complexity that is quadratic. In certain aspects where cluster associations are stored in a database, the hierarchical clustering service12, via the clustering module28, provides economical benefits since the number of updates for already clustered data is reduced as compared to conventional approaches. In systems that include initial data, the initial data can be clustered once using the original complete-linkage approach, an then the hierarchical clustering service12, via the clustering module28, can use the results as an initial state to increase accuracy for the next incoming data.

The first computing device10aincludes a processor30, the communications module20, and a memory32. The processor30of the first computing device10ais configured to execute instructions, such as instructions physically coded into the processor30, instructions received from software in memory32, or a combination of both. The processor30of the first computing device10ais configured to transmit the clustering threshold to the hierarchical clustering service12.

The database14includes a processor34, the communications module22, and a memory36. The processor34of the push notification service16is configured to execute instructions, such as instructions physically coded into the processor36, instructions received from software in the memory38, or a combination of both.

FIG.4illustrates an example process400for additive online complete linkage clustering using the hierarchical clustering service12, the first computing device10aof the at least one computing device10, and the database14ofFIG.2. WhileFIG.4is described with reference toFIG.2, it should be understood that the process steps ofFIG.4may be performed by other systems.

As depicted at block410, the database14includes elements50tagged with cluster IDs42. Cluster structures of the clusters46are loaded from the database14into the memory36, if such previous state exists, as illustrated at block410. The clusters46and their associated elements50are stored in the memory36, as depicted at block414.

The process400starts at block416with the processor24of the hierarchical clustering service12receiving an incoming element50. Responsive to receiving the incoming element50, the processor24of the hierarchical clustering service12searches for the nearest existing element stored in the memory36, as illustrated at block418. The nearest existing element is defined as a minimum distance according to the provided distance function.

At block420, the processor24of the hierarchical clustering service12determines whether the distance of the incoming element to the nearest found element is above the clustering threshold. If the distance of the incoming element to the nearest element is above the clustering threshold, the processor24of the hierarchical clustering service12creates a new cluster, associates the new cluster to the incoming element, and updates the memory36of the database14, as depicted a block422. On the other hand, if the distance of the incoming element to the nearest element is not above the clustering threshold, the processor24of the hierarchical clustering service12then determines, as depicted at block424, whether distances from the incoming element to the contents of the nearest found element are all below the clustering threshold. If the distances from the incoming element to the contents of the nearest found element are all below the clustering threshold, the processor24of the hierarchical clustering service12associates the incoming element50to the cluster of the nearest element, as depicted at block426. If the distances from the incoming element to the contents of the nearest found element are not all below the clustering threshold, the processor24of the hierarchical clustering service12processes the elements of the cluster of the nearest element together with the incoming element using the original complete-linkage algorithm, as depicted at block428. As a result, the processor24of the hierarchical clustering service12generates two clusters (e.g., a first cluster and a second cluster) with the incoming element contained in one of the two clusters. Responsive to generating the two clusters, the processor24of the hierarchical clustering service12creates a new cluster and re-associates all the elements that appeared in the smallest of the two returned clusters into the new cluster, as depicted at block430. If the incoming element appeared in the larger of the two returned clusters, the processor24of the hierarchical clustering service12explicitly assigns the incoming element and updates the memory36of the database14.

With reference toFIGS.1-4, an exemplary process according to certain aspects is described in detail below. For each incoming element received at the processor24of the hierarchical clustering service12, the clustering module28checks if the element's vector40is already contained in the hash map (e.g., the hash table52) and ends. If the element's vector40is contained in the hash map, the clustering module28sets a cluster ID42of the incoming element to the cluster ID42of the parent cluster of the element object found in the hash map. If the element's vector40is not contained in the hash map, the clustering module28creates a new element object for this incoming element and adds this new element object to the hash map. (This can be performed in a single operation with the check operation.) The element object doesn't have a reference to a cluster at this point. The clustering module28then goes over all existing clusters in the memory36. For each cluster, the clustering module28goes over all the elements of the cluster and (1) measures the distance between the vector of the incoming element and the vectors of the clustered elements using the provided distance function, (2) if the distance is below that of the nearest element, updates it to reference the tested element and update the nearest distance, and (3) updates the max distance from incoming element to cluster's elements if the current distance is above the previous value. If the nearest element was updated during the iterations on this cluster and max distance from the incoming element to cluster's elements is greater than the clustering threshold, the clustering module28sets the value of requires rebuild (is the cluster of the nearest element contains any element with distance from the incoming element higher than the clustering threshold) to true (otherwise it stays false).

If the nearest distance is greater than the clustering threshold, the clustering module28(1) creates a new cluster object with new cluster ID, adds the element object to that cluster and adds the reverse reference from the object to the cluster, (2) adds the new cluster to the clusters list44, (3) sets the cluster ID42of the incoming element to that of the new cluster and ends.

If require rebuild is false (the new element doesn't cause any other element in the cluster to become further than threshold), the clustering module28(1) adds the new element object to the parent cluster of nearest element and add reverse reference to that cluster to the element object, (2) sets the cluster ID42of the incoming element to that of the parent of the nearest element and ends.

The clustering module28takes all the elements from the parent cluster of the nearest element and adds the new element object to them. The clustering module28feeds this list to the original complete-linkage clustering algorithm, which returns two clusters (e.g., the first cluster and the second cluster). With the two clusters created, the clustering module28(1) replaces the contents of the parent cluster of nearest element with the contents of the largest of the returned clusters. Set reference to that cluster in the contained element objects, (2) creates a new cluster object with new cluster ID and adds it to the list of clusters (fill this cluster with the contents of the smaller returned cluster after converting them to cluster objects with the bi-directional references between cluster and contained elements), (3) updates the cluster ID of all the elements of the new cluster and explicitly updates the incoming element, if that was assigned to the existing cluster (other elements of the existing cluster don't require update because they keep the old cluster ID) and ends.

With reference toFIGS.1-4, an exemplary process according to certain aspects in which the complete-linkage clustering algorithm is utilized is described in detail below. For each input vector, the complete-linkage clustering algorithm creates a cluster object that holds this single vector wrapped as an element. In case the discrete vectors optimization is relevant, in the process of this collection use hash map where the vectors are keys, in order to ignore duplications. This list of clusters would be the first/bottom level of the clustering hierarchy. The complete-linkage clustering algorithm merges clusters of one level as long as the output of the previous level is not empty, where the input for this part is an (ordered) list of clusters of size Ne, (1) prepares two arrays with length equal to Ne: nearest IDs and nearest IDs distances, (2) initializes nearest IDs distances with infinity values, and (3) for each index i from 0 to Nc(exclusive): for each index j from i+1 to Nc(exclusive): (a) measures the distance between cluster at index i and cluster at index j (Distance between clusters defined as the maximum of the distances between all their components. The distance between each two components (vectors) is calculated using the provided distance function), (b) if the distance is less than the value in index i of nearest IDs distances, updates the value at i with the new distance and set the value j in index i of nearest IDs. (Note that in the beginning of this inner loop, index i of the arrays already contains the optimal values for i as measured for j<i from previous iterations of the outer loop that runs on the i index.)

Following this, for each cluster i has a reference (index) of its nearest cluster and the distance between them.

For each index i from 0 to Nc(exclusive), the complete-linkage clustering algorithm (1) if the list of clusters is empty at index i, continues to next i (explanation below), (2) if the nearest distance as appears in index i of nearest IDs distances is above the clustering threshold, adds cluster i to the list of final clusters and continue to next i, (3) (The value at i of nearest IDs (hereafter j) is the index of the nearest cluster to i.) if the value at j of nearest IDs equals i this means they are pointing on each other so they are a “nearest pair,” adds all elements of cluster j into the elements list of cluster i and erase the content of cell j of the clusters list so element j won't be processed in following iterations, and (4) adds cluster i to the list of next level clusters.

If this list of next level clusters is not empty, the complete-linkage clustering algorithm repeats merging clusters with the list of next level clusters. For each cluster in the list of final clusters, for each element in the cluster, the complete-linkage clustering algorithm sets reference to its parent cluster. The list of final clusters is the complete-linkage clustering algorithm's output.

FIG.5is a block diagram illustrating an example computer system500with which the at least one computing device10, such as the first computing device10a, the hierarchical clustering service12, and the database14ofFIG.2can be implemented. In certain aspects, the computer system500may be implemented using hardware or a combination of software and hardware, either in a dedicated server, or integrated into another entity, or distributed across multiple entities.

Computer system500(e.g., the at least one computing device10, such as the first computing device10a, the hierarchical clustering service12, and the database14) includes a bus508or other communication mechanism for communicating information, and a processor502(e.g., the processor24,30,34) coupled with bus508for processing information. According to one aspect, the computer system500can be a cloud computing server of an IaaS that is able to support PaaS and SaaS services.

Computer system500can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them stored in an included memory504(e.g., the memory26,32,36), such as a Random Access Memory (RAM), a flash memory, a Read Only Memory (ROM), a Programmable Read-Only Memory (PROM), an Erasable PROM (EPROM), registers, a hard disk, a removable disk, a CD-ROM, a DVD, or any other suitable storage device, coupled to bus508for storing information and instructions to be executed by processor502. The processor502and the memory504can be supplemented by, or incorporated in, special purpose logic circuitry.

The instructions may be stored in the memory504and implemented in one or more computer program products, e.g., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, the computer system500.

Computer system500further includes a data storage device506such as a magnetic disk or optical disk, coupled to bus508for storing information and instructions. Computer system500may be coupled via input/output module510to various devices. The input/output module510can be any input/output module. Example input/output modules510include data ports such as USB ports. In addition, input/output module510may be provided in communication with processor502, so as to enable near area communication of computer system500with other devices. The input/output module510may provide, for example, for wired communication in some implementations, or for wireless communication in other implementations, and multiple interfaces may also be used. The input/output module510is configured to connect to a communications module512. Example communications modules512(e.g., the communications module18,20,22) include networking interface cards, such as Ethernet cards and modems.

In certain aspects, the input/output module510is configured to connect to a plurality of devices, such as an input device514and/or an output device516. Example input devices514include a keyboard and a pointing device, e.g., a mouse or a trackball, by which a user can provide input to the computer system500. Other kinds of input devices514can be used to provide for interaction with a user as well, such as a tactile input device, visual input device, audio input device, or brain-computer interface device.

According to one aspect of the present disclosure the at least one computing device10, such as the first computing device10a, the hierarchical clustering service12, and the database14can be implemented using a computer system500in response to processor502executing one or more sequences of one or more instructions contained in memory504. Such instructions may be read into memory504from another machine-readable medium, such as data storage device506. Execution of the sequences of instructions contained in main memory504causes processor502to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in memory504. Processor502may process the executable instructions and/or data structures by remotely accessing the computer program product, for example by downloading the executable instructions and/or data structures from a remote server through communications module512(e.g., as in a cloud-computing environment). In alternative aspects, hard-wired circuitry may be used in place of or in combination with software instructions to implement various aspects of the present disclosure. Thus, aspects of the present disclosure are not limited to any specific combination of hardware circuitry and software.

Various aspects of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. For example, some aspects of the subject matter described in this specification may be performed on a cloud-computing environment. Accordingly, in certain aspects a user of systems and methods as disclosed herein may perform at least some of the steps by accessing a cloud server through a network connection. Further, data files, circuit diagrams, performance specifications and the like resulting from the disclosure may be stored in a database server in the cloud-computing environment, or may be downloaded to a private storage device from the cloud-computing environment.

The term “machine-readable storage medium” or “computer-readable medium” as used herein refers to any medium or media that participates in providing instructions or data to processor502for execution. The term “storage medium” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such a medium may take many forms, including, but not limited to, non-volatile media, volatile media, and transmission media.

As used in this specification of this application, the terms “computer-readable storage medium” and “computer-readable media” are entirely restricted to tangible, physical objects that store information in a form that is readable by a computer. These terms exclude any wireless signals, wired download signals, and any other ephemeral signals. Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus508. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications. Furthermore, as used in this specification of this application, the terms “computer”, “server”, “processor”, and “memory” all refer to electronic or other technological devices. These terms exclude people or groups of people. For the purposes of the specification, the terms display or displaying means displaying on an electronic device.