The Random Forest Kernel and creating other kernels for big data from random partitions

We present Random Partition Kernels, a new class of kernels derived by demonstrating a natu-ral connection between random partitions of ob-jects and kernels between those objects. We show how the construction can be used to cre-ate kernels from methods that would not nor-mally be viewed as random partitions, such as Random Forest. To demonstrate the potential of this method, we propose two new kernels, the Random Forest Kernel and the Fast Cluster Ker-nel, and show that these kernels consistently out-perform standard kernels on problems involving real-world datasets. Finally, we show how the form of these kernels lend themselves to a nat-ural approximation that is appropriate for cer-tain big data problems, allowing O(N) inference in methods such as Gaussian Processes, Support Vector Machines and Kernel PCA. 1