Computerized cluster analysis framework for decorrelated cluster identification in datasets

A computing device to automatically cluster a dataset is provided. Data that includes a plurality of observations with a plurality of data points defined for each observation is received. Each data point of the plurality of data points is associated with a variable to define a plurality of variables. A number of clusters into which to segment the received data is repeatedly selected by repeatedly executing a clustering algorithm with the received data. A plurality of sets of clusters is defined based on the repeated execution of the clustering algorithm that resulted in the selected number of clusters. A plurality of composite clusters is defined based on the defined plurality of sets of clusters. The plurality of observations is assigned to the defined plurality of composite clusters using the plurality of data points defined for each observation.

BACKGROUND

Given a data matrix X of size n by p, clustering assigns the observations (rows of X) to clusters, or groups based on some or all of the data variables (columns of X). Clustering is a cornerstone of business intelligence, with wide-ranging applications such as market segmentation and fraud detection. Machine learning is a branch of artificial intelligence that is concerned with building systems that require minimal human intervention in order to learn from data.

SUMMARY

In an example embodiment, a method of automatically clustering a dataset is provided. Data that includes a plurality of observations with a plurality of data points defined for each observation is received. Each data point of the plurality of data points is associated with a variable to define a plurality of variables. A number of clusters into which to segment the received data is repeatedly selected by repeatedly executing a clustering algorithm with the received data. A plurality of sets of clusters is defined based on the repeated execution of the clustering algorithm that resulted in the selected number of clusters. A plurality of composite clusters is defined based on the defined plurality of sets of clusters. The plurality of observations is assigned to the defined plurality of composite clusters using the plurality of data points defined for each observation.

In another example embodiment, a computer-readable medium is provided having stored thereon computer-readable instructions that, when executed by a computing device, cause the computing device to perform the method of automatically clustering a dataset.

In yet another example embodiment, a computing device is provided. The system includes, but is not limited to, a processor and a computer-readable medium operably coupled to the processor. The computer-readable medium has instructions stored thereon that, when executed by the computing device, cause the computing device to perform the method of automatically clustering a dataset.

Other principal features of the disclosed subject matter will become apparent to those skilled in the art upon review of the following drawings, the detailed description, and the appended claims.

DETAILED DESCRIPTION

Referring toFIG. 1, a block diagram of a data transformation device100is shown in accordance with an illustrative embodiment. Data transformation device100may include an input interface102, an output interface104, a communication interface106, a non-transitory computer-readable medium108, a processor110, a cluster data application122, a data matrix124, and cluster data126. Fewer, different, and/or additional components may be incorporated into data transformation device100.

Input interface102provides an interface for receiving information from the user for entry into data transformation device100as understood by those skilled in the art. Input interface102may interface with various input technologies including, but not limited to, a keyboard112, a mouse114, a microphone115, a display116, a track ball, a keypad, one or more buttons, etc. to allow the user to enter information into data transformation device100or to make selections presented in a user interface displayed on the display. The same interface may support both input interface102and output interface104. For example, display116comprising a touch screen provides user input and presents output to the user. Data transformation device100may have one or more input interfaces that use the same or a different input interface technology. The input interface technology further may be accessible by data transformation device100through communication interface106.

Output interface104provides an interface for outputting information for review by a user of data transformation device100. For example, output interface104may interface with various output technologies including, but not limited to, display116, a speaker118, a printer120, etc. Data transformation device100may have one or more output interfaces that use the same or a different output interface technology. The output interface technology further may be accessible by data transformation device100through communication interface106.

Communication interface106provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media as understood by those skilled in the art. Communication interface106may support communication using various transmission media that may be wired and/or wireless. Data transformation device100may have one or more communication interfaces that use the same or a different communication interface technology. For example, data transformation device100may support communication using an Ethernet port, a Bluetooth antenna, a telephone jack, a USB port, etc. Data and messages may be transferred between data transformation device100and/or a distributed control device130and/or distributed systems132using communication interface106.

Computer-readable medium108is an electronic holding place or storage for information so the information can be accessed by processor110as understood by those skilled in the art. Computer-readable medium108can include, but is not limited to, any type of random access memory (RAM), any type of read only memory (ROM), any type of flash memory, etc. such as magnetic storage devices (e.g., hard disk, floppy disk, magnetic strips, . . . ), optical disks (e.g., compact disc (CD), digital versatile disc (DVD), . . . ), smart cards, flash memory devices, etc. Data transformation device100may have one or more computer-readable media that use the same or a different memory media technology. For example, computer-readable medium108may include different types of computer-readable media that may be organized hierarchically to provide efficient access to the data stored therein as understood by a person of skill in the art. As an example, a cache may be implemented in a smaller, faster memory that stores copies of data from the most frequently/recently accessed main memory locations to reduce an access latency. Data transformation device100also may have one or more drives that support the loading of a memory media such as a CD, DVD, an external hard drive, etc. One or more external hard drives further may be connected to data transformation device100using communication interface106.

Processor110executes instructions as understood by those skilled in the art. The instructions may be carried out by a special purpose computer, logic circuits, or hardware circuits. Processor110may be implemented in hardware and/or firmware. Processor110executes an instruction, meaning it performs/controls the operations called for by that instruction. The term “execution” is the process of running an application or the carrying out of the operation called for by an instruction. The instructions may be written using one or more programming language, scripting language, assembly language, etc. Processor110operably couples with input interface102, with output interface104, with communication interface106, and with computer-readable medium108to receive, to send, and to process information. Processor110may retrieve a set of instructions from a permanent memory device and copy the instructions in an executable form to a temporary memory device that is generally some form of RAM. Data transformation device100may include a plurality of processors that use the same or a different processing technology.

Cluster data application122performs operations associated with creating cluster data126from data stored in data matrix124. Cluster data application122can automatically select relevant variables from data stored in data matrix124, determine a best number of clusters into which to segment the data stored in data matrix124, define composite clusters, assign observations to the defined composite clusters, and present a visualization of the defined composite clusters. The created cluster data126may be used to perform various data mining functions and to support various data analysis functions as understood by a person of skill in the art. Some or all of the operations described herein may be embodied in cluster data application122. The operations may be implemented using hardware, firmware, software, or any combination of these methods. Referring to the example embodiment ofFIG. 1, cluster data application122is implemented in software (comprised of computer-readable and/or computer-executable instructions) stored in computer-readable medium108and accessible by processor110for execution of the instructions that embody the operations of cluster data application122. Cluster data application122may be written using one or more programming languages, assembly languages, scripting languages, etc.

Cluster data application122may be implemented as a Web application. For example, cluster data application122may be configured to receive hypertext transport protocol (HTTP) responses and to send HTTP requests. The HTTP responses may include web pages such as hypertext markup language (HTML) documents and linked objects generated in response to the HTTP requests. Each web page may be identified by a uniform resource locator (URL) that includes the location or address of the computing device that contains the resource to be accessed in addition to the location of the resource on that computing device. The type of file or resource depends on the Internet application protocol such as the file transfer protocol, HTTP, H.323, etc. The file accessed may be a simple text file, an image file, an audio file, a video file, an executable, a common gateway interface application, a Java applet, an extensible markup language (XML) file, or any other type of file supported by HTTP.

Data matrix124may organized to include a plurality of rows and one or more columns. The rows of data matrix124may be referred to as observations or records and the columns, representing variables, associated with an observation may be referred to as data points for the observation. Of course, in an alternative embodiment, data matrix124may be transposed and may be organized in other manners. Data matrix124may be stored in various compressed formats such as a coordinate format, a compressed sparse column format, a compressed sparse row format, etc.

The data stored in data matrix124may include any type of content represented in any computer-readable format such as binary, alphanumeric, numeric, string, markup language, etc. The content may include textual information, graphical information, image information, audio information, numeric information, etc. that further may be encoded using various encoding techniques as understood by a person of skill in the art. Data matrix124may be stored in computer-readable medium108or on one or more other computing devices, such as on distributed systems132, and accessed using communication interface106. Data matrix124may be stored using various formats as known to those skilled in the art including a file system, a relational database, a system of tables, a structured query language database, etc. For example, data matrix124may be stored in a cube distributed across a grid of computers as understood by a person of skill in the art. As another example, data matrix124may be stored in a multi-node Hadoop® cluster, as understood by a person of skill in the art. Apache™ Hadoop® is an open-source software framework for distributed computing. Apache Spark™, an engine for large-scale data processing may also be used.

