First of all, keep this in mind:
After all, if it was easy to do this without any labels, then, what would be the point of needing the labels in the first place?
I can see two options:
- Use a pre-trained image classifier to represent your images
As Vincent Young suggests, you can find pre-trained networks which have been trained on similar detection tasks. ModelZoo is a good place to find pre-trained networks for the framework you are using.
- Try mean-shift instead of K-Means
K-Means is straight forward but has some flow. It doesn't deal well with clusters of uneven size and will learn towards creating circular clusters due to Euclidean distance.
Mean-shift can deal with arbitrary feature spaces and can use arbitrary kernel functions. You may not end up with 2 clusters, but you may be able to find useful clusters regardless. On this note, if you try using more than 2 clusters with K-Means, you may find some clusters being "pure" (containing a single class) while some may be mixed. These pure clusters can be a good start.
I wrote a chapter on Mean Shift on my website, including other resources, if you want to read it.