3.4 Self-organizing Trees3.4.1 Clus

3.4 Self-organizing Trees

3.4.1 Clustering discovery with hierarchical relations
The idea is to add a new hierarchical dimension to SOM map (see Figure 3.10). It
means to generate a set of trees arranged according to certain topology. The map
preserves the data topology while data similarity lies on the hierarchical structure.
The network nodes represent the prototypes in the grid. Unlike other hierarchical
representation where only the leaf nodes contain data information, every tree node in
SoT structure corresponds to input data. The proposed algorithm is able to detect
clusters and to represent these clusters as topological and hierarchical structure.
Here each tree is not only a cluster but a sub-tree from any branch is also a sub-
cluster. Condence of each cluster may be easily observed because of hierarchical
relations among the input data.
In this hierarchical and topological structure, similarity between a pair of data
is avaiable through hierarchical links, while distances between two clusters depend
on the topological links.



3.4.2 SoT - Topological and hierarchical clustering

From this moment, the notations: an input data object or vector xi and a tree node
xiare all equal. A cluster i, a network node Ci, the prototype wiare too.
The size of the grid W denoted by K = p × q must be provided a priori.
Each network node Ck∈ W associated with a prototype as well as a treek. So
following the initalization, we should have K trees in the network. For each
pair of treecandtreeronW, their mutual inuence is dened by the function
KT(δ(Cc, Cr)) = exp( −δ(CTc,Cr)). Based on Equation 3.1, the new cost function is
re-written in Equation 3.2.


K


K

R(φ, W) =

∑

∑

∑

KT(δ(φ(subtreexi), Cr))kxi− wrk2

(3.2)

c=1 i∈treec r=1






3.4. Self-organizing Trees


where φ is the assignment function which is expressed as following:

K
∑
φ(subtreexi ) = arg min KT(d(xi, Ck)) kxi− wkk2





31





(3.3)

k

k=1

where subtreexicontains xi and all tree nodes recursively connected to it. It should
be noted that data in the sub-tree are similar due to the self-assembly rules. We
take this as an advantage to reduce algorithm complexity. The Lemma 3.4.1 shows
how to assign simultaneously a data group.

Theorem 3.4.1

∀xj∈ subtreexi, φ(xj) = φ(xi)

(3.4)




Proof Let d(xi, Cc) be the distance from xitowc and suppose that Cc = φ(xi)
then we have:
d(xi, Cc) < d(xi, Ck), ∀k = [1, .., K]
When xj∈ subtreexi=⇒ xiand xiare similiar, their distance should tend to 0.

lim d(xi, xj ) = 0
xj→xi
We deduce that:

d(xj , Cc) ≈ d(xi, Cc) + d(xj, xi ) < d(xi, Ck) + d(xj , xi) ≈ d(xj , Ck)

=⇒ φ(xj) = Ccor φ(xj) = φ(xi) = Cc

Minimizing cost function R(φ, L) is a combinatorial optimization problem. In
this work we propose to minimize the cost function in the same way as "batch" ver-
sion using statistical characteristics provided by trees to accelerate the convergence
of the algorithm. These characteristics are used in assignment function 3.3.

3.4.3 Batch algorithm
Here we want to show how to adapt the self-assembly rules provided by AntTree
in Algorithm 2 to topological models including SOM. During the learning process,
the status of a tree node can be various due to the connecting or disconnecting rules.
Therefore, we dene three possibilities for the node status:
1. Initial : the default status before training;
2. Connected : the tree node is currently connected to another node;
3. Disconnected : the tree node were connected at least once but now gets dis-
connected.







32





Chapter 3. Self-Organizing Trees and its applications for graph
summarization

Algorithm 6 SoT batch algorithm
1: initialize k prototypes
2: while stopping criteria have not been fullled do
3: initialize list
4: while list is not empty do

5:

xiis the rst data from list

6:

c = φ(xi)

// Find the best match network node

7:
8:
9:

if xiis initial then
treec= constructT ree(treec, xi)
else


// connect xito treec

10:

11:

subtreexi = {xiand all tree nodes recursively and temporarily connected
to xi}
if xiisdisconnected then

12:

13:

treec= constructT ree(treec, subtreexi)
subtreexitotreec
else if xiisconnected and c6= coldthen

// connect either xior

14:

subtreexi=disconnect subtreexi from treecold

15:

16:
17:
18:
19:
20:

treec = constructT ree(treec, subtreexi)
treec
end if
end if
if xi is not connected then
list = {list, xi} // put xiat the end of list
else

// connect subtreexito

21:
22:

list = list subtreexi
end if

// remove subtreexifrom list