For example, cluster data application122may be used to create cluster data126from observations included in data matrix124. For example, referring toFIG. 21, ten observations, Obs1, Obs2, Obs3, . . . , Obs10are shown divided into a first cluster2100, a second cluster2102, and a third cluster2104, where first cluster2100includes Obs1, Obs6, Obs8, second cluster2102includes Obs2, Obs3, Obs7, Obs9, and third cluster2104includes Obs4, Obs5, Obs10. Cluster data126is a transformation of data matrix124that may be used in support of various data mining and data analysis tasks.FIG. 21provides an example visual representation of clusters though no visual representation is needed as understood by a person of skill in the art.

Referring toFIG. 2, example operations associated with cluster data application122are described. Additional, fewer, or different operations may be performed depending on the embodiment. The order of presentation of the operations ofFIG. 2is not intended to be limiting. Although some of the operational flows are presented in sequence, the various operations may be performed in various repetitions, concurrently (in parallel, for example, using threads), and/or in other orders than those that are illustrated. For example, a user may execute cluster data application122, which causes presentation of a first user interface window, which may include a plurality of menus and selectors such as drop down menus, buttons, text boxes, hyperlinks, etc. associated with cluster data application122as understood by a person of skill in the art. The plurality of menus and selectors may be accessed in various orders. An indicator may indicate one or more user selections from a user interface, one or more data entries into a data field of the user interface, one or more data items read from computer-readable medium108or otherwise defined with one or more default values, etc. that are received as an input by cluster data application122.

In an operation200, a first indicator is received that indicates data to transform to cluster data126. For example, the first indicator indicates a location of data matrix124. In an alternative embodiment, the data to cluster may not be selectable. For example, a most recently created data set may be used automatically.

The first indicator may be received by cluster data application122, for example, after selection from a user interface window or after entry by a user into a user interface window. The first indicator may further indicate that only a portion of the data stored in data matrix124be clustered. For example, in a large dataset only a subset of the observations may be used. First indicator may indicate a number of observations to include, a percentage of observations of the entire dataset to include, etc. A subset may be created from data matrix124by sampling. An example sampling algorithm is uniform sampling. Other random sampling algorithms may be used. Additionally, less than all of the columns may be used to determine the clusters. The first indicator may further indicate the subset of the columns (variables) to use to determine the clusters.

In an operation202, the data indicated by the first indicator is pre-processed, if any pre-processing is to be performed. For example, cluster data application122may provide user selectable options that perform pre-processing functions. As understood by a person of skill in the art, example pre-processing functions include removing variables with an excessive number of cardinality levels, removing variables with an excessive number of missing values, imputing numeric missing values using distributional methods, imputing class variables using decision tree methods, replacing numeric outliers an excessive number of standard deviations from a mean value, binning class variable outliers, standardizing interval variables, scaling or encoding class variables, etc.

In an operation204, decorrelated variables are selected. For example, the decorrelated variables may be selected from the columns included in data matrix124. As an example, the decorrelated variables may be selected using an unsupervised graph-based method that automatically removes correlated variables from data matrix124. Referring toFIG. 3, example operations associated with selecting the decorrelated variables using cluster data application122are described. The order of presentation of the operations ofFIG. 3is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation300, a second indicator of a correlation algorithm to execute is received. For example, the second indicator indicates a name of a correlation algorithm. The second indicator may be received by cluster data application122after selection from a user interface window or after entry by a user into a user interface window. A default value for the correlation algorithm to execute may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the correlation algorithm may not be selectable. An example correlation algorithm is a Pearson product-moment correlation algorithm, a Spearman rank-order correlation algorithm, an unscaled correlation algorithm, etc. as understood by a person of skill in the art.

In an operation302, a third indicator of a binary threshold used to compute a binary similarity matrix is received. The third indicator indicates a value of the binary threshold. The third indicator may be received by cluster data application122after a selection from a user interface window or after entry by a user into a user interface window. A default value for the binary threshold may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the binary threshold may not be selectable. A value range for the binary threshold may vary depending on the correlation algorithm selected. For example, the value range for the binary threshold using the Pearson product-moment correlation algorithm may be between −1 and 1.

In an operation303, a fourth indicator of a drop percentage is received. The fourth indicator indicates a value of the drop percentage. The drop percentage value is used to randomly select nodes to drop as discussed further below. The fourth indicator may be received by cluster data application122after a selection from a user interface window or after entry by a user into a user interface window. A default value for the drop percentage may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the drop percentage may not be selectable. A value range for the drop percentage may be 0 to 100 though other ranges may be used. For example, instead of a percentage, a decimal value may be defined.

In an operation304, a fifth indicator of a stop criterion used to stop the decorrelated variable selection process is received. The fifth indicator may be received by cluster data application122after a selection from a user interface window or after entry by a user into a user interface window. A default value for the stop criterion may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the stop criterion may not be selectable.

In an operation306, stop criterion input data, if any, is received based on the indicated stop criterion or the defined default stop criterion. For example, a value for a minimum number of variables may be received for the indicated stop criterion as discussed further below. As another example, a desired percentage of variables may be received for the indicated stop criterion as discussed further below.

In an operation308, a correlation matrix is computed using the correlation algorithm indicated in operation300. The correlation matrix includes a correlation value computed between each pair of variables in data matrix124or the subset of variables (columns) indicated in operation200. As understood by a person of skill in the art, the correlation value may be positive or negative. For example, a value of one may indicate a total positive correlation, a value of zero may indicate no correlation, and a value of negative one may indicate a total negative correlation between the pair of variables. In general, the correlation matrix is symmetric, and the diagonal cells are equal to one.

In an operation310, a binary similarity matrix is computed from the correlation matrix using the value of the binary threshold. The correlation value in each cell of the correlation matrix is compared to the value of the binary threshold and a one or a zero is placed in the corresponding cell of the binary similarity matrix. For example, when a positive correlation value is greater than the binary threshold or a negative correlation value is less than the negative of the binary threshold, a one may be placed in the associated cell of the binary similarity matrix indicating sufficient correlation to potentially select. Conversely, when a positive correlation value is less than the binary threshold or a negative correlation value is greater than the negative of the binary threshold, a zero may be placed in the associated cell of the binary similarity matrix. When the correlation matrix is symmetric and the diagonal cells are equal to one, these cells may not need to be compared to the binary threshold.

In an operation312, an undirected graph is defined based on the binary similarity matrix where the correlated variables are connected nodes in the undirected graph. For example, the undirected graph is defined to capture connectivity between variables when the value of the associated cell is one to indicate correlated variables.

For illustration, referring toFIG. 4, a first undirected graph400is shown.FIG. 4provides an example visual representation of an undirected graph though no visual representation is needed as understood by a person of skill in the art. The undirected graph may be a data structure that stores the connectivity information for the variables. First undirected graph400may include a first subgraph402and a second subgraph404. A subgraph is a group of one or more connected nodes. First undirected graph400may include a fewer or a greater number of subgraphs. For example, all of the nodes may be connected such that first undirected graph400includes a single subgraph. First subgraph402may include a first node406and a second node408. Second subgraph404may include a third node410, a fourth node412, a fifth node414, a sixth node416, a seventh node418, an eighth node420, a ninth node422, a tenth node424, and an eleventh node426.

Each node is associated with a variable in the binary similarity matrix. For example, a first variable is associated with first node406, a second variable is associated with second node408, a third variable is associated with third node410, a fourth variable is associated with fourth node412, a fifth variable is associated with fifth node414, a sixth variable is associated with sixth node416, a seventh variable is associated with seventh node418, a eighth variable is associated with eighth node420, a ninth variable is associated with ninth node422, a tenth variable is associated with tenth node424, and an eleventh variable is associated with eleventh node426.

