CS345A, Winter 2009: Data Mining.

Course Information

Instructors: Anand Rajaraman (anand @ kosmix dt com), Jeffrey D. Ullman (ullman @ gmail dt com).

TA: Anish Johnson (ajohna @ stanford dt edu).

Staff Mailing List: cs345a-win0809-staff@mailman.stanford.edu

Meeting: MW 4:15 - 5:30PM; Room: History Corner basement 200-002.

Office Hours:
Anand Rajaraman: MW 5:30-6:30pm (after the class in the same room)
Jeff Ullman 2-4PM on the days I teach, in 433 Gates.
TA: Anish Johnson Tuesdays: 9:15-10:45am in B26A Gates
Thursdays: 1-3pm in B24B Gates

Prerequisites: CS145 or equivalent.

Materials: There is no text. However, if you have the second edition of Database Systems: The Complete Book (Garcia-Molina, Ullman, Widom), you will find Section 20.2 and Chapters 22 and 23 relevant. Slides from the lectures will be made available in PPT and PDF formats.

Students will use the Gradiance automated homework system for which a fee will be charged. Note: if you already have Gradiance (GOAL) privileges from CS145 or CS245 within the past year, you should also have access to the CS345A homework without paying an additional fee. Notes and/or slides will be posted on-line.

You can see earlier versions of the notes and slides covering Data Mining. Not all these topics will be covered this year.

Requirements: There will be periodic homeworks (some on-line, using the Gradiance system), a final exam, and a project on web-mining. The homework will count just enough to encourage you to do it, about 20%. The project and final will account for the bulk of the credit, in roughly equal proportions.

Handouts

Assignments

Gradiance Assignments

You can try the work as many times as you like, and we hope everyone will eventually get 100%. The secret is that each of the questions involves a "long-answer" problem, which you should work. The Gradiance system gives you random right and wrong answers each time you open it, and thus samples your knowledge of the full problem. While there are ways to game the system, we group several questions at a time, so it is hard to get 100% without actually working the problems. Also notice that you have to wait 10 minutes between openings, so brute-force random guessing will not work.

Solutions appear after the problem-set is due. However, you must submit at least once, so your most recent solution appears with the solutions embedded.

Challenge Problems

Project

• Overview: a software project that discovers or leverages interesting relationships within a significant amount of data. Best if the project leverages what we have learned in class.

• A Project Proposal should be sent in positively by midnight, Feb. 9.

• Access to Aster nCluster resources now available.

• ShareThis datasets have been loaded onto both nClusters: check in the 'sharethis' database. Details to the database format here

• Some project ideas (these serve merely as ideas. They should by no means restrict your imagination)
  • Implement anti-spam algorithm (e.g. Trust Rank) on a collection of webpages
  • Implement a better version of topic-sensitive PageRank on a collection of webpages (by "better," we mean "incorporating your own ideas")
  • Implement collaborative filtering technique on certain basket/item data (from Ebay or Amazon, for instance)
  • Tell something useful about a collection of documents -- Web pages, news articles, reviews, blogs, e.g. Possible goals include identifying sentiment (is a review positive or negative?), telling wise blogs from foolish, telling real news from publicity releases, e.g.
  • Take a shot at the $1,000,000 Netflix Prize.

• Be sure to look under Resources to see what data sets are available.
• Deliverables:
  • Final project writeup (5-10 pages) due Wednesday, March 11, in class. This is a comprehensive description of your project. You should include the following:
    1. Project idea
    2. Your specific implementation
    3. Key results and metrics of your system
    4. What worked, what did not work, what surprised you, and why
  • Final Presentation: Each team presents their project to the rest of the class. The presentation should have no more than 3 slides (not counting title/reference etc.) and last no more than 5 minutes. 3 minutes will be allotted for questions. There are three sessions, at 4:15PM on Weds.-Fri., March 11-13. We'll announce a way for people to pick slots shortly, but if you have absolute constraints, you should contact the staff list now.
  • Demo with Course Staff: If you woud like more time to demo your work, you can optionally schedule time with the course staff during dead week and finals week.

Course Outline

References and Resources

• Last Year's Final. Note that the subject matter is somewhat different this year, so you should not assume the coverage on this year's final will be exactly the same. It will, however, cover all material in the course up to and including the 3/4 lecture.

• References. We'll put in this file citations or links to papers that you may wish to read to learn more about certain topics covered in the class. They are not required reading.

• Yahoo! Catalog of data sets available. Note: Jeff Ullman will have to apply for any sets you want, and we must agree not to distribute them further. There may be a delay, so get requests in early.

• Yannis Antonellis and Jawed Karim offer a file that contains information about the search queries that were used to reach pages on the Stanford Web server. The format is

  visitor_hash	timestamp	requested_url	referer_from_a_search_engine

  E.g.,

  a997c1950718d75c03f22ca8715e50b3

  [28/Feb/2007:23:45:47 -0800]

  /group/svsa/cgi-bin/www/officers.php

  "http://www.google.com/sea rch?sourceid=navclient&ie=UTF-8&rls=HPIB,HPIB:2006-47,HPIB:en&q=sexy+random+facts"

  See http://www.stanford.edu/~antonell/tags_dataset.html for more information about how to get and use this file.

• The Stanford WebBase project provides a crawl, and may even be talked into providing a specialized crawl if you have a need. Find description here. Find how to access web pages in the repository here.

• Here's a data set that might be interesting to some of you as you think about your project. e.g., on news clustering, identifying trends in news stories, etc. There is a nominal fee to get the DVD with the data, but if someone if really interested I'm sure we could arrange to make it available: http://open.blogs.nytimes.com/2009/01/12/fatten-up-your-corpus/

  Excerpt: Available for noncommercial research license from The Linguistic Data Consortium (LDC), the corpus spans 20 years of newspapers between 1987 and 2007 (that's 7,475 issues, to be exact). This collection includes the text of 1.8 million articles written at The Times (for wire service articles, you'll have to look elsewhere). Of these, more than 1.5 million have been manually annotated by The New York Times Index with distinct tags for people, places, topics and organizations drawn from a controlled vocabulary. A further 650,000 articles also include summaries written by indexers from the New York Times Index. The corpus is provided as a collection of XML documents in the News Industry Text Format and includes open source Java tools for parsing documents into memory resident objects.

• A former CS345A student and the TA from last year have started a company, Celixis, to do a cellphone-based advisor. They offer two data sets that might be of interest; both are based on restaurant reviews:
  1. A corpus of restaurants and reviews (100+ thousand restaurants, text of reviews can be tagged by part-of-speech). They are interested, for example, in knowing the keywords or key phrases (consecutive words) that best characterize different kinds of restaurants. As a baseline for word occurrence, they can also provide a sample corpus of the web (10+ million pages), and average single word stats over that corpus.

  2. A training set of (user id, restaurant id, rating) tuples. They can also provide a corpus of restaurant info and reviews (in case a model-based approach is used). This data can be used in a manner similar to the Netflix data, but they are not offering $1M for a good solution. And you would have to excise from the data a small portion to measure your performance, while Netflix retains the test data itself.

  If you are interested in obtaining either of these data sets, they can be emailed as love-cs345 at cellixis dt cm.

• ACM has just issued its Multimedia Grand Challege(s). Many of these involve images in a way that we don't have the resources to deal with in the next month, but you might want to read the material to see if anything looks doable and interesting.