23: end while
24: for c = 1 → KTdo

25:

∑K

r=1K(δ(c,r)) ∑

j∈Crxj

// Update prototype vectors where nris the

wc=

∑K

T

r=1K(δ(c,r))nr
number of data found in cluster r
26: end for
27: end while

. Let us denote xpos is the support (the tree root) or the tree node position where xi
is located. At the beginning, xi is located on the support and will move in the tree
(toward other tree nodes) in order to nd its best position; x+and x− two tree nodes
connected to xpos which are respectively the most similar and dissimilar tree node
to xi. Let list denote a list of tree nodes. Before training, list contains only initial
tree nodes, whenever a tree node becomes connected, it is immediately removed
from list; alternatively whenever a tree node and its children get disconnected from
a tree, we put them back onto list. After several iterations, list might contain both
initial and disconnected tree nodes.
The batch algorithm is shown in Algorithm 6. The algorithm includes three






3.4. Self-organizing Trees





33



steps as in the SOM algorithm (Section 3.2). Besides, SoT has an additional step
for tree construction. While the initialization stays the same as the one in SOM,
the others must be modied to adapt to the new structure. Then SoT can proceed
by alternating between three steps: assignment, tree construction and update.

Assignment
From Equation 3.3 and 3.4, it can be deduced that there are two distinct cases of
assignment:
1. For one single object xi. This can be considered as a sub-tree with one single
node. It may happen when xiis either initial (see Line 6 in Algorithm 6) or
disconnected (see Line 11 in Algorithm 6). It can be assigned by developping
Equation 3.3:
∑

φ(xi) = arg min

KT(δ(xi, Ck)) kxi− wkk2

r

k=1..K


2. For a subtreexi(subtreexiconsists of the sub-tree with xi as the root) , it will
be assigned by Equation 3.3 and see Line 16 in Algorithm 6.












Figure 3.7: Group assignment from treecoldtotreec

An example where multiple tree nodes are simultaneously assigned is shown in
Figure 3.7. Due to the last update, subtreex consists of three violet tree nodes that
are no longer connected to treecold. Now we have to determine the new best match
treecfor the tree node x using φ(subtreex). As in Equation 3.4 the assignments of
child nodes of x follow automatically the one of x using the statistical characteristics
of tree. Even though these three nodes are now found in the new network node Cc,
their hierarchy in new cell remains in the old network node Ccold.


Tree construction
This step is realized by the function constructTree in which we use the rules from
Algorithm 2. This function is to nd the best position in the tree structure to
which the learning node xi is connected. In the case of this function being called to







34





Chapter 3. Self-Organizing Trees and its applications for graph
summarization

assign subtreexi, only xi will be learnt with those three rules dened in Algorithm
2. One subtree to be re-connected must be disconnected before. Concerning to
disconnection, there is two distinct cases:
1. disconnect tree node(s) due to the assignment (Line 14 in Algorithm 6),
2. disconnect tree node when a node comes into play (Line 7 in Algorithm 2).













Figure 3.8: Disconnect subtreexfrom treecold and put it in list

Whenever a tree node gets disconnected from a tree, we have to check whether it
does exist other child nodes in subtreexi or not? If it's the case, we disconnect all of
them or for more specic subtreexi. A simple example of disconnection for a group
of nodes (or sub-tree) is depicted in Figure 3.8. Given treecold as in this example,
the tree node x consisting of three violet nodes is to disconnect from this tree. All
the nodes connected to x must be recursively disconnected too; it applies to two
child nodes of x. Therefore subtreexhave disconnected status and are immediately
put back onto the pool list.
After being disconnected, these nodes will be connected again by the function
constructTree. Suppose that xibecomes connected at a moment, we will keep this
sub-tree structure by re-connecting these child nodes together, hence this way can
accelerate the learning process. For example, let's re-take the example in Figure 3.8.
After getting new assignment, x is going to connect to treec. It leads to that the
child node of x have treecas their best match tree too. We systematically connect
this sub-tree to treec and the result is shown in Figure 3.9. We remind that this
subtree is not kept till the end of learning. There is possiblity that the nodes in the
subtree will be disconnected in next iterations.

Update
This step is necessary to compute the new prototypes. We can easily adapt our
algorithm to choose a representative prototype. In order to update the prototype
vectors, we can use the same way as in the batch version of the SOM algorithm.






3.4. Self-organizing Trees














Figure 3.9: Re-connect subtreexto treec

3.4.4 Computational complexity





35

Lemma 3.4.2 SoT has a complexity of θ(NiterN log N ) where Niter is the number
of total iterations when the learning has been terminated.