The number shown in each node indicates a connectivity counter value for that node determined based on a number of connections between that variable and other variables based on values in the binary similarity matrix. The connections exist because the binary similarity matrix includes a one (or other predefined value) in the cell between that pair of variables. As an example, the fourth variable associated with fourth node412is sufficiently correlated (e.g., correlation value>binary threshold or correlation value<−binary threshold) with the third variable associated with third node410and with the fifth variable associated with fifth node414to connect these variables in second subgraph404; the fifth variable associated with fifth node414is also sufficiently correlated with the sixth variable associated with sixth node416and with the eighth variable associated with eighth node420to connect these variables in second subgraph404; and so on as indicated in first undirected graph400.

Referring again toFIG. 3, in an operation314, a node is selected from the undirected graph. As an example, any node of the least connected nodes (as indicated by a minimum value of the connectivity counter values) may be selected from the undirected graph. For illustration, and referring again toFIG. 4, the least connected nodes are first node406and second node408of first subgraph402, and third node410, seventh node418, ninth node422, tenth node424, and eleventh node426of second subgraph404. As an example, first node406may be selected. As another example, seventh node418may be selected randomly from third node410, seventh node418, ninth node422, tenth node424, and eleventh node426of second subgraph404.

Referring again toFIG. 3, in an operation316, a determination is made concerning whether or not the selected node is removed. If the selected node is removed, processing continues in an operation318. If the selected node is not removed, processing continues in operation314to select a different node from the least connected nodes remaining in the undirected graph.

For illustration, a random draw value may be determined using a statistical distribution, such as a uniform statistical distribution, as understood by a person of skill in the art. Other statistical distributions may be used and may be user selectable in a process similar to that described with reference to operation300, but for a statistical distribution algorithm. The random draw value is compared to the drop percentage value to determine whether or not a node is removed from a subgraph. A constraint may be that at least one node is kept for each subgraph initially defined in operation312.

In operation318, the selected node is removed from the undirected graph. Assuming that input variables that are highly correlated to other input variables are generally representative of each other, correlation between the input variables is removed while preserving the most representative variables by successively removing the least connected nodes. For example, the drop percentage value is used to remove the least connected nodes from each subgraph.

For illustration, in operation314, first node406may be selected from first subgraph402, and a first random draw value determined in operation316. When the first random draw value is greater than the drop percentage value, first node406is not removed from first subgraph402, and processing continues in operation314. When the first random draw value is less than the drop percentage value, first node406is removed from first subgraph402in operation318. Of course, the less than and greater than tests may be reversed, and the first random draw value equal to the drop percentage value may be designed to trigger either removing or not removing the node.

In an operation320, after removal of the selected node, a determination is made concerning whether or not a stop criterion is satisfied. If the stop criterion is satisfied, processing continues in an operation326. If the stop criterion is not satisfied, processing continues in an operation322.

For example, a stop criterion may test whether or not there is a subgraph in the undirected graph that includes more than one node. The stop criterion may be satisfied when each subgraph includes a single node.

As another example, a stop criterion may test whether or not a number of remaining nodes (variables) in the undirected graph is equal to the minimum number of variables optionally defined in operation306. The stop criterion may be satisfied when the number of remaining nodes equals the minimum number of variables.

As still another example, a stop criterion may test whether or not a percentage of original nodes (variables) in the undirected graph remain. For example, a desired number of remaining variables may be initialized in operation312, after defining the undirected graph, as a percentage of the number of nodes in the undirected graph. The desired percentage of nodes (variables) used to determine the desired number of remaining variables may be optionally defined in operation306. The stop criterion may be satisfied when the number of remaining nodes equals the desired number of remaining variables.

In operation322, a determination is made concerning whether or not the connectivity counters associated with each node in the undirected graph are updated to reflect the removed node. When the connectivity counters are updated, processing continues in an operation324. By updating the connectivity counters, the least connected nodes are redefined. When the connectivity counters are not updated, processing continues in operation314to select a different node from the least connected nodes remaining in the undirected graph. By not updating the connectivity counters, the currently defined least connected nodes remain the same.

In operation324, the connectivity counter values for each node in the undirected graph are updated to reflect lost connectivity between nodes when nodes are removed from the undirected graph in operation318resulting in a new set of least connected nodes. Processing continues in operation314to select a different node from the least connected nodes remaining in the undirected graph.

Referring again toFIG. 4, after testing first node406of first subgraph402and each of third node410, seventh node418, ninth node422, tenth node424, and eleventh node426from second subgraph404for removal, first node406, third node410, and tenth node424may have been selected for removal. For example, third node410may be selected from second subgraph404, and a second random draw value determined. When the second random draw value is less than the drop percentage value, third node410is removed from second subgraph404. Seventh node418may be selected from second subgraph404, and a third random draw value determined. When the third random draw value is greater than the drop percentage value, seventh node418is not removed from second subgraph404. Ninth node422may be selected from second subgraph404, and a fourth random draw value determined. When the fourth random draw value is greater than the drop percentage value, ninth node422is not removed from second subgraph404. Tenth node424may be selected from second subgraph404, and a fifth random draw value determined. When the fifth random draw value is less than the drop percentage value, tenth node424is removed from second subgraph404. Eleventh node426may be selected from second subgraph404, and a sixth random draw value determined. When the sixth random draw value is greater than the drop percentage value, eleventh node426is not removed from second subgraph404.

Referring toFIG. 5, a second undirected graph400ais shown after removing first node406, third node410, and tenth node424and updating the connectivity counter values for each node. Second undirected graph400amay include third subgraph402aand fourth subgraph404a. Third subgraph402amay include second node408. Fourth subgraph404amay include fourth node412, fifth node414, sixth node416, seventh node418, eighth node420, ninth node422, and eleventh node426. Because only second node408of first subgraph402remains in first subgraph402, third subgraph402amay not be processed further, and the second variable associated with second node408may be selected as a decorrelated variable.

Fourth node412, seventh node418, ninth node422, and eleventh node426of fourth subgraph404aare now the least connected nodes from which a node is selected in operation314. Referring toFIG. 6, a third undirected graph400bis shown after removing seventh node418and ninth node422from fourth subgraph404a, based on additional random draw values, and updating the connectivity counter values for each node in third undirected graph400b. Third undirected graph400bmay include third subgraph402aand a fifth subgraph404b. Fifth subgraph404bmay include fourth node412, fifth node414, sixth node416, eighth node420, and eleventh node426.

Fourth node412, sixth node416, and eleventh node426of fifth subgraph404bare now the least connected nodes from which a node is selected in operation314. Referring toFIG. 7, a fourth undirected graph400cis shown after removing fourth node412and eleventh node426from fifth subgraph404b, based on additional random draw values, and updating the connectivity counter values for each node in third undirected graph400b. Fourth undirected graph400cmay include third subgraph402aand a sixth subgraph404c. Sixth subgraph404cmay include fifth node414, sixth node416, and eighth node420.

Sixth node416and eighth node420of sixth subgraph404care now the least connected nodes from which a node is selected in operation314. Referring toFIG. 8, a fifth undirected graph400dis shown after removing sixth node416and eighth node420from sixth subgraph404c, based on additional random draw values, and updating the connectivity counter values for each node in fourth undirected graph400c. Fifth undirected graph400dmay include third subgraph402aand a seventh subgraph404d. Seventh subgraph404dmay include fifth node414. Because only fifth node414remains in seventh subgraph404d, seventh subgraph404dmay not be processed further, and the fifth variable associated with fifth node414may be selected as a decorrelated variable.

Referring again toFIG. 3, in operation326, the remaining nodes in the undirected graph when the stop criterion is satisfied are output as the decorrelated variables. As examples, the decorrelated variables may be stored in computer-readable medium108and/or may be output to the user using display116or printer120. For example, in the illustrative embodiment ofFIG. 8, the second variable associated with second node408and the fifth variable associated with fifth node414are output as the decorrelated variables by storing in computer-readable medium108. Reducing the number of variables decreases an execution time of further processing performed by cluster data application122.

