Statistics and linear algebra really should be required by all CS programs. It's funny that at many schools those courses are not, yet Calculus is. First, Calculus should have been handled in HS. Second, I've never had a use for Calculus professionally or for anything I've worked on in my free time.
- Machine Learning by Tom M Mitchell http://www.cs.cmu.edu/~tom/mlbook.html
For general reading and introductions I also like:
- Pattern Classification by Richard Duda
- Pattern Recognition and Machine Learning by Christopher Bishop
For a bit more emphasis on statistics and math, I usually dive in to
- Classification,Parameter Estimation and State Estimation by van der Heijden
And last, but certainly not least:
- Information Theory, Inference, and Learning Algorithms by David MacKay, available here:
I've read O'Reilly's Collective Intelligence. It's a great introductory survey, but it was very light on theory.
I also own Collective Intelligence in Action. It had more explanation of theory than O'Reilly's offering, but most of the chapters devolved into how to use Java data mining framework X.