Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithms]

An unambiguous list of computational steps involved in finding a solution to a class of problems.

13
votes
2answers
10k views

Algebra of LDA. Fisher discrimination power of a variable and Linear Discriminant Analysis

Apparently, the Fisher analysis aims at simultaneously maximising the between-class separation, while minimising the within-class dispersion. A useful measure of the discrimination power of a ...
12
votes
1answer
16k views

Steps done in factor analysis compared to steps done in PCA

I know how to perform PCA (principal component analysis), but I would like to know steps that should be used for factor analysis. To perform PCA, let us consider some matrix $A$, for instance: ...
21
votes
2answers
14k views

Why PCA of data by means of SVD of the data?

This question is about an efficient way to compute principal components. Many texts on linear PCA advocate using singular-value decomposition of the casewise data. That is, if we have data $\bf X$ ...
4
votes
1answer
3k views

Canonical Correlation analysis without raw data (algebra of CCA)

I want to run a Canonical Correlation (in R) but I don't have the original (raw) data. I have only the correlation matrix of all the variables. I have seen some ...
49
votes
6answers
12k views

Efficient online linear regression

I'm analysing some data where I would like to perform ordinary linear regression, however this is not possible as I am dealing with an on-line setting with a continuous stream of input data (which ...
13
votes
8answers
2k views

Testing random variate generation algorithms

Which methods are used for testing random variate generation algorithms?
50
votes
7answers
26k views

Period detection of a generic time series

This post is the continuation of another post related to a generic method for outlier detection in time series. Basically, at this point I'm interested in a robust way to discover the periodicity/...
42
votes
6answers
26k views

What algorithm is used in linear regression?

I usually hear about "ordinary least squares". Is that the most widely used algorithm used for linear regression? Are there reasons to use a different one?
24
votes
7answers
5k views

Algorithm to dynamically monitor quantiles

I want to estimate the quantile of some data. The data are so huge that they can not be accommodated in the memory. And data are not static, new data keep coming. Does anyone know any algorithm to ...
53
votes
7answers
25k views

Best PCA algorithm for huge number of features (>10K)?

I previously asked this on StackOverflow, but it seems like it might be more appropriate here, given that it didn't get any answers on SO. It's kind of at the intersection between statistics and ...
13
votes
1answer
18k views

Generating values from a multivariate Gaussian distribution

I am currently trying to simulate values of a $N$-dimensional random variable $X$ that has a multivariate normal distribution with mean vector $\mu = (\mu_1,...,\mu_N)^T$ and covariance matrix $S$. I ...
21
votes
2answers
6k views

Is it possible to accumulate a set of statistics that describes a large number of samples such that I can then produce a boxplot?

I must clarify immediately that I am a practicing software developer, not a statistician, and that my college stats class was a very long time ago… That said, I would like to know if there is a ...
44
votes
5answers
17k views

Optimized implementations of the Random Forest algorithm

I have noticed that there are a few implementations of random forest such as ALGLIB, Waffles and some R packages like randomForest. Can anybody tell me whether ...
45
votes
10answers
21k views

What is a good algorithm for estimating the median of a huge read-once data set?

I'm looking for a good algorithm (meaning minimal computation, minimal storage requirements) to estimate the median of a data set that is too large to store, such that each value can only be read once ...
33
votes
6answers
4k views

Data mining: How should I go about finding the functional form?

I'm curious about repeatable procedures that can be used to discover the functional form of the function y = f(A, B, C) + error_term where my only input is a set of ...
18
votes
9answers
8k views

Pairwise Mahalanobis distances

I need to calculate the sample Mahalanobis distance in R between every pair of observations in a $n \times p$ matrix of covariates. I need a solution that is efficient, i.e. only $n(n-1)/2$ distances ...
4
votes
1answer
673 views

Algorithm for minimization of sum of squares in regression packages