Referring again toFIG. 2, processing may continue in an operation206. In operation206, a number of clusters is determined using the decorrelated variables selected in operation204. As an example, the number of clusters may be determined using a clustering algorithm that automatically determines a number of clusters for the selected correlated variables using data in data matrix124. Referring toFIG. 9, example operations are described that are associated with determining the number of clusters using cluster data application122. The order of presentation of the operations ofFIG. 9is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation900, a sixth indicator is received that indicates data to continue processing. For example, the sixth indicator may indicate a location of data matrix124and the selected decorrelated variables that identify columns in data matrix124. In an alternative embodiment, the sixth indicator may not indicate the selected decorrelated variables and may use all of the variables or variables selected using a different process, such as selection by a user. The sixth indicator may be received by cluster data application122, for example, after selection from a user interface window or after entry by a user into a user interface window. The sixth indicator may include information from the first indicator. The sixth indicator may further indicate that only a portion of the data stored in data matrix124be clustered whether or not the first indicator indicated that only a portion of the data stored in data matrix124be clustered. For example, in a large dataset only a subset of the observations may be used to determine the number of clusters. Sixth indicator may indicate a number of observations to include, a percentage of observations of the entire dataset to include, etc. A subset may be created from data matrix124by sampling.

In an operation902, a seventh indicator of a range of numbers of clusters to evaluate is received. For example, the seventh indicator indicates a minimum number of clusters to evaluate and a maximum number of clusters to evaluate. The seventh indicator may further indicate an increment that is used to define an incremental value for incrementing from the minimum to the maximum number of clusters or vice versa. Of course, the incremental value may be or default to one. The seventh indicator may be received by cluster data application122after selection from a user interface window or after entry by a user into a user interface window. Default values for the range of numbers of clusters to evaluate may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the range of numbers of clusters to evaluate may not be selectable.

In an operation904, an eighth indicator of a number of Monte Carlo iterations to execute for a reference dataset is received. The eighth indicator may be received by cluster data application122after a selection from a user interface window or after entry by a user into a user interface window. A default value for the number of Monte Carlo iterations to execute for generating reference datasets may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the number of Monte Carlo iterations may not be selectable.

In an operation906, a ninth indicator of a clustering algorithm to execute to cluster the data and the reference dataset is received. For example, the ninth indicator indicates a name of a clustering algorithm. The ninth indicator may be received by cluster data application122after selection from a user interface window or after entry by a user into a user interface window. A default value for the clustering algorithm to execute may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the clustering algorithm may not be selectable. Example clustering algorithms include the k-means algorithm, Ward's minimum-variance algorithm, a hierarchical algorithm, a median algorithm, McQuitty's similarity analysis algorithm, or other algorithms based on minimizing the cluster residual sum of squares as understood by a person of skill in the art.

In an operation908, a tenth indicator of a variable selection algorithm to execute to cluster the data and the reference dataset is received. For example, the tenth indicator indicates a name of a statistical distribution algorithm. The tenth indicator may further include values associated with parameters used to define the statistical distribution algorithm. For example, if the statistical distribution algorithm indicated is “Normal Distribution”, the parameter may be a standard deviation and/or a mean. As another example, if the statistical distribution algorithm indicated is “Uniform Distribution”, the parameter may be a probability threshold. The tenth indicator may be received by cluster data application122after selection from a user interface window or after entry by a user into a user interface window. A default value for the statistical distribution algorithm to execute may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the statistical distribution algorithm may not be selectable.

In an operation910, one or more variables are selected from data matrix124using the variable selection algorithm. For example, the one or more variables may be selected from the selected decorrelated variables randomly using the variable selection algorithm. The same or a different number of the one or more variables may be selected for each iteration of operation910. Selecting random subsets from the selected decorrelated variables corresponds to random projections of the data in data matrix124onto multiple subspaces of the original input space. Each subspace is defined by the selected decorrelated variables.

In an operation912, observation data points for the selected one or more variables are selected from data matrix124. The number of the observation data points selected may be all or less than all of the observation data points for the selected one or more variables included in data matrix124due to sampling.

In an operation914, a number of clusters is determined using the selected observation data points for the selected one or more variables. For illustration, the number of clusters is determined using the selected observation data points and clustering in the input space without transforming to another space. As an example, the number of clusters may be determined using example operations described with reference toFIG. 10. The order of presentation of the operations ofFIG. 10is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation1000, a number of clusters is initialized. For example, the number of clusters may be initialized to the minimum number of clusters to evaluate or to the maximum number of clusters to evaluate defined in operation902.

In an operation1002, the clustering algorithm indicated in operation906is executed to cluster the data selected in operation912into the defined number of clusters. The number of clusters may be defined based on the initialized number of clusters defined in operation1000or in an operation1026. The executed clustering algorithm may be selected for execution based on the ninth indicator. The clustering algorithm performs a cluster analysis on the basis of distances that are computed from the selected one or more variables. The selected observation data points are divided into clusters such that each observation belongs to a single cluster. Additionally, the clustering algorithm defines a centroid location for each cluster.

In an operation1004, a first residual sum of squares is computed for the defined clusters as Wk=Σj=1kΣi=1nj∥xi,j−cj∥2, where k is the defined number of clusters, njis a number of data points in cluster j of the defined clusters, xi,jis an ith observation data point in cluster j of the defined clusters, and cjis a centroid location of cluster j of the defined clusters.

In an operation1006, a boundary is defined for each of the clusters defined in operation1004. For example, a minimum value and a maximum value are defined for each dimension of each cluster to define a possibly multi-dimensional box depending on a number of the selected one or more variables defined in operation910.

In an operation1008, a reference distribution is created. The reference distribution includes a new plurality of data points. The new plurality of data points are created within the defined boundary of at least one cluster of the defined clusters. The new data points may be selected based on a uniform distribution within the boundary of each defined cluster. For example, a first plurality of data points are created within the boundary defined for a first cluster of the defined clusters, a second plurality of data points are created within the boundary defined for a second cluster of the defined clusters, a third plurality of data points are created within the boundary defined for a third cluster of the defined clusters, and so on up to the number of clusters created.

In an illustrative embodiment, n*j, a number of data points in cluster j of the reference distribution is selected based on nj, the number of data points in cluster j of the clusters defined in operation1002. For example, n*jmay be proportional to nj. The proportion may be less than one, equal to one, or greater than one. The proportion may be predefined by a user or based on a default value. In another illustrative embodiment, n*jis a predetermined number of data points regardless of the value of nj. The reference distribution data may be created and stored on one or more devices and/or on computer-readable medium108.

In an operation1010, the clustering algorithm indicated in operation906is executed to cluster the reference distribution created in operation1008into the defined number of clusters. The data may be received from one or more devices through communication interface106and/or may be received from storage in computer-readable medium108.

In an operation1012, a second residual sum of squares is computed for the clusters defined using the reference distribution created in operation1008(second clusters) as W*kb=Σj=1kΣi=1n*j∥x*i,j−c*j∥2, where b is an index for a Monte Carlo iteration number, n*jis the number of data points in cluster j of the defined second clusters, x*i,jis the ith observation in cluster j of the defined second clusters, and c*jis the centroid location of cluster j of the defined second clusters.

In an operation1014, a determination is made concerning whether or not another Monte Carlo iteration is to be executed. If another Monte Carlo iteration is to be executed, processing continues in an operation1016. If the number of Monte Carlo iterations indicated by the third indicator has been executed, processing continues in an operation1018. In an alternative embodiment, instead of pre-determining a number of Monte Carlo iterations as the number of repetitions of operations1008,1010, and1012, an evaluation may be made by a user to determine when the results appear satisfactory or stable based on a display of a line or curve showing an average or a dispersion of the number of clusters.

In operation1016, a next random seed is selected for the next Monte Carlo iteration. Processing continues in operation1008to create another reference distribution. Because the data points included in the reference distribution are selected based on sampling within the boundary of each defined cluster, changing the random seed changes the data points included in the next reference distribution. If data transformation device100is multi-threaded, operations1008,1010, and1012may be performed concurrently.

In operation1018, an averaged residual sum of squares is computed for the Monte Carlo iterations as

Wk*=1B⁢∑b=1B⁢log(∑j=1k⁢∑i=1nj*⁢xi,j*-cj*2⁢)⁢⁢or⁢Wk*=1B⁢∑b=1B⁢log⁡(Wkb*),
where B is the number of Monte Carlo iterations or the number of the plurality of times that operation1008is repeated.

