3

私の問題は、URLパスを比較して、それらが類似しているかどうかを推測する必要があることです。以下に、処理するサンプルデータを示します。

# GROUP 1
/robots.txt

# GROUP 2
/bot.html

# GROUP 3
/phpMyAdmin-2.5.6-rc1/scripts/setup.php
/phpMyAdmin-2.5.6-rc2/scripts/setup.php
/phpMyAdmin-2.5.6/scripts/setup.php
/phpMyAdmin-2.5.7-pl1/scripts/setup.php
/phpMyAdmin-2.5.7/scripts/setup.php
/phpMyAdmin-2.6.0-alpha/scripts/setup.php
/phpMyAdmin-2.6.0-alpha2/scripts/setup.php

# GROUP 4
//phpMyAdmin/

レーベンシュタイン距離を比較してみましたが、私にとっては十分に正確ではありません。100％正確なアルゴリズムは必要ありませんが、90％以上は必須だと思います。

ある種の分類子が必要だと思いますが、問題は、新しいデータの各部分に、新しい未知のクラスに分類する必要のあるパスが含まれている可能性があることです。

私を正しい方向に向けていただけませんか。

ありがとう

4

3 に答える 3

1

レーベンシュタイン距離が最良のオプションですが、距離を調整します。加重編集距離を使用する必要があり、場合によってはトークン（単語と数字）のパスを分割する必要があります。したがって、たとえば「2.5.6-rc2と2.5.6」のようなバージョンは0の重みの違いとして扱うことができますが、phpMyAdminやjavaMyAdminのような名前トークンは1の重みの違いを与えます。

于 2011-10-19T09:21:15.203 に答える
1

@ jakub.gierylukの提案を確認したところ、私が満足する解決策を偶然見つけました。「元々は生物学的配列データセットの冗長性を減らすために考案されたHobohmクラスタリングアルゴリズム」です。

Bruno Vecchiによって実装されたPERLライブラリのテストは、私に本当に良い結果をもたらしました。唯一の問題は、Pythonの実装が必要なことですが、インターネットでPythonを見つけるか、自分でコードを再実装できると信じています。

次のことは、私はまだこのアルゴリズムの能動学習能力をチェックしていないということです;）

于 2011-10-20T13:12:05.973 に答える
0

それがあなたの質問に対する正確な答えではないことは知っていますが、k-meansアルゴリズムに精通していますか？

レーベンシュタインでもここで機能すると思いますが、難しいのは、そのアプローチで重心を計算する方法です。

おそらく、入力セットを互いに素なサブセットに分割し、各サブセットの各URLについて、同じサブセット内の他のすべてのURLまでの距離を計算し、距離の合計が最も小さいURLをセントロイドにする必要があります（もちろん、入力セットの大きさについて。巨大なセットの場合、そうするのは良い考えではないかもしれません）。

k-meansの良いところは、完全にランダムな除算から始めて、それを繰り返し改善できることです。

k-meansの悪い点は、k開始する前に正確にする必要があることです。ただし、実行中（おそらく、最初の数回の反復後に状況が安定した場合）、各セットの類似性を測定できます。それが低い場合は、セットを2つのサブセットに分割し、同じアルゴリズムを続行できます。

于 2011-10-18T22:01:26.057 に答える