Data Mining

Computing binary item similarity is not simply a matter of counting the number of a’s and d’s in the table above. For example, we may want to weight 1-1 (or “a”) matches greater than 0-0 (or “d”) matches or compute various ratios of matches to mismatches. Richard A. Johnson & Dean W. Wichern (2002) have compiled a list of weighting schemes for binary item similarity which is reproduced below with minor changes (note that p=a+b+c+d):

If we wanted to create a class that calculated binary item similarity according to these different weighting schemes then the class skeleton might look like this: <?php /** * Class to compute binary item similarity according to * eight different weighting schemes */ class BinaryItemSimilarity { // store the contingency table so all // methods can access it var $ContingencyTable = array(); // instantiate class with contingency table values function BinaryItemSimilarity($ContingencyTable) {); function useEqualWeightForMatches() {); function useDoubleWeightForMatches() {); function useDoubleWeightForNonMatches() {); function useNoZeroMatchesInNumerator() {); function useNoZeroMatches() {); function useNoZeroMatchesWithDoubleWeightMatches() {); function useNoZeroMatchesWithDoubleWeightNonMatches() {); function useRatioOfMatchesToNonMatchesExcludingZeroMatches() {); } ?> Exercises 1. Complete the implementation of the BinaryItemSimilarity class. 2. Do you think the API for this class is too verbose? Is a self-documenting API a good thing even when method names get this long? 3. Are there alternate names for these weighting schemes? Would it be better to use these names instead of these long method names? Permalink

1.00001 == 1.0 ? false
1.00001 > 1.0 ? true
1.00001 >= 1.0 ? true
1.00001 < 1.0 ? false
1.00001 <= 1.0 ? false
==================
1.000001 == 1.0 ? true
1.000001 > 1.0 ? false
1.000001 >= 1.0 ? true
1.000001 < 1.0 ? false
1.000001 <= 1.0 ? true

Exercise If you were developing a data mining/machine learning library, do you think it would be a good idea to rely upon PHP’s native comparison functions or would you use the above comparison functions?

array(count(no/no), count(no/yes), count(yes/no), count(yes/yes));

or a two dimensional array (use the kappa2 function below):

array(
 array(count(no/no), count(no/yes)),
 array(count(yes/no), count(yes/yes))
);

<?php /** * Compute kappa for a 2x2 table. * * An index which compares the agreement against that which might be * expected by chance. Possible values range from +1 (perfect agreement) * to 0 (no agreement above that expected by chance) to -1 (complete * disagreement). * * @see http://www.dmi.columbia.edu/homepages/chuangj/kappa/ * * @param $table2x2 array of interrater no/yes agreements/disagreements * * @return $kappa statistic */ function kappa2($table2x2) { $row1 = $table2x2[0][0] + $table2x2[0][1]; $row2 = $table2x2[1][0] + $table2x2[1][1]; $col1 = $table2x2[0][0] + $table2x2[1][0]; $col2 = $table2x2[0][1] + $table2x2[1][1]; $n = $col1+$col2; $pObserved = ($table2x2[0][0] + $table2x2[1][1]) / $n; $pExpected = (($col1 * $row1) + ($col2 * $row2)) / ($n*$n); $kappa = ($pObserved - $pExpected) / (1 - $pExpected); return $kappa; } /* * @see http://bij.isi.uu.nl/ImageJ/api/index.html {BIJStats.java} */ function kappa1($table) { $g1 = $table[0] + $table[1]; $g2 = $table[2] + $table[3]; $f1 = $table[0] + $table[2]; $f2 = $table[1] + $table[3]; $n = $f1+$f2; $pObserved = ($table[0] + $table[3]) / $n; $pExpected = (($f1 * $g1) + ($f2 * $g2)) / ($n*$n); $kappa = ($pObserved - $pExpected) / (1 - $pExpected); return $kappa; } $table2x2 = array( array(10, 7), array(0, 12) ); echo kappa2($table2x2); ?> The example values input and output by this script were taken from this discussion of the kappa statistic. There are two reasons why I am particularly interested in the kappa statistic: 1. The kappa statistic is a close cousin of the chi square statistic which I have written about on numerious occasions and developed math packages for. I have seen the kappa statistic used alongside the chi square statistic to provide additional insight into tables of categorical count data. 2. An important aspect of the concept of “Collaborative Filtering” is the idea of “interrater reliability” – developing operational defintions of what it means to agree or disagree in your assessment of some object attribute. The kappa statistic is a good place to begin one’s exploration of the mathematics of collaborative filtering. Exercise Generalize the algorithm for computing a “kappa” score so that it can be used on 3×3 tables and nxn tables.

1. d(x, y) >= 0 (non-negativity)
2. d(x, y) = 0 if and only if x = y (identity)
3. d(x, y) = d(y, x) (symmetry)
4. d(x, z) <= d(x, y) + d(y, z) (triangle inequality)

The Minkowski vector distance metric (i.e., minkowski($exp)) is a generalization of the Euclidean and Cityblock vector distance metrics achieved by passing in an “exponent” term (i.e., $exp). Here is the code used to compute these 3 vector distance metrics: <?php function euclidean() { $sum = 0.0; for($i=0; $i<$this->n; $i++) $sum += pow($this->X[$i]-$this->Y[$i], 2); return sqrt($sum); } function cityblock() { $sum = 0.0; for($i=0; $i<$this->n; $i++) $sum += abs($this->X[$i]-$this->Y[$i]); return $sum; } function minkowski($exp) { $sum = 0.0; for($i=0; $i<$this->n; $i++) $sum += pow(abs($this->X[$i]-$this->Y[$i]), $exp); return pow($sum, 1/$exp); } ?> Exercise 1: Constuct a program that illustrates the idea/fact that the minkoski() function is a generalization of the cityblock() and euclidean() functions. Is the PHP program “proof” of this mathematical idea/fact? Exercise 2: Construct a PHP program that tests whether the minkowski($exp) function satisfies the triangle inequality relationship. I will provide some code tomorrow that offers a stochoastic answer. Exercise 3: Discuss the relationships between space and distance? Is space “real” and/or “constructed”? Is distance “real” and/or “constructed”?

d(u, v) <= d(u,w) + d(w, v) for all u, v, w vectors

Snagged this definition from The C Clustering Library (PDF) documentation which has a good discussion of distance metrics and applications.

1. Rotatable Scatterplots
2. Slicing Engine
3. Nearness Engine
4. Smoothing Engine

These are all interactive graphic discovery tools for multi-dimensional spaces. You will need to read the book to get a sense of how these tools might work, however, the exact nature of what these tools are and how they work is the subject of future research so don’t expect crisp definitions (otherwise I would have provided them above) but rather suggestive examples. The book also contains numerious interesting and instructive tidbits such as this one:

Abraham Wald, in some work he did during World War II, was trying to determine where to add extra armor to planes on the basis of the pattern of bullet holes in returning aricraft. His conclusion was to determine carefully where returning planes had been shot and put extra armor every place else! (p. 148)

Why do you think Wald did this?

1. Add these settings to your .htaccess file (where mysqluser and mysqlpass are to be changed to appropriate values): SetEnv DBUSER mysqluser SetEnv DBPASS mysqlpass
2. Test that the values of the environment variables can be accessed from a PHP script: <?php echo "<pre>"; echo $_SERVER['DBUSER']; echo $_SERVER['DBPASS']; echo "</pre>"; ?>
3. You can then connect to your db like this: $db = mysqli_connect('localhost', $_SERVER['DBUSER'], $_SERVER['DBPASS']);

In the future, php/Math datamining applications will utilize a database connection setup like this to make sharing of php-mysql code easier. Those of you who can’t set the .htaccess environment for your web directories, could instead set the $_SERVER values via a config.php file that would be included at the top of every datamining application script. This is less convenient to set up and tarball than using Apache environment variables to maintain your database username and password.

Content composed with the instant Online HTML editor. Please purchase a HTMLg license to remove the promotional messages from the edited documents.