Saturday, May 16, 2009

Sense Networks: Mining Location Data

There is an enormous amount of location data being generated by cell phones, wi-fi enabled devices, and gps devices every minute. Sense Networks, a company founded by Columbia University and MIT faculty members, is a company that mines this location data in real-time to discover behavioral patterns of mobile phone users. One simple mobile application that the company has produced is CitySense, which produces an activity "heat map" of a city, showing the user where all of the busiest locations are in real-time. "Citysense shows the overall activity level of [a] city, top activity hot spots, and places with unexpectedly high activity, all in real-time. Then it links to Yelp and Google to show what venues are operating at those locations."
At the heart of Sense Networks' technology is the MVE algorithm:
Sense Networks attributes 487,500 dimensions to every place in a city, thus identifying a unique and complex 'DNA' which describes it completely... Proprietary MVE (Minimum Volume Embedding) algorithms reduce the dimensionality of location and temporal data to 2 dimensions while retaining over 90% of the information.

The company eventually plans to produce an application that learns the movement patterns of a mobile phone user over time, subsequently providing recommendations for places to visit when the user visits a new city. For example, if you like to visit ice-cream shops in your hometown, the application will automatically learn this behavior. When you go to visit another city in another state, the application can automatically "sense" and report to you where the most popular ice-cream shops are in that city based on location data from other ice-cream lovers.
The application of this kind of technology to social networks and consumer-enriching applications is exciting, but the privacy implications can be frightening. Sense Networks has a special executive called the CPA (the "Chief Privacy Advocate") who deals with privacy concerns. Their philosophy is to give a user complete ownership over the data they choose to share, as well as a provision for the user to easily delete at any time the data they have already chosen to share.

Tuesday, December 9, 2008

Metalearning Book Available

We are pleased to announce that, after much work, the book:

Metalearning: Applications to Data Mining

co-authored by Christophe and 3 of his colleagues (Pavel Brazdil, Carlos Soares and Ricardo Vilalta) is now available from Springer.

See http://www.springer.com/978-3-540-73262-4 for details.

Friday, October 10, 2008

Information Pathways in Social Networks

The first talk presented in the social network session of KDD 2008 was for an interesting paper by G. Kossinets, J. Kleinberg, and D. Watts titled The Structure of Information Pathways in a Social Communication Network (PDF). Although I was not at KDD I was able to watch it online at videolectures.net.
Kleinberg, the presenter, made some interesting observations having to do with our "rhythmic" everyday conversations. The approach to analyzing communication within these social networks is focused on the frequency of correspondence, rather than the content conveyed.

They measure "distance" between individuals by measuring the minimum time required for information to pass from one node to another. A methodology based on Lamport's work and vector clocks in the area of distributed computing.

Using this metric they are able to filter a busy network (one having edges for all communication packets) in a simplified network that contains only the edges that are minimum-delay paths between a pair of nodes. They call this simplified network view the network backbone. Below is an example of such a network (along with the caption) taken from the paper.
The nodes further outside of the center of the graph are more "out-of-date" with respect to node v, since they communicate less frequently.

I found the approach to be novel and useful. As with nearly any analysis technique, caution should be used in selecting the time-period and group size to be studied. Recency and frequency issues come into play as correspondence is aggregated. However, this pursuit offers another approach for more fully understanding information flow.

Originally published by Matt on his blog at: http://dmine.blogspot.com

Thursday, October 9, 2008

AMIA Competition Finalists!

Jun, Yao and Matt participated in the 2008 Data Mining Competition: Discovering Knowledge in NHANES Data, sponsored by the AMIA Knowledge Discovery and Data Mining Working Group, and were selected as one of the finalists by the judging panel. They will be presenting their results in a dedicated session of the AMIA Annual Symposium in Washington, DC, in November 2008. Congratulations!

Thursday, September 25, 2008

A Couple of Interesting Papers

Here are a couple of papers that others might also find interesting.

Title: Information-Theoretic Definition of Similarity (PDF)
Conference: ICML 1998

The paper provides a general similarity measure applicable across many domains. The authors insist that their formulation satisfies "universality" and "theoretical justification". Previous similarity measures are domain-specific. The formula is:
sim(A,B) = log P(common(A,B)) / log P(description(A,B))
where common(A,B) is a proposition that states the commonalities between A and B, and description(A,B) is a proposition that describes what A and B are.

Title: An Introduction to Quantum Computing.
Author: Norson S. Yanofsky

