7

それぞれが特定の「ラベル」でタグ付けされた数十万の文字列 (重要であれば自然言語の文) のデータセットがあるとします。各センテンスには 1 つのラベルがタグ付けされており、約 10 個のラベルがあり、それぞれにデータ セットの約 10% が属しています。ラベル内の文の構造には高度な類似性があります。

上記は機械学習の問題の古典的な例のように聞こえますが、少し異なる質問をしたいと思います。将来のテストデータに一般化しながら、トレーニングデータを正常に分類できる、各ラベルの正規表現のセットをプログラムで生成するための既知の手法はありますか?

文献への参照をいただければ幸いです。これは単純なアルゴリズムではないことを認識しています:)

PS:分類を行う通常の方法は、SVM などの機械学習技術を使用することです。ただし、正規表現を生成する方法を明示的に探しています。(分類自体を行うための機械学習技術ではなく、正規表現を生成するための機械学習技術に満足しています!)

4

3 に答える 3

3

この問題は通常、正規表現ではなく文字列のセットから有限オートマトンを生成する方法として組み立てられますが、FA は等価であるため明らかに RE を生成できます。

オートマトン誘導を検索すると、GA アプローチを含む、このトピックに関するかなり多くの文献を見つけることができるはずです。

于 2012-05-25T08:12:36.927 に答える
1

私の知る限り、これは進化計算における現在の研究対象です。

ここではいくつかの例を示します。

スライド 40 ～ 44 を参照してください。

https://cs.byu.edu/sites/default/files/Ken_De_Jong_slides.pdf (この回答の投稿時点でスライドが存在します)。

また、参照してください

http://www.citeulike.org/user/bartolialberto/article/10710768

GECCO 2012 で発表されたシステムの詳細なレビューについては、

于 2012-07-16T14:41:00.227 に答える
0

注： これが何らかの助けになるかもしれません。a以下の関数は、およびの指定された値に対して RegEx パターンを生成しbます。whereaとbboth はアルファ文字列です。そして、関数は とのRegEx間の範囲に一致する公平なパターンを生成します。関数はパターンを生成するために最初の 3 文字のみを使用し、一般的な RegEx 支持のヒントを備えた言語の関数のようなものを生成します。abresultstarts-with()

簡単な VB.NET の例