In an operation1020, a gap statistic is computed for the defined number of clusters as gap(k)=W*k−log(Wk). In operation1020, a standard deviation is also defined for the defined number of clusters as

sd⁡(k)=[1B⁢∑b=1B⁢(log⁡(Wkb*)-Wk*)2]1/2.
The gap statistic is not a constant when k=1. To avoid this, the gap statistic may be normalized. For example, the gap statistic may be normalized as

Normgap⁡(k)=Wk*W1*-log⁡(WkW1),
which equals zero for k=1. As another example, the gap statistic may be normalized as

Normgap⁡(k)=Wk*-log⁡(Wk)E⁡(Wk*-log⁡(Wk)),
where E(.) is the empirical expectation. As yet another example, the gap statistic may be normalized as Normgap(k)=W*k−log(Wk)−E(W*k−log(Wk)). As still another example, the gap statistic may be normalized as

Normgap⁡(k)=Wk*-log⁡(Wk)-E⁡(Wk*-log⁡(Wk)).std⁡(Wk*-log⁡(Wk)),
where std(.) is the empirical standard deviation.

In an operation1022, the computed gap statistic and the computed standard deviation are stored in association with the defined number of clusters. For example, the computed gap statistic and the computed standard deviation are stored in computer-readable medium108indexed by the defined number of clusters.

In an operation1024, a determination is made concerning whether or not another iteration is to be executed with a next number of clusters. For example, the determination may compare the current defined number of clusters to the minimum number of clusters or the maximum number of clusters to determine if each iteration has been executed as understood by a person of skill in the art. If another iteration is to be executed, processing continues in an operation1026. If each of the iterations has been executed, processing continues in an operation1028.

In operation1026, a next number of clusters is defined by incrementing or decrementing a counter of the number of clusters from the minimum number of clusters or the maximum number of clusters, respectively. Processing continues in operation1002to execute the clustering algorithm with the next number of clusters as the defined number of clusters. If data transformation device100is multi-threaded, operations1002-1026may be performed concurrently.

In operation1028, an estimated best number of clusters for the received data is selected by comparing the gap statistic computed for each iteration of operation1020. Referring toFIG. 22, a plot of a gap statistic value computed as a function of a number of clusters for a sample dataset is shown. A first local maxima for the gap statistic is indicated at a first data point2200. A second local maxima for the gap statistic is indicated at a second data point2202. A third local maxima for the gap statistic is indicated at a third data point2204. First data point2200also has a maximum value for the computed gap statistic.

In an illustrative embodiment, the estimated best number of clusters may be selected as the first local maxima for a number of clusters greater than one. In another illustrative embodiment, the estimated best number of clusters may be selected as the local maxima that has a maximum value for the gap statistic for the number of clusters greater than one. Of course, if the gap statistic is normalized, the gap statistic for k=1 is not a local maxima. In the illustrative embodiment shown inFIG. 22, the estimated best number of clusters is three clusters based on the gap statistic of first data point2200.

In yet another illustrative embodiment, the estimated best number of clusters may be selected as the defined number of clusters associated with a minimum defined number of clusters for which the computed gap statistic for that cluster is greater than the determined error gap of a subsequent cluster. The error gap is the difference between the computed gap statistic and the computed standard deviation as err(k)=gap(k)−sd(k).

In still another illustrative embodiment, a first number of clusters may be determined as the first local maxima for a number of clusters greater than one; a second number of clusters may be determined as the local maxima that has a maximum value for the gap statistic for the number of clusters greater than one; and a third number of clusters may be determined as the defined number of clusters associated with a minimum defined number of clusters for which the computed gap statistic for that cluster is greater than the determined error gap of the subsequent cluster. The estimated best number of clusters may be selected as the determined first number of clusters unless the determined second number of clusters equals the determined third number of clusters in which case the estimated best number of clusters is determined as the determined second number of clusters. Other rules for selecting among the first number of clusters, the second number of clusters, and third number of clusters may be defined.

Referring again toFIG. 9, processing may continue in an operation916. In operation916, cluster data for the determined best number of clusters is output. For example, cluster centroid locations for each of the determined best number of clusters and cluster assignments for the observation data points to the determined best number of clusters may be stored in computer-readable medium108. The cluster centroid locations for each of the determined best number of clusters and cluster assignments for the observation data points to the determined best number of clusters define a set of clusters.

Referring again toFIG. 2, processing may continue in an operation208. In operation208, a determination is made concerning whether or not another determination of the number of clusters is to be performed. If another determination is to be performed, processing continues in operation910to determine another number of clusters. If another determination is not to be performed, processing continues in an operation210. The determination may be based on a pre-defined number of determinations that may be defined similar to the number of Monte Carlo iterations in operation904. 250 determinations may be a default value. In an alternative embodiment, instead of pre-determining a number of determinations, an evaluation may be made by a user to determine when the results appear satisfactory or stable based on a display of a line or curve showing a standard deviation or a dispersion of the number of clusters determined in each iteration of operation910. Instead of an evaluation by a user, an automatic evaluation may be performed. For example, a pre-defined standard deviation threshold may be defined similar to the number of Monte Carlo iterations in operation904. The calculated standard deviation may be compared to the pre-defined standard deviation threshold. When the calculated standard deviation is less than the pre-defined standard deviation threshold, no additional determination of the number of clusters is performed.

In operation210, a number of clusters is selected from the plurality of determinations determined in each performance of operation1028. The selected number of clusters has been cross-validated on random subsets of variables and considering a plurality of clustering solutions resulting in a global best estimate for the number of clusters. For illustration, referring toFIG. 11, a histogram1100showing the determined number of clusters from each execution of operation1028is presented. In the illustrative embodiment ofFIG. 11, operation1028was performed 1000 times though a greater or a fewer number of performances may be performed in alternative embodiments. A maximum histogram value is indicated for eight clusters. If a maximum value is selected, the number of clusters is eight in the illustrative embodiment. Other methods may be used to select the number of clusters from histogram data for the number of clusters. For example, one or more criterion similar to that described in operation1028for selecting the best number of clusters may be used in operation210.

Referring again toFIG. 2, processing may continue in an operation212. In operation212, composite cluster centroid locations are determined to use to cluster observations. There is a different set of cluster centroid locations defined for each iteration of operation1028that resulted in the number of clusters selected in operation210. Composite cluster centroid locations are determined to define a single set of cluster centroid locations. As an example, the composite cluster centroid locations may be determined using example operations described with reference toFIG. 12. The order of presentation of the operations ofFIG. 12is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation1200, cluster data for each iteration of operation1028that resulted in the number of clusters selected in operation210is received. For example, referring toFIG. 11, cluster data is received for the approximately 150 iterations of operation1028that resulted in eight clusters selected as the best number of clusters. For example, the cluster data may be received by reading the data stored in computer-readable medium108in operation916.

In an operation1202, first centroid locations are selected. For example, the centroid locations are selected from the cluster data associated with the first performance of operation1028that resulted in the number of clusters selected in operation210. These centroid locations are selected as the first centroid locations.

In an operation1204, composite centroid locations are initialized with the selected first centroid locations. For example, if the number of clusters selected in operation210is eight, the composite centroid locations will include eight centroid locations.

In an operation1206, next centroid locations are selected. For example, the next centroid locations are selected from the cluster data associated with the next performance of operation1028that resulted in the number of clusters selected in operation210. These centroid locations are selected as the next centroid locations.

In an operation1208, a distance if computed between pairs of the composite centroid locations and the next centroid locations. For example a Euclidian distance may be computed between each pair of the composite centroid locations and the next centroid locations using a Euclidian distance computation algorithm, a Manhattan distance computation algorithm, a Minkowski distance computation algorithm, a Hamming distance computation algorithm, a Jacquard distance computation algorithm, etc. as understood by a person of skill in the art.

In an operation1210, an optimum pairing between the composite centroid locations and the next centroid locations is selected. For example, a pairing associated with a minimum distance may be selected. Each composite centroid location is optimally paired to a single next centroid location. In an operation1212, the composite centroid locations are updated based on the selected optimum pairing.