The paper gives a taste of quantum computing targeted at computer science undergraduates (and even advanced high school students). Some of the (fun) basic points in Quantum Computing include the following. A quantum can exist in SEVERAL states AT THE SAME TIME (Superposition), but when it is measured, it collapses to either 0 or 1. (in the case of a 2 (qu)bit quantum computer). When two quantums are added, their magnitude can be decreased (Interference).

Wednesday, April 16, 2008

Picture of our Blog

powered by bscopes.com

Here is a picture of the our blog provided by bscopes.com.

Here is the legend they provide to help interpret the graph. It is clear that the all of the blogs referencing our blog are not listed (due to the sparsity of data collected at bscopes). As is, the value of this graph limited to showing the number of links within each of our blog entries. Despite the current limitations, I find the idea of providing a web service that produces a visual representation of a blog interesting.

Wednesday, April 2, 2008

Recipe for Kim-Chee Fried Rice

One of our lab's fun traditions is our weekly potluck lunch. Once a week, everyone brings something from home that we put together and share for lunch. This is a great time to socialize and talk informally about our research or anything else. People typically bring left-overs, but Jun, our in-house Korean lab member, makes a point of bringing a Korean dish that he prepares for us on purpose every week. It is typically some curry dish or kim-chee. As we do not wish to keep this to ourselves, a picture of Jun's kim-chee with his recipe are found below. Enjoy!

