Search NASA⌕ Search

SEARCH · Search NASA

Results for “k nearest neighbors algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

Comparison of crisp and fuzzy character networks in handwritten word recognition

Experiments involving handwritten word recognition on words taken from images of handwritten address blocks from the United States Postal Service mailstream are described. The word recognition algorithm relies on the use of neural networks at the character level. The neural networks are trained using crisp and fuzzy desired outputs. The fuzzy outputs were defined using a fuzzy k-nearest neighbor algorithm. The crisp networks slightly outperformed the fuzzy networks at the character level but the fuzzy networks outperformed the crisp networks at the word level.

Gader, Paul↗
NASA NTRSDate not supplied

Aero-Engines AI - A Machine-Learning App for Aircraft Engine Concepts Assessment

Effective deployment of machine-learning (ML) models could drive a high level of efficiency in aircraft engine conceptual design. Aero-Engines AI is a user-friendly app that has been created to deploy trained machine-learning (ML) models to assess aircraft engine concepts. It was created using tkinter, a GUI (graphical user interface) module that is built into the standard Python library. Employing tkinter greatly facilitates the sharing of ML application as an executable file which can be run on Windows machines (without the need to have Python or any library installed). The app gets user input for a turbofan design, preprocesses the input data, and deploys trained ML models to predict turbofan thrust specific fuel consumption (TSFC), engine weight, core size, and turbomachinery stage-counts. The ML predictive models were built by employing supervised deep-learning and K-nearest neighbor regression algorithms to study patterns in an existing open-source database of production and research turbofan engines. They were trained, cross-validated, and tested in Keras, an open-source neural networks API (application programming interface) written in Python, with TensorFlow (Google open-source artificial intelligence library) serving as the backend engine. The smooth deployment of these ML models using the app shows that Aero-Engines AI is an easy-touse and a time-saving tool for aircraft engine design-space exploration during the conceptual design stage. Current version of the app focuses on the performance prediction of conventional turbofans. However, the scope of the app can easily be expanded to include other engine types (such as turboshaft and hybrid-electric systems) after their ML models are developed. Overall, the use of a machine-learning app for aircraft engine concept assessment represents a promising area of development in aircraft engine conceptual design.

machine learning↗
NASA NTRS2023

Aero-Engines AI - A Machine-Learning App for Aircraft Engine Concepts Assessment

Effective deployment of machine-learning (ML) models could drive a high level of efficiency in aircraft engine conceptual design. Aero-Engines AI is a user-friendly app that has been created to deploy trained machine-learning (ML) models to assess aircraft engine concepts. It was created using tkinter, a GUI (graphical user interface) module that is built into the standard Python library. Employing tkinter greatly facilitates the sharing of ML application as an executable file which can be run on Windows machines (without the need to have Python or any library installed). The app gets user input for a turbofan design, preprocesses the input data, and deploys trained ML models to predict turbofan thrust specific fuel consumption (TSFC), engine weight, core size, and turbomachinery stage-counts. The ML predictive models were built by employing supervised deep-learning and K-nearest neighbor regression algorithms to study patterns in an existing open-source database of production and research turbofan engines. They were trained, cross-validated, and tested in Keras, an open-source neural networks API (application programming interface) written in Python, with TensorFlow (Google open-source artificial intelligence library) serving as the backend engine. The smooth deployment of these ML models using the app shows that Aero-Engines AI is an easy-touse and a time-saving tool for aircraft engine design-space exploration during the conceptual design stage. Current version of the app focuses on the performance prediction of conventional turbofans. However, the scope of the app can easily be easily expanded to include other engine types (such as turboshaft and hybrid-electric systems) after their ML models are developed. Overall, the use of a machine-learning app for aircraft engine concept assessment represents a promising area of development in aircraft engine conceptual design.

machine learning↗
NASA NTRS2003

Enhancing and Archiving the APS Catalog of the POSS I