For illustration, referring toFIG. 13, a first composite centroid location1300, a second composite centroid location1302, a third composite centroid location1304, a first next centroid location1306, a second next centroid location1308, and a third next centroid location1310are shown in accordance with an illustrative embodiment that includes three clusters. In operation1210, the optimum pairing was determined as first composite centroid location1300and first next centroid location1306, second composite centroid location1302and second next centroid location1308, and third composite centroid location1304and third next centroid location1310based on the distance computation. New composite centroid locations for each of first composite centroid location1300, second composite centroid location1302, and third composite centroid location1304are shown, respectively, at a first new centroid location1312, a second new centroid location1314, and a third new centroid location1316. First new centroid location1312, second new centroid location1314, and third new centroid location1316may be computed by averaging coordinate locations between the paired centroid locations. In an alternative embodiment, a weight may be used to compute the new centroid locations. For example, a ratio of a number of observations in each cluster of the paired clusters may be used to determine a weight that is used to adjust the new centroid locations.

Referring again toFIG. 12, in an operation1214, cluster assignments for the observations included in the cluster associated with each centroid location are updated to reflect the composite cluster to which the observation is assigned based on the optimum pairing. For example, cluster assignment for the observations associated with a first cluster having first next centroid location1306are updated to indicate first composite centroid location1300. As an example, an index to the first cluster is changed to a new index associated with the first composite centroid location1300in the cluster data for the iteration of operation1028that resulted in first next centroid location1306; an index to the second cluster is changed to a new index associated with the second composite centroid location1302in the cluster data for the iteration of operation1028that resulted in second next centroid location1308; an index to the third cluster is changed to a new index associated with the third composite centroid location1304in the cluster data for the iteration of operation1028that resulted in third next centroid location1310. In this manner, the cluster assignments for each iteration of operation1028that resulted in the number of clusters selected in operation210are updated to reflect the composite cluster assignment instead.

In an operation1216, a determination is made concerning whether or not another iteration of operation1028resulted in the number of clusters selected in operation210. If another iteration of operation1028did not result in the number of clusters selected in operation210, processing continues in an operation1218. If another iteration of operation1028resulted in the number of clusters selected in operation210, processing continues in operation1206to select the next cluster data and update the composite centroid locations and observation cluster assignments.

For example, referring toFIG. 14, a fourth next centroid location1400, a fifth next centroid location1402, and a sixth next centroid location1404are shown in accordance with an illustrative embodiment. In operation1210, the optimum pairing was determined as first composite centroid location1300and fourth next centroid location1400, second composite centroid location1302and fifth next centroid location1402, and third composite centroid location1304and sixth next centroid location1404based on the distance computation. New composite centroid locations for each of first composite centroid location1300, second composite centroid location1302, and third composite centroid location1304are shown, respectively, at a fourth new centroid location1406, a fifth new centroid location1408, and a sixth new centroid location1410.

In operation1218, data defining the composite centroid locations and cluster assignments is output, for example, to computer-readable medium108.

Referring again toFIG. 2, processing may continue in an operation214. In operation214, observations are assigned to the composite clusters. As an example, the observations are assigned to clusters associated with the composite centroid locations using example operations described with reference toFIG. 15. The order of presentation of the operations ofFIG. 15is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation1500, a first observation to assign to a composite cluster is selected, for example, from data matrix124. All or a subset of the observations stored in data matrix124may be assigned to the composite clusters.

In an operation1501, an eleventh indicator is received that indicates a cluster assignment algorithm. For example, the eleventh indicator indicates a name of a cluster assignment algorithm. The eleventh indicator may be received by cluster data application122after selection from a user interface window or after entry by a user into a user interface window. A default value for the cluster assignment algorithm to execute may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the cluster assignment algorithm may not be selectable.

In an operation1502, a determination is made concerning whether or not a nearest cluster assignment algorithm is used based on the eleventh indicator or default value for the cluster assignment algorithm. If the nearest cluster assignment algorithm is used, processing continues in an operation1504. If the nearest cluster assignment algorithm is not used, processing continues in an operation1508.

In operation1504, a distance is computed between the values of the selected decorrelated variables for the selected observation and each composite centroid location. In an operation1506, the observation is assigned to the composite cluster associated with a minimum distance. Processing continues in an operation1518.

In operation1508, a probability of assigning the observation to each composite cluster is determined. Because the composite cluster assignment was updated in operation1214for each iteration of operation1028that resulted in the number of clusters selected in operation210, a probability of assigning the observation to a specific composite cluster can be determined based on how many times a given observation was placed into the specific composite cluster. For example, if a given observation was placed into a specific composite cluster n times, the probability that the observation belongs to that composite cluster is n/r, where r is the number of iterations of operation1028that resulted in the number of clusters selected in operation210. If the same observation was placed into another composite cluster m times, the probability of the observation belonging to the other composite cluster is m/r. If the same observation was placed into still another composite cluster p times, the probability of the observation belonging to the other composite cluster is p/r. Of course, if the observation was assigned to the same composite cluster each time, the probability is one for that same composite cluster and zero for the remaining composite clusters.

In an operation1510, a determination is made concerning whether or not a probability is one for a specific composite cluster. For example, the probability is one if the assignment was consistently to the same composite cluster. If the probability is one for a specific composite cluster, processing continues in an operation1512. If the probability is not one for a specific composite cluster, processing continues in an operation1514. In operation1512, the observation is assigned to the specific composite cluster having a probability of one.

In operation1514, a random draw value is computed, for example, from a statistical distribution algorithm such as a uniform statistical distribution algorithm. In operation1516, the observation is assigned to a composite cluster having a probability greater than zero based on the random draw value. For example, the probability values may be converted to consecutive values from zero to one by successively adding the computed probability to a previous value and selecting the composite cluster whose probability includes the random draw value. For illustration, Table I below shows the conversion to consecutive values.

If the random draw value is 0.67, the observation is assigned to composite cluster number239because 0.67 is between 0.48 and 0.85.

As an alternative, operations1510,1512,1514, and1516may not be performed. Instead, the observation may be assigned to the composite cluster having a highest probability. As another alternative, the observation is assigned to all of the composite clusters having a probability greater than zero.

In operation1518, a determination is made concerning whether or not there is another observation to process. If there is another observation to process, processing continues in operation1502. If there is not another observation to process, processing continues in optionally one of operations216,220, or224shown with reference toFIG. 2.

Referring again toFIG. 2, in operation216, cluster data126is output that defines each composite cluster of the composite clusters. For each composite cluster, the associated composite centroid location may be output, for example, by storing in computer-readable medium108. Additionally, the selected decorrelated variables may be stored, for example, in computer-readable medium108. Further, a probability of assigning an observation to each composite cluster may be determined and output, for example, by storing in computer-readable medium108. For example, a probability may be calculated for each composite cluster of the composite clusters based on a percentage of the observations assigned to each composite cluster in operation214. Still further, a centroid location of each of the centroid locations assigned to each composite cluster of the composite clusters based on the optimum pairing in operation1210may be output, for example, by storing in computer-readable medium108. Yet further, an observation cluster assignment table may be output, for example, by storing in computer-readable medium108. For example, the observation cluster assignment table may include the probability of assigning the observation to each composite cluster with an index to the observation in data matrix124. As another option, the observation cluster assignment table may be added to data matrix124.

In an operation218, a visualization of the composite clusters may be presented. As an example, the composite clusters may be visualized using example operations described with reference toFIG. 16. The order of presentation of the operations ofFIG. 16is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation1600, a twelfth indicator is received of a number of hidden layers and a number of neurons per layer for a multi-layer neural network. The twelfth indicator may be received by cluster data application122after a selection from a user interface window or after entry by a user into a user interface window. A default value for the number of hidden layers and a number of neurons per layer may further be stored, for example, in computer-readable medium108. For example, a default may be five for the number of hidden layers with the 2nd and 4th layers including half the number of neurons as the 1st and 5th layers. In an alternative embodiment, the number of hidden layers and a number of neurons per layer may not be selectable. Because the hidden units defined by the middle layer of the multi-layer neural network define are used to visualize the composite clusters, the number of neurons in the middle layer typically may be two or three. For example with two neurons in the middle layer, a two-dimensional scatterplot of composite clusters can be used, and with three neurons in the middle layer, a three-dimensional scatterplot of composite clusters can be used.

