-snip-
How do you distinguish change addresses form normal outputs?
I found the refined version of Heuristic 2.
The simplest way is to identify the transactions that only have two output addresses.
And only one of the output appears first time in the blockchain (new address).
The new address will be identify as the change address.
-snip-
Its not correct. I have seen people asking to send Bitcoins to new addresses due to privacy concerns. I don't think "heuristic 2" will work. I might be wrong though!
I see that a lot too with businesses, since it also makes it easier to track payments. I think a better way to think of heuristic 2 is that the change addresses are usually weird numbers. You typically sent some nice even number of Bitcoin to someone, like 0.10 BTC, and not something like 0.1876573 BTC. I think in transactions where one output is clean and the other is not, then the assumption can be made that the weird output is the change.
Unless the price was given in USD and caluclated to BTC as is often the case with payment processors. They also use new address every time they request a payment from you. I personally also often send the exact input to a casino as the exact amount I want to gamble with is not that important and I want to avoid a change address. This might be very specific to people that have full control over the inputs they spend though.
Many of the assumptions here are just that, assumptions and as long as you keep that in mind when analyzing the blockchain you should be fine. The problem I see however is that this is often used as concrete evidence of something, while its nothing more than a possibility.