I would think random pat-downs would in fact be part of good security. If you can predict who's going to get them, they lose their impact. And I am someone who generally thinks that most of the airport security is theatre... (See http://www.theatlantic.com/doc/200811/airport-security for a great article on this).

If you are unwilling to submit to this infrequent security screen, then you shouldn't fly. Your rights/privacy aren't being compromised.