Referring toFIG. 23, a first neural network2300is shown for illustration. first neural network2300may include a first hidden layer2302, a second hidden layer2304, a middle hidden layer2306, a fourth hidden layer2308, and a fifth hidden layer2310. The number of neurons in each layer are shown in parentheses. For example, as inputs, the number of layers may have been five with a number of neurons per layer defined as 100, 50, and 2. The neurons for the remaining layers may be based on the layers above the middle hidden layer2306in reverse order as understood by a person of skill in the art and illustrated inFIG. 23.

In an operation1602, a thirteenth indicator is received of a statistical distribution algorithm to use to add noise to the data input to the neural network. For example, the thirteenth indicator indicates a name of a statistical distribution algorithm. The thirteenth indicator may be received by cluster data application122after selection from a user interface window or after entry by a user into a user interface window. A default value for the statistical distribution algorithm to execute may further be stored, for example, in computer-readable medium108. In an alternative embodiment, the statistical distribution algorithm may not be selectable.

In an operation1604, any input parameters used by the statistical distribution algorithm may be input. For example, after a user selects a statistical distribution algorithm, cluster data application122may present a user interface window that requests entry by a user of values associated with the input parameters used by the selected statistical distribution algorithm or presents default values for the input parameters used by the selected statistical distribution algorithm.

In an operation1606, noised centroid location data is created from the data defining the composite clusters. For example, noise may be added to the centroid location of each of the centroid locations assigned to each composite cluster of the composite clusters based on the optimum pairing in operation1210by determining a random draw value from the statistical distribution algorithm as understood by a person of skill in the art.

In an operation1608, each hidden layer of the neural network is trained separately as a single-layer neural network in a pretraining step as described, for example, in Hinton et al.,Reducing the Dimensionality of Data with Neural Networks, Science, Vol. 313, Jul. 28, 2006, pp. 504-507. For example, the created noised data is input to the first hidden layer, which is trained to determine a weight(s); the output of the first hidden layer training is input to the second hidden layer, which is trained to determine a weight(s); and so on to the middle layer that has the fewest number of neurons. For example, referring again toFIG. 23, a first weight W1(or vector of weights) may be defined for first hidden layer2302, a second weight W2(or vector of weights) may be defined for second hidden layer2304, a third weight W3(or vector of weights) may be defined for middle hidden layer2306, a fourth weight W4(or vector of weights) may be defined for fourth hidden layer2308, and a fifth weight W4(or vector of weights) may be defined for fifth hidden layer2310in operation1608.

Referring again toFIG. 16, in an operation1610, the weights determined for each hidden layer in operation1608are used to initialize the entire multi-layer neural network. In an operation1612, each hidden layer of the initialized multi-layer neural network is trained simultaneously using the created noised data as input to the first hidden layer. When a large number of inputs are used in conjunction with a much smaller number of hidden units, the features that are extracted as outputs of the middle hidden units are an optimal, nonlinear projection of the training examples onto a lower-dimensional space.

In an operation1614, the output features defining the trained neural network are output. For example, the output features defining the trained neural network may be output by storing the output features in computer-readable medium108.

In an operation1616, a first centroid location is selected. For example, a first centroid location of the centroid locations assigned to the composite clusters may be read from computer-readable medium108.

In an operation1618, the selected centroid location is input to the trained neural network. In an operation1620, a projected centroid location is determined by executing the trained neural network with the selected centroid location. The projected centroid location is the value of the hidden units from the middle hidden layer computed when executing the trained neural network.

In an operation1622, the determined projected centroid location is added to a graph such as a two-dimensional or a three-dimension graph. For example, when two neurons are selected for the middle layer, the centroid location for the members of each composite cluster can be plotted in two dimensions by extracting the features determined by the middle layer of the trained neural network in operation1622. Referring toFIG. 24, six composite clusters, a first composite cluster2400, a second composite cluster2402, a third composite cluster2404, a fourth composite cluster2406, a fifth composite cluster2408, and a sixth composite cluster2410, are shown for illustration with the centroid location for each member of the respective composite cluster plotted using the values of the hidden units from the middle hidden layer. For each centroid location, a first value of the hidden unit for a first neuron of the two neurons is plotted on an x-axis, and a second value of the hidden unit for a second neuron of the two neurons is plotted on a y-axis. Of course, if three neurons are used for the middle layer, a third value of the hidden unit for a third neuron of the three neurons is plotted on a z-axis. The clusters are separate and easily identifiable providing an additional interpretability and visualization of the clusters.

In an operation1624, a determination is made concerning whether or not there is another centroid location to process. For example, each centroid location assigned to the composite clusters may be plotted on the graph. If there is another centroid location to process, processing continues in operation1618with a next selected centroid location. If there is not another observation to process, processing continues in operation220.

Referring again toFIG. 2, in operation220, a fourteenth indicator is received indicating new data to cluster with the composite clusters. For example, the fourteenth indicator indicates a location of a second data matrix. Similar to the first indicator, the fourteenth indicator may further indicate that only a portion of the data stored in the second data matrix be clustered as discussed previously. All or a subset of the observations may be assigned to the composite clusters.

In an operation222, the new observations are assigned to the composite clusters based on the composite centroid locations. As an example, the observations are assigned to clusters associated with the composite centroid locations using example operations described with reference toFIG. 17. The order of presentation of the operations ofFIG. 17is not intended to be limiting, and additional, fewer, or different operations may be performed depending on the embodiment.

In an operation1700, a first observation to assign to a composite cluster is selected, for example, from the second data matrix.

Similar to operation1501, in an operation1701, a fifteenth indicator is received that indicates a cluster assignment algorithm.

Similar to operation1504, in an operation1702, a distance is computed between the values of the selected decorrelated variables for the selected observation and each composite centroid location.

In an operation1704, a determination is made concerning whether or not a nearest neighbors cluster assignment algorithm is used based on the thirteenth indicator or the default value for the cluster assignment algorithm. If the nearest neighbors assignment method is used, processing continues in an operation1708. If the nearest neighbors cluster assignment algorithm is not used, processing continues in an operation1706.

Similar to operation1506, in operation1706, the observation is assigned to the composite cluster associated with a minimum distance. Processing continues in an operation1714.

In operation1708, a probability of assigning the observation to each composite cluster is determined. For example, a probability may be calculated for each composite cluster of the composite clusters based on the percentage of observations assigned to each cluster in operation214. As another option, the probability may be determined by reading the probability data stored in computer-readable medium108in operation216.

In an operation1710, the probability calculated for each composite cluster of the composite clusters is applied as a weight to the distance to each composite cluster computed in operation1702to compute a weighted distance to each composite centroid location.

In an operation1712, the observation is assigned to the composite cluster associated with a minimum weighted distance to the composite centroid location.

Similar to operation1518, in operation1714, a determination is made concerning whether or not there is another observation to process. If there is another observation to process, processing continues in operation1702. If there is not another observation to process, processing continues in operation224.

Referring again toFIG. 2, in operation224, the cluster data determinations for the observations in either of data matrix124or the second data matrix may be used for further exploratory analysis of the data as understood by a person of skill in the art.

Referring toFIG. 18, a block diagram of a cluster determination system1800is shown in accordance with an illustrative embodiment. In an illustrative embodiment, cluster determination system1800may include distributed systems132, data transformation systems1802, distributed control device130, and a network1801. Distributed systems132store distributed data. Data transformation systems1802access data distributed to the distributed systems132. Distributed control device130coordinates and controls access by data transformation systems1802to the data stored by the distributed systems132. One or more components of cluster determination system1800may support multithreading, as understood by a person of skill in the art.

The components of cluster determination system1800may be located in a single room or adjacent rooms, in a single facility, and/or may be distributed geographically from one another. Each of distributed systems132, data transformation systems1802, and distributed control device130may be composed of one or more discrete devices.

Network1801may include one or more networks of the same or different types. Network1801can be any type of wired and/or wireless public or private network including a cellular network, a local area network, a wide area network such as the Internet, etc. Network1801further may comprise sub-networks and include any number of devices.

