Scientific Method / Science & Exploration

New algorithm classifies everything from gene data to POTUS speeches

Accurately determines whether a State of the Union is pre- or post-Reagan.

After eight years of Reagan, State of the Union speeches were permanently changed.

The last few decades have seen an explosion of data in fields such as biology, medicine, and genomics. Some of the methods used to analyze these large data sets are outdated and in need of an update, but scaling up data analysis methods creates its own hurdles, such as limits in computational power and the manpower needed to follow up on findings. Now, some researchers are combining techniques from machine learning and statistics to develop algorithms capable of mining large data sets without the need for human supervision.

One such algorithm, recently presented in PNAS, uses an integrated procedure that cross-validates the system’s initial results to find features in large, high-dimensional, noisy data. The algorithm is called KODAMA (short for “knowledge discovery by accuracy maximization”) and uses a hybrid of semi-supervised and unsupervised learning tactics to reveal features within large data sets as different as gene expression and presidential speeches.

The algorithm consists of five steps, one of which is iterative, to maximize the accuracy of the predicted results. During the first step, data is assigned to a class defined by the user. The assignments are then cross validated using a 10-fold procedure using supervised classifiers such as k-Nearest Neighbor (kNN) or Support Vector Machines (SVM). The results from this cross-validation are quantified using a global accuracy value, which is the sum of the number of correctly classified samples divided by the total number of samples. This step is repeated until the global accuracy reaches 100 percent or a user-specified limit on the number of iterations.

The pruned and classified data is then used to generate a proximity matrix. A proximity matrix is a square matrix that provides a measure of the similarity (or distance) between two elements based on the cell's row and column—the smaller the value in the cell, the closer together these two elements will be. This step is repeated to optimize the distances between elements in the data set. All the proximity matrices are then averaged to generate a final proximity matrix for the data. Visualization of the average proximity matrix thus provides clues on how the data is distributed.

By minimizing the distances and iteratively optimizing the results at each step, the algorithm is able to avoid the issues experienced by some conventional algorithms, such as PCA, which defines the space of the data set to be linear or to have limited degrees of freedom. This allows KODAMA to extract information from large data sets without attenuating a high number of dimensions.

The algorithm’s efficiency was tested on experimental data sets of gene expression and metabolomics. In these cases, KODAMA compared favorably with existing methods of feature extraction from large data sets. The algorithm was also used to extract unintuitive features, such as changes in linguistic transitions. The researchers tested it on State of the Union speeches, and it was able to classify a speech as having occurred either post-Reagan or pre-Reagan.

Analysis of high-dimensional and noisy data sets demonstrates the robustness and efficiency of KODAMA to extract unique features from large data sets. More information about the algorithm can be found at

PNAS, 2014. DOI: 10.1073/pnas.1220873111  (About DOIs).

Expand full story

You must to comment.