Proof Algorithm 6 requires Niter iterations to reach stopping criteria. During one
iteration, an operation includes three iterative steps: assignment, tree construction
and updating support. The number of assignme

Kết quả (Việt) 1:

3.4 cây tự tổ chức3.4.1 clustering khám phá với quan hệ phân cấpMục đích là để thêm một chiều hướng thứ bậc mới vào bản đồ SOM (xem hình 3,10). Nócó nghĩa là để tạo ra một tập các cây sắp xếp theo cấu trúc liên kết nhất định. Bản đồbảo tồn cấu trúc liên kết dữ liệu trong khi dữ liệu giống nhau nằm trên cấu trúc phân cấp.Các nút mạng đại diện cho nguyên mẫu trong lưới điện. Không giống như các phân cấpđại diện nơi chỉ có nút lá có chứa dữ liệu thông tin, mỗi nút cây trongCấu trúc soT tương ứng với đầu vào dữ liệu. Các thuật toán được đề xuất có thể phát hiệncụm và đại diện cho cụm các cấu trúc tô pô và phân cấp.Ở đây cây mỗi là không chỉ là một cụm sao nhưng một cây-con từ bất kỳ chi nhánh cũng là một phụ-cụm. Condence của mỗi nhóm có thể dễ dàng thấy vì phân cấpmối quan hệ giữa các dữ liệu đầu vào.Trong cấu trúc phân cấp và tô pô, giống nhau giữa một cặp của dữ liệulà avaiable thông qua liên kết thứ bậc, trong khi khoảng cách giữa hai cụm phụ thuộcvào các liên kết tô pô. 3.4.2 soT - tô pô và phân cấp cụmTừ thời điểm này, các notations: một đầu vào dữ liệu đối tượng hoặc vector xi và một nút câyXiare tất cả như nhau. A cụm tôi, một nút mạng Ci, mẫu thử nghiệm wiare quá.Kích thước của lưới điện W biểu hiện bằng K = p × q phải được cung cấp một tiên nghiệm.Mỗi nút mạng Ck∈ W liên kết với một mẫu thử nghiệm và một treek. Vì vậysau initalization, chúng ta nên có K cây trong mạng. Cho mỗiCặp treecandtreeronW, của inuence lẫn nhau là dened bởi các chức năngKT (δ (Cc, Cr)) = exp (−δ(CTc,Cr)). Dựa trên phương trình 3.1, các chức năng mới chi phí làtái viết bằng phương trình 3.2. K K R (Φ, W) = ∑ ∑ ∑ KT(δ(φ(subtreexi), Cr)) kxi− wrk2 (3.2) c = 1 i∈treec r = 1 3.4. tự tổ chức câynơi φ là chức năng chuyển nhượng được thể hiện như sau:K∑Φ (subtreexi) = arg min KT (d (xi, Ck)) kxi− wkk2 31(3,3) k k = 1 nơi subtreexicontains xi và tất cả cây nút đệ quy kết nối đến nó. Nó nênlưu ý rằng dữ liệu trong cây-con được tương tự do các quy tắc tự assembly. Chúng tôicó điều này như là một lợi thế để giảm độ phức tạp thuật toán. Cho thấy bổ đề 3.4.1làm thế nào để chỉ định cùng một lúc một nhóm dữ liệu.Định lý 3.4.1 ∀XJ∈ subtreexi, φ(xj) = φ(xi) (3,4) Bằng chứng cho d (xi, Cc) là khoảng cách từ xitowc và giả sử rằng Cc = φ(xi)sau đó chúng tôi có:d (xi, Cc) < d (xi, Ck), ∀k = [1,..., K]Khi xj∈ subtreexi = ⇒ xiand xiare tương tự, khoảng cách của họ nên có xu hướng 0.Lim d (xi, xj) = 0XJ→xiChúng ta suy ra rằng:d (xj, Cc) ≈ d (xi, Cc) + d (xj, xi) < d (xi, Ck) + d (xj, xi) ≈ d (xj, Ck)= ⇒ φ(xj) = Ccor φ(xj) = φ(xi) = CcGiảm thiểu chi phí chức năng R (φ, L) là một vấn đề tối ưu hóa tổ hợp. Ởcông việc này, chúng tôi đề xuất để giảm thiểu các chức năng chi phí trong cùng một cách như là "hàng loạt" ver-Sion sử dụng thống kê đặc điểm cung cấp bởi cây để thúc đẩy sự hội tụcủa thuật toán. Những đặc điểm được sử dụng trong gán chức năng 3.3.3.4.3 thuật toán lôỞ đây chúng tôi muốn hiển thị làm thế nào để thích ứng với các quy tắc tự assembly cung cấp bởi AntTreetrong thuật toán 2 để tô pô mô hình bao gồm SOM. Trong quá trình học tập,tình trạng của một nút cây có thể khác nhau do các kết nối hoặc ngắt kết nối quy tắc.Vì vậy, chúng tôi dene ba khả năng cho trạng thái nút:1. Ban đầu: tình trạng mặc định trước khi đào tạo;2. kết nối: các nút cây kết nối với một nút;3. ngắt kết nối: các nút cây đã được kết nối ít nhất một lần nhưng bây giờ được dis-kết nối. 32 Chương 3. Tự tổ chức các cây và các ứng dụng cho đồ thịTổng hợp Thuật toán 6 SoT lô thuật toán1: khởi tạo mẫu thử nghiệm k2: trong khi dừng lại tiêu chí đã không là fullled làm3: khởi tạo danh sách4: trong khi danh sách không phải là sản phẩm nào 5: xiis các rst dữ liệu từ danh sách 6: c = φ(xi) Tìm tốt nhất phù hợp với mạng nút 7:8:9: Nếu xiis đầu tiên sau đótreec = constructT ree (treec, xi)khác kết nối xito treec 10:11: subtreexi = {xiand tất cả cây nút đệ quy và tạm thời được kết nốiđể xi}Nếu xiisdisconnected sau đó 12:13: treec = constructT ree (treec, subtreexi)subtreexitotreeckhác nếu xiisconnected và c6 = coldthen kết nối hoặc xior 14: subtreexi = ngắt kết nối subtreexi từ treecold 15:16:17:18:19:20: treec = constructT ree (treec, subtreexi)treeckết thúc nếukết thúc nếuNếu xi không kết nối sau đódanh sách = {danh sách, xi} / / đặt xiat cuối cùng của danh sáchkhác kết nối subtreexito 21:22: danh sách = danh sách subtreexikết thúc nếu hủy bỏ subtreexifrom danh sách 23: kết thúc trong khi24: cho c = 1 → KTdo 25: ∑K r=1K(δ(c,r)) ∑ j∈Crxj Cập Nhật mẫu vectơ nơi nris các WC = ∑K T nr r=1K(δ(c,r))số lượng dữ liệu được tìm thấy trong cụm r26: kết thúc cho27: kết thúc trong khi. Hãy để chúng tôi biểu thị xpos là sự hỗ trợ (gốc cây) hoặc vị trí nút cây nơi xicó vị trí. Lúc đầu, xi nằm trên sự hỗ trợ và sẽ di chuyển trong cây(đối với các nút cây khác) trong đặt hàng để nd vị trí tốt nhất của nó; x + và x− hai cây nútkết nối với xpos mà là tương ứng nút cây đặt tương tự và không giống nhauđể xi. Cho danh sách biểu thị một danh sách các nút cây. Trước khi đào tạo, danh sách chứa chỉ ban đầucác nút cây, bất cứ khi nào một nút cây trở thành kết nối, nó ngay lập tức gỡ bỏtừ danh sách; Ngoài ra bất cứ khi nào một nút cây và trẻ em của nó nhận được kết nối từmột cây, chúng tôi đặt chúng trở lại vào danh sách. Sau khi lặp đi lặp lại một số, danh sách có thể chứa cả haicác nút cây ban đầu và bị ngắt kết nối.Thuật toán lô Hiển thị trong thuật toán 6. Các thuật toán bao gồm ba 3.4. tự tổ chức cây 33 bước như trong các thuật toán SOM (phần 3.2). Bên cạnh đó, SoT có một bước bổ sungxây dựng cây. Trong khi khởi tạo được giống như một trong SOM,những người khác phải modied để thích ứng với cấu trúc mới. Sau đó SoT có thể tiến hànhbởi Luân phiên giữa ba bước: phân công, xây dựng cây và Cập Nhật.Chuyển nhượngTừ phương trình 3.3 và 3,4, nó có thể được suy luận rằng không có hai trường hợp riêng biệtchuyển nhượng:1. đối với một đối tượng duy nhất xi. Điều này có thể được coi như là một cây-con với một trang duy nhấtnút. Nó có thể xảy ra khi xiis hoặc ban đầu (xem dòng 6 trong thuật toán 6) hoặcbị ngắt kết nối (hãy xem dòng 11 trong thuật toán 6). Nó có thể được chỉ định bởi developpingPhương trình 3.3:∑ Φ(xi) = arg min KT (δ (xi, Ck)) kxi− wkk2 r k = 1..K 2. đối với một subtreexi (subtreexiconsists của cây-con với xi là gốc), nó sẽđược chỉ định bởi phương trình 3.3 và xem dòng 16 trong thuật toán 6.Con số 3,7: Nhóm gán từ treecoldtotreecMột ví dụ nơi nhiều cây nút cùng một lúc được chỉ định Hiển thị trongCon số 3,7. Do cuối Cập Nhật, subtreex bao gồm ba tím cây nút màkhông được kết nối với treecold. Bây giờ chúng ta phải xác định phù hợp mới nhấttreecfor nút cây x bằng cách sử dụng φ(subtreex). Như trong phương trình 3.4 bài tập củanút con của x tự động theo một trong x bằng cách sử dụng các đặc tính thống kêcủa cây. Mặc dù những ba nút bây giờ được tìm thấy trong nút mạng mới của Cc,Hệ thống phân cấp của họ trong các tế bào mới vẫn còn trong nút mạng cũ của Ccold.Xây dựng câyBước này được thực hiện bởi constructTree chức năng mà chúng tôi sử dụng các quy tắc từThuật toán 2. Chức năng này là để nd vị trí tốt nhất trong cơ cấu cây đểmà học tập nút xi được kết nối. Trong trường hợp của chức năng này được gọi là để 34 Chương 3. Tự tổ chức các cây và các ứng dụng cho đồ thịTổng hợp chỉ định subtreexi, chỉ xi sẽ được học với những quy tắc ba dened trong thuật toán2. một subtree để được tái kết nối phải bị ngắt kết nối trước khi. Liên quan đến đểngắt kết nối, có hai trường hợp riêng biệt:1. ngắt kết nối cây node(s) do việc chuyển nhượng (dòng 14 trong thuật toán 6),2. ngắt kết nối cây nút khi một nút đi vào chơi (dòng 7 trong thuật toán 2).Con số 3.8: Ngắt kết nối subtreexfrom treecold và đặt nó trong danh sáchBất cứ khi nào một nút cây bị ngắt kết nối từ một cây, chúng tôi phải kiểm tra xem nókhông tồn tại các nút con ở subtreexi hay không? Nếu đó là trường hợp, chúng tôi ngắt kết nối tất cảhọ hoặc cho hơn specic subtreexi. Một ví dụ đơn giản của ngắt kết nối với một nhómnút (hoặc cây-con) được mô tả trong hình 3.8. Treecold nhất định như trong ví dụ này,các nút cây x bao gồm ba nút tím là để ngắt kết nối từ cây này. Tất cảcác nút kết nối với x phải là đệ quy ngắt kết nối quá; nó áp dụng cho hainút con của x. Do đó subtreexhave bị ngắt kết nối tình trạng và ngay lập tứcđưa trở lại vào danh sách ngoài trời.Sau khi bị ngắt kết nối, các nút sẽ được kết nối lại chức năngconstructTree. Giả sử rằng xibecomes kết nối tại một thời điểm, chúng tôi sẽ giữ cho điều nàycây-con các cấu trúc bằng cách tái kết nối các nút con với nhau, do đó theo cách này có thểtăng tốc quá trình học tập. Ví dụ, chúng ta hãy tái Lấy ví dụ trong hình 3.8.Sau khi nhận được nhiệm vụ mới, x sẽ kết nối với treec. Nó dẫn đến mà cáctrẻ em nút của x có treecas của họ tốt nhất phù hợp với cây quá. Chúng tôi có hệ thống kết nốinày cây-con treec và kết quả hiển thị trong hình 3.9. Chúng tôi nhắc nhở rằng điều nàysubtree không được lưu giữ cho đến cuối của học tập. Có là possiblity mà các nút trong cácsubtree sẽ bị ngắt kết nối trong lặp đi lặp lại tiếp theo.Cập NhậtBước này là cần thiết để tính toán các nguyên mẫu mới. Chúng tôi có thể dễ dàng điều chỉnh của chúng tôithuật toán để lựa chọn một mẫu đại diện. Để cập nhật các mẫu thử nghiệmvector, chúng tôi có thể sử dụng cùng một cách như trong các phiên bản hàng loạt của các thuật toán SOM. 3.4. tự tổ chức câyCon số 3.9: Kết nối lại với subtreexto treec3.4.4 tính toán phức tạp 35 Bổ đề 3.4.2 SoT có một phức tạp của θ (NiterN log N) nơi tiêu thạch là sốcủa tất cả lặp khi học tập đã được kết thúc.Bằng chứng thuật toán 6 đòi hỏi lặp đi lặp lại tiêu thạch để đạt được tiêu chuẩn dừng. Trong mộtlặp đi lặp lại, một hoạt động bao gồm ba bước lặp đi lặp lại: chuyển nhượng, cây xây dựngvà Cập Nhật hỗ trợ. Số assignme

