# Tag Info

29

Here is a scatterplot of some multivariate data (in two dimensions): What can we make of it when the axes are left out? Introduce coordinates that are suggested by the data themselves. The origin will be at the centroid of the points (the point of their averages). The first coordinate axis (blue in the next figure) will extend along the "spine" of ...

13

Obviously, k-means needs to be able to compute means. However, there is a well-known variation of it known as k-medoids or PAM (Partitioning Around Medoids), where the medoid is the existing object most central to the cluster. K-medoids only needs the pairwise distances.

11

We can solve this problem analytically using some geometric intuition and arguments. Unfortunately, the answer is quite long and a bit messy. Basic setup First, let's set out some notation. Assume we draw points uniformly at random from the rectangle $[0,a] \times [0,b]$. We assume without loss of generality that $0 < b < a$. Let $(X_1,Y_1)$ be the ...

10

You are exactly describing the problem setting of kernel $k$-means; when you cannot represent a data point as a Euclidean vector, but if you can still calculate (or define) the inner product between two data points then you can kernelize the algorithm. The following webpage provides brief description of the algorithm: Kernel $k$-means page This kernel ...

9

It is plain, from looking at the question geometrically, that the expected distance between two independent, uniform, random points within a convex set is going to be a little less than half its diameter. (It should be less because it's relatively rare for the two points to be located within extreme areas like corners and more often the case they will be ...

8

According to cosine theorem, in euclidean space the (euclidean) squared distance between two points (vectors) 1 and 2 is $d_{12}^2 = h_1^2+h_2^2-2h_1h_2cos\phi$. Squared lengths $h_1^2$ and $h_2^2$ are the sums of squared coordinates of points 1 and 2, respectively (they are the pythagorean hypotenuses). Quantity $h_1h_2cos\phi$ is called scalar product (= ...

6

A couple more recent research on this: M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert and A. Zimek, SSDBM 2010: "Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?" T. Bernecker, M. E. Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert and A. Zimek, SSTD 2011: "Quality of Similarity Rankings in Time Series" Don't remember the others, ...

6

I have tried to collect a few remarks on distance covariance based on my impressions from reading the references listed below. However, I do not consider myself an expert on this topic. Comments, corrections, suggestions, etc. are welcome. The remarks are (strongly) biased towards potential drawbacks, as requested in the original question. As I see it, the ...

5

Given a $n$ by $p$ matrix $\pmb X$ the SVD decomposition of $\pmb X$ is: $$\text{svd}((\pmb X-\bar{x})/\sqrt{n-1})=\pmb{UDV}'$$ (I will denote $\pmb V_k$ the matrix formed of the first $k$ columns of $\pmb V$ and $\pmb D_k$ the diagonal matrix formed of the first $k$ rows and columns of $\pmb D$) The SVD decomposition divides the total variance of $\pmb ... 4 I certainly don't know how it's "normally" done, and for the record, I don't know much about cluster analysis. However, are you familiar with Multidimensional Scaling? (Here's another reference, the wiki, and you could search CV under the multidimensional-scaling tag.) Multidimensional scaling takes in a matrix of pairwise distances, which sounds like ... 4 The distance function is an essential input parameter to any distance- or density based clustering algorithm. Choosing an appropriate distance function is a key step to preparing for data mining. It can be seen as a kind of preprocessing to analyze the various distance functions. And in fact: common data normalization methods - everything that is linear - ... 4 Why do you think there is no way that matrix could be singular? A QR decomposition shows that the rank of this 380 x 372 matrix is just 300. In other words, it is highly singular: url <- "http://mkk.szie.hu/dep/talt/lv/CentInpDuplNoHeader.txt" df <- read.table(file = url, header = FALSE) m <- as.matrix(df) dim(m) # [1] 380 372 qr(m)$rank # [1] ...

3

KL divergence would be natural because you have a natural base distribution, the single Gaussian, from which your mixture diverges. On the the other hand, the KL divergence (or its symmetrical 'distance' form) between two Gaussian mixtures, of which your problem is a special case, seems to be intractable in general. Hershey and Olson (2007) looks like a ...

3

A somewhat complicated answer to your first question about distances goes like this. Rencher's Multivariate Analysis cites Lance and Williams (1967) who proposed a general (flexible beta) method underlying most of the existing hierarchical cluster analysis: for three objects A, B and C, be that clusters or individual points considered to be clusters of size ...

3

Many of the linkage distances are computed on a set of pairwise distances. Then this works just fine with a distance matrix. So most of the time, while the intuition is to have a "handle", what is being done is more a statistical approach. E.g. single-linkage is the minimum distance, and average linkage is the mean distance taken from the submatrix ...

3

The distance between two points from multivariate Gaussian distributions with the same covariance is the Mahalanobis distance. It is more complicated when the covariance matrices are different. The distance between the two means is a positive constant. If you are looking at the distance between the sample mean vectors this is a random variable but not a ...

3

@gung is absolutely correct suggesting you multidimensional scaling (MDS) as a tool to create points X dimensions data out of distance matrix. I'm to add just few strokes. K-means clustering implies euclidean distances. MDS will give you points-in-dimensions coordinates thereby guaranteeing you euclidean distances. You should use metric MDS and request ...

3

Make sure that you do not have an all-0 vector in your data set! Because for this object, the distances will degenerate. I figure you might get either an exception or NaN. Also make sure to not confuse similarity and distance. Similarity will be high for similar objects, a distance would be low. There are two common variants of inverting the cosine ...

3

By the end of the function you take the arccosine of the computed score. Actually, according to the definition (see the Wikipedia page for example) you should not. If you want the dissimilarity, I think you should just do return (1 - sum0 / ( sqrt(sum1) * sqrt(sum2) )); The similarity score will always be within $(-1,1)$, by direct application of the ...

3

A very common solution for this very common problem (ie, over-weighting variables) is to standardize your data. To do this, you just perform two successive column-wise operations on your data: subtract the mean and divide by the standard deviation For instance, in NumPy: >>> # first create a small data matrix comprised of three variables ...

3

Gower dissimilarity is just 1 minus Gower similarity. So, they are "the same", and limitations of one are the limitations of the other. Ward clustering computes cluster centroids and in order for those to be geometrically "real" it demands (squared) euclidean distances as its input. Euclidean distance is metric. Not every metric distance is euclidean. Thus, ...

3

I would suggest you look at metric learning, and then perform k-nn with the learned metric. Here's a Matlab toolkit for it, or a useful talk. If you're providing similar pairs with their distances, then you can learn the metric directly: if not, you can learn it by making an assumption like: the distance between similar pairs is less than the distance ...

3

Be careful when mixing arbitrary distance functions with k-means. K-means does not use Euclidean distance. That is a common misconception. K-means assigns points so that the variance contribution is minimized. I.e. $(x_i - \mu_i)^2$ for all dimensions $i$. But if you sum up all these contributions, you get squared Euclidean distance, and since $\sqrt{}$ is ...

3

Technically to compute a dis(similarity) measure between individuals on nominal attributes most programs first recode each nominal variable into a set of dummy binary variables and then compute some measure for binary variables. There are many measures for binary variables, however, not all of them logically suit dummy binary variables, i.e. former nominal ...

3

I'll try to explain you as simply as possible: Mahalanobis distance measures the distance of a point x from a data distribution. The data distribution is characterized by a mean and the covariance matrix, thus is hypothesized as a multivariate gaussian. It is used in pattern recognition as similarity measure between the pattern (data distribution of ...

3

My grandma cooks. Yours might too. Cooking is a delicious way to teach statistics. Pumpkin Habanero cookies are awesome! Think about how wonderful cinnamon and ginger can be in Christmas treats, then realize how hot they are on their own. The ingredients are: habanero peppers (10, seeded and finely minced) sugar (1.5 cups) butter (1 cup) vanilla ...

3

As a starting point, I would see the Mahalanobis distance as a suitable deformation of the usual Euclidean distance $d(x,y)=\sqrt{\langle x,y \rangle}$ between vectors $x$ and $y$ in $\mathbb R^{n}$. The extra piece of information here is that $x$ and $y$ are actually random vectors, i.e. 2 different realizations of a vector $X$ of random variables, lying ...

3

You are referring to a very hard problem of finding the best possible metric. It is a hard problem even for the unimodal data, the multimodal case you are referring to is a great challenge. There are basically three possibilities: use some primitive metric, like Euclidean distance, treating everything as numbers (you can convert categorical values to some ...

3

There is a close relationship between Euclidean distance and Angular distance. (see also: http://en.wikipedia.org/wiki/Cosine_similarity#Properties) So if you want to take magnitude into account, you may actually be looking for Euclidean distance... Let's look at squared Euclidean, for simplicity:  \sum_i (a_i - b_i)^2 = \sum_i \left(a_i^2 - 2 a_i b_i + ...

2

Sorry I can't help with mclust (I don't know r). What if you run K-mean clustering with some initial centres fixed and some free to move? To fix a centre you simply need to pad it with large amount of points. For example, if there is centre A with known coordinates, to fix it add many (say, a thousand) extra data points, all with these same coordinates, so ...

Only top voted, non community-wiki answers of a minimum length are eligible