The best introductory book and also the most cohesive one is "Learning from Data" from Yaser Abu-Mostafa, accompanied by great video lectures:

http://amlbook.com/

It differs from other books in that all the material is treated from the unified perspective of statistical learning theory and VC dimension, as a result the book feels less like a hodgepodge of unrelated techniques and more like an introduction to a coherent field.

Hastie and Tibshirani also have a new, less demanding mathematically book out:

http://www.amazon.com/Introduction-Statistical-Learning-Appl...