WikiDer > Уақыттың өзгеруі қашықтығы

Бұл мақалада бірнеше мәселе бар. Өтінемін көмектесіңіз оны жақсарту немесе осы мәселелерді талқылау талқылау беті. (Бұл шаблон хабарламаларын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала тақырыпты білмейтіндерге контексттің жеткіліксіздігін қамтамасыз етеді. Өтінемін көмектесіңіз мақаланы жақсарту арқылы оқырманға көбірек контекст беру. (Қараша 2016) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала оқырмандардың көпшілігінің түсінуіне тым техникалық болуы мүмкін. өтінемін оны жақсартуға көмектесу дейін оны мамандар емес адамдарға түсінікті етіңіз, техникалық мәліметтерді жоймай. (Қараша 2016) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала көп қажет басқа мақалаларға сілтемелер көмектесу оны энциклопедияға енгізу. Өтінемін көмектесіңіз осы мақаланы жақсарту сілтемелер қосу арқылы мәнмәтінге сәйкес келетін бар мәтін ішінде. (Қыркүйек 2016) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала болып табылады жетім, басқа мақалалар сияқты емес оған сілтеме. өтінемін сілтемелерді енгізу осы параққа қатысты мақалалар; көріңіз Сілтеме құралын табыңыз ұсыныстар үшін. (Қыркүйек 2016) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

Уақыттың өзгеруі қашықтығы (TWED) - дискретті қашықтық өлшемі уақыт қатары уақыт «икемділігімен» сәйкес келеді. Басқа қашықтық шараларымен салыстырғанда, (мысалы, DTW (Уақыттың динамикасы) немесе LCS (Ең көп таралған салдарлық проблема)), TWED - бұл а метрикалық. Оның есептеу уақытының күрделілігі мынада ${ displaystyle O (n ^ {2})}$, бірақ іздеу кеңістігін азайту үшін дәлізді қолдану арқылы кейбір нақты жағдайларда күрт азайтуға болады. Оның жад кеңістігінің күрделілігін төмендетуге болады ${ displaystyle O (n)}$. Оны алғаш рет 2009 жылы П.Ф. Марто.

Анықтама

${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {p}, B_ {1} ^ {q}) = Min { begin {case} delta _ { lambda, nu} (A_ {1} ^ {p-1}, B_ {1} ^ {q}) + Gamma (a_ {p} ^ {'} to Lambda) және { rm {delete in A}} delta _ { lambda, nu} (A_ {1} ^ {p-1}, B_ {1} ^ {q-1}) + Gamma (a_ {p} ^ {'} to b_ {q} ^ {'}) & { rm {match or substitution}} delta _ { lambda, nu} (A_ {1} ^ {p}, B_ {1} ^ {q- 1}) + Gamma ( Lambda to b_ {q} ^ {'}) & { rm {delete in B}} end {case}}}$
ал