1. Prepare for Kim-chee. (You can purchase in either Korean market or Asian Market)
2. Mix with vegetables or beef (I recommend to put chopped Onion, garlic, and Tuna)
3. Fry them with Olive oil for 4-5 minutes.
4. Done!!! (Isn't it so easy?)

Pictures from AAAI Symposium

Here are a few more pictures from the AAAI Social Information Processing Spring Symposium at Stanford University.


An example of the beautiful architecture

A beautiful field out in front of the symposium location

The building where the symposium was held



Thursday, March 27, 2008

AAAI Social Information Processing Symposium Summary

I apologize for not getting back sooner with results and thoughts from the symposium. Like I said in my previous post, Matt and I attended the AAAI 2008 Social Information Processing Symposium. Matt presented on Social Capital in the Blogosphere and it seemed to be well received by the community. They followed up on our presentation about social capital with a number of questions regarding possible actions and experiments that could be taken within our framework for measuring social capital. It furthered our opinion that the work we have done provides an intuitive way to understand a seemingly abstract topic like social capital. There is still a lot of work to be done in determining what constitutes and explicit and implicit link within the blogosphere, but we are on our way.

Several other thoughts specifically related to our research.
  • Bonding links (a relationship with someone similar to you) should be easier to make than a bridging links (a relationship with someone different that you). Thus in a social network representation you should probably see a substantial amount more bonding than bridging taking place.
  • There is a cost associated with forming a bonding or bridging link that we have not addressed up to this point. In general, this cost involves both the type (bonding/bridging) of link and also the individual social capital of the person you are attempting to form a link with.
  • Nearly everything in the social information processing domain, when graphed, seems to follow a power law. Does individual social capital follow this distribution as well, ie. do certain individuals have much more social capital than the population at large? If so is there anyway to leverage the social capital of all the individuals found in the long tail of the graph? For example, the wisdom of the masses approach is working wonderfully in Wikipedia, where information may in some cases be more accurate than that of the so-called authorities. It's all theory, but just some ideas I've been thinking about.
  • High cost, high reward. Blogging can take a lot of time, because good writing takes time. It takes substantially more time than other activities we heard about in the conference such as tagging, posting pictures or rating a product. But with the high cost comes the high rewards, as blogging has become mainstream it has become a powerful tool for advancing ideas, products, companies and careers. Ultimately we need to get some type of reward for our involvement in a social network even if it is just personal fulfillment or our activity will dwindle.
Other cool things about the symposium.
  • Stanford is the most beautiful campus I've ever been on.
  • We heard about a cool new project called Freebase that seems to have the potential to someday replace Wikipedia as the best source for free, open content information. It looks smooth, provides easy ways to query for information and has an awesome API. It could be the next big thing. Matt posted his thoughts about it as well at his blog.
  • Gustavo Glusman presented one of the coolest social network graphs I've ever seen (the flickrverse) which can be found here.
  • Meeting a wide variety of people. There was representation from both academia and industry from a variety of locations. Plenty of people were from California, but there was also representation from other parts of the United States, the UK, Germany, China, Taiwan, Switzerland and probably more that I am forgetting. It was a great group to become involved in.
  • Getting to learn from those who know more than I do. Everyone had their own expertise in specific social networks and with specific ideas. I learned a lot about social networking principles that are somewhat different than those found here in the blogosphere.
Matt posted some of his thoughts about specific papers on his blog here and here for those who are interested. For any out there who would consider attending next year, go for it, it was a wonderful experience.

Wednesday, March 26, 2008

Hello from Stanford

Matt Smith and I will be at the AAAI 2008 Spring Symposium which is being held at Stanford University from now until Friday. We are attending the Social Information Processing session and will be presenting on a paper we co-authored with Christophe entitled Social Capital in the Blogosphere: A Case Study. The morning and afternoon sessions were great and I'll give a rundown later on. Matt will be presenting in about an hour and a half so I'll post about how that went and everything else we are learning here.


Saturday, March 22, 2008

On Correlation versus Causation

Among the common mistakes made by data miners who lack training in statistics is the confusion between correlation and causation, often arising from the difference between observational studies and random controlled trials. To start with, here are some simple definitions.
  • There is a relation of (positive) correlation between two random variables when high values of one are likely to be associated with high values of the other.
  • There is a relation of cause and effect between two random variables when one is a determinant of the other.
It is easy to see from these definitions that:
  • Causation implies correlation, but correlation does not necessarily imply causation.
  • Correlation is easy to establish, causation is not.
As a matter of fact:
  • Random controlled trials establish causation.
  • Observational studies only bring out correlation.
One of the main reasons correlation, although often appealing, cannot be "safely" acted upon as if it were causation lies in the potential presence of confounding variables. A confounding variable is one that affects the variable of interest but it has either not been considered or not been controlled for (wherein the name "confounding" or "lurking"). Consider the following simple example of a confounding effect. Suppose that a very profitable customer C has placed your company BetterSoft in competition with another company GoodSoft to test your relative abilities to develop good software. The task is to design an algorithm to solve a class P of problems. Your company produces algorithm A, while the other company produces algorithm B. Both you and your competitor are asked to run your own batch of 350 tests and report how often your algorithm gave acceptable solutions (as defined by C). GoodSoft comes out on top with a score of 83% against only 78% for your algorithm. Just as C is about to award its lucrative contract to GoodSoft, you realize that the problems in class P are not all of the same complexity. In fact, it turns out that there are two clear levels of difficulty: simple and complex. You ask the customer to collect more detailed data from GoodSoft and yourself, namely splitting the 350 test problems into simple an complex problems. The results, when complexity is thus factored in, are as follows.
  • Simple problems: A solves 81 out of 87 and B solves 234 out of 270
  • Complex problems: A solves 192 out of 263 and B solves 55 out of 80
Should this additional information change C's decision as to which company to hire? Of course. Although GoodSoft does better overall, it actually has worse performance on both the simple problems and the complex problems. Such situation are also known as examples of Simpson's paradox. It is a paradox because although mathematically correct, it is somewhat counterintuitive. The "variable" complexity in this example is a confounding variable, because it interacts with the calculated outcome in a way that may easily be overlooked, but may have an adverse effect on conclusions reached. Another well-known instance of Simpson's paradox arises in some of our US presidential elections where the winner does not carry a popular vote (i.e., the tally of individual votes gives the opponent as winner). The confounding variable in this case is the electoral college.
In the medical domain, for example, it is critical to discover causal rather than only correlational relationships. One cannot take the risk of treating the "wrong" cause of a particular ailment. The same is also true of many other situations outside of medicine. Hence, data miners should do well to understand confounding effects and use that knowledge both in the design of the experiments they run and the conclusions they draw from experiments in general. I have been guilty of "jumping the gun" myself and reporting results that clearly ignored possible confounding effects.

Let me turn now to more mundane business applications. In reaction to a (much shorter) comment I posted about the difference between correlation and causation here, a couple of individuals reacted as follows (I reproduce some of that conversation here for completeness):

  • (Jaime) - I don't think that insurance companies or any other business that would use data mining would or necessarily should care about the difference between correlation and causation in factors they don't have any control. (exceptions, of course, for anything medical or legal). If they can determine that people with freckles have less car accidents, why shouldn't they offer people with freckles lower rates?
  • (Will) - Jamie makes a good point. The question of correlation versus causation will be of only philosophical interest to a data mining practitioner, assuming that the underlying behavior being modeled does not change (and this will often be a safe bet). An illustration should make this subtlety clear. Suppose that insurance data indicates that people who play the board game Monopoly are better life insurance risk than people who do not. An insurance company might very well like to take advantage of such knowledge. Is their necessarily a causal arrow between these two items? No, of course not. Monopoly might not "make" someone live longer, and living longer may not "make" someone play Monpoly. Might there exist another characteristic which gives rise to both of these items (such as being a home-body who avoids death by automobile)? Yes, quite possibly. The insurance company does not care, as long as the relationship continues to hold.

This brings up an interesting point of course. Is the matter of causation versus correlation only a philosophical one, with little bearing in practice (a little bit like the No Free Lunch Theorem is a great theoretical result but seems to have little real impact in practical applications of machine learning; but that is another discussion: here for details on this unrelated but interesting topic). Let me try to address this here a little bit (much of this is also found in my response on the above blog). The statistician (I use the term loosely, I am not a statistician myself) seeks the true cause, the one that remains valid through time. On the other hand, the (business) practitioner seeks mainly utility or applicability, which may become invalid over time but serves him/her right for some reasonable amount of time. Under this view of the world, I think it is possible to reconcile the two perspectives. Indeed, one can see that the statements "assuming that the underlying behavior being modeled does not change" and "as long as the relationship continues to hold" may be interpreted (in some way, see below) as effectively equivalent to what statisticians regard as "controlling for variables". By taking this kind of dynamic approach where the relationship (or behavior) is "continuously" monitored for validity and the action is taken only as long as that relationship holds, the user is, in effect, relieved from the problem of lurking variables. Let me illustrate on Will's example. Statisticians would indeed argue that there may be a confounding variable that explains the insurance company's finding, one that has nothing to do with playing monopoly. Will proposed one: "being a home-body". I'll continue the argument with that one. In this case, it may therefore be that there are more home-body monopoly players than not; and it is the "home-bodyness" (if such a word exists) that explains the lower risk for life insurance (and not the monopoly-playing). Now, a statistician would be right in this case, and if one had to come up with the "correct" answer and build a model that remains accurate for now AND the future, you would have to accept the statistician's approach and build your model using home-bodyness rather than monopoly playing. There is little arguing here. I think that what Will and Jaime are be getting at is that there is a way to, in some sense, side-step this issue; namely: monitor the relationship. Indeed, if I keep on looking and checking that the correlation continues to hold, then I don't care about any confounding effect. If there are none, then the correlation also manifests a causation and I am safe; if there are some confounding effects, they will become manifest over time as the observed correlation is weakened. Hence, I can choose at that time to invalidate my model. But in the meantime, it served me right, was accurate, and I did not worry about controlling anything. Going back to the example, as long as the correlation is strong, I am OK. If it turns out that it is home-bodyness that causes the lower risk, I may eventually see more and more non monopoly players with low risk who also turn out to be home-bodies. In this case the originally observed correlation will decrease telling me that I may wish to discontinue the use of my model.

The distinction may be viewed as only of philosophical interest, at least in the context of such business cases. Again, in medicine, one may have a different perspective as also pointed out by Jaime and Will. One of the drawbacks of the "correlation-driven" approach is that when the model is no longer valid (as seen by the decreasing correlation value), the practitioner has no idea what may be the cause and is thus left with no information as to where to go next. Then again, as suggested by Jaime and Will, maybe he/she does not care. From a strictly business standpoint, he/she was able to quickly build a model with high utility (even if only for a shorter period of time) instead of having to expand a lot of resources to build a "causation" model, with the risk of not doing any better as not all confounding can ever be controlled for! (In fact, there are even situations where the controlled experiments that would be necessary cannot be run; see here for a fun example).

After all is said and done, and more has been said than done :-), one should be aware of confounding effects (or Simpson's paradox), and know how to deal with them: 1) stick to strictly random controlled experiments; or 2) use observations but handle with careful and continuous monitoring.

Wednesday, March 5, 2008

Ian Ayres' Super Crunchers Book

I recently came across Ian Ayres' book: Super Crunchers. It is a nice read. Ayres essentially makes the case for number crunching (data mining for many of us) in all aspects of business and social life. The book describes a large number of case studies where number crunching has been successfully applied (e.g., wine quality, teaching methods, medical practices, etc.), often providing answers that challenge traditional wisdom. The examples are rather compelling. Most of the studies rely exclusively on random controlled trials and the use of regression techniques. Yet, I think this is a great book for people starting in data mining or looking for good reasons to begin. (The other nice thing is that the book is very cheap: less than $20 on Amazon!). Enjoy!

Spring Research Conference

The 22nd Annual Spring Research Conference for the College of Physical and Mathematical Sciences is coming up on Saturday, March 15th. The current presentation schedule for the conference can be found here. Six members of the lab will be presenting research at the conference.
We're happy about our representation and it is shaping up to be a great conference.

Wednesday, February 27, 2008

Data Mining Lab -- Experience is Key

My name is Nathan Davis. I've been a member of the Data Mining Lab at BYU for 3 years now, and have had a wonderful experience. In fact, I've had a lot of great experiences, many of which have prepared me for future work and research.

With respect to work, I've had a chance to conduct real world data mining for large industry partners. In addition to learning, through experience, about the technical aspects of the data mining process, the lab has also given me an opportunity to learn about business aspects, by meeting face-to-face with industry partner representatives. Most recently we were able to meet with a Vice President of a large retail company to discuss several issues relevant to the research we conduct!

Further, the lab has provided me with great research experience. Dr. Giraud-Carrier is a tremendous academic, with a great deal of interest in his students and research assistants. Under his tutelage I've published academic papers and will soon be completing a Masters degree. I even had the opportunity to travel to the Netherlands to present at an academic conference.

Currently I'm conducting a software engineering internship with Google, and my experience in the lab is helping me to be successful. For anyone interested gaining experience that will help them succeed academically and professionally, I'd highly recommend dropping by the lab and finding out about the great experiences that await you.

Tuesday, February 26, 2008

10 Reasons Why Data Mining is Fun and Rewarding

1. You can train your computer to do things you can't.
2. The methods are complicated, but the applications are intuitive.
3. It can save/make lots of money.
4. Data mining has applications in nearly any area you can think of.
5. You get to deal with data sets larger than you could ever process in your mind.
6. There are big developments taking place in the industry.
7. Data mining algorithms attempt to model how things work in biology and the real world. (ie. Neural networks/genetic algorithms)
8. There is no one size fits all solution when it comes to data mining.
9. You help make the statement "I have more data than I know what to do with" obsolete.
10. Your results can make an immediate impact in whatever industry you are involved in.

Why do you like data mining today? What got you interested in the first place?

Friday, February 22, 2008

Data Mining in the Workplace

I graduate in a few months and so I've been job hunting lately. I attended the Technical Career Fair here at BYU a few weeks back and I was impressed by the number of companies that were interested in data mining. With the exception of one or two companies, they all either were currently involved in data mining or were interested in becoming involved in the near future. I think that as more and more companies amass mounds of data, they are realizing that collecting data for data's sake is useless and that they can get much more out of their data than they have in the past. Data mining is no longer 'a hiss and a byword'. I am witnessing firsthand that it is the direction that many companies are taking to improve the efficiency of their operations.

Wednesday, February 20, 2008

Our Lab in Utah CEO Magazine

The BYU Data Mining Lab is featured in an article published in this months Utah CEO Magazine. The article, found here, includes expert opinions from our own Professor Christophe Giraud-Carrier on why finding a champion for data mining within a company is important and how successful data mining is defined. In addition, the article contains a short feature on the lab which explains the benefits students and businesses gain from being involved with the lab. It is exciting to see outside recognition for the great work that goes on here everyday.

Wednesday, February 13, 2008

Social Connections in Decline

Robert Putnam, an influential social capital researcher, visited BYU nearly two years ago to discuss how social connections are on the decline. Here is good summary of Putnam's talk on BYU NewsNet. His research during the past decade has shown a negative trend in that people are socially connecting less these days. The speech gave fuel to the research on social networks that we had been involved in and has been a strong motivation to our current work on social capital.

Figure 1. "The TV Connection" shows that group membership tends to decline as television viewing increases among those having twelve or more years of education. (see The Strange Disappearance of Civic America)

Empirical studies on group membership, like the study shown in the plot above contribute to the evidence which Putnam uses to support this claim.

(Note: This article was originally posted on dmine.blogspot.com)

Data Mining Search Engine

I recently learned at the Data Mining Research blog about a data mining search engine. The search engine, which can be found here, allows search queries to be performed so that the results come largely from a list of data mining sites. It might prove to be a useful tool for focusing your research on trusted data mining sites, or for discovering new resources in our field of interest. Give it a shot, I don't have much experience with custom Google Search engines, but it seems useful.