5,924 matches
-
un număr aproximativ egal de componente. Metode de partiționare iterativătc "Metode de partiționare iterativă" În contrast cu metodele de grupare ierarhice, cele de partiționare nu au formă arborescentă, ci pornesc de la o împărțire inițială a obiectelor într-un număr specificat de grupuri. Algoritmul generic de grupare într-o metodă de partiționare iterativă este următorul. Se pornește de la o partiționare a setului de date într-un număr specificat de grupuri (k grupuri). Se calculează centroidul fiecăruia dintre aceste grupuri (centrul de cluster). Fiecare obiect
[Corola-publishinghouse/Science/2075_a_3400]
-
de k grupuri, reactualizând calculele pentru tot setul de date. În continuare, se calculează centroizii acestor grupuri. Se repetă procedura- realocarea obiectelor în raport cu noii centroizi - până când nu se mai produc schimbări în componența grupurilor. Există mai multe variante ale acestui algoritm: (i) Se pornește nu de la o partiție oarecare, ci direct de la k puncte care să funcționeze ca niște „centri inițiali de cluster” (cluster seeds). Aceștia sunt selectați după o logică oarecare, putând fi obținuți de pildă prin realizarea în prealabil
[Corola-publishinghouse/Science/2075_a_3400]
-
un al doilea grup din toate obiectele aflate la distanța respectivă. Dacă un obiect a intrat deja într-un grup, el nu va fi considerat pentru grupurile următoare. Se continuă astfel până când se obțin k grupuri. Mai departe, se urmează algoritmul general descris mai sus2. Există câteva avantaje ale acestui tip de metode, față de cele ierarhice aglomerative. Spre deosebire de primul tip de metode, care necesită calculul unei matrice de distanțe considerabil de mare (matrice simetrică de ordinul N, unde N este numărul
[Corola-publishinghouse/Science/2075_a_3400]
-
unică pentru un număr dat de grupuri (Single solution), fie pentru mai multe soluții, corespunzătoare unor numere diferite de grupuri, specificate de către cercetător (Range of solutions). În meniul deschis de butonul Plots, putem cere două forme de reprezentare grafică a algoritmului de grupare. Dendograma este una dintre opțiuni. Cealaltă poartă numele de Icicle (în românește „țurțure”), care indică de asemenea modul în care sunt grupate obiectele în pași succesivi. Cu cât obiectele sunt situate mai aproape de capătul unui țurțure, cu atât
[Corola-publishinghouse/Science/2075_a_3400]
-
Funcțiile de transformare pot fi ordinale - ele păstrează rangul (ordinea) dintre proximități. Relația definită de f nu este una precisă în termeni de cifre, ci una monotonă: rangurile transformatelor f(x) corespund cu rangurile lui x2. Trebuie să găsim un algoritm prin care să aducem valorile distanțelor dij cât mai aproape de valorile transformatelor proximităților f(€δij). Cel mai probabil, configurația de puncte D aleasă inițial nu va reflecta cel mai bine situarea relativă a obiectelor în termeni de proximități Δ. Acest
[Corola-publishinghouse/Science/2075_a_3400]
-
ameliorarea configurației de puncte. Pentru a face acest lucru vom selecta o nouă configurație de puncte, care să redea mai bine relațiile dintre obiecte, și se va recalcula măsura de adecvare. Dacă în continuare aceasta este prea mare, vom continua algoritmul. Ne vom opri fie atunci când măsura de adecvare nu se mai schimbă, în ciuda ameliorării configurației de puncte, fie atunci când este îndeplinit un criteriu de convergență, adică măsura de adecvare a ajuns sub un prag stabilit de cercetător (cât mai aproape de
[Corola-publishinghouse/Science/2075_a_3400]
-
de puncte, fie atunci când este îndeplinit un criteriu de convergență, adică măsura de adecvare a ajuns sub un prag stabilit de cercetător (cât mai aproape de zero). Relațiile subiective (percepute) dintre obiecte vor fi reprezentate de ultima configurație de puncte a algoritmului. Realizarea unei analize de scalare multidimensionalătc " Realizarea unei analize de scalare multidimensională" Scalarea multidimensională este o tehnică de analiză decompozițională. Ce înseamnă acest lucru? Metodele decompoziționale prelucrează măsuri globale sau generale de similaritate, pe baza cărora sunt produse hărți perceptuale
[Corola-publishinghouse/Science/2075_a_3400]
-
subiect, pentru a obține o bază de date care să conțină informația pentru toți subiecții din eșantion. În acest caz, scalarea poate ține cont de diferențele individuale în calcule. Acest tip de analiză, care ia în considerare diferențele individuale în algoritmul de obținere a reprezentării poziționării relative a obiectelor, se numește scalare multidimensională repetată sau Replicated Multidimensional Scaling (RMDS) în engleză. Diferența principală față de scalarea multidimensională simplă, cunoscută în engleză drept Classic Multidimensional Scaling (CMDS), este faptul că permite analiza mai
[Corola-publishinghouse/Science/2075_a_3400]
-
acuratețe dimensionalitatea datelor de intrare (a proximităților). Aici merită să notăm că, indiferent de caracterul real metric sau non-metric al datelor, soluțiile obținute prin aplicarea unei metode non-metrice sau a uneia metrice sunt foarte asemănătoare. Mai sus am arătat pașii algoritmului prin care se obține configurația de puncte ce reflectă relațiile percepute dintre obiecte. Pentru obținerea soluției vom folosi un pachet de programe statistice pe calculator care realizează algoritmul în funcție de specificările date de cercetător: matricea inițială de date (similaritate sau preferințe
[Corola-publishinghouse/Science/2075_a_3400]
-
sau a uneia metrice sunt foarte asemănătoare. Mai sus am arătat pașii algoritmului prin care se obține configurația de puncte ce reflectă relațiile percepute dintre obiecte. Pentru obținerea soluției vom folosi un pachet de programe statistice pe calculator care realizează algoritmul în funcție de specificările date de cercetător: matricea inițială de date (similaritate sau preferințe), modalitatea de obținere a matricei de proximități, criteriul de oprire a algoritmului, dimensionalitatea modelului. Voi descrie acest lucru pentru SPSS 10.1 în secțiunea următoare. Decizia asupra dimensionalității
[Corola-publishinghouse/Science/2075_a_3400]
-
dintre obiecte. Pentru obținerea soluției vom folosi un pachet de programe statistice pe calculator care realizează algoritmul în funcție de specificările date de cercetător: matricea inițială de date (similaritate sau preferințe), modalitatea de obținere a matricei de proximități, criteriul de oprire a algoritmului, dimensionalitatea modelului. Voi descrie acest lucru pentru SPSS 10.1 în secțiunea următoare. Decizia asupra dimensionalității modeluluitc "Decizia asupra dimensionalității modelului" Alegerea numărului de dimensiuni în care să fie reprezentate obiectele este importantă pentru acuratețea redării relațiilor dintre ele. În
[Corola-publishinghouse/Science/2075_a_3400]
-
din pachetul SPSS Base, prezentă în versiuni anterioare ale SPSS și care a rămas încorporată și în versiunea 10.1. Cea de-a doua, conținută în pachetul SPSS Categories, este o variantă mai performantă a aceleiași proceduri. Proxscal oferă un algoritm accelerat pentru anumite modele și permite punerea unor condiții asupra spațiului reprezentării 1. În cele ce urmează voi descrie procedura Alscal din pachetul SPSS Base2. Procedura se accesează din meniul Analyze, Scale, Multidimensional Scaling (Alscal) și deschide o fereastră în
[Corola-publishinghouse/Science/2075_a_3400]
-
de dimensiuni pe care dorim să îl aibă soluția. În meniul deschis prin apăsarea butonului Options putem cere afișarea reprezentării grafice a soluțiilor individuale sau comune, matricea de date (proximități) și caracteristicile modelului. Tot aici specificăm criteriul de convergență a algoritmului (valoarea minimă pentru s-stress și numărul maxim de iterații). Programul va produce și câteva diagrame care raportează transformatele proximităților (numite disparities în engleză) la distanțe, proximitățile la distanțe sau proximitățile la transformatele proximităților. Aceste diagrame sunt foarte utile în evaluarea
[Corola-publishinghouse/Science/2075_a_3400]
-
Pitești se găsește la sud de București. Teoretic, dacă distanțele introduse de noi ar fi cele geografice, măsurate ca distanțe euclidiene (ca linii drepte între orașe), nu ar trebui să apară inexactități, căci distanțele modelului scalat ar corespunde perfect, conform algoritmului de reprezentare, transformatelor proximităților. De ce apar totuși mici erori? Explicația este simplă și nu se referă nici la algoritm, nici la specificația modelului, ci la datele noastre. Distanțele (proximitățile) introduse în baza de date nu sunt distanțele reale dintre orașe
[Corola-publishinghouse/Science/2075_a_3400]
-
distanțe euclidiene (ca linii drepte între orașe), nu ar trebui să apară inexactități, căci distanțele modelului scalat ar corespunde perfect, conform algoritmului de reprezentare, transformatelor proximităților. De ce apar totuși mici erori? Explicația este simplă și nu se referă nici la algoritm, nici la specificația modelului, ci la datele noastre. Distanțele (proximitățile) introduse în baza de date nu sunt distanțele reale dintre orașe, ci distanțele dintre orașe pe calea ferată. Cum calea ferată nu leagă orașele în linie dreaptă, ci are diferite
[Corola-publishinghouse/Science/2075_a_3400]
-
REȚELE DE SORTARE Așa cum se știe algoritmii de sortare pentru calculatoare seriale (mașini cu acces aleator sau RAM-uri) permit execuția doar a unei singure operații la un moment dat. În această lucrare voi încerca să mă ocup într-o oarecare măsura și de investigarea algoritmilor de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
știe algoritmii de sortare pentru calculatoare seriale (mașini cu acces aleator sau RAM-uri) permit execuția doar a unei singure operații la un moment dat. În această lucrare voi încerca să mă ocup într-o oarecare măsura și de investigarea algoritmilor de sortare bazați pe un model de calcul care folosește o rețea de comparare, rețea în care pot fi executate simultan mai multe operații de comparare. Rețelele de comparare diferă de RAM-uri prin două aspecte importante. În primul rând
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
calcul care folosește o rețea de comparare, rețea în care pot fi executate simultan mai multe operații de comparare. Rețelele de comparare diferă de RAM-uri prin două aspecte importante. În primul rând, ele pot executa doar comparații. Astfel, un algoritm cum ar fi counting sort (sortarea prin numărare) nu poate fi implementat pe o rețea de comparare. În al doilea rând, dacă în cazul modelului RAM operațiile se execută secvențial - adică una după alta în timp - într-o rețea de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
și adâncimea rețelei. În secțiunea 2 se demonstrează principiul zero- unu care simplifică foarte mult procesul de analiză a corectitudinii unei rețele de sortare. Rețeaua eficientă de sortare pe care o vom proiecta este în esență o versiune paralelă a algoritmului de sortare prin interclasare. Construcția rețelei se va realiza în trei pași. În secțiunea 3 se prezintă proiectarea așa numitului algoritm de sortare bitonic, care va fi celula de bază în construcția rețelei de sortare. În secțiunea 4 vom modifica
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețele de sortare. Rețeaua eficientă de sortare pe care o vom proiecta este în esență o versiune paralelă a algoritmului de sortare prin interclasare. Construcția rețelei se va realiza în trei pași. În secțiunea 3 se prezintă proiectarea așa numitului algoritm de sortare bitonic, care va fi celula de bază în construcția rețelei de sortare. În secțiunea 4 vom modifica puțin sortatorul bitonic pentru a obține o rețea cu interclasare care poate interclasa, două secvențe deja sortate într-o singură secvență
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de c perechi de numere întregi de la 1 la n. Dacă două perechi au un număr în comun, ordinea comparatorilor respectivi în rețea se poate determina prin ordinea perechilor în lista. Astfel ca având data aceasta reprezentare putem descrie un algoritm secvențial de complexitate O(n+că pentru determinarea adâncimii rețelei de comparare. Se construiește un tablou de n elemente constituind cele n conductoare inițializat cu 0. Se parcurge lista de conductori și pentru fiecare conductor (a,bă se incrementează valorile
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
cu 0. Se parcurge lista de conductori și pentru fiecare conductor (a,bă se incrementează valorile din tablou de pe pozițiile a și b cu o unitate. La final se parcurge tabloul și se reține maximul care constituie dimensiunea rețelei. Complexitatea algoritmului este O(n+că deoarece se parcurge odată lista de c comparatori și apoi tabloul cu n elemente. Secțiunea 2 Principiul zero-unu Principiul zero-unu afirmă că dacă o rețea de sortare lucrează corect atunci când la orice intrare se aplică doar
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
BITONIC-SORTER[n]. Secțiunea 5 O rețea de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
la care se află comparatorul precum și a valorilor noi pe care acesta le induce conductoarelor: Modul de implementare a semi-cleanerului poate fi remarcată prin utilizarea procedurii următoare, în care își fac apariția și procedurile de adăugare și sortare a comparatorilor: Algoritmul de sortare bitonică poate fi de asemenea pus în evidență prin secvența: Algoritmul de sortare prin interclasare în care este prezentă adăugarea, sortarea comparatorilor precum și sortarea bitonică, se poate evidenția în cele ce urmează: Modul de implementare a algoritmului de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
induce conductoarelor: Modul de implementare a semi-cleanerului poate fi remarcată prin utilizarea procedurii următoare, în care își fac apariția și procedurile de adăugare și sortare a comparatorilor: Algoritmul de sortare bitonică poate fi de asemenea pus în evidență prin secvența: Algoritmul de sortare prin interclasare în care este prezentă adăugarea, sortarea comparatorilor precum și sortarea bitonică, se poate evidenția în cele ce urmează: Modul de implementare a algoritmului de sortare ce își face prezența în cadrul procedurii ce este apelată la accesarea butonului
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]