${ displaystyle Gamma ( alpha _ {p} ^ {'} to Lambda) = d_ {LP} (a_ {p} ^ {'}, a_ {p-1} ^ {'}) + nu cdot (t_ {a_ {p}} - t_ {a_ {p-1}}) + lambda}$
${ displaystyle Gamma ( alpha _ {p} ^ {'} to b_ {q} ^ {'}) = d_ {LP} (a_ {p} ^ {'}, b_ {q} ^ {'} ) + d_ {LP} (a_ {p-1} ^ {'}, b_ {q-1} ^ {'}) + nu cdot (| t_ {a_ {p}} - t_ {b_ {q}) } | + | t_ {a_ {p-1}} - t_ {b_ {q-1}} |)}$
${ displaystyle Gamma ( Lambda to b_ {q} ^ {'}) = d_ {LP} (b_ {p} ^ {'}, b_ {p-1} ^ {'}) + nu cdot (t_ {b_ {q}} - t_ {b_ {q-1}}) + lambda}$

Ал рекурсия болса${ displaystyle delta _ { lambda, nu}}$инициалданған:
${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {0}, B_ {1} ^ {0}) = 0,}$
${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {0}, B_ {1} ^ {j}) = infty { rm {{for } j geq 1}} }$
${ displaystyle delta _ { lambda, nu} (A_ {1} ^ {i}, B_ {1} ^ {0}) = infty { rm {{for } i geq 1}} }$
бірге${ displaystyle a '_ {0} = b' _ {0} = 0}$

Іске асыру

TWED-алгоритмінің C немесе Matlab-та орындалуын авторлардың үй парағынан жүктеуге болады^[1]

TWED R-ді енгізу TraMineR-ге, күйлердің немесе оқиғалардың тізбегін сипаттайтын және бейнелейтін, сонымен қатар жалпы дискретті дәйектілік деректерді сипаттайтын және бейнелейтін R пакетіне біріктірілген.^[2]

Қосымша, cuTWED TWED-тің CUDA жеделдетілген енгізілуі болып табылады, ол Г.Райттың арқасында жетілдірілген алгоритмді қолданады (2020). Бұл әдіс жадында сызықтық және жаппай параллелизацияланған. cuTWED CUDA C / C ++ тілінде жазылған, питон байланыстырумен бірге, сонымен қатар Marteau сілтемесін енгізу үшін питон байланыстырады.

Python

импорт мылқау сияқты npдеф Dlp(A, B, б=2):    құны = np.сома(np.күш(np.абс(A - B), б))    қайту np.күш(құны, 1 / б)деф твед(A, уақыт SA, B, timeSB, жоқ, _lambda):    # [арақашықтық, DP] = TWED (A, timeSA, B, timeSB, lambda, nu)    # Берілген уақыт А және В сериялары үшін уақытты өзгертудің қашықтығын есептеу (TWED)    #    # A: = А қатарлары (мысалы, [10 2 30 4])    # timeSA: = А уақыттық қатарының уақыт белгісі (мысалы, 1: 4)    # B: = В қатарлары    # timeSB: = В қатарларының уақыт штампы    # lambda: = Жою әрекеті үшін айыппұл    # nu: = Серпімділік параметрі - nu> = 0 қашықтықты өлшеу үшін қажет    # Анықтама:    # Марто, П .; Ф. (2009). «Уақыт тізбегін сәйкестендіру үшін қаттылықты реттей отырып, уақыттың өзгеруінің қашықтығы».    # IEEE транзакциясы шаблонды талдау және машиналық интеллект. 31 (2): 306-318. arXiv: cs / 0703033    # http://people.irisa.fr/Pierre-Francois.Marteau/    # Кіріс аргументтерін тексеріңіз    егер лен(A) != лен(уақыт SA):        басып шығару(«А ұзындығы АС уақытына тең емес»)        қайту Жоқ, Жоқ    егер лен(B) != лен(timeSB):        басып шығару(«B ұзындығы SB уақытының ұзындығына тең емес»)        қайту Жоқ, Жоқ    егер жоқ < 0:        басып шығару(«nu теріс»)        қайту Жоқ, Жоқ    # Толтырғыш қосыңыз    A = np.массив([0] + тізім(A))    уақыт SA = np.массив([0] + тізім(уақыт SA))    B = np.массив([0] + тізім(B))    timeSB = np.массив([0] + тізім(timeSB))    n = лен(A)    м = лен(B)    # Динамикалық бағдарламалау    DP = np.нөлдер((n, м))    # DP Matrix инициализациясы және бірінші жол мен бағанды ​​шексіздікке орнатыңыз    DP[0, :] = np.инф    DP[:, 0] = np.инф    DP[0, 0] = 0    # Минималды шығынды есептеңіз    үшін мен жылы ауқымы(1, n):        үшін j жылы ауқымы(1, м):            # Әр түрлі операциялардың құнын есептеңіз және үнемдеңіз            C = np.бір((3, 1)) * np.инф            # Жою            C[0] = (                DP[мен - 1, j]                + Dlp(A[мен - 1], A[мен])                + жоқ * (уақыт SA[мен] - уақыт SA[мен - 1])                + _lambda            )            # В жою            C[1] = (                DP[мен, j - 1]                + Dlp(B[j - 1], B[j])                + жоқ * (timeSB[j] - timeSB[j - 1])                + _lambda            )            # Екі уақыт қатарында деректер нүктелерін сақтаңыз            C[2] = (                DP[мен - 1, j - 1]                + Dlp(A[мен], B[j])                + Dlp(A[мен - 1], B[j - 1])                + жоқ * (абс(уақыт SA[мен] - timeSB[j]) + абс(уақыт SA[мен - 1] - timeSB[j - 1]))            )            # Әрекетті минималды шығындармен таңдап, DP Matrix-ті жаңартыңыз            DP[мен, j] = np.мин(C)    қашықтық = DP[n - 1, м - 1]    қайту қашықтық, DP

Артқа шегіну, үнемді жолды табу үшін:

деф кері шегіну(DP):    # [best_path] = БЕКЕРТУ (DP)    # Ең үнемді жолды есептеңіз    # DP: = TWED функциясының DP матрицасы    х = np.пішін(DP)    мен = х[0] - 1    j = х[1] - 1    # Жолдардың индекстері қарсы бағытта сақталады    # path = np.ones ((i + j, 2)) * np.inf;    ең жақсы_жол = []    қадамдар = 0    уақыт мен != 0 немесе j != 0:        ең жақсы_жол.қосу((мен - 1, j - 1))        C = np.бір((3, 1)) * np.инф        # Екі уақыт қатарында деректер нүктелерін сақтаңыз        C[0] = DP[мен - 1, j - 1]        # Жою        C[1] = DP[мен - 1, j]        # В жою        C[2] = DP[мен, j - 1]        # Ең төменгі шығындар индексін табыңыз        idx = np.аргмин(C)        егер idx == 0:            # Екі уақыт қатарында деректер нүктелерін сақтаңыз            мен = мен - 1            j = j - 1        элиф idx == 1:            # Жою            мен = мен - 1            j = j        басқа:            # В жою            мен = мен            j = j - 1        қадамдар = қадамдар + 1    ең жақсы_жол.қосу((мен - 1, j - 1))    ең жақсы_жол.кері()    қайту ең жақсы_жол[1:]

MATLAB

функциясы[арақашықтық, DP] =твед(A, timeSA, B, timeSB, lambda, nu)% [арақашықтық, DP] = TWED (A, timeSA, B, timeSB, lambda, nu)    Берілген уақыттық А және В сериялары үшін уақытты есептеудің қашықтықты есептеу (TWED)    %    % A: = А қатарлары (мысалы, [10 2 30 4])    % timeSA: = А уақыттық қатарының уақыт белгісі (мысалы, 1: 4)    % B: = В қатарлары    % timeSB: = В қатарларының уақыт штампы    % lambda: = Жою әрекеті үшін айыппұл    % nu: = Серпімділік параметрі - қашықтықты өлшеу үшін қажет nu> = 0    %    % Код авторы: P.-F. Марто - http://people.irisa.fr/Pierre-Francois.Marteau/     Кіріс аргументтерін тексеріңіз    егер ұзындық (A) ~ = ұзындық (уақыт SA)        ескерту('А ұзындығы АС уақытына тең емес')        қайтуСоңы    егер ұзындық (B) ~ = ұзындық (уақыт SB)        ескерту('B ұзындығыSB уақыт ұзақтығына тең емес')        қайтуСоңы    егер nu <0        ескерту(«теріс»)        қайтуСоңы    Толтырғыш қосыңыз    A = [0 A];    уақыт SA = [0 уақыт SA];    B = [0 B];    timeSB = [0 timeSB];     % Динамикалық бағдарламалау    DP = нөлдер(ұзындығы(A), ұзындығы(B));     DP Matrix инициализациясы және бірінші жол мен бағанды ​​шексіздікке орнату    DP(1, :) = инф;    DP(:, 1) = инф;    DP(1, 1) = 0;     n = ұзындығы(уақыт SA);    м = ұзындығы(timeSB);    Минималды құнын есептеу    үшін i = 2: n        үшін j = 2: м            құны = Dlp(A(мен), B(j));                     % Әр түрлі операциялардың құнын есептеңіз және үнемдеңіз            C = бір(3, 1) * инф;                     A-да жою            C(1) = DP(мен - 1, j) + Dlp(A(мен - 1), A(мен)) + жоқ * (уақыт SA(мен) - уақыт SA(мен - 1)) + лямбда;            В-да жою            C(2) = DP(мен, j - 1) + Dlp(B(j - 1), B(j)) + жоқ * (timeSB(j) - timeSB(j - 1)) + лямбда;            % Екі уақыт қатарында деректер нүктелерін сақтаңыз            C(3) = DP(мен - 1, j - 1) + Dlp(A(мен), B(j)) + Dlp(A(мен - 1), B(j - 1)) + ...            жоқ * (абс(уақыт SA(мен) - timeSB(j)) + абс(уақыт SA(мен - 1) - timeSB(j - 1)));                     % Минималды шығындармен операцияны таңдап, DP Matrix-ті жаңартыңыз            DP(мен, j) = мин(C);        СоңыСоңы     қашықтық = DP(n, м);     Евклидтік қашықтықты есептеу функциясы    функциясы[құны] =Dlp(A, B)құны = кв(сома((A - B) .^ 2, 2));    СоңыСоңы

Артқа шегіну, үнемді жолды табу үшін:

функциясы[жол] =кері шегіну(DP)% [жол] = БЕРУ (DP)    Ең тиімді жолды есептеңіз    % DP: = TWED функциясының DP матрицасы     х = өлшемі(DP);    мен = х(1);    j = х(2);     % Жолдардың индекстері қарсы бағытта сақталады    жол = бір(мен + j, 2) * Инф;     қадамдар = 1;    уақыт (мен ~= 1 || j ~= 1)        жол(қадамдар, :) = [мен; j];             C = бір(3, 1) * инф;             % Екі уақыт қатарында деректер нүктелерін сақтаңыз        C(1) = DP(мен - 1, j - 1);        A-да жою        C(2) = DP(мен - 1, j);        В-да жою        C(3) = DP(мен, j - 1);             % Ең төменгі шығындар индексін табыңыз        [~, idx] = мин(C);             қосқыш idx            іс 1                % Деректер нүктелерін екі уақыт қатарында сақтаңыз                мен = мен - 1;                j = j - 1;            іс 2                A-да жою                мен = мен - 1;                j = j;            іс 3                В-да жою                мен = мен;                j = j - 1;        Соңы        қадамдар = қадамдар + 1;    Соңы    жол (қадамдар, :) = [мен j];     Жол кері бағытта есептелді.    жол = жол(1:қадамдар, :);    жол = жол(Соңы: - 1:1, :); Соңы

Әдебиеттер тізімі

• Марто, П .; Ф. (2009). «Уақыт тізбегін сәйкестендіру үшін қаттылықты реттей отырып, уақыттың өзгеруінің қашықтығы». Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары. 31 (2): 306–318. arXiv:cs / 0703033. дои:10.1109 / TPAMI.2008.76.