We have worked on two different projects: 1) Archiving the APS Catalog of the POSS I for distribution to NASA's NED at IPAC, SIMBAD in France, and individual astronomers and 2) The automated morphological classification of galaxies. We have completed archiving the Catalog into easily readable binary files. The database together with the software to read it has been distributed on DVD's to the national and international data centers and to individual astronomers. The archived Catalog contains more than 89 million objects in 632 fields in the first epoch Palomar Observatory Sky Survey. Additional image parameters not available in the original on-line version are also included in the archived version. The archived Catalog is also available and can be queried at the APS web site (URL: http://aps.umn.edu) which has been improved with a much faster and more efficient querying system. The Catalog can be downloaded as binary datafiles with the source code for reading it. It is also being integrated into the SkyQuery system which includes the Sloan Digital Sky Survey, 2MASS, and the FIRST radio sky survey. We experimented with different classification algorithms to automate the morphological classification of galaxies. This is an especially difficult problem because there are not only a large number of attributes or parameters and measurement uncertainties, but also the added complication of human disagreement about the adopted types. To solve this problem we used 837 galaxy images from nine POSS I fields at the North Galactic Pole classified by two independent astronomers for which they agree on the morphological types. The initial goal was to separate the galaxies into the three broad classes relevant to issues of large scale structure and galaxy formation and evolution: early (ellipticals and lenticulars), spirals, and late (irregulars) with an accuracy or success rate that rivals the best astronomer classifiers. We also needed to identify a set of parameters derived from the digitized images that separate the galaxies by type. The human eye can easily recognize complicated patterns in images such as spiral arms which can be spotty, blotchy affairs that are difficult for automated techniques. A galaxy image can potentially be described by hundreds of parameters, all of which may have some relation to the morphological type. In the set of initial experiments we used 624 such parameters, in two colors, blue and red. These parameters include the surface brightness and color measured at different radii, ratios of these parameters at different radii, concentration indices, Fourier transforms and wavelet decomposition coefficients. We experimented with three different classes of classification algorithms; decision trees, k-nearest neighbors, and support vector machines (SVM). A range of experiments were conducted and we eventually narrowed the parameters to 23 selected parameters. SVM consistently outperformed the other algorithms with both sets of features. By combining the results from the different algorithms in a weighted scheme we achieved an overall classification success of 86%.

Humphreys, Roberta M.↗
NASA NTRSDate not supplied

Algorithmic Classification of Raman Spectra Biosignatures: Improving Life Detection Confidence

“Agnostic” biosignatures – indicators of life (or the absence of life), independent of a particular biochemistry – are increasingly considered a high standard for life detection. The Ladder of Life Detection (2018) called for investigating how combinations of independent and different potential biosignatures affect confidence. To address this gap, statistical classification of elemental abundances, isotopic fractionation, and reflectance spectroscopy (VNIR) has been implemented. Raman spectroscopy, highly desirable due to its wide availability, has the potential to improve this predictive power. This work implemented biosignature classification algorithms on Raman data alone, in preparation for combination with the other data types. Raman spectroscopy data was collected from published databases and papers as part of a manually curated dataset of “indicative” and “non-indicative of life” samples. These currently include 61 non-indicative samples (meteorites, magnetite); 3 indicative living samples (bacteria); 20 indicative non-living samples (chalk, bone); and 12 indicative mixed (with non-indicative material) samples (soil, microbial mats). Laboratory work is ongoing to characterize additional samples, particularly a greater breadth of mixed systems. Spectra were interpolated, filtered with the Savitzsky-Golay filter, and de-noised. For a preliminary examination, agnostic features were manually extracted including mean intensity, number of peaks, and mean peak width. Different peak prominences and filtering polynomials were used to refine features. Classification algorithms were implemented: k-nearest neighbors (KNN), logistic regression (LR), linear support vector machines (SVM), random forest (RF), Gaussian naïve bayes (GNB). Lastly, Monte Carlo simulations on 1,000 50%-train-test-splits were used to validate classification performance and feature significance. The preliminary feature set achieved its highest AUC of 0.52 with LR, with no strongly discriminatory features. Work to improve feature extraction, such as through deep learning with back propagation, is planned. In future work, the Raman data will be combined with the other data types, and potentially new data types such as enantiomeric excess. This project was partially supported through the NASA Ames Project EXcellence (APEX) incubator program.

Astrobiology↗
NASA NTRS2004

Finite Element Modeling Used to Study Stress Distribution on the Foot

A method to study the stress distribution inside the forefoot during walking was developed at the Cleveland Clinic Foundation by a researcher from the NASA Glenn Research Center. In this method, a semiautomated process was outlined to create a three-dimensional, patient-specific, finite element model (FEM) of the forefoot using magnetic resonance images (MRI). The images were processed in Matlab using the k-nearest neighbor (k-NN) classification algorithm and Sobel edge detection to separate the different tissue types: bone, skin, fat, and muscle. This information was used to create curves and surfaces that were exported to an FEM preprocessor known as Truegrid. In Truegrid, eight-noded or brick elements were created by using surface mapping. The FEM was processed and postprocessed in Abaqus. Material properties of the models were obtained from past experiments such as fat pad confined compression, skin axial and biaxial tests, muscle in vivo compressive tests, and reference literature (bone properties). Nonlinear (hyperelastic) material models were used for the skin (epidermis and dermis), fat, and muscles; and a linear elastic model was used for the bones. Muscle activation during walking yielded uncertainties in the muscle material model since contracted muscles are stiffer than relaxed muscles. These uncertainties were resolved by performing a sensitivity analysis of the muscle material properties. The original properties were multiplied by arbitrary factors of 2, 3, 0.5, and 0.33. The strain and stress distributions, as well as the locations of peak values, were similar in all cases. The peak contact pressure P obtained for each case varied with respect to the applied factor f as follows:

Morales, Nelson↗
NASA NTRS2021

Passive Microwave Signatures and Retrieval of High-Latitude Snowfall Over Open Oceans and Sea Ice: Insights From Coincidences of GPM and CloudSat Satellites

This article studies changes in microwave signals of oceanic snowfall in response to the formation of snow-covered sea ice using active and passive coincident data from the radar and radiometer onboard the CloudSat and the global precipitation measurement satellites. Using reanalysis data of liquid and ice water path as well as satellite retrievals of sea ice snow-cover depth, spectral regions are determined over which the snowfall signatures are likely to be obscured or falsely detected. Relying on an a priori database populated with the active–passive coincidences, a Bayesian snowfall retrieval algorithm is presented that links a k -nearest neighbor matching with the inverse Gaussian estimator used in the Goddard profiling algorithm. Without relying on any ancillary data of air temperature, the results demonstrate that over open oceans (sea ice), we can passively retrieve the CloudSat active snowfalls with a true positive rate of 92 (85%) and the root mean squared error of 0.24 (0.15) mm per h.

Sajad Vahedizade↗
NASA NTRS2003

A Fast Implementation of the ISOCLUS Algorithm

Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in d-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called k-means. One significant feature of ISOCLUS over k-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge lor split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing .interest in the remote sensing community in computing it efficiently. We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm of Kanungo, et al. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for k-means. Both the k-means and ISOCLUS algorithms are based on iterative schemes, in which nearest neighbors are calculated until some convergence criterion is satisfied. Each iteration requires that the nearest center for each data point be computed. Naively, this requires O(kn) time, where k denotes the current number of centers. Traditional techniques for accelerating nearest neighbor searching involve storing the k centers in a data structure. However, because of the iterative nature of the algorithm, this data structure would need to be rebuilt with each new iteration. Our approach is to store the data points in a kd-tree data structure. The assignment of points to nearest neighbors is carried out by a filtering process, which successively eliminates centers that can not possibly be the nearest neighbor for a given region of space. This algorithm is significantly faster, because large groups of data points can be assigned to their nearest center in a single operation. Preliminary results on a number of real Landsat datasets show that our revised ISOCLUS-like scheme runs about twice as fast.

Memarsadeghi, Nargess↗
NASA NTRS2011

Pattern Recognition for a Flight Dynamics Monte Carlo Simulation

The design, analysis, and verification and validation of a spacecraft relies heavily on Monte Carlo simulations. Modern computational techniques are able to generate large amounts of Monte Carlo data but flight dynamics engineers lack the time and resources to analyze it all. The growing amounts of data combined with the diminished available time of engineers motivates the need to automate the analysis process. Pattern recognition algorithms are an innovative way of analyzing flight dynamics data efficiently. They can search large data sets for specific patterns and highlight critical variables so analysts can focus their analysis efforts. This work combines a few tractable pattern recognition algorithms with basic flight dynamics concepts to build a practical analysis tool for Monte Carlo simulations. Current results show that this tool can quickly and automatically identify individual design parameters, and most importantly, specific combinations of parameters that should be avoided in order to prevent specific system failures. The current version uses a kernel density estimation algorithm and a sequential feature selection algorithm combined with a k-nearest neighbor classifier to find and rank important design parameters. This provides an increased level of confidence in the analysis and saves a significant amount of time.

Restrepo, Carolina↗
NASA NTRS2018

Using Machine-Learning Methods and Expert Prediction Probabilities to Forecast Solar Flares

It has long been known that studying connection between solar flares and properties of magnetic field in active regions is very important for understanding the flare physics and developing space weather forecasts. The Helioseismic and Magnetic Imager onboard the Solar Dynamics Observatory (SDO/HMI) obtains tremendous amounts of magnetic field data products. However the operational NOAA Space Weather Prediction Center (SWPC) forecasts of solar flares still represent prediction probabilities issued by the experts. In this research we investigate the possibilities to enhance the daily operational flare forecasts performed at the SWPC by developing a synergy of the expert predictions and physics-based criteria, and by employing machine-learning methods. Among the physics-based criteria we consider the descriptors of the Polarity Inversion Line (PIL) and Space weather HMI Active Region Patches (SHARP), and derive from them daily characteristics of the entire Sun. We also consider the daily descriptors of the GOES Soft X-Ray (SXR) 1-8 Angstroms flux such as the flare history of the previous days and averaged X-Ray flux. We estimate the effectiveness in separation of flaring and non-flaring cases for each characteristic, as well as for the expert prediction probabilities, and find that some PIL, SHARP and SXR descriptors are as effective as the expert prediction probabilities and should be considered to issue the flare forecast. Finally, we train and test several Machine-Learning classification algorithms (Support Vector Classifiers with various kernel functions, k-Nearest Neighbor Classifier, Random Forest Classifier, and Neural Networks) using the most effective descriptors and expert prediction probabilities, and compare the obtained predictions with the current SWPC forecasts.

Machine-Learning↗
NASA NTRS2022

Landslide Likelihood Prediction using Machine Learning Algorithms

The supply of electricity via power plants is criticalto the operation of many critical infrastructure systems in mod-ern society. Natural hazards can disrupt the power supply, causepower outages that can halt economic growth, and impede emer-gency response until power is restored. The proposed work aimsto predict the landslides likelihood in these critical infrastructurelocations in the Northeastern USA using integrated databases ofexplanatory variables and machine learning algorithms. First,data related to landslides are obtained and merged, includingtopographic, soil moisture, and precipitation-related data. Fiveregression algorithms, namely: Random Forest, Extreme Gradi-ent Boosting (XGBoost), K-Nearest Neighbor regression (KNN),Linear Support Vector Regressor (SVR), and Linear regression,are utilized to predict the landslide probability and evaluatedon the dataset. The accuracy of the models is assessed by usingstatistical metrics such as mean absolute error (MAE), meansquared error (MSE), and root mean squared error (RMSE).The study results show that Random Forest outperformed othermodels with the mutual information feature selection method.It achieved an MSE of 0.0011 with mutual information-basedfeature selection and an MSE of 0.00157 without feature selection.KNN regressor outperformed the other models with an MSEof 0.00139 with correlation-based information selection. Theproposed landslide identification model with Random Forestalgorithm shows outstanding robustness and great potential intackling the landslide likelihood prediction by employing MLalgorithms.

Vasundhara Acharya↗
NASA NTRS2018

Generating Exploration Mission-3 Trajectories to a 9:2 NRHO using Machine Learning

The purpose of this thesis is to design a machine learning algorithm platform that provides expanded knowledge of mission availability through a launch season by improving trajectory resolution and introducing launch mission forecasting. The specific scenario addressed in this paper is one in which data is provided for four deterministic translational maneuvers through a mission to a Near Rectilinear Halo Orbit (NRHO) with a 9:2 synodic frequency. Current launch availability knowledge under NASA's Orion Orbit Performance Team is established by altering optimization variables associated to given reference launch epochs. This current method can bean abstract task and relies on an orbit analyst to structure a mission based on an established mission design methodology associated to the performance of Orion and NASA's Space Launch System. Introducing a machine learning algorithm trained to construct mission scenarios within the feasible range of known trajectories reduces the required interaction of the orbit analyst by removing the needed step of optimizing the orbit to fit an expected translational response required of the spacecraft. In this study, k-Nearest Neighbor and Bayesian Linear Regression successfully predicted classical orbital elements for the launch windows observed. However both algorithms had limitations due to their approaches to model fitting. Training machine learning algorithms off of classical orbital elements introduced a repetitive approach to reconstructing mission segments for different arrival opportunities through the launch window and can prove to be a viable method of launch window scan generation for future missions.

Guzman, Esteban↗
NASA NTRS2004

Fast Query-Optimized Kernel-Machine Classification

A recently developed algorithm performs kernel-machine classification via incremental approximate nearest support vectors. The algorithm implements support-vector machines (SVMs) at speeds 10 to 100 times those attainable by use of conventional SVM algorithms. The algorithm offers potential benefits for classification of images, recognition of speech, recognition of handwriting, and diverse other applications in which there are requirements to discern patterns in large sets of data. SVMs constitute a subset of kernel machines (KMs), which have become popular as models for machine learning and, more specifically, for automated classification of input data on the basis of labeled training data. While similar in many ways to k-nearest-neighbors (k-NN) models and artificial neural networks (ANNs), SVMs tend to be more accurate. Using representations that scale only linearly in the numbers of training examples, while exploring nonlinear (kernelized) feature spaces that are exponentially larger than the original input dimensionality, KMs elegantly and practically overcome the classic curse of dimensionality. However, the price that one must pay for the power of KMs is that query-time complexity scales linearly with the number of training examples, making KMs often orders of magnitude more computationally expensive than are ANNs, decision trees, and other popular machine learning alternatives. The present algorithm treats an SVM classifier as a special form of a k-NN. The algorithm is based partly on an empirical observation that one can often achieve the same classification as that of an exact KM by using only small fraction of the nearest support vectors (SVs) of a query. The exact KM output is a weighted sum over the kernel values between the query and the SVs. In this algorithm, the KM output is approximated with a k-NN classifier, the output of which is a weighted sum only over the kernel values involving k selected SVs. Before query time, there are gathered statistics about how misleading the output of the k-NN model can be, relative to the outputs of the exact KM for a representative set of examples, for each possible k from 1 to the total number of SVs. From these statistics, there are derived upper and lower thresholds for each step k. These thresholds identify output levels for which the particular variant of the k-NN model already leans so strongly positively or negatively that a reversal in sign is unlikely, given the weaker SV neighbors still remaining. At query time, the partial output of each query is incrementally updated, stopping as soon as it exceeds the predetermined statistical thresholds of the current step. For an easy query, stopping can occur as early as step k = 1. For more difficult queries, stopping might not occur until nearly all SVs are touched. A key empirical observation is that this approach can tolerate very approximate nearest-neighbor orderings. In experiments, SVs and queries were projected to a subspace comprising the top few principal- component dimensions and neighbor orderings were computed in that subspace. This approach ensured that the overhead of the nearest-neighbor computations was insignificant, relative to that of the exact KM computation.

Mazzoni, Dominic↗
NASA NTRS2019

ASCot, the NASA Analogy Software Cost Tool Suite: expanding our estimation horizons

The NASA Analogy Software Costing Tool Suite (ASCoT) consists of a cluster-based analogy estimator for estimating software development effort, a K-Nearest Neighbors (KNN) analogy estimator for estimating effort and delivered lines of code, a simple regression-based cost estimating relationship (CER) model that estimates cost in dollars, and a probabilistic version of COCOMO II. In this paper we document the analogy algorithms as well as summarize the results of the performance of the KNN and the principle components (PCA) cluster analogy models. KNN performance is assessed by varying the number of inputs and number of neighbors. Four different clustering methods: K-means, Spectral Clustering, Hierarchical Clustering, and Principle Components Analysis (PCA), and their respective evaluation criterion are described in detail. The comparative performance of all four estimation models is assessed using magnitude of relative error (MRE) measurements.

Menzies, Tim↗
NASA NTRS1990

A neural network approach to cloud classification

It is shown that, using high-spatial-resolution data, very high cloud classification accuracies can be obtained with a neural network approach. A texture-based neural network classifier using only single-channel visible Landsat MSS imagery achieves an overall cloud identification accuracy of 93 percent. Cirrus can be distinguished from boundary layer cloudiness with an accuracy of 96 percent, without the use of an infrared channel. Stratocumulus is retrieved with an accuracy of 92 percent, cumulus at 90 percent. The use of the neural network does not improve cirrus classification accuracy. Rather, its main effect is in the improved separation between stratocumulus and cumulus cloudiness. While most cloud classification algorithms rely on linear parametric schemes, the present study is based on a nonlinear, nonparametric four-layer neural network approach. A three-layer neural network architecture, the nonparametric K-nearest neighbor approach, and the linear stepwise discriminant analysis procedure are compared. A significant finding is that significantly higher accuracies are attained with the nonparametric approaches using only 20 percent of the database as training data, compared to 67 percent of the database in the linear approach.

Lee, Jonathan↗
NASA NTRS1989

A class of parallel algorithms for computation of the manipulator inertia matrix

Parallel and parallel/pipeline algorithms for computation of the manipulator inertia matrix are presented. An algorithm based on composite rigid-body spatial inertia method, which provides better features for parallelization, is used for the computation of the inertia matrix. Two parallel algorithms are developed which achieve the time lower bound in computation. Also described is the mapping of these algorithms with topological variation on a two-dimensional processor array, with nearest-neighbor connection, and with cardinality variation on a linear processor array. An efficient parallel/pipeline algorithm for the linear array was also developed, but at significantly higher efficiency.

Fijany, Amir↗
NASA NTRS1984

Augmenting computer networks

Three methods of augmenting computer networks by adding at most one link per processor are discussed: (1) A tree of N nodes may be augmented such that the resulting graph has diameter no greater than 4log sub 2((N+2)/3)-2. Thi O(N(3)) algorithm can be applied to any spanning tree of a connected graph to reduce the diameter of that graph to O(log N); (2) Given a binary tree T and a chain C of N nodes each, C may be augmented to produce C so that T is a subgraph of C. This algorithm is O(N) and may be used to produce augmented chains or rings that have diameter no greater than 2log sub 2((N+2)/3) and are planar; (3) Any rectangular two-dimensional 4 (8) nearest neighbor array of size N = 2(k) may be augmented so that it can emulate a single step shuffle-exchange network of size N/2 in 3(t) time steps.

Bokhari, S. H.↗
NASA NTRS1972

Nearest Neighbor Algorithms for Pattern Classification

A solution of the discrimination problem is considered by means of the minimum distance classifier, commonly referred to as the nearest neighbor (NN) rule. The NN rule is nonparametric, or distribution free, in the sense that it does not depend on any assumptions about the underlying statistics for its application. The k-NN rule is a procedure that assigns an observation vector z to a category F if most of the k nearby observations x sub i are elements of F. The condensed nearest neighbor (CNN) rule may be used to reduce the size of the training set required categorize The Bayes risk serves merely as a reference-the limit of excellence beyond which it is not possible to go. The NN rule is bounded below by the Bayes risk and above by twice the Bayes risk.

Barrios, J. O.↗