I'd like to know what technique or techniques are used by regression packages, (in particular the lm function of R) to minimize the sum of squares. Does it use ...
6
votes
3answers
1k views

Can sub-optimality of various hierarchical clustering methods be assessed or ranked?

Classic agglomerative hierarchical clustering methods are based on a greedy algorithm. This means that they (many of them) are prone to give sub-optimal solutions instead of the global optimum result, ...
38
votes
5answers
36k views

What is the difference between the forward-backward and Viterbi algorithms?

I want to know what the differences between the forward-backward algorithm and the Viterbi algorithm for inference in hidden Markov models (HMM) are.
52
votes
9answers
14k views

Measuring entropy/ information/ patterns of a 2d binary matrix

I want to measure the entropy/ information density/ pattern-likeness of a two-dimensional binary matrix. Let me show some pictures for clarification: This display should have a rather high entropy: ...
34
votes
6answers
8k views

Approximate $e$ using Monte Carlo Simulation

I've been looking at Monte Carlo simulation recently, and have been using it to approximate constants such as $\pi$ (circle inside a rectangle, proportionate area). However, I'm unable to think of a ...
22
votes
1answer
23k views

How to define the termination condition for gradient descent?

Actually, I wanted to ask you how can I define the terminating condition for gradient descent. Can I stop it based upon the number of iterations, i.e. considering parameter values for, say, 100 ...
11
votes
2answers
6k views

Do Random Forests exhibit prediction bias?

I think this is a straightforward question, although the reasoning behind why or why not may not be. The reason I ask is that I have recently written my own implementation of a RF and although it ...
15
votes
1answer
14k views

How should decision tree splits be implemented when predicting continuous variables?

I'm actually writing an implementation of Random Forests but I believe the question is specific to decision trees (independent of RFs). So the context is that I'm creating a node in a decision tree ...
7
votes
1answer
4k views

How to calculate ratings/rankings from Paired comparison / Pairwise comparison of large data-sets?

As part of my graduate thesis (area: psychology) I have gathered preference data. The data includes approximately 50000 heads-up comparison between elementX and elementX. I have a total of 15 elements....
3
votes
2answers
32k views

Identify seasonality in time series data [duplicate]

I want to detect presence of seasonality in time series data. I know one can achieve that by plotting the autocorrelation function but I need an automatic process if the series is seasonal or not, ...
16
votes
5answers
4k views

Online algorithm for mean absolute deviation and large data set

I have a little problem that is making me freaking out. I have to write procedure for an online acquisition process of a multivariate time series. At every time interval (for example 1 second), I get ...
11
votes
1answer
6k views

LogLikelihood Parameter Estimation for Linear Gaussian Kalman Filter

I have written some code that can do Kalman filtering (using a number of different Kalman-type filters [Information Filter et al.]) for Linear Gaussian State Space Analysis for an n-dimensional state ...
12
votes
5answers
3k views

Is automated machine learning a dream?

As I discover machine learning I see different interesting techniques such as: automatically tune algorithms with techniques such as grid search, get more ...
12
votes
3answers
8k views

What fast algorithms exist for computing truncated SVD?

Possibly off topic here, but there exist several (one, two) related questions already. Poking around in the literature (or a google search for Truncated SVD Algorithms) turns up a lot of papers that ...
16
votes
2answers
7k views

Which optimization algorithm is used in glm function in R?

One can perform a logit regression in R using such code: ...
8
votes
4answers
1k views

FA: Choosing Rotation matrix, based on “Simple Structure Criteria”

One of the most important issues in using factor analysis is its interpretation. Factor analysis often uses factor rotation to enhance its interpretation. After a satisfactory rotation, the rotated ...
6
votes
1answer
286 views

Minimisation algorithm for a mix of discreet and continuous parameters?

I have a minimisation problem in which the parameters are a mix of integers and scalars. Some of the integers have a small range, around 0-10 but others range in the thousands. To give some context, ...
10
votes
1answer
2k views

Is large scale PCA even possible?

