I want to understand what exactly is curse of dimensionality and how does it effect the model performance. Does the the concept apply to all the models?. Is it equally bad for distance based models like KNN and tree based models like random forest? Curse of Dimensionality: &quot;Consider applying a KNN classifier to data where the inputs are uniformly distributed in the D-dimensional unit cube. Suppose we estimate the density of class labels around a test point x by growing” a hyper-cube around x until it contains a desired fraction f of the data points. The expected edge length of this cube will be eD(f) = f1/D. If D = 10, and we want to base our estimate on 10% of the data, we have e10(0.1) = 0.8, so we need to extend the cube 80% along each dimension around x. Even if we only use 1% of the data, we find e10(0.01) = 0.63. Since the entire range of the data is only 1 along each dimension, we see that the method is no longer very local, despite the name “nearest neighbor”. The trouble with looking at neighbors that are so far away is that they may not be good predictors about the behavior of the input-output function at a given point.&quot; This is the explanation of curse of dimensionality in the Machine learning book by Kevin P. Murphy. However, I only partially understand the concept. Can someone explain it in detail? Thanks in advance!
84428
I read that 'Euclidean distance is not a good distance in high dimensions'. I guess this statement has something to do with the curse of dimensionality, but what exactly? Besides, what is 'high dimensions'? I have been applying hierarchical clustering using Euclidean distance with 100 features. Up to how many features is it 'safe' to use this metric?
113651
I am trying to learn data in higher space into lower space. To have a clue, I'd like to know how to transform the data in the image below into a lower dimension preserving the structure. Hope to hear some explanations and what should I study to learn mapping data to lower dimension?
103042
I'm experimenting with random forests with scikit-learn and I'm getting great results of my training set, but relatively poor results on my test set...  Here is the problem (inspired from poker) which I'm trying to solve: Given player A's hole cards, player B's hole cards and a flop (3 cards), which player has the best hand? Mathematically, this is 14 inputs (7 cards -- one rank and one suit for each) and one output (0 or 1).   Here are some of my results so far:  Training set size: 600k, test set size: 120k, number of trees: 25 Success rate in training set: 99.975% Success rate in testing set: 90.05%  Training set size: 400k, test set size: 80k, number of trees: 100 Success rate in training set: 100% Success rate in testing set: 89.7%  Training set size: 600k, test set size: 120k, number of trees: 5 Success rate in training set: 98.685% Success rate in testing set: 85.69%   Here is the relevant code used:  from sklearn.ensemble import RandomForestClassifier Forest = RandomForestClassifier(n_estimators = 25) #n_estimator varies Forest = Forest.fit(inputs[:trainingSetSize],outputs[:trainingSetSize]) trainingOutputs = Forest.predict(inputs[:trainingSetSize]) testOutputs = Forest.predict(inputs[trainingSetSize:])   It appears that regardless of the number of trees used, performance on training set is  much  better than on test set, despite a relatively large training set and a reasonably small number of features...
105781
The usual implementation of decision trees, and estimators based on ensembles of decision trees, use decision trees that threshold on a single predictor at each split. So they divide the feature space into perpendicular hyperlanes.  Is there any benefit to generalizing this a tiny bit. So at each split, the decision tree uses 2 features, and thresholds based on whether $ax_1 + bx_2 \ge T$. In other words, the feature space is now getting divided into hyperplanes that are not necessarily perpendicular.   I think the main disadvantages would be:    increased computation, and  overfitting since now using more degrees of freedom   I guess to help both of these issues, randomization could be used analogous to extra trees. The pair of features could be randomly selected, instead of exhaustively trying every pair, and the threshold T and parameters a and b could be chosen randomly as well (perhaps from a set of few discrete values such that the hyperplanes could have a few orientations).  Are there some cases where you think these non-perpendicular decision trees would be an improvement over the regular implementation of various decision tree algorithms?
107838
In Decision Trees, when doing classification or regression, do we use only numerical values? Suppose I have a categorical column Wind as a feature. Suppose I am have 5 rows (observations), and the values for Wind are [high,low,high,medium,medium].  Can I feed this categorical data into a decision tree classifier (like scikit-learn), will it take the data? That is, will the splitting of node based on wind happen on categorical values high with count 2, medium with count 2 and low with count 1. Or, will the system converts it into dummy variable?
27718
I have seen somewhere that classical distances (like Euclidean distance) become weakly discriminant when we have multidimensional and sparse data. Why? Do you have an example of two sparse data vectors where the Euclidean distance does not perform well? In this case which similarity should we use?
110157
I'm new to data mining and I'm trying to train a decision tree against a data set which is highly unbalanced. However, I'm having problems with poor predictive accuracy.  The data consists of students studying courses, and the class variable is the course status which has two values - Withdrawn or Current.   Age Ethnicity Gender Course  ... Course Status   In the data set there are many more instances which are Current than Withdrawn. Withdrawn instances only accounting for 2% of the total instances.  I want to be able to build a model which can predict the probability that a person will withdraw in the future. However when testing the model against the training data, the accuracy of the model is terrible.  I've had similar issues with decision trees where the data is dominated by one or two classes.  What approach can I use to solve this problem and build a more accurate classifier?
75064
I'm trying to identify the best model to predict the prices of automobiles, using the prices and features available on automobile classified advertisement sites.  For this I used a couple of models from the scikit-learn library and neural network models from pybrain and neurolab. The approach I used so far is to run a fixed amount of data through some models(machine learning algorithms) and compare there $R^2$ values which was calculated with the scikit-learn metrics module.   Is $R^2$ a good method to compare the performance of different models? Although I got quite acceptable results for models such as Elastic net and Random forests I got very poor $R^2$ values for Neural network models,so is $R^2$ an appropriate method for evaluating neural networks (or non-linear methods)?
59686
I am currently trying to compute the BIC for my toy data set (ofc iris (: ). I want to reproduce the results as shown  (Fig. 5). That paper is also my source for the BIC formulas.  I have 2 problems with this:   Notation:   $n_i$ = number of elements in cluster $i$ $C_i$ = center coordinates of cluster $i$ $x_j$ = data points assigned to cluster $i$ $m$ = number of clusters    1) The variance as defined in Eq. (2):  $$ \sum_i = \frac{1}{n_i-m}\sum_{j=1}^{n_i}\Vert x_j - C_i \Vert^2 $$  As far as I can see it is problematic and not covered that the variance can be negative when there are more clusters $m$ than elements in the cluster. Is this correct?  2) I just cannot make my code work to compute the correct BIC. Hopefully there is no error, but it would be highly appreciated if someone could check. The whole equation can be found in Eq. (5) in the paper. I am using scikit learn for everything right now (to justify the keyword :P ).  from sklearn import cluster from scipy.spatial import distance import sklearn.datasets from sklearn.preprocessing import StandardScaler import matplotlib.pyplot as plt import numpy as np  def compute_bic(kmeans,X):     """     Computes the BIC metric for a given clusters      Parameters:     -----------------------------------------     kmeans:  List of clustering object from scikit learn      X     :  multidimension np array of data points      Returns:     -----------------------------------------     BIC value     """     # assign centers and labels     centers = [kmeans.cluster_centers_]     labels  = kmeans.labels_     #number of clusters     m = kmeans.n_clusters     # size of the clusters     n = np.bincount(labels)     #size of data set     N, d = X.shape      #compute variance for all clusters beforehand     cl_var = [(1.0 / (n[i] - m)) * sum(distance.cdist(X[np.where(labels == i)], [centers[0][i]], 'euclidean')**2)  for i in xrange(m)]      const_term = 0.5 * m * np.log10(N)      BIC = np.sum([n[i] * np.log10(n[i]) -            n[i] * np.log10(N) -          ((n[i] * d) / 2) * np.log10(2*np.pi) -           (n[i] / 2) * np.log10(cl_var[i]) -          ((n[i] - m) / 2) for i in xrange(m)]) - const_term      return(BIC)    # IRIS DATA iris = sklearn.datasets.load_iris() X = iris.data[:, :4]  # extract only the features #Xs = StandardScaler().fit_transform(X) Y = iris.target  ks = range(1,10)  # run 9 times kmeans and save each result in the KMeans object KMeans = [cluster.KMeans(n_clusters = i, init="k-means++").fit(X) for i in ks]  # now run for each cluster the BIC computation BIC = [compute_bic(kmeansi,X) for kmeansi in KMeans]  plt.plot(ks,BIC,'r-o') plt.title("iris data  (cluster vs BIC)") plt.xlabel("# clusters") plt.ylabel("# BIC")   My results for the BIC look like this:     Which is not even close to what I have expected and also makes no sense... I looked at the equations now for some time and am not getting any further locating my mistake ):
47664
When it comes to decision trees, can the predicted value lay outside of the range of the training data?  For example, if the training data set range of the target variable is 0-100, when I generate my model and apply it to something else, can my values be -5?  or 150?  Given that my understanding of decision tree regression is that it is still a rules based - left/right progression and that at the bottom of the tree in the training set it can never see a value outside a certain range, it will never be able to predict it?
118484
I am trying to test how well my unsupervised K-Means clustering properly clusters my data.  I have an unsupervised K-Means clustering model output (as shown in the first photo below) and then I clustered my data using the actual classifications.    The photo below are the actual classifications.  I am trying to test, in Python, how well my K-Means classification (above) did against the actual classification.    For my K-Means code, I am using a simple model, as follows:  kmeans = KMeans(n_clusters=4, random_state=0).fit(myData) labels = kmeans.labels_   What would be the best way for me to compare how well my unsupervised KMeans clustering model did against the actual classifications?
98267
Let $d(\cdot, \cdot)$ be a distance metric on some space (not necessarily Euclidean) $\mathcal{X}$. Is it true that  $$ K(x, y) := \exp(-d(x, y)) $$ always defines a positive definite kernel? If not, are there certain conditions on $d(\cdot, \cdot)$ under which the result is true?
33005
I have been building models with categorical data for a while now and when in this situation I basically default to using scikit-learn's LabelEncoder function to transform this data prior to building a model.  I understand the difference between OHE, LabelEncoder and DictVectorizor in terms of what they are doing to the data, but what is not clear to me is when you might choose to employ one technique over another.    Are there certain algorithms or situations in which one has advantages/disadvantages with respect to the others?
117702
I am new to machine learning and would like to know if it makes sense to fix the number of estimators and the maximal depth of a random forest with cross validation ?  My intuition would be that yes, as cross validation enables one to determine models' hyper parameters. Nevertheless, I think I heard a professor saying that it is illogical to estimate random forests hyperparameters with such procedures... Maybe because the number of estimators would be chosen based on the training data, and then there would be a kind of overfitting as the training and testing datasets are not of the same size, and for instance, having a bigger set size might permit one to consider deeper trees, or maybe averaging on more trees would be necessary to reduce the variance...  What are the other possible ways to determine Random Forests hyper-parameters to use ?  More generally, what are the main model selection procedures in machine learning ?
122277
While implementing Batch Normalization for a particular layer 'L' with 'n' hidden neurons/units in a Neural Network, we first normalize the Activation values of that layer using their respective Mean and Standard Deviation, and then apply the Scaling and Offset factor as shown:     X-norm = (X - mu)/sd X' = (Y * X-norm) + B       where    mu = mean of X and it is a (n,1) vector          sd = standard deviation of X and it is also a (n,1) vector         X = Activation values of layer 'L' with dimension (n,m) if mini-batch    size = m   X-norm = normalized X with dimension (n,m)   Y = Gamma / Scaling factor   B = Beta / Offset factor   Now my question is, what are the dimensions of Gamma and Beta ? Are they (n,1) vectors or are they (n,m) matrices ? My intuition says that since they somewhat are analogous to the Mean and Standard Deviation, they should be (n,1) vectors.
106079
I'm trying to gain an intuition as to why increasing the number of features could reduce performance.  I'm currently using an LDA classifier which performs better bivariately among certain features but worse when looking at more features.  My classification accuracy is performed using a stratified 10-fold xval.    Is there a simple case of when a classifier would work better univariately than bivaraiately to gain a somewhat physical or spatial intuition of what is happening in these higher dimensions?
9746
I am trying to understand the differences between the linear dimensionality reduction methods (e.g., PCA) and the nonlinear ones (e.g., Isomap).  I cannot quite understand what the (non)linearity implies in this context. I read from  that     By comparison, if PCA (a linear dimensionality reduction algorithm) is   used to reduce this same dataset into two dimensions, the resulting   values are not so well organized. This demonstrates that the   high-dimensional vectors (each representing a letter 'A') that sample   this manifold vary in a non-linear manner.   What does     the high-dimensional vectors (each representing a letter 'A') that   sample this manifold vary in a non-linear manner.   mean? Or more broadly, how do I understand the (non)linearity in this context?