CS345, Autumn 2006: Data Mining.

Course Information

The Final for 2006.

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

TA: Jeff Klingner

Email Address for Questions: cs345a-aut0607-staff @ lists dt stanford dt edu (This is the best way to reach all three of us simultaneously)

Meeting: MW 3:15 - 4:30PM; Room: 200-030 (In the history corner, the part of the quad closest to Hoover tower.)

Office Hours: Instructors will be available after classes that they teach. Jeff Ullman is in 433 Gates and Anand in 413 Gates. Jeff Klingner's office hours: Tuesdays 10am-noon & Thursdays 3pm-5pm, Gates 396, or by appointment.

Prerequisites: CS145 or equivalent.

Materials: There is no text, but students will use the Gradiance automated homework system for which a nominal fee will be charged. 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, using the Stanford WebBase. 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.

Newsgroup: There is a class newsgroup: su.class.cs345a on nntp.stanford.edu. You can use the newsgroup to share datasets, form study groups, or find project partners. The course staff will not read the newsgroup regularly, and we won't use it for any official announcements. To get in touch with us, use cs345a-aut0607-staff @ lists dt stanford dt edu.

Handouts

Assignments

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.

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.
• 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)
  • Implement key components of a vertical search engine (e.g. crawler)
  • Implement a meta-search engine that post-processes Google and Yahoo's results
  • Implement a meta-search engine that queries multiple databases and meshes and presents their results in a meaningful way
  • Implement a heuristic/algorithm for ranking Stanford domain web pages
  • Design and implement frequent itemset identification by better 1-pass algorithms
  • Design and implement your alternative to locality-sensitive hashing algorithm
  • Take a shot at the $1,000,000 Netflix Prize. See this NY Times article (local_cache) for more info.
    Resources: Stanford WebBase project. Find description here. Find how to access web pages in the repository here.
• Deliverables:
  • Project proposal: A one-page description of what you plan to do for your project, due Nov. 1st. Please include:
    • who is in your group
    • project title
    • brief description of the problem you'll solve or the question you'll investigate
    • what data you'll use and where you'll get it
    • which algorithms/techniques you plan to use
    • what you expect to submit at the end of the quarter

    Please submit your proposal in a reasonable format (text, html, pdf, etc.) to the staff email list (cs345a-aut0607-staff @ lists daht stanford dawt edu). One copy per group is fine.

    This is intended mainly as a check to make sure you've got a workable idea and a plan for carrying it through, so don't spend a lot of time making it beautiful, but do think seriously about what you're planning to do. It is to your benefit to flesh out your ideas as much as possible in this proposal.

  • Final project writeup (5-10 pages) due Wednesday Dec 6th at 11:59pm. 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: In the last week of class (December 4th and 6th), 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.
  • Demo with professors and TA: 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

Resources and Readings

• References for lectures on association rules.

• For the course project: Stanford WebBase

• References for Web Mining lectures.

• References for minhashing and Locality-Sensitive Hashing.

• References for lectures on stream mining.

• References for lectures on clustering.