Оценка размера рабочего набора виртуальной машины исходя из гостевых показателей производительности (1187411), страница 5
Текст из файла (страница 5)
Ñâîéñòâî:βˆj − βj∼ N (0, 1)(3.65)se (βj )íå âûïîëíÿåòñÿ, íå ìîæåì òåñòèðîâàòü ãèïîòåçû è ñòðîèòü äîâåðèòåëüíûå èíòåðâàëû íåëüçÿ;4. Ñâîéñòâî:RSSR − RSSU R→ χ2r(3.66)RSSU Rn − kU Ríå âûïîëíÿåòñÿ, ïðîâåðÿòü ãèïîòåçû ñ íåñêîëüêèìè îãðàíè÷åχ2 =íèÿìè íåëüçÿ.39Âûõîäû:1. Îñëàáèòü ïðåäïîñûëêè [28];2. Èñïîëüçîâàòü óñòîé÷èâûå(ðîáàñòíûå) ñòàíäàðòíûå îøèáêè:βˆj − βj→ N (0, 1)seHAC (βj )(3.67)Ñëåäîâàòåëüíî, ðîáàñòíûå ñòàíäàðòíûå îøèáêè ìîæíî èñïîëüçîâàòü äëÿ îöåíêè ãèïîòåç è ïîñòðîåíèÿ äîâåðèòåëüíûõ èíòåðâàëîâ;3.
Èñïîëüçîâàòü ìåòîä ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ (MLE), îïèñàííûé â ñåêöèè 3.2.12.Ìåòîäû îáíàðóæåíèÿ:1. Òåñò Äàðáèíà-Óîòñà.Ïðåäíàçíà÷åí äëÿ ïðîâåðêè ãèïîòåç îá àâòîêîððåëÿöèÿõ 1-ãîïîðÿäêà:t = φ1 t−1 + ut(3.68)Äàííûé òåñò òàê æå òðåáóåò ïðåäïîëîæåíèå î íîðìàëüíîñòèðàñïðåäåëåííîñòè îñòàòêîâ è ñîáëþäåíèÿ óñëîâèÿ ýêçîãåííîñòè(ñìîòðè 3.2.11).Ãèïîòåçû òåñòà:H0 : φ1 = 0(3.69)Ha : φ1 6= 0(3.70)402.
Òåñò Áðîéøà-ÃîäôðèÏðåäíàçíà÷åí äëÿ ïðîâåðêè ãèïîòåç îá àâòîêîððåëÿöèÿõ ïîðÿäêà p:t = φ1 t−1 + φ2 t−2 + · · · + φp t−p + ut(3.71)Ãäå i - îøèáêà â ìîìåíò âðåìåíè i, φi - ñòåïåíü âëèÿíèÿ äàííîéîøèáêè, ut - íåçàâèñèìûé, îäèíàêîâî ðàñïðåäåëåííûé ñëó÷àéíûé êîìïîíåíò.Íå òðåáóåò ïðåäïîëîæåíèÿ î íîðìàëüíîñòè îñòàòêîâ, äîïóñêàåòíàðóøåíèå óñëîâèÿ ýêçîãåííîñòè(ñìîòðè 3.2.11).Ãèïîòåçû òåñòà:3.2.11H0 : φ1 = φ2 = · · · = φk = 0(3.72)Ha : ∃φi 6= 0, i = 1 · · · k(3.73)Ýíäîãåííîñòü è ýêçîãåííîñòüÓñëîâèå ýêçîãåííîñòè - åñëè ìîäåëü ïðåäñòàâëåííà â âèäå:yi = β0 + β1 x1 + β2 x2 + · · · + βk xk + i(3.74)Òî E (i |X) = 0.Ýòî óñëîâèå îáåñïå÷èâàåò àñèìïòîòè÷åñêóþβ̂ → β , è ñõîäèìîñòüíåñìåùåííîñòü îöåíîê ÌÍÊ E β̂|X= β , E β̂ = β×àùå âñåãî ýêçîãåííîñòü ôàêòîðîâ ïîñòóëèðóåòñÿ ïðè ïîñòðîåíèè ìîäåëè.
Òåì íå ìåíåå, ñóùåñòâóþò ìåòîäû, ïîçâîëÿþùèå ïðîâåðèòü ýòè ïðåäïîëîæåíèÿ. Äëÿ ïîäòâåðæäåíèÿ ïðåäïîëîæåíèÿ îáýêçîãåííîñòè èñïîëüçóåòñÿ òåñò Õàóñìàíà.413.2.12Ìåòîä ìàêñèìàëüíîãî ïðàâäîïîäîáèÿÌåòîä ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ - ýòî ìåòîä îöåíèâà-íèÿ íåèçâåñòíîãî ïàðàìåòðà ïóò¼ì ìàêñèìèçàöèè ôóíêöèè ïðàâäîïîäîáèÿ[19].Îñíîâàí íà ïðåäïîëîæåíèè î òîì, ÷òî âñÿ èíôîðìàöèÿ î ñòàòèñòè÷åñêîé âûáîðêå ñîäåðæèòñÿ â ôóíêöèè ïðàâäîïîäîáèÿ.Ïóñòü åñòü âûáîðêà X1 , · · · , Xn èç ðàñïðåäåëåíèÿ Pθ , ãäå θ ∈ Θ íåèçâåñòíûå ïàðàìåòðû îöåíèâàåìîé ìîäåëè.
Ïóñòü L (x|θ) : Θ → R- ôóíêöèÿ ïðàâäîïîäîáèÿ, ãäå x ∈ Rn . Òîãäà òî÷å÷íàÿ îöåíêà:θ̂M LE = θ̂M LE = arg max L (X1 , · · · , Xn |θ) , θ ∈ Θ(3.75)íàçûâàåòñÿ îöåíêîé ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ θ. Òàêèì îáðàçîì îöåíêà ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ ýòî òàêàÿ îöåíêà, êîòîðàÿ ìàêñèìèçèðóåò ôóíêöèþ ïðàâäîïîäîáèÿ ïðè ôèêñèðîâàííîéðåàëèçàöèè âûáîðêè.Îáû÷íî âìåñòî ôóíêöèè ïðàâäîïîäîáèÿ L èñïîëüçóþò åå ëîãàðèôì l = ln L, ò.ê. ýòî îáëåã÷àåò ïîèñê ìàêñèìóìà, òàêèì îáðàçîì:θ̂M LE = θ̂M LE = arg max l (X1 , · · · , Xn |θ) , θ ∈ Θ(3.76)Äëÿ ìàêñèìèçàöèè äàííîé ôóíêöèè ðåøàåòñÿ ñëåäóþùåå óðàâíåíèå äëÿ ïîèñêà ýêñòðåìóìà:g (θ) =δl (x, θ)=0δθÑâîéñòâà:42(3.77)1. Îöåíêè ñîñòîÿòåëüíû:(3.78)θ̂M L → θ, n → ∞2. Àñèìïòîòè÷åñêè íåñìåùåíû:E θ̂M L → θ, n → ∞(3.79)3.
Àñèìïòîòè÷åñêè ýôôåêòèâíû: Äèñïåðñèÿ V ar θ̂M L íàèìåíüøàÿ ñðåäè àñèìïòîòè÷åñêè íåñìåùåííûõ îöåíîê4. Îöåíêè θ̂M L àñèìïòîòè÷åñêè íîðìàëüíî ðàñïðåäåëåííû:θ̂M L ∼ N θ, I −1 , n >> 0(3.80)Ãäå I - èíôîðìàöèÿ ôèøåðà, I = −E (l00 (θ))Ïðîâåðêà ãèïîòåç ïðîèçâîäèòñÿ ïðè ïîìîùè ñïåöèàëüíîãî LRòåñòà(Likelihood Ration, LR).
 ýòîì òåñòå H0 - ñèñòåìà èç q óðàâíåíèé íà íåèçâåñòíûå ïàðàìåòðû, Ha - õîòÿ áû îäíîé èç q óñëîâèé íåâûïîëíåííî. LR = 2 I θ̂ − I θ̂H0∼ χ2q3.2.13(3.81)ÑòàöèîíàðíîñòüÑòàöèîíàðíîñòü - ñâîéñòâî ïðîöåññà íå ìåíÿòü ñâîéñòâà ñ òå-÷åíèåì âðåìåíè. Âðåìåííîé ðÿä íàçûâàåòñÿ ñòàöèîíàðíûì åñëè:1.E (yi ) = const43(3.82)Ðèñ. 3.1: Ëèíåéíàÿ ðåãðåññèÿ ñ breaks.2.V ar (yi ) = const(3.83)Cov(yt , yt−k ) = γk(3.84)3. ñëó÷àå, åñëè ðÿä íå ñòàöèîíàðåí[19]:1.
