How to write/represent the state-of-the-art analysis in a research paper?
State of the art means the best known methodology. This should have turned up in your literature review and if it didn't  you have a gap. The gap would likely be in finding results in very recent papers. 

The first reviewer comment could mean that you haven't actually found and discussed the current best available method to compare with, or that you are somehow misrepresenting it in your paper. 

But it isn't enough to discuss in in the lit review section. You need to explicitly show how your results compare with the results of the best available.  Very possibly it would be a long section of a thesis, though page limits in papers provide a constraint. If your results are superior, you need to show how and discuss why. 

As to number 3 on your list, the methodology you use is up to you to design and should be consistent with practice in your field, unless it introduces, also, a new comparison metric, in which case that needs to be discussed in detail as well. 

For data mining, probably something along the lines of applying the "best known" algorithms along with your own to the same set of data is likely appropriate. 

But you need to assure the reviewers that you compare apples to apples so that the results are directly compared. 

Sorry, I don't have any examples.