Course Information
Meeting Times and Locations
Tuesday & Thursday 9:30AM - 10:45AM in NVidia Auditorium, Jen-Hsun Huang Engineering Center
In the first two weeks of the class, we will also hold 2 recitation sessions that will serve as refreshers on important course material:
- Review of basic probability. It will be held on Friday, January 10, at 4:15-5:30pm in Gates B03.
- Review of basic linear algebra. It will be held on Monday, January 13, at 4:15-5:30pm in Gates B03.
Course description
The course will discuss data mining and machine learning algorithms for analyzing very large amounts of data. The emphasis will be on Map Reduce as a tool for creating parallel algorithms that can process very large amounts of data.
Topics include: Frequent itemsets and Association rules, Near Neighbor Search in High Dimensional Data, Locality Sensitive Hashing (LSH), Dimensionality reduction, Recommendation Systems, Clustering, Link Analysis, Large scale supervised machine learning, Data streams, Mining the Web for Structured Data, Relation extraction and Web Advertising.
CS246 is the first part in a two part sequence CS246--CS341. CS246 will discuss methods and algorithms for mining massive data sets, while CS341: Project in Mining Massive Data Sets will be a project-focused advanced class with an unlimited access to a large MapReduce cluster.
For students who want to learn more about Hadoop we are also offering CS246H: Mining Massive Data Sets: Hadoop Labs. In CS246H Hadoop will be covered in depth to give students a more complete understanding of the platform and its role in data mining.
Course outline
Tentative list of topics to be covered. These topics may change as the quarter progresses.
- Introduction and MapReduce
- Association Rules: Frequent itemsets and Association rules
- Near Neighbor Search in High Dimensional Data
- Locality Sensitive Hashing (LSH)
- Dimensionality reduction: SVD and CUR
- Recommendation Systems
- Clustering
- Link Analysis: Personalized PageRank, Hubs and Authorities
- Web spam and TrustRank
- Proximity search on Graphs: Random Walks with Restarts
- Large scale supervised machine learning (1): k-nearest neighbor, Perceptron
- Large scale supervised machine learning (2): Classification and regression trees
- Large scale supervised machine learning (3): Support Vector Machines
- Mining data streams
- Mining the Web for Structured Data, Relation extraction
- Web Advertising
See Handouts for a list of topics and reading materials.
Important Dates: Assignments
See FAQ for information on how to submit assignments and other work.
Important Dates: Gradiance quizzes
Gradiance quizzes are out on Friday afternoon and due exactly a week later. Note that we cannot under any circumstances extend the quiz deadline. Once the deadline has passed students will not be able to submit their quizzes.
Prerequisites
Students are expected to have the following background:
- The ability to write very non-trivial computer programs (at a minimum, at the level of CS107).
- Good knowledge of Java will be extremely helpful since most assignments will require the use of Hadoop which is written in Java.
- Familiarity with basic probability theory is essential (at a minimum, at the level of CS109 or Stat116).
- Familiarity with writing rigorous proofs (at a minimum, at the level of CS 103).
- Familiarity with basic linear algebra (e.g., any of Math 51, Math 103, Math 113, CS 205, or EE 263 would be much more than necessary).
- Familiarity with algorithmic analysis (e.g., CS 161 would be much more than necessary).
The recitation sessions in the first weeks of the class will give the overview of the expected background.
Course materials
Lecture notes and slides will be posted on-line. Readings have been derived from the book Mining of Massive Datasets by Anand Rajaraman and Jeff Ullman.
You can see earlier versions of the notes and slides for the Winter 2013 version of the course. Note there may be a slight change in the topics covered this year.
Course handouts and other reading materials can be downloaded here.
Course work and grading
The coursework for the course will consist of:
- Gradiance quizzes: Short weekly Gradiance quizzes. 20% of the final grade.
- Homeworks: Four biweekly homeworks that include programming. 40% of the final grade.
- Final exam. 40% of the final grade
Gradiance quizzes
With regard to the weekly quizzes on Gradiance. Here are the instructions:
- Go to http://www.newgradiance.com/services
- Register and use the class token 5D72F278
- Make sure you register using your Stanford email (SUNet ID) so we can match enrollment records
- There is a MapReduce quiz assigned (see under the Homeworks tab) with 4 quick questions.
- To answer some of them you will need access to the Mining Massive Datasets book
- You will have exactly 1 week to complete the quiz. (There are no late days!)
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.
Gradiance quizzes are generally out on Friday afternoon and due exactly a week later. Note that we cannot under any circumstances extend the quiz deadline. Once the deadline has passed students will not be able to submit their quizzes.
Homeworks
Four biweekly homeworks that will involve programming, working with Hadoop, as well as regular numerical/algebraic theory problems.
Questions: We try very hard to make questions unambiguous, but some ambiguities may remain. Ask (i.e., post a question on Piazza) if confused or state your assumptions explicitly. Reasonable assumptions will be accepted in case of ambiguous questions.
Honor code: We strongly encourage students to form study groups. Students may discuss and work on homework problems in groups. However, each student must write down the solutions independently, and without referring to written notes from the joint session. In other words, each student must understand the solution well enough in order to reconstruct it by him/herself. In addition, each student should write on the problem set the set of people with whom she/he collaborated.
Since we occasionally reuse problem set questions from previous years, we expect students not to copy, refer to, or look at the solutions in preparing their answers. It is an honor code violation to intentionally refer to a previous year's solutions. This applies both to the official solutions and to solutions that you or someone else may have written up in a previous year.
Finally, we consider it an Honor Code Violation to post your homework solutions to a place where it is easy for other students to access it. This includes uploading your solutions to publicly-viewable repositories like on GitHub.
Late assignments: Each student will have a total of two late periods to use for homeworks, reaction papers and project proposals. One late period expires at the start of every class. (This means that if the assignment is due on Thursday then the first late period expires on the following Tuesday at the start of the class.) Once late periods are exhausted, any assignments turned in late will be penalized 50% per late period. However, no assignment will be accepted more than one late period after its due date.
Assignment submission: See the F.A.Q.
Regrade policy: We take great care to ensure that grading is fair and consistent. Since we will always use the same grading procedure, any grades you receive are unlikely to change significantly. However, if you feel that your work deserves a regrade, please submit a written request within a week of receiving your grade. In your request, indicate which components of your submission you would like regraded, and prepare a clear and concise argument why you feel we should regrade those components. Write your request on a sheet of paper, attach it to your original homework, and resubmit both together in the submission box (or via SCPD, if you're an SCPD student). However, note that we reserve the right to regrade the entire assignment.
For grading questions, please talk to us during office hours. If you want a regrade and you are a regular student, drop the homework and the request into the submission box in the Gates submission box. If you're an SCPD student, then please send the request through SCPD (attach the SCPD routing form to make sure it gets to us).
Hadoop in a Virtual Machine
Most assignments will require some level of programming in Hadoop. Hadoop is the open source implementation of MapReduce distributed data processing environment for mining large data sets across clusters of computers.
You will be running Hadoop jobs on your local laptop/desktop. However, since installing and setting up Hadoop is non-trivial we prepared a Linux virtual machine with Hadoop already installed. We will post the instructions and the VM soon.
Recitation sessions
Two recitation sessions will be held:
- Linear Algebra Review: properties such as rank and nullspace, operations such as inverse and trace, quadratic forms, eigendecomposition.
- Probability Review: random variables, moments, basic limits and bounds, maximum likelihood, basic optimization algorithms like gradient descent.
The recitation sessions are only intended to be refreshers; it is expected that you have already taken courses that include this material.
Previous versions of the course
The previous version of the course is CS345A: Data Mining which also included a course project. CS345A has now been split into two courses CS246 (Winter, 3 Units, homeworks, final, no project) and CS341 (Spring, 3 Units, project focused).
CS246 was first offered in Winter 2011. Here is the course webpage with all the materials.
Communication
General course questions should be posted Piazza.
If you need to reach the course staff, you can reach us at cs246-win1314-staff@lists.stanford.edu (consists of the TAs and the professor).