Îöåíêè ìåòîäîì ÌÍÊ ñìåùåííû â ñòîðîíó 0;2. t ñòàòèñòèêà íå èìååò íîðìàëüíîãî ðàñïðåäåëåíèÿ.Åùå îäíîé ïðîáëåìîé íå ñòîõàñòè÷åñêèõ ðÿäîâ ÿâëÿþòñÿ òàê íàçûâàåìûåbreaks. Breaks - ýòî èçìåíåíèÿ êîýôôèöèåíòîâ ðåãðåññèèñ òå÷åíèåì âðåìåíè.Ïðèìåð ëèíåéíîé ðåãðåññèè ñ breaks ïðèâåäåí íà ðèñóíêå 3.1.Êàê âèäíî íà ïðîìåæóòêå x = 0 · · · 3.5 ëèíåéíàÿ ðåãðåññèÿ èìååòîäíè êîýôôèöèåíòû, ïîñëå äðóãèå.44Ñëåäñòâèåì òàêîãî ïîâåäåíèÿ âðåìåííîãî ðÿäà ÿâëÿåòñÿ áîëüøèåîøèáêè ïðè ïðåäñêàçàíèè.
ÌÍÊ îöåíèâàåò ðåãðåññèþ, îòîáðàæàÿçàâèñèìîñòè â ñðåäíåì[19].Äëÿ îïðåäåëåíèÿ íåñòàöèîíàðíîñòè ðÿäà ñóùåñòâóþò ñëåäóþùèåìåòîäû:1. Ãðàôè÷åñêèé;2. Òåñò Äèêè-Ôóëëåðà(Dicky-Fuller test, ADW test);3. Òåñò KPSS(KwiatkowskiPhillipsSchmidtShin (KPSS) tests).Òàê æå ñóùåñòâóþò òåñòû íà äåòåêöèþ breaks, åñëè èõ òî÷êè íåèçâåñòíû, èñïîëüçóþòñÿ: Quandt likelihood ratio(QLR) statistic.Èäåÿ òåñòà çàêëþ÷àåòñÿ â ñëåäóþùåì, ìû ñòðîèì íîâóþ ìîäåëü:Yt = β0 +β1 Yt−1 +δ1 X1 +γ0 Dt (τ )+γ1 [Dt (τ ) × Yt−1 ]+γ2 [Dt (τ ) × X1 ]+ut(3.85)Ãäå Dt (τ ) - áèíàðíàÿ ïåðåìåííàÿ, êîòîðàÿ ðàâíà 0 äî ìîìåíòàt < τ , è ðàâíà 1 âî âñåõ îñòàëüíûõ ñëó÷àÿõ. Òåñòèðóåòñÿ ãèïîòåçà:H0 : γ0 = γ1 = γ2 = 0. Äëÿ âñåõ τ ïðè ïîìîùè F -ñòàòèñòèêè. Ìàêñèìàëüíîå ñðåäè âñåõ ïðîâåðåííûõ τ çíà÷åíèå F -ñòàòèñòèêè è áóäåòçíà÷åíèåì Quandt likelihood ratio.
Êðèòè÷åñêèå çíà÷åíèÿ òåñòà âûìîæåòå íàéòè â [19] â ñîîòâåòñòâóþùèì ðàçäåëå. Íàïðèìåð, äëÿ 5%óðîâíÿ çíà÷èìîñòè ñ 6-þ îãðàíè÷åíèÿìè(â H0 âõîäèò 6 êîýôôèöèåíòîâ), ýòî çíà÷åíèå ðàâíî 3.37.Êàê ïîêàçàííî â [19] ëó÷øèé ñïîñîá èçáåæàòü ïðîáëåì, âûçûâàåìûõ breaks - ýòî èçìåíÿòü ïàðàìåòðû ðåãðåññèè â çàâèñèìîñòè îòbreaks. Ñïîñîáû îáíàðóæåíèÿ breaks ÿâëÿåòñÿ îòäåëüíîé òåìîé äëÿèññëåäîâàíèÿ.45Òàê æå â [19] óêàçàí îäèí ñïîñîá áîðüáû ñ íåñòàöèîíàðíîñòüþ- ýòî äèôôåðåíöèðîâàíèå âðåìåííîãî ðÿäà.
Ò.å. åñëè ó íàñ åñòüâðåìåííîé ðÿä yt = {y0 , y1 , · · · , ym }, òî ìû ñòðîèì íîâûé âðåìåííîéðÿä âèäà:∆yi = yi − yi−1 , i = 1 · · · m(3.86)Ê ñîæàëåíèþ, êàê áóäåò ïîêàçàííî â 5 ýòîò ìåòîä ïîìîãàåò íåâñåãäà.3.3Àëãîðèòìû êëàñòåðèçàöèèÊëàñòåðèçàöèÿ - ñïîñîá ðàçáèòèÿ äàííûõ íà êëàññû ïî íåêîòîðîéìåòðèêå. Ñóùåñòâóþò ðàçëè÷íûå âèäû àëãîðèòìîâ êëàñòåðèçàöèè[32]:1. Âåðîÿòíîñòíûå ìåòîäû :(a) K-ñðåäíèõ (K-means);(b) K-medians;(c) EM-àëãîðèòì;(d) Àëãîðèòìû ñåìåéñòâà FOREL;(e) Äèñêðèìèíàíòíûé àíàëèç;(f) DBSCAN.2. Ìåòîäû èñêóññòâåííîãî èíòåëëåêòà : âåñüìà óñëîâíàÿãðóïïà, òàê êàê ìåòîäîâ î÷åíü ìíîãî è ìåòîäè÷åñêè îíè âåñüìàðàçëè÷íû.(a) Àëãîðèòì íå÷åòêîé êëàñòåðèçàöèè C-means;46(b) Íåéðîííàÿ ñåòü Êîõîíåíà;(c) Ãåíåòè÷åñêèå àëãîðèòìû.3.
Ëîãè÷åñêèé ìåòîäû . Ïîñòðîåíèå äåíäðîãðàììû îñóùåñòâëÿåòñÿ ñ ïîìîùüþ äåðåâà ðåøåíèé.4. Èåðàðõè÷åñêèå ìåòîäû . Ïðåäïîëàãàåòñÿ íàëè÷èå âëîæåííûõ ãðóïï (êëàñòåðîâ ðàçëè÷íîãî ïîðÿäêà). Àëãîðèòìû â ñâîþî÷åðåäü ïîäðàçäåëÿþòñÿ íà àãëîìåðàòèâíûå (îáúåäèíèòåëüíûå)è äèâèçèâíûå (ðàçäåëÿþùèå). Ïî êîëè÷åñòâó ïðèçíàêîâ èíîãäàâûäåëÿþò ìîíîòåòè÷åñêèå è ïîëèòåòè÷åñêèå ìåòîäû êëàññèôèêàöèè. Èåðàðõè÷åñêàÿ äèâèçèâíàÿ êëàñòåðèçàöèÿ èëè òàêñîíîìèÿ.5. Òåîðåòèêî-ãðàôîâûé ìåòîäû .(a) Ãðàôîâûå àëãîðèòìû êëàñòåðèçàöèè3.3.1K-MeansÎäèí èç íàèáîëåå ïîïóëÿðíûõ àëãîðèòìîâ êëàñòåðèçàöèè.
Èäåÿñîñòîèò â ìèíèìèçàöèè ñóììàðíîãî êâàäðàòíîãî îòêëîíåíèÿ îáúåêòîâ îò öåíòðà êëàñòåðîâ:V =k XX(xj − µj )2(3.87)i=1 xj ∈SjÃäå k - ÷èñëî êëàñòåðîâ, Si - ïîëó÷åííûå êëàñòåðû, i = 1, 2, · · · , kè µi - öåíòðû ìàññ âåêòîðîâ xj ∈ Sj .47Àëãîðèòì èìååò âðåìåííóþ ñëîæíîñòü O 2Ω(k) [33].Ðåçóëüòàò äàííîãî ìåòîäà çàâèñèò îò íà÷àëüíûõ óñòàíîâîê öåíòðîâ ìàññ. Òàê æå ñóùåñòâåííûì íåäîñòàòêîì ÿâëÿåòñÿ òîò ôàêò,÷òî êîëè÷åñòâî êëàñòåðîâ óñòàíàâëèâàåò ïîëüçîâàòåëü, à íå íàõîäèòñÿ àâòîìàòè÷åñêè àëãîðèòìîì.3.3.2DBSCANÀëãîðèòì DBSCAN îòíîñèòñÿ ê òàê íàçûâàåìûì density-based[34]àëãîðèòìàì.
Èäåÿ àëãîðèòìà çàêëþ÷àåòñÿ â ñëåäóþùåì:1. Îáúÿâëÿåòñÿ îêðåñòíîñòü îáúåêòà - r;2. Îáúÿâëÿåòñÿ ìèíèìàëüíîå êîëè÷åñòâî îáúåêòîâ â îêðåñòíîñòè- ;3. Åñëè îáúåêò èìååò â ðàäèóñå r îáúåêòîâ íå ìåíüøå ÷åì ýòî êëàñòåð. Âñå òî÷êè íàõîäÿùèåñÿ â ðàäèóñå r íàçûâàþòñÿíåïîñðåäñòâåííî äîñòèæèìûìè ;4.
Åñëè òî÷êà, ïðèíàäëåæàùàÿ îêðåñòíîñòè íåêîòîðîé òî÷êè m(èýòà òî÷êà âõîäèò â êëàñòåð) òàê æå â ñâîåé îêðåñòíîñòè r èìååòíå ìåíå ñîñåäåé, òî ýòà òî÷êà è åå ñîñåäè â îêðåñòíîñòè rïðèñîåäèíÿþòñÿ ê êëàñòåðó òî÷êè m. Òàêèå òî÷êè íàçûâàþòñÿïðîñòîäîñòèæèìûìè ;5. Âñå íåäîñòèæèìûå òî÷êè ñ÷èòàþòñÿ âûáðîñàìè.Àëãîðèòì èìååò âðåìåííóþ ñëîæíîñòü O (n ln n).48Îñîáåííîñòüþ àëãîðèòìà ÿâëÿåòñÿ òî, ÷òî â îòëè÷èè îò k-meansäàííûé àëãîðèòì âîçâðàùàåò êëàñòåðû íå ñôåðè÷åñêîé ôîðìû. Äëÿðàáîòû íåîáõîäèìî çàäàòü r è , îò êîòîðûõ çàâèñèò ðåçóëüòàò êëàñòåðèçàöèè.3.3.3Èåðàðõè÷åñêàÿ êëàñòåðèçàöèÿÑóùåñòâóåò äâà íàïðàâëåíèÿ, íàçûâàåìûå ñâåðõó-âíèç(top-down,íèñõîäÿùàÿ êëàñòåðèçàöèÿ) è ñíèçó-ââåðõ(buttom-up, âîñõîäÿùàÿ êëàñòåðèçàöèÿ)[ ïåðâîì ñëó÷àå âñå îáúåêòû ñ÷èòàþòñÿ îäíèì êëàññîì, èòåðàòèâíî ïðîèñõîäèò ðàçáèåíèå êëàññà íà ïîäêëàññû íà îñíîâå çàäàííîéìåòðèêè.
Âîñõîäÿùèé àëãîðèòì äåéñòâóåò íàîáîðîò. Íà ñòàðòå âñåîáúåêòû ñ÷èòàþòñÿ îòäåëüíûì êëàññîì, àëãîðèòì èòåðàòèâíî îáúåäèíÿåò íàèáîëåå áëèçêèå êëàññû íà îñíîâå çàäàííîé ìåòðèêè.Èåðàðõè÷åñêèå àëãîðèòìû êëàñòåðèçàöèè èìåþò ñëîæíîñòü[35]:1. Âîñõîäÿùèå àëãîðèòìû êëàñòåðèçàöèè èìåþò ñëîæíîñòü O n3 ;2. Íèñõîäÿùèå àëãîðèòìû êëàñòåðèçàöèè èìåþò ñëîæíîñòü O (2n ).3.3.4ÌåòðèêèÄëÿ èñïîëüçîâàíèÿ ìåòîäîâ êëàñòåðèçàöèè íåîáõîäèìî çàäàòüôóíêöèþ ìåòðèêè, êîòîðàÿ áóäåò èçìåðÿòü ñòåïåíü áëèçîñòè îáúåêòîâ ìåæäó ñîáîé. Äëÿ ñðàâíåíèÿ âðåìåííûõ ðÿäîâ ìîãóò áûòü èñïîëüçîâàííû ðàçëè÷íûå ìåòðèêè:491. Åâêëèäîâî ðàññòîÿíèå [34]. Ðàññòîÿíèå ìåæäó òî÷êàìè â n- ìåðíîì ïðîñòðàíñòâå â ìîìåíò âðåìåíè t ðàññ÷èòûâàåòñÿ ïîôîðìóëå:vu nuX(xti − yti )2dist(xt , yt ) = t(3.88)i=0Ýâêëèäîâà ðàññòîÿíèå ìåæäó âðåìåííûìè ðÿäàìè ýòî ñóììàâñåõ ðàññòîÿíèé ìåæäó òî÷êàìè t = 0 .
. . k :dist(X, Y ) =kX(dist(xi , yi ))(3.89)i=02. Ìàíõýòòåíñêîå ðàññòîÿíèå [34]: Ðàññòîÿíèå ìåæäó òî÷êàìè â n - ìåðíîì ïðîñòðàíñòâå â ìîìåíò âðåìåíè t ðàññ÷èòûâàåòñÿ ïî ôîðìóëå:dist(xt , yt ) =nX|xti − yti |(3.90)i=0Ìàíõýòòåíñêîå ðàññòîÿíèå ìåæäó âðåìåííûìè ðÿäàìè ýòî ñóììà âñåõ ðàññòîÿíèé ìåæäó òî÷êàìè t = 0 . . . k :dist(X, Y ) =kX(dist(xi , yi ))(3.91)i=03. Ðàññòîÿíèå ×åáûøåâà [34]: Ðàññòîÿíèå ìåæäó òî÷êàìè â n- ìåðíîì ïðîñòðàíñòâå â ìîìåíò âðåìåíè t ðàññ÷èòûâàåòñÿ ïîôîðìóëå:l∞ (xt , yt ) = max |xti − yti |50(3.92)Ðèñ.
3.2: Ïðèìåð ñëè÷åíèÿ äâóõ îäèíàêîâûõ, íî ñäâèíóòûõ ñèãíàëîâ ìåòðèêîé Dynamic Time Warping. Íà êàðòèíêåÀïîêàçàííûðàññòîÿíèé è îïòèìàëüíûé åå îáõîä(êðàñíàÿ ëèíèÿ),Câèçóàëèçè-äâà ñðàâíèâàåìûõ ñèãíàëà, íà B ïîêàçàíî êîíñòðóèðîâàíèå ìàòðèöûðóåò ñîïîñòàâëåíèå ñèãíàëîâ.Ðàññòîÿíèå ×åáûøåâà ìåæäó âðåìåííûìè ðÿäàìè ýòî ñóììàâñåõ ðàññòîÿíèé ìåæäó òî÷êàìè t = 0 . . . k :dist(X, Y ) =kX(dist(xi , yi ))(3.93)i=04. Dynamic Time Warping (DTW) [36] - ñïåöèàëüíàÿ ìåòðèêà,ðàçðàáîòàííàÿ äëÿ ñëè÷åíèÿ çâóêîâûõ ñåìïëîâ. Íå ÷óâñòâèòåëüíàÿ ê ñäâèãó, â îòëè÷èè îò ïåðå÷èñëåííûõ âûøå.Ïðåäïîëîæèì ÷òî èìååì äâà âðåìåííûõ ðÿäà:Q = {q0 , q1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