Data transformation systems1802can include any number and type of computing devices that may be organized into subnets. Data transformation device100is an example computing device of data transformation systems1802. The computing devices of data transformation systems1802send and receive communications through network1801to/from another of the one or more computing devices of data transformation systems1802, to/from distributed systems132, and/or to/from distributed control device130. The one or more computing devices of data transformation systems1802may include computers of any form factor such as a smart phone1804, a desktop1806, a laptop1808, a personal digital assistant, an integrated messaging device, a tablet computer, etc. The one or more computing devices of data transformation systems1802may communicate using various transmission media that may be wired and/or wireless as understood by those skilled in the art.

For illustration,FIG. 18represents distributed systems132with a first server computer1810, a second server computer1812, a third server computer1814, and a fourth server computer1816. Distributed systems132can include any number and form factor of computing devices that may be organized into subnets. The computing devices of distributed systems132send and receive communications through network1801to/from another of the one or more computing devices of distributed systems132, to/from distributed control device130, and/or to/from data transformation systems1802. The one or more computing devices of distributed systems132may communicate using various transmission media that may be wired and/or wireless as understood by those skilled in the art.

In the illustrative embodiment, distributed control device130is represented as a server computing device though distributed control device130may include one or more computing devices of any form factor that may be organized into subnets. Distributed control device130sends and receives communications through network1801to/from distributed systems132and/or to/from data transformation systems1802. Distributed control device130may communicate using various transmission media that may be wired and/or wireless as understood by those skilled in the art.

Cluster determination system1800may be implemented as a grid of computers with each computing device of distributed systems132storing a portion of data matrix124in a cube, as understood by a person of skill in the art. Cluster determination system1800may be implemented as a multi-node Hadoop® cluster, as understood by a person of skill in the art. Cluster determination system1800may use cloud computing technologies, which support on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. Cluster determination system1800may use SAS® High Performance Analytics server. Cluster determination system1800may use the SAS LASR™ Analytic Server to deliver statistical modeling and machine learning capabilities in a highly interactive programming environment, which may enable multiple users to concurrently manage data, transform variables, perform exploratory analysis, and build and compare models. Cluster determination system1800may use SAS In-Memory Statistics for Hadoop® to read big data once and analyze it several times by persisting it in-memory. Some systems may be of other types and configurations.

Referring toFIG. 19, a block diagram of distributed control device130is shown in accordance with an example embodiment. Distributed control device130may include a second input interface1902, a second output interface1904, a second communication interface1906, a second non-transitory computer-readable medium1908, a second processor1910, a distributed control application1912, and second data1914. Fewer, different, and additional components may be incorporated into distributed control device130.

Second input interface1902provides the same or similar functionality as that described with reference to input interface102of data transformation device100though referring to distributed control device130. Second output interface1904provides the same or similar functionality as that described with reference to output interface104of data transformation device100though referring to distributed control device130. Second communication interface1906provides the same or similar functionality as that described with reference to communication interface106of data transformation device100though referring to distributed control device130. Data and messages may be transferred between distributed control device130and distributed systems132and/or data transformation systems1802using second communication interface1906. Second computer-readable medium1908provides the same or similar functionality as that described with reference to computer-readable medium108of data transformation device100though referring to distributed control device130. Second processor1910provides the same or similar functionality as that described with reference to processor110of data transformation device100though referring to distributed control device130.

Distributed control application1912performs operations associated with controlling access to the distributed data, with performing one or more operations described with reference toFIGS. 2,3,9,10,12, and15-17, and/or with instructing distributed systems132to perform one or more operations described with reference toFIGS. 2,3,9,10,12, and15-17.

Some or all of the operations described herein may be embodied in distributed control application1912. The operations may be implemented using hardware, firmware, software, or any combination of these methods. Referring to the example embodiment ofFIG. 19, distributed control application1912is implemented in software (comprised of computer-readable and/or computer-executable instructions) stored in second computer-readable medium1908and accessible by second processor1910for execution of the instructions that embody the operations of distributed control application1912. Distributed control application1912may be written using one or more programming languages, assembly languages, scripting languages, etc. Distributed control application1912may be implemented as a Web application.

Data1914may include data used by distributed control application1912in support of clustering data in data matrix124.

Referring toFIG. 20, a block diagram of a data node device2000is shown in accordance with an illustrative embodiment. Data node device2000is an example computing device of distributed systems132. Data node device2000may include a third input interface2002, a third output interface2004, a third communication interface2006, a third non-transitory computer-readable medium2008, a third processor2010, a local control application2012, and a data subset2014. Fewer, different, and additional components may be incorporated into data node device2000.

Third input interface2002provides the same or similar functionality as that described with reference to input interface102of data transformation device100though referring to data node device2000. Third output interface2004provides the same or similar functionality as that described with reference to output interface104of data transformation device100though referring to data node device2000. Third communication interface2006provides the same or similar functionality as that described with reference to communication interface106of data transformation device100though referring to data node device2000. Data and messages may be transferred between data node device2000and distributed control device130and/or data transformation systems1802using third communication interface2006. Third computer-readable medium2008provides the same or similar functionality as that described with reference to computer-readable medium108of data transformation device100though referring to data node device2000. Third processor2010provides the same or similar functionality as that described with reference to processor110of data transformation device100though referring to data node device2000.

Local control application2012performs operations associated with controlling access to the data stored in data subset2014and/or with executing one or more operations described with reference toFIGS. 2,3,9,10,12, and15-17. Some or all of the operations described herein may be embodied in local control application2012. The operations may be implemented using hardware, firmware, software, or any combination of these methods. Referring to the example embodiment ofFIG. 20, local control application2012is implemented in software (comprised of computer-readable and/or computer-executable instructions) stored in third computer-readable medium2008and accessible by third processor2010for execution of the instructions that embody the operations of local control application2012. Local control application2012may be written using one or more programming languages, assembly languages, scripting languages, etc. Local control application2012may be implemented as a Web application.

Data subset2014stores a portion of the data distributed across distributed systems132with each computing device of the distributed systems132storing a different portion of the data. Distributed control device130further may store a portion of the data.

A user may execute cluster data application122that interacts with distributed control application1912by requesting that distributed control device130perform one or more operations described with reference toFIGS. 2,3,9,10,12, and15-17. Distributed control application1912triggers processing by local control application2012executing at each node device of the distributed systems132to perform one or more operations described with reference toFIGS. 2,3,9,10,12, and15-17. Any number of different users may be accessing the data at any given time.

Various levels of integration between the components of cluster determination system1800may be implemented without limitation as understood by a person of skill in the art. For example, local control application2012and distributed control application1912may be the same or different applications or part of an integrated, distributed application supporting some or all of the same or additional types of functionality as described herein. As another example, cluster data application122and distributed control application1912may be the same or different applications or part of an integrated, distributed application supporting some or all of the same or additional types of functionality as described herein.

The various operations described with reference toFIGS. 2,3,9,10,12, and15-17provide a process for automatically generating interpretable segmentation of raw data. A raw dataset may be cleaned and preprocessed, relevant variables selected, and observations grouped into clusters, all in automatic fashion and in an unsupervised setting that is in the absence of target variables. Example application areas include market segmentation, recommendation systems, monitoring equipment or conditions with sensors, image segmentation, etc.

The word “illustrative” is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as “illustrative” is not necessarily to be construed as preferred or advantageous over other aspects or designs. Further, for the purposes of this disclosure and unless otherwise specified, “a” or “an” means “one or more”. Still further, in the detailed description, using “and” or “or” is intended to include “and/or” unless specifically indicated otherwise. The illustrative embodiments may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to control a computer to implement the disclosed embodiments.

The foregoing description of illustrative embodiments of the disclosed subject matter has been presented for purposes of illustration and of description. It is not intended to be exhaustive or to limit the disclosed subject matter to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the disclosed subject matter. The embodiments were chosen and described in order to explain the principles of the disclosed subject matter and as practical applications of the disclosed subject matter to enable one skilled in the art to utilize the disclosed subject matter in various embodiments and with various modifications as suited to the particular use contemplated.