Public Function GetRangePattern(ByVal f_surname As String, ByVal l_surname As String) As String
        Dim f_sn, l_sn As String
        Dim mnLength% = 0, mxLength% = 0, pdLength% = 0, charPos% = 0
        Dim fsn_slice$ = "", lsn_slice$ = ""
        Dim rPattern$ = "^"
        Dim alphas As New Collection
        Dim tmpStr1$ = "", tmpStr2$ = "", tmpStr3$ = ""

        '///init local variables
        f_sn = f_surname.ToUpper.Trim
        l_sn = l_surname.ToUpper.Trim

        '///do null check
        If f_sn.Length = 0 Or l_sn.Length = 0 Then
            Return "-!ERROR!-"
        End If

        '///return if both equal
        If StrComp(f_sn, l_sn, CompareMethod.Text) = 0 Then
            Return "^" & f_sn & "$"
        End If

        '///return if 1st_name present in 2nd_name
        If InStr(1, l_sn, f_sn, CompareMethod.Text) > 0 Then
            tmpStr1 = f_sn
            tmpStr2 = l_sn.Replace(f_sn, vbNullString)
            If Len(tmpStr2) > 1 Then
                tmpStr3 = "[A-" & tmpStr2.Substring(1) & "]*"
            Else
                tmpStr3 = tmpStr2 & "*"
            End If
            tmpStr1 = "^" & tmpStr1 & tmpStr3 & ".*$"
            tmpStr1 = tmpStr1.ToUpper
            Return tmpStr1
        End If

        '///initialize alphabets
        alphas.Add("A", CStr(Asc("A")))
        alphas.Add("B", CStr(Asc("B")))
        alphas.Add("C", CStr(Asc("C")))
        alphas.Add("D", CStr(Asc("D")))
        alphas.Add("E", CStr(Asc("E")))
        alphas.Add("F", CStr(Asc("F")))
        alphas.Add("G", CStr(Asc("G")))
        alphas.Add("H", CStr(Asc("H")))
        alphas.Add("I", CStr(Asc("I")))
        alphas.Add("J", CStr(Asc("J")))
        alphas.Add("K", CStr(Asc("K")))
        alphas.Add("L", CStr(Asc("L")))
        alphas.Add("M", CStr(Asc("M")))
        alphas.Add("N", CStr(Asc("N")))
        alphas.Add("O", CStr(Asc("O")))
        alphas.Add("P", CStr(Asc("P")))
        alphas.Add("Q", CStr(Asc("Q")))
        alphas.Add("R", CStr(Asc("R")))
        alphas.Add("S", CStr(Asc("S")))
        alphas.Add("T", CStr(Asc("T")))
        alphas.Add("U", CStr(Asc("U")))
        alphas.Add("V", CStr(Asc("V")))
        alphas.Add("W", CStr(Asc("W")))
        alphas.Add("X", CStr(Asc("X")))
        alphas.Add("Y", CStr(Asc("Y")))
        alphas.Add("Z", CStr(Asc("Z")))

        '///populate max-min length values
        mxLength = f_sn.Length
        If l_sn.Length > mxLength Then
            mnLength = mxLength
            mxLength = l_sn.Length
        Else
            mnLength = l_sn.Length
        End If
        '///padding values
        pdLength = mxLength - mnLength
        f_sn = f_sn.PadRight(mxLength, "A")
        'f_sn = f_sn.PadRight(mxLength, "~")
        l_sn = l_sn.PadRight(mxLength, "Z")
        'l_sn = l_sn.PadRight(mxLength, "~")

        '///get a range like A??-B??
        If f_sn.Substring(0, 1).ToUpper <> l_sn.Substring(0, 1).ToUpper Then
            fsn_slice = f_sn.Substring(0, 3).ToUpper
            lsn_slice = l_sn.Substring(0, 3).ToUpper
            tmpStr1 = fsn_slice.Substring(0, 1) & fsn_slice.Substring(1, 1) & "[" & fsn_slice.Substring(2, 1) & "-Z]"
            tmpStr2 = lsn_slice.Substring(0, 1) & lsn_slice.Substring(1, 1) & "[A-" & lsn_slice.Substring(2, 1) & "]"
            tmpStr3 = "^(" & tmpStr1 & "|" & tmpStr2 & ").*$"
            Return tmpStr3
        End If

        '///looping charwise
        For charPos = 0 To mxLength
            fsn_slice = f_sn.Substring(charPos, 1)
            lsn_slice = l_sn.Substring(charPos, 1)
            If StrComp(fsn_slice, lsn_slice, CompareMethod.Text) = 0 Then
                rPattern = rPattern & fsn_slice
            Else
                'rPattern = rPattern & "("
                If charPos < mxLength Then
                    Try
                        If Asc(fsn_slice) < Asc(lsn_slice) Then
                            tmpStr1 = fsn_slice & "[" & f_sn.Substring(charPos + 1, 1) & "-Z" & "]|"
                            If CStr(alphas.Item(Key:=CStr(Asc(fsn_slice) + 1))) < CStr(alphas.Item(Key:=CStr(Asc(lsn_slice) - 1))) Then
                                tmpStr2 = "[" & CStr(alphas.Item(Key:=CStr(Asc(fsn_slice) + 1))) & "-" & CStr(alphas.Item(Key:=CStr(Asc(lsn_slice) - 1))) & "]|"
                            Else
                                tmpStr2 = vbNullString
                            End If
                            tmpStr3 = lsn_slice & "[A-" & l_sn.Substring(charPos + 1, 1) & "]"
                            rPattern = rPattern & "(" & tmpStr1 & tmpStr2 & tmpStr3 & ").*$"
                            'MsgBox("f_sn:= " & f_sn & " -- l_sn:= " & l_sn & vbCr & rPattern)
                            Exit For
                        Else
                            Return "-#ERROR#-"
                        End If
                    Catch ex As Exception
                        Return "-|ERROR|-" & ex.Message
                    End Try
                End If
            End If
        Next charPos
        Return rPattern
    End Function

そして、それは次のように呼ばれます

?GetRangePattern("ABC","DEF")

これを生成します

"^(AB[C-Z]|DE[A-F]).*$"
于 2012-05-24T17:40:22.453 に答える