1) AUC can be computed for any classifier whose final decision for classification of a new data relies on comparing some measure computed from the data to a cut-off. A clear case is an SVM for example, where one computes the distance of the new data to the separating hyperplane and declare the data as "1" or "+" if $distance > 0$. The cut-off in this case is 0. The ROC curve is computed by changing the cut-off and the area under the ROC curve is the AUC.
Even some algorithms that do not seem to be based on computing a measure for the new data can be interpreted as being so. For example k-NN does not seems to compute a measure, but there is a measure and a cut-off. The measure is the number of "+" / k, where number of "+" is the number of positive examples among the k nearest neighbors. The cut-off is 0.5: one will classify a new data as positive if most of its k-NN are positive! For k=1 this is the only possible cut-off, but for larger k one can use other cut-offs to generate a (stairs like) ROC, and compute the AUC.
The "accuracy of a classifier" really means "the accuracy of the classifier when one uses the default cut-off"
2) Another way of understanding the AUC is that it is measuring the order of the classification regarding the computed measure. Examples of the "0" or "-"class should have a measure that is lower than that of examples of the "1" or "+" class. I am almost sure that the AUC is the probability that a random "+" example has a measure larger than a random "-" example.
Now let us see an example,
- - - - | + - + + + +
where the measure increases from left to right, and the | marks the default cut-off. The classifier has an accuracy of 0.9. The 4 negative examples are below the cutoff, and thus are correctly classified as -, and the negative example to the right of the cutoff will be wrongly classified as +
Another example:
- - - - | + + + + - +
the accuracy is the same, 0.9, but in this case the order of the measure is "more messed up".
For the first example , of the 6x4=24 pairs of positive/negative data, only for one of them it is not the case that the measure for the + is larger than the measure of the -, and thus the AUC is 23/24. For the second example, 4 of the pairs are in the wrong order, and thus the AUC is 20/24.
Thus it is possible for a classifier to have higher accuracy than another but lower AUC. The higher accuracy classifier makes fewer mistakes but these mistakes are further away from the cutoff. The lower accuracy classifier makes more mistakes but those mistakes are closer to the cutoff!