Kết quả (Việt) 2:

3.4 Cây tự tổ chức 3.4.1 Clustering khám phá với quan hệ thứ bậc Ý tưởng là để thêm một chiều hướng phân cấp mới để đồ SOM (xem Hình 3.10). Nó có nghĩa là để tạo ra một tập hợp các cây sắp xếp theo cấu trúc liên kết nhất định. Bản đồ bảo tồn các cấu trúc liên kết dữ liệu trong khi dữ liệu giống nhau nằm trên các cấu trúc phân cấp. Các nút mạng đại diện cho các nguyên mẫu trong lưới. Không giống như các thứ bậc khác đại diện, nơi chỉ có các nút lá chứa thông tin dữ liệu, mỗi nút cây trong cấu trúc sốt tương ứng với dữ liệu đầu vào. Các thuật toán được đề xuất có thể phát hiện các cụm và đại diện cho các cụm như cấu trúc tô pô và thứ bậc. Ở đây mỗi cây không chỉ là một cụm nhưng một cây con từ bất kỳ chi nhánh cũng là một phụ cluster. Condence của mỗi cụm có thể được quan sát dễ dàng vì có thứ bậc quan hệ giữa các dữ liệu đầu vào. Trong cấu trúc phân cấp và tôpô này, giống nhau giữa một cặp dữ liệu là avaiable thông qua các liên kết phân cấp, trong khi khoảng cách giữa hai cụm phụ thuộc vào các liên kết topo. 3.4.2 Sot - phân nhóm tôpô và thứ bậc Từ thời điểm này, các ký hiệu: một đối tượng dữ liệu đầu vào hoặc vector xi và một nút cây xiare tất cả như nhau. Một cụm i, một nút mạng Ci, nguyên mẫu wiare quá. Kích thước của lưới W biểu thị bằng K = p × q phải được cung cấp một ưu tiên. Mỗi nút mạng Ck∈ W kết hợp với một nguyên mẫu cũng như một treek. Vì vậy, sau initalization, chúng ta nên có cây K trong mạng. Đối với mỗi cặp treecandtreeronW, inuence lẫn nhau của họ được xác định bởi các chức năng KT (δ (Cc, Cr)) = exp (-δ (CTC, Cr)). Dựa trên phương trình 3.1, hàm chi phí mới được tái bản trong phương trình 3.2. K K R (φ, W) = Σ Σ Σ KT (δ (φ (subtreexi), Cr)) kxi- wrk2 (3.2) c = 1 r i∈treec = 1 3.4. Tự tổ chức Trees nơi φ là hàm chuyển nhượng mà được thể hiện như sau: K Σ φ (subtreexi) = arg min KT (d (xi, Ck)) kxi- wkk2 31 (3.3) k k = 1 nơi subtreexicontains xi và tất cả các nút cây đệ quy kết nối với nó. Nó nên được lưu ý rằng dữ liệu trong phụ cây tương tự do các quy tắc tự lắp ráp. Chúng tôi coi đây là một lợi thế để giảm độ phức tạp thuật toán. Các bổ đề 3.4.1 cho thấy làm thế nào để gán đồng thời một nhóm dữ liệu. Định lý 3.4.1 ∀xj∈ subtreexi, φ (xj) = φ (xi) (3.4) Proof Hãy d (xi, Cc) là khoảng cách từ xitowc và giả sử rằng Cc = φ (xi) sau đó chúng ta có: d (xi, Cc) <d (xi, Ck), ∀k = [1, .., K] Khi xj∈ subtreexi = ⇒ xiand tương tự xiare, khoảng cách của họ nên có xu hướng 0. lim d (xi, xj) = 0 xj → xi Chúng tôi suy luận rằng: d (xj, Cc) ≈ d (xi, Cc) + d (xj, xi) <d (xi, Ck) + d (xj , xi) ≈ d (xj, Ck) = ⇒ φ (xj) = Ccor φ (xj) = φ (xi) = Cc Giảm thiểu chi phí chức năng R (φ, L) là một vấn đề tối ưu hóa tổ hợp. Trong công việc này, chúng tôi đề xuất để giảm thiểu chi phí chức năng trong cùng một cách như là "lô" version sion sử dụng đặc tính thống kê được cung cấp bởi cây để đẩy nhanh sự hội tụ của thuật toán. Những đặc điểm này được sử dụng trong chức năng chuyển nhượng 3.3. Thuật toán 3.4.3 hàng loạt Ở đây chúng tôi muốn thể hiện như thế nào để thích ứng với các quy tắc tự lắp ráp cung cấp bởi AntTree trong Algorithm 2 đến mô hình topo bao gồm SOM. Trong quá trình học tập, . tình trạng của một nút cây có thể khác nhau do các quy tắc kết nối hoặc ngắt kết nối Do đó, chúng tôi Dene ba khả năng cho tình trạng nút: 1. Ban đầu: trạng thái mặc định trước khi đào tạo; 2. Kết nối: các nút cây hiện đang được kết nối với một nút khác; 3. Ngắt kết nối: các nút cây đã được kết nối với ít nhất một lần nhưng bây giờ được dis- kết nối. 32 Chương 3. Tự-Tổ chức Cây và ứng dụng của nó cho đồ thị tổng hợp Algorithm 6 Sot thuật toán đợt 1: khởi tạo k nguyên mẫu 2: trong khi tiêu chí dừng chưa được fullled làm 3: khởi tạo danh sách 4: trong khi danh sách không có sản phẩm nào làm 5: xiis các dữ liệu đầu tiên trong danh sách 6: c = φ (xi) // Tìm nút mạng phù hợp nhất 7: 8: 9: nếu xiis ban đầu sau đó treec = constructT ree (treec, xi) khác // kết nối xito treec 10: 11: subtreexi = {xiand tất cả các nút cây đệ quy và các kết nối tạm thời để xi} nếu xiisdisconnected sau đó 12: 13: treec = constructT ree (treec, subtreexi) subtreexitotreec khác nếu xiisconnected và c6 = coldthen // kết nối hoặc xior 14: subtreexi = disconnect subtreexi từ treecold 15: 16: 17: 18: 19: 20: treec = constructT ree (treec, subtreexi) treec kết thúc nếu kết thúc nếu nếu xi không được kết nối sau đó danh sách = {danh sách, xi} // đặt xiat cuối danh sách khác // kết nối subtreexito 21: 22: list = danh sách subtreexi kết thúc nếu // loại bỏ danh sách subtreexifrom 23: kết thúc trong khi 24: cho c = 1 → KTdo 25: Σ K r = 1K (δ (c, r)) Σ j∈Crxj // Cập nhật vectơ nguyên mẫu mà NRI các wc = ΣK T r = 1K (δ (c, r)) nr số dữ liệu được tìm thấy trong cụm r 26: kết thúc cho 27: kết thúc trong khi . Chúng ta hãy biểu xpos là sự hỗ trợ (gốc cây) hoặc vị trí nút cây nơi xi nằm. Lúc đầu, xi ​​nằm trên hỗ trợ và sẽ di chuyển trong cây (đối với các nút cây khác) để nd vị trí tốt nhất của nó; x + x- và hai nút cây kết nối với xpos đó lần lượt là các nút cây giống nhất và không tương tự để xi. Hãy để danh sách biểu thị một danh sách các nút cây. Trước khi đào tạo, danh sách ban đầu chỉ chứa các nút cây, bất cứ khi nào một nút cây bị kết nối, nó ngay lập tức bị loại bỏ khỏi danh sách; cách khác bất cứ khi nào một nút cây và con của nó được ngắt kết nối từ một cây, chúng tôi đặt chúng trở lại vào danh sách. Sau một số lần lặp, danh sách có thể chứa cả các nút cây ban đầu và ngắt kết nối. Các thuật toán hàng loạt được thể hiện trong thuật toán 6. Các thuật toán bao gồm ba 3.4. Tự tổ chức Trees 33 bước như trong thuật toán SOM (mục 3.2). Bên cạnh đó, sốt có một bước bổ sung để xây dựng cây. Trong khi khởi tạo vẫn giống như một trong SOM, những người khác phải được modied để thích ứng với cấu trúc mới. Sau đó, sốt có thể tiến hành bằng cách luân phiên giữa ba bước sau:. chuyển nhượng, xây dựng cây và cập nhật chuyển nhượng Từ phương trình 3.3 và 3.4, nó có thể được suy ra rằng có hai trường hợp riêng biệt của công việc: 1. Đối với một xi đối tượng duy nhất. Đây có thể được coi là một cây tiểu với một đơn node. Nó có thể xảy ra khi một trong hai xiis ban đầu (xem dòng 6 trong 6 Algorithm) hoặc bị ngắt kết nối (xem dòng 11 trong Algorithm 6). Nó có thể được gán bởi developping Equation 3.3: Σ φ (xi) = arg min KT (δ (xi, Ck)) kxi- wkk2 r k = 1..K 2. Đối với một subtreexi (subtreexiconsists của sub-cây với xi như root), nó sẽ được chỉ định bởi phương trình 3.3 và xem dòng 16 trong Algorithm 6. Hình 3.7: Nhóm phân công từ treecoldtotreec Một ví dụ mà nhiều nút cây được đồng thời phân công được thể hiện trong hình 3.7. Do bản cập nhật mới, subtreex bao gồm ba nút cây tím mà không còn kết nối với treecold. Bây giờ chúng ta phải xác định các trận đấu mới nhất treecfor các nút cây x sử dụng φ (subtreex). Như trong Equation 3.4 các bài tập của các nút con của x tự động theo một trong x bằng cách sử dụng đặc tính thống kê của cây. Mặc dù ba nút giờ được tìm thấy trong các nút mạng mới Cc, hệ thống cấp bậc của họ trong tế bào mới vẫn còn trong nút mạng Ccold. cũ xây dựng Tree Bước này được thực hiện bởi các constructTree chức năng mà chúng ta sử dụng các quy tắc từ Algorithm 2. Chức năng này là nd vị trí tốt nhất trong cơ cấu cây để mà nút xi học được kết nối. Trong trường hợp chức năng này được gọi đến 34 Chương 3. Tự-Tổ chức Cây và ứng dụng của nó cho đồ thị tổng hợp assign subtreexi, chỉ xi sẽ được học với những ba quy tắc định nghĩa trong thuật toán 2. Một cây con được tái kết nối phải được ngắt kết nối trước. Liên quan đến ngắt kết nối, có hai trường hợp riêng biệt: 1. nút ngắt kết nối cây (s) do chuyển nhượng (Line 14 trong Algorithm 6), 2. nút cây ngắt kết nối khi một nút đến chơi (Line 7 trong Algorithm 2). Hình 3.8: Ngắt kết nối subtreexfrom treecold và đặt nó trong danh sách Bất cứ khi nào một nút cây bị ngắt kết nối từ một cây, chúng ta phải kiểm tra xem nó có tồn tại các nút con khác trong subtreexi hay không? Nếu đó là trường hợp, chúng tôi ngắt kết nối tất cả chúng hoặc cho subtreexi specic hơn. Một ví dụ đơn giản đứt kết nối cho một nhóm các nút (hoặc sub-tree) được mô tả trong hình 3.8. Với treecold như trong ví dụ này, các nút cây x gồm ba nút màu tím là để ngắt kết nối từ cây này. Tất cả các nút kết nối với x phải được đệ quy bị ngắt kết nối quá; nó áp dụng cho hai nút con của x. Vì vậy subtreexhave tình trạng ngắt kết nối và ngay lập tức được đưa trở lại vào danh sách hồ bơi. Sau khi bị ngắt kết nối, các nút này sẽ được kết nối lại bằng chức năng constructTree. Giả sử rằng xibecomes kết nối tại một thời điểm, chúng tôi sẽ giữ điều này cơ cấu cây con bằng cách tái kết nối những con các nút với nhau, do đó cách này có thể thúc đẩy quá trình học tập. Ví dụ, chúng ta hãy lại lấy ví dụ trong hình 3.8. Sau khi nhận nhiệm vụ mới, x là sẽ kết nối với treec. Nó dẫn đến các nút con của x có treecas cây trận đấu tốt nhất của họ quá. Chúng tôi có hệ thống kết nối phụ cây này để treec và kết quả được thể hiện trong hình 3.9. Chúng tôi nhắc nhở rằng đây cây con không được giữ cho đến khi kết thúc học tập. Có possiblity rằng các nút trong cây con sẽ bị ngắt kết nối trong các phiên tiếp theo. Cập nhật Bước này là cần thiết để tính toán các mẫu mới. Chúng ta có thể dễ dàng thích nghi của chúng tôi thuật toán để chọn một mẫu đại diện. Để cập nhật các mẫu vector, chúng ta có thể sử dụng cùng một cách như trong các phiên bản hàng loạt các thuật toán SOM. 3.4. Tự tổ chức Trees kết nối Re-subtreexto treec: Hình 3.9 3.4.4 phức tạp tính toán 35 Bổ đề 3.4.2 sốt có độ phức tạp của θ (NiterN log N) trong đó chất ni tơ là số của tổng số lần lặp lại khi học tập đã bị chấm dứt. Algorithm Proof 6 yêu cầu tiêu thạch lặp để đạt tiêu chuẩn dừng. Trong một lần lặp lại, một hoạt động bao gồm ba bước lặp đi lặp lại: chuyển nhượng, xây dựng cây và cập nhật hỗ trợ. Số assignme