Principal component analysis' (PCA) classical way is to do it on an input data matrix which columns have zero mean (then PCA can "maximize variance"). This can be achieved easily by centering the ...
11
votes
4answers
6k views

How can I (numerically) approximate values for a beta distribution with large alpha & beta

Is there a numerically stable way to calculate values of a beta distribution for large integer alpha, beta (e.g. alpha,beta > 1000000)? Actually, I only need a 99% confidence interval around the mode,...
8
votes
2answers
14k views

Forcing a set of numbers to a gaussian bell-curve

(This relates to my programming question on Stack Overflow: Bell Curve Gaussian Algorithm (Python and/or C#).) On Answers.com, I found this simple example: Find the arithmetic mean (average) => Sum ...
1
vote
1answer
433 views

Relatively normalizing values for collaborative filtering

I am trying to derive a formula for my collaborative algorithm problem to calculate popularity rating of an item. I am considering three factors to calculate rating for an item based on three ...
0
votes
1answer
480 views

Transform sample to achieve target mean, skewness, etc

I have a sample of data with N values from which I calculate basic moments such as mean, standard deviation and skewness. I will then change these moments to different values according to my own rules,...
3
votes
1answer
384 views

Using Covariance Estimator to Perform Linear Regression?

Suppose you had a method for estimating the population covariance of a vector-valued random variable given observations of that random variable, say $f(Z) \rightarrow C$, where the rows of $Z$ are ...
0
votes
2answers
377 views

Customization of a standard Bell Curve

Hopefully this isn't a duplicate, I've tried to search for similar things, but to no luck. I'm curious on how you would computationally compute a random distribution of numbers that follows a bell ...
0
votes
0answers
19 views

Algorithm for creation of groups with cohesion

I don't know if this belongs here, but anyway, here's my doubt. I have a 52x52 matrix with the distances between each pair of 52 points. I want to create an algorithm that classifies them into a ...
26
votes
1answer
17k views

Difference between standard and spherical k-means algorithms

I would like to understand, what is the major implementation difference between standard and spherical k-means clustering algorithms. In each step, k-means computes distances between element vectors ...
18
votes
8answers
15k views

Algorithms to compute the running median?

On smaller window sizes, n log n sorting might work. Are there any better algorithms to achieve this?
17
votes
1answer
6k views

Updating SVD decomposition after adding one new row to the matrix

Suppose that I have a dense matrix $ \textbf{A}$ of $m \times n$ size, with SVD decomposition $$\mathbf{A}=\mathbf{USV}^\top.$$ In R I can calculate the SVD as ...
20
votes
2answers
4k views

How does random forest generate the random forest

I am not an expert of random forest but I clearly understand that the key issue with random forest is the (random) tree generation. Can you explain me how the trees are generated? (i.e. What is the ...
17
votes
1answer
5k views

What are efficient algorithms to compute singular value decomposition (SVD)?

The Wikipedia article on principal component analysis states that Efficient algorithms exist to calculate the SVD of $X$ without having to form the matrix $X^TX$, so computing the SVD is now the ...
10
votes
2answers
7k views

Anomaly detection: what algorithm to use?

Context: I'm developing a system that analyzes clinical data to filter out implausible data that might be typos. What I did so far: To quantify the plausibility, my attempt so far was to normalize ...
11
votes
1answer
7k views

Defining quantiles over a weighted sample

I have a weighted sample, for which I wish to calculate quantiles.1 Ideally, where the weights are equal (whether = 1 or otherwise), the results would be consistent with those of ...
12
votes
3answers
3k views

Can someone please explain the back-propagation algorithm?

What is the back-propagation algorithm and how does it work?
4
votes
3answers
1k views

Looking for sparse and high-dimensional clustering implementation

I'm looking for a clustering implementation with the following features: Support for high-dimensional data. Now I have approximately 160.000 dimensions/features. Be able to manage sparse matrix. That ...