2
$\begingroup$

I want to do a simple nearest neighbour calculation in Excel over a multivariate space to get an idea of how my data clusters. I have a set of data points $\{X_1, X_2, \ldots X_n\}$ and a set of possible cluster centers $\{M_1, M_2, \ldots, M_m\}$. Initially, I propose to simply use a weight vector $w$, and compute the scalar product of $w$ and $[X_i - M_j]$ to get the distance of point $i$ to cluster centre $j$. This is all very simple... but completely unwieldy if $n$ and/or $m$ and/or the dimensionality of my data points is large. So is there any (simple) way of hiding all the matrix calculations and producing a (matrix/vector) formula that produces the (scalar) distance without using temporary arrays?

$\endgroup$
6
  • $\begingroup$ In the absence of any elegant alternatives, I have added a worksheet for each cluster centre to hold the temporary calculations. Is this as good as it gets? $\endgroup$
    – omatai
    Jan 8, 2013 at 1:48
  • 2
    $\begingroup$ I strongly suggest getting a statistical package: R or SAS or Stata or whichever you like. That will make all this easier. $\endgroup$
    – Peter Flom
    Jan 8, 2013 at 11:14
  • $\begingroup$ I take your point, but I strongly favour not learning a statistical package at all :-) I favour understanding the limits of Excel, and working within them. From the lack of responses here, I assume that Excel lacks the syntax to do this. For example, to compute a scalar product, it would use SUMPRODUCT([range1],[range2]), where each range specifies a group of cells. There is no option to specify a vector variable that is computed from some other data. So the syntax of Excel forces one to do the calculations "long hand". $\endgroup$
    – omatai
    Jan 8, 2013 at 22:00
  • $\begingroup$ Omatai, Excel does perform (limited) matrix operations. Its native "range" object is a generalization of a matrix. It supports matrix multiplication (MMULT), transposition (TRANSPOSE), and inversion (MINVERSE). You can compute determinants (MDETERM). There are also some not-so-obvious matrix operations available, such as ordinary least squares estimation (LINEST). See the Excel help pages for these functions. Moreover, most scalar functions apply in obvious ways to ranges; e.g., addition of like-sized ranges is matrix addition. $\endgroup$
    – whuber
    Jun 25, 2013 at 14:12
  • $\begingroup$ True - that is what I did, and what I mean by "long hand". You have to string together a bunch of these commands, and put the intermediate results somewhere. Excel simply lacks any notion that a range of cells might represent a vector or matrix independently of the function applied to those cells. It would need this to be able to pass the output of one function to the input of the next function, and hide the temporary results completely. $\endgroup$
    – omatai
    Jul 3, 2013 at 2:35

2 Answers 2

3
$\begingroup$

Excel supports matrix operations.

In this case, do the following:

  • Put the data points in an $n$ by $p$ array where $p$ is the dimensionality of the space. Call this array X.

  • Put the cluster centers in an $m$ by $p$ array and call it M.

  • Put the weights into a $1$ by $p$ array and call it W.

  • Create a range for the $n$ by $m$ calculation. Bound it on the left with the sequence $1,2,\ldots, n$, going down the column. To be concrete, let's suppose this sequence is in cells A2, A3, etc. Bound it above with the sequence $1,2,\ldots, m$. To be concrete, let's suppose this is in cells B1, C1, etc. Thus the upper left corner of the results will in cell B2.

  • Select the top cell in the result array (B2). In the formula bar type

    =MMULT(W, ABS(TRANSPOSE(OFFSET(X, $A2-1, 0, 1) - OFFSET(M, B$1-1, 0, 1))))

and press Enter. Drag this formula throughout the entire array, first to the right across all $m$ cells of the top row, and then after selecting the entire top row, down to include all $n$ rows. Judicious use of "\$" in the formula causes it to update appropriately when dragged. (This illustrates how to compute an outer product in Excel.)

This formula does the following:

  1. OFFSET(X, $A2-1, 0, 1) uses the entries in the left column (column A) to index into the rows of array X.

  2. OFFSET(M, B$1-1, 0, 1) uses the entries in the top row (row 1) to index into the rows of array M.

  3. - subtracts the designated row of M from the designated row of X, yielding a $1$ by $p$ array.

  4. TRANSPOSE converts that result to a $p$ by $1$ array.

  5. MMULT performs the matrix multiplication of the $1$ by $p$ array W by the $p$ by $1$ array computed in the preceding step, producing a $1$ by $1$ array: that is, a number (the distance).

$\endgroup$
3
  • $\begingroup$ +1 an excellent explanation and I think the best way to do it in vanilla Excel, but as a task ... wow what a rigmarole $\endgroup$
    – Glen_b
    Jun 13, 2013 at 6:47
  • 1
    $\begingroup$ @Glen_b I won't defend Excel, but it's interesting to consider what is being done here. In R-speak, these procedures are subsetting and selecting two dataframes, computing a generalized outer product, and performing a matrix multiplication. There is a perfect step-by-step translation between how it would be done in R (in the most efficient, economical way) and how it must be done in Excel. $\endgroup$
    – whuber
    Jun 13, 2013 at 13:13
  • 1
    $\begingroup$ Brilliant! Terrific! I simply had no idea that you could name a set of cells in Excel - I've never encountered it before. I found instructions on how to do it here $\endgroup$
    – omatai
    Jul 12, 2013 at 22:07
0
$\begingroup$

The formula provided by whuber works like a charm. Please notice that the distance formula used is the so called Taxicab distance (or Manhattan distance). If you want the traditional distance you can modify the formula above like that:

=MMULT(W, ABS(TRANSPOSE(OFFSET(X, \$A2-1, 0, 1) - OFFSET(M, B\$1-1, 0, 1))^2))^.5

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.