1つのラベルが変更されたときにROCの領域を効率的に再計算する

Question

バイナリラベル（簡単にするため、同義語は使用しない）のスコアリストがあり、ラベルを使用して、動作特性（ROC）曲線。 n個のスコアの集合については、この計算はO（n log n）時間で簡単に行うことができます。単純にリストをソートし、並べ替えられた順にリストをトラバースし、今まで見たことがあります。ネガティブラベルが表示されるたびに、ポジティブ数を追加し、最後にポジティブ数×ネガティブ数の積で除算します。

この計算を実行したところ、誰かが来て、1つのラベル（正から負またはその逆）をちょうど反転させているとします。スコアそのものは変更されないので、並べ替える必要はありません。ソートされたリストを再トラバースすることによって、O（n）時間内の曲線下の新しい領域（AUC）を計算するのは簡単です。私の質問は、新しいAUCをO（n）よりも優れたもので計算することが可能なのでしょうか？つまり、新しいAUCを取得するためにソートされたリスト全体を再トラバースする必要がありますか？

私は、ランク付けされたリストの各位置で、この位置より上のポジティブとネガティブの数にカウントを格納することによって、O（1）時間で再計算を行うことができると思います。しかし、より多くのラベルが反転するにつれ、AUCを繰り返し計算する必要があります。そして、もし私がそれらの記憶された値に頼ると、次回の更新はO（n）になります。

Answer 1

はい、O（log（n））でAUCを計算することは可能です。ラベルのスコアが反転され（所定の値よりも高い（または低い）スコアアイテムの数を照会

1. ：次の操作を提供するスコア、陽性用とネガのための1つの二組を必要とします）。
2. 要素の挿入と削除。

上記のポジションの上下の数を知ることで、すでに述べたようにAUCを効率的に更新することができます。その後、アイテムをポジティブ/ネガティブセットから削除し、それぞれネガティブ/ポジティブに挿入する必要があります。 平衡検索ツリーは、両方の操作をO（log（n））で実行できます。

さらに、スコアの実際の値は重要ではなく、位置のみが関係します。これにより、バイナリ索引ツリーを使用した非常に簡単で効率的な実装が可能になります。説明については、http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTreesを参照してください。 また、実際には2つのセットを維持する必要はありません。あなたはすでに与えられたポジションより上のポジティブとネガティブの総数を知っているので、1セットで十分です。