Декомпозиція простору під час кластеризації даних великої розмірності
Для зменшення часових затрат під час кластеризації даних великих розмірів запропоновано декомпозиційний підхід, що базується на розбитті простору згідно з координатними вісями гіперкубів. Відповідне керування алгоритмом дає змогу об'єднувати кластери - результати з підмножин - у кінцеві при нез...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Фізико-механічний інститут ім. Г.В. Карпенка НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/16097 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Декомпозиція простору під час кластеризації даних великої розмірності / Р.А. Мельник, Р.Б. Тушницький // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 31(107). — С. 65-72. — Бібліогр.: 7 назв. — укp. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860107839677136896 |
|---|---|
| author | Мельник, Р.А. Тушницький, Р.Б. |
| author_facet | Мельник, Р.А. Тушницький, Р.Б. |
| citation_txt | Декомпозиція простору під час кластеризації даних великої розмірності / Р.А. Мельник, Р.Б. Тушницький // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 31(107). — С. 65-72. — Бібліогр.: 7 назв. — укp. |
| collection | DSpace DC |
| description | Для зменшення часових затрат під час кластеризації даних великих розмірів запропоновано декомпозиційний підхід, що базується на розбитті простору згідно з координатними вісями гіперкубів. Відповідне керування алгоритмом дає змогу об'єднувати кластери - результати з підмножин - у кінцеві при незначних втратах точності. Як приклади практичних даних використані зображення із значними кількостями пікcелів.
An approach to reduce algorithmic complexity for clustering of large-scale dataset is considered. The main idea is decomposition of item dataset and space by hypercube coordinates. To join clusters from subsets into the result clusters and to minimize the accuracy losses are the main tasks of the algorithm. Some visual patterns with large pixel numbers as test examples were investigated.
|
| first_indexed | 2025-12-07T17:32:42Z |
| format | Article |
| fulltext |
ISSN 0474-8662. . 2009. . 31 (107) 65
004.93’14
. . , . .
An approach to reduce algorithmic complexity for clustering of large-scale dataset is considered. The
main idea is decomposition of item dataset and space by hypercube coordinates. To join clusters from
subsets into the result clusters and to minimize the accuracy losses are the main tasks of the
algorithm. Some visual patterns with large pixel numbers as test examples were investigated.
-
, -
. – -
– . -
.
, -
, , [1–4]. , -
[1] -
. [2–3] -
, .
[4]
O(N 3) O(N 2). -
.
.
[5–7].
. -
.
O(N 3), O(N 2),
[4] -
. [6]
.
-
,
. : -
-
.
– -
. -
, .
Q(Q1, Q2, Q3, … QN) p
O1(Q1, Q2, Q3, … Qz), O2(Qz+1, Q z+2, Q z+3, … Qt), … , Op(Qt+1, Q t+2, Qt+3, … QN).
( , -
, K1(k1, k2, k3, …),
K2(ks, ks+1, ks+2, …), … , Kp(kr, kr+1, kr+2, …), k1, k2,…, ki, ... – ,
O1, O2, …, Op.
1- K
. . , . . , 2009
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)66
K =K1(k1, k2, k3,…) K2(ks, ks+1, ks+2,…) … Kp(kr, kr+1, kr+2,…). (1)
,
k1, k2,…, ki, ... , .
( 1- ) , . -
1- O1, O2, …, Op,
-
2- . 2-
, – .
,
( ). -
( . 1).
. 1. .
: , 20000 -
100 200 2- 20 -
. 2- 100·20=2000 , 10
200 20 . -
, -
. .
10000 -
-
. (
) 0- . , , -
, :
1) , -
. -
;
2) , -
, .
-
O1, O2, …, Op , , .
O1, O2, …, Op,
.
O1, … , Op:
1) , , -
. , -
ISSN 0474-8662. . 2009. . 31 (107) 67
, .
.
ni -
Oi , : O(p·ni
3);
2) .
-
( ).
. -
.
.
, -
: O(p·ni
3) + O(N2).
-
,
.
. n -
. -
n -
,
.
s n : C = C(a, b, …, z). -
n , b – m , ..., z – k . -
n, m, … , k
l = (n, m, …, k). -
. 2 .
. 2. ( ) :
– ; – .
: ,
; –
, , -
. . 2 20000 2- -
, . . 2
l = (2, 2) ( 2- ) -
, . . 2 -
.
. 2 – ( ) 5000 . . 2
: 1- 2030 , 2- – 11350, 3- – 4540, 4- –
2080 .
-
, O(p·ni
3) + p·O(N2).
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)68
. -
, -
0,75 0,95.
– 10000 5- .
: 5000, 2000, 3000.
(1- )
(2- ).
4 2500 , 8 1250 ,
16 625 .
, 10% .
(3- ) (4- ). -
l1 = (2, 2, 1, 1, 1) – 4 , l2 = (2, 2, 2, 1, 1)
– 8 l3 = (2, 2, 2, 2, 1) – 16 . -
– 2500, 1250 625 . -
. -
10% .
:
, , ( ), -
[5]. . 3 -
.
:
– –
, ;
– – -
QuickSort ;
– -
;
– –
.
-
. -
. , -
.
. 4 -
8 .
. 1. -
.
154×103 ( . 5 – ). – x, y color – -
. 15862 3- -
. ( ) , -
10% .
. 5 ,
. 2. ( -
)
( ), -
( ) -
( , ). . 5 , -
, . , -
ISSN 0474-8662. . 2009. . 31 (107) 69
, : ,
, .
. 3. ( ) ( )
4, 8 16 :
– ; – ; – ; – .
. 4.
8 :
– ; – ; – ; – .
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)70
1.
- , ,
4 2500 23:30 1 1,2576 3,1140 0,7991
8 1250 04:53 1 1,5791 2,9706 0,9107-
16 625 01:09 2 1,8985 2,7125 1,0281
4 2500 17:53 1 0,8571 3,5619 0,6274
8 1250 04:31 1 0,9039 3,5553 0,6449-
16 625 01:12 2 1,0857 3,6323 0,6817
4 2500 20:49 1 0,8649 3,6123 0,6279
8 1250 05:00 1 0,8768 3,5616 0,6352
-
-
16 625 01:30 1 0,8961 3,5023 0,6450
4 – 34:39 1 0,8529 3,5435 0,6275
8 – 08:12 1 0,8724 3,5402 0,6349-
16 – 02:21 1 0,8971 3,5534 0,6433
. 5. ( ): – -
; – -
; – (4, 4, 1);
– (2, 2, 1).
ISSN 0474-8662. . 2009. . 31 (107) 71
2.
(
)
, ,
1527
(1530) 3 2 44,0811 1,5003 3,6189 1,50
1557
(1566) 9 2 45,9041 1,4808 3,6117 1,58-
( )
1476
(1480) 4 2 34,7678 1,5503 3,1879 1,34
16/992
1541
(1548) 7 2 44,2001 1,5076 3,5855 1,51
1543
(1553) 10 2 46,1983 1,4723 3,6555 1,57-
( )
1498
(1501) 3 2 34,6141 1,5448 3,1900 1,35
16/992
2033
(2043) 10 1 15,1658 2,0907 1,3590 1.51
2041
(2051) 10 1 16,0968 2,0411 1,3784 1,52
2011
(2014) 3 1 11,7393 2,1788 1,2023 1,36
(4,4,1)
2968
(2971) 3 1 14,7260 2,0956 1,3417 10,33
3005
(3015) 10 1 15,6494 2,0456 1,3617 11,19
-
( – )
2945
(2948) 3 1 11,5100 2,1889 1,1857 8,24
(2,2,1)
. 2 , ,
,
. 5.
, -
(2- -
) (4- ).
. , -
. -
, -
. ,
. . -
.
.
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 31 (107)72
1. Yip A. M., Ding C., Chan T. F. Dynamic Cluster Formation Using Level Set Methods // IEEE
Trans. on Pattern Analysis and Machine Intelligence. – 2006. – 28, 6. – P. 877–889.
2. Grady L., Schwartz E. L. Isoperimetric Graph partitioning for Image segmentation // IEEE Trans.
on Pattern Analysis and Machine Intelligence. – 2006. – 28, 3. – P. 469–475.
3. Pavan M., Pelillo M. Dominant sets and Pairwise Clustering // IEEE Trans. on Pattern Analysis
and Machine Intelligence. – 2007. – 29, 1. – P. 167–172.
4. Ding C., He X. Cluster Aggregate Inequality and Multilevel Hierarchical Clustering // Proc. 9th
European Conf. Principles of Data Mining and Knowledge Discovery. – 2005. – P. 71–83.
5. Melnyk R., Tushnytskyy R. Algorithm Accuracy and Complexity Optimization by Inequality
Merging for Data Clustering // Proc. of the Xth Intern. Conf. The Experience of Designing and
Application of CAD Systems in Microelectronics (CADSM). – 2009. – P. 453–455.
6. . ., . .
// . 2006. – . 24(100). – . 110 114.
7. . ., . .
// . – 2008.
– 604. – . 249 254.
“ ”
17.02.2009
ОБРОБКА ЗОБРАЖЕНЬ ТА РОЗПІЗНАВАННЯ ОБРАЗІВ
УДК 004.93’14
Р. А. Мельник, Р. Б. Тушницький
ДЕКОМПОЗИЦІЯ ПРОСТОРУ ПІД ЧАС КЛАСТЕРИЗАЦІЇ ДАНИХ ВЕЛИКОЇ РОЗМІРНОСТІ
|
| id | nasplib_isofts_kiev_ua-123456789-16097 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0474-8662 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:32:42Z |
| publishDate | 2009 |
| publisher | Фізико-механічний інститут ім. Г.В. Карпенка НАН України |
| record_format | dspace |
| spelling | Мельник, Р.А. Тушницький, Р.Б. 2011-02-04T17:56:37Z 2011-02-04T17:56:37Z 2009 Декомпозиція простору під час кластеризації даних великої розмірності / Р.А. Мельник, Р.Б. Тушницький // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 31(107). — С. 65-72. — Бібліогр.: 7 назв. — укp. 0474-8662 https://nasplib.isofts.kiev.ua/handle/123456789/16097 004.93'14 Для зменшення часових затрат під час кластеризації даних великих розмірів запропоновано декомпозиційний підхід, що базується на розбитті простору згідно з координатними вісями гіперкубів. Відповідне керування алгоритмом дає змогу об'єднувати кластери - результати з підмножин - у кінцеві при незначних втратах точності. Як приклади практичних даних використані зображення із значними кількостями пікcелів. An approach to reduce algorithmic complexity for clustering of large-scale dataset is considered. The main idea is decomposition of item dataset and space by hypercube coordinates. To join clusters from subsets into the result clusters and to minimize the accuracy losses are the main tasks of the algorithm. Some visual patterns with large pixel numbers as test examples were investigated. uk Фізико-механічний інститут ім. Г.В. Карпенка НАН України Обробка зображень та розпізнавання образів Декомпозиція простору під час кластеризації даних великої розмірності Large-scale dataset clustering by space decomposition Article published earlier |
| spellingShingle | Декомпозиція простору під час кластеризації даних великої розмірності Мельник, Р.А. Тушницький, Р.Б. Обробка зображень та розпізнавання образів |
| title | Декомпозиція простору під час кластеризації даних великої розмірності |
| title_alt | Large-scale dataset clustering by space decomposition |
| title_full | Декомпозиція простору під час кластеризації даних великої розмірності |
| title_fullStr | Декомпозиція простору під час кластеризації даних великої розмірності |
| title_full_unstemmed | Декомпозиція простору під час кластеризації даних великої розмірності |
| title_short | Декомпозиція простору під час кластеризації даних великої розмірності |
| title_sort | декомпозиція простору під час кластеризації даних великої розмірності |
| topic | Обробка зображень та розпізнавання образів |
| topic_facet | Обробка зображень та розпізнавання образів |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/16097 |
| work_keys_str_mv | AT melʹnikra dekompozicíâprostorupídčasklasterizacíídanihvelikoírozmírností AT tušnicʹkiirb dekompozicíâprostorupídčasklasterizacíídanihvelikoírozmírností AT melʹnikra largescaledatasetclusteringbyspacedecomposition AT tušnicʹkiirb largescaledatasetclusteringbyspacedecomposition |