Getting rid of old contacts in iCloud

Hey guys,

So I've recently cleaned out the contacts on my phone, but when it sync's with iCloud all my old contacts reappear.

How do I replace the contacts stored in iCloud with the contacts that are currently on my phone?

Thanks for the help.

Chris