Clustering method for multilingual documents

• US 20170235823A1
• Filed: 09/16/2013
• Published: 08/17/2017
• Est. Priority Date: 09/12/2013
• Status: Abandoned Application

• Current Assignee: Guangdong Electronics Industry Institute Company Limited
• Original Assignee: Guangdong Electronics Industry Institute Company Limited
• Inventors: Yuan, Zimu, Peng, Peng, Ji, Tongkai, Yue, Qiang
• Application Number:
  US14/408,461
• Publication Number:
  US 20170235823A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

The present invention relates to a technical field of information retrieval, and more particularly to a clustering method for multilingual documents, comprising steps of: step 1: establishing a similar words bank comprising multilingual words; step 2: extracting eight eigenvalues; step 3: calculating a similarity of any two documents i and j; step 4: selecting accumulation points from a set of the documents to establish a cluster; step 5: adding residual documents which are not selected in the set to the cluster; and step 6: disposing the cluster in a circular ring structure. The method of the present invention without limiting categories of languages in the documents, the accumulation points are selected according to judgments of similarity to establish clusters and classify multilingual documents in the clusters. The method of the present invention is suitable for clustering multilingual documents.

Claims

1-11. -11. (canceled)

12. :

A clustering method for multilingual documents, comprising following steps of;

step 1;

establishing a similar words bank comprising multilingual words;

step 2;

extracting eight eigenvalues;

step 3;

calculating a similarity of any two documents i and j according to the eight eigenvalues;

step 4;

selecting accumulation points from a set of the documents to establish a cluster;

step 5;

adding residual documents which are not selected in the set to the cluster; and

step 6;

disposing the cluster in a circular ring structure.

13. :

The clustering method, as recited in claim 12, wherein in the step 1, multilingual words having identical or similar meanings are recorded in each line of the similar words bank, and whether the multilingual words are verbs or nouns is marked.

14. :

The clustering method, as recited in claim 12, wherein in the step 2, the eight eigenvalues comprise;

an eigenvalue of citation relationships (f₁), an eigenvalue of identical references (f₂), an eigenvalue of identical strings (f₃), an eigenvalue of similar strings (f₄), an eigenvalue of identical nouns (f₅), an eigenvalue of similar nouns (f₆), an eigenvalue of identical verbs (f₇), and an eigenvalue of similar verbs (f₈);

wherein the eight eigenvalues are not limited to a particular language, and the multilingual documents are fused in classification of the clusters;

wherein citation documents refer to references listed in a document;

the identical strings refer to strings formed by a section of identical words;

the similar strings refer to strings having a section of identical words or formed by a section of similar words recorded in the similar words bank;

the identical nouns refer to absolutely identical nouns;

the similar nouns refer to nouns recorded in a same line of the similar words bank;

the identical verbs refer to absolutely identical verbs; and

the similar verbs refer to verbs recorded in a same line of the similar words bank;

wherein for a document i, an eigenvector thereof is F(i),

F(i)=(f₁(i),f₂(i),f₃(i),f₄(i),f₅(i),f₆(i),f₇(i),f₈(i)).

15. :

The clustering method, as recited in claim 13, wherein in the step 2, the eight eigenvalues comprise;

an eigenvalue of citation relationships (f₁), an eigenvalue of identical references (f₂), an eigenvalue of identical strings (f₃), an eigenvalue of similar strings (f₄), an eigenvalue of identical nouns (f₅), an eigenvalue of similar nouns (f₆), an eigenvalue of identical verbs (f₇) and an eigenvalue of similar verbs (f₈);

wherein the eight eigenvalues are not limited to a particular language, and the multilingual documents are fused in classification of the clusters;

wherein citation documents refer to references listed in a document;

the identical strings refer to strings formed by a section of identical words;

the similar strings refer to strings having a section of identical words or formed by a section of similar words recorded in the similar words bank;

the identical nouns refer to absolutely identical nouns;

the similar nouns refer to nouns recorded in a same line of the similar words bank;

the identical verbs refer to absolutely identical verbs; and

the similar verbs refer to verbs recorded in a same line of the similar words bank;

wherein for a document i, an eigenvector thereof is F(i),

F(i)=(f₁(i),f₂(i),f₃(i),f₄(i),f₅(i),f₆(i),f₇(i),f₈(i)).

16. :

The clustering method, as recited in claim 12, wherein in the step 3, importance of the eight eigenvalues is f₁>

f₂>

f₃>

f₄>

f₅>

f₆>

f₇>

f₈;

wherein the step 3 specifically comprises a step of calculating products of eigenvalues of any two documents i and j, wherein the step of calculating the products comprises;

calculating a product of citation documents f₁(i)f₁(j), wherein W is defined as a weight of one document in i and j cited by the other document in i and j;

bool represents that whether a citation relationship exists, wherein a value of bool is 0 or 1, the value 0 represents that the citation relationship does not exist, and the value 1 represents that the citation relationship exists;

wherein a calculating expression is;

f₁(i)f₁(j)=bool×

W;

calculating a product of the identical references f₂(i)f₂(j), wherein d is defined as a weighting factor of division and d≧

1;

Refs represents a number of the references;

Max{Refs(i),Refs(j)} represents a maximum of the number of the references selected from i and j;

CommonRefs(i,j) represents a number of identical references in the two documents of i and j, and a calculating expression is;

17. :

The clustering method, as recited in claim 13, wherein in the step 3, importance of the eight eigenvalue is f₁>

f₂>

f₃>

f₄>

f₅>

f₆>

f₇>

f₈;

wherein the step 3 specifically comprises a step of calculating products of eigenvalues of any two documents i and j, wherein the step of calculating the products comprises;

calculating a product of citation documents f₁(i)f₁(j), wherein W is defined as a weight of one document in i and j cited by the other document in i and j;

bool represents that whether a citation relationship exists, wherein a value of bool is 0 or 1, the value 0 represents that the citation relationship does not exist, and the value 1 represents that the citation relationship exists;

wherein a calculating expression is;

f₁(i)f₁(j)=bool×

W;

calculating a product of the identical references f₂(i)f₂ (j), wherein d is defined as a weighting factor of division and d≧

1;

Refs represents a number of the references;

Max{Refs(i),Refs(j)} represents a maximum of the number of the references selected from i and j;

CommonRefs(i,j) represents a number of identical references in the two documents of i and j, and a calculating expression is;

18. :

The clustering method, as recited in claim 14, wherein, in the step 3, importance of the eight eigenvalue is f₁>

f₂>

f₃>

f₄>

f₅>

f₆>

f₇>

f₈;

wherein the step 3 specifically comprises a step of calculating products of eigenvalues of any two documents i and j, wherein the step of calculating the products comprises;

calculating a product of citation documents f₁(i)f₁(j), wherein W is defined as a weight of one document in i and j cited by the other document in i and j;

bool represents that whether a citation relationship exists, wherein a value of bool is 0 or 1, the value is 0 represents that the citation relationship does not exist, and the value 1 represents that the citation relationship exists;

wherein a calculating expression is;

f₁(i)f₁(j)=bool×

W;

calculating a product of the identical references f₂(i)f₂(j), wherein d is defined as a weighting factor of division and d≧

1;

Refs represents a number of the references;

Max{Refs(i),Refs(j)} represents a maximum of the number of the references selected from i and j;

CommonRefs(i,j) represents a number of identical references in the two documents of i and j, and a calculating expression is;

19. :

The clustering method, as recited in claim 15, wherein, in the step 3, importance of the eight eigenvalues is f₁>

f₂>

f₃>

f₄>

f₅>

f₆>

f₇>

f₈;

wherein the step 3 specifically comprises a step of calculating products of eigenvalues of any two documents i and j, wherein the step of calculating the products comprises;

calculating a product of citation documents f₁(i)f₁(j), wherein W is defined as a weight of one document in i and j cited by the other document in i and j;

bool represents that whether a citation relationship exists, wherein a value of bool is 0 or 1, the value is 0 represents that the citation relationship does not exist, and the value 1 represents that the citation relationship exists;

wherein a calculating expression is;

f₁(i)f₁(j)=bool×

W;

calculating a product of the identical references f₂(i)f₂(j), wherein d is defined as a weighting factor of division and d≧

1;

Refs represents a number of the references;

Max{Refs(i),Refs(j)} represents a maximum of the number of the references selected from i and j;

CommonRefs(i,j) represents a number of identical references in the two documents of i and j, and a calculating expression is;

20. :

The clustering method, as recited in claim 12, wherein in the step 4, on an initial condition, two most dissimilar documents, i.e., with a minimum Proximity(i,j), are selected for serving as two initial accumulation points p₁ and p₂, p₁ and p₂ are added to an accumulation point set denoted as Points;

residual accumulation points are selected according to a following maximum and minimum formula;

21. :

The clustering method, as recited in claim 13, wherein in the step 4, on an initial condition, two most dissimilar documents, i.e., with a minimum Proximity(i,j), are selected for serving as two initial accumulation points p₁ and p₂, p₁ and p₂ are added to an accumulation point set denoted as Points;

residual accumulation points are selected according to a following maximum and minimum formula;

22. :

The clustering method, as recited in claim 14, wherein in the step 4, on an initial condition, two most dissimilar documents, i.e., with a minimum Proximity(i,j), are selected for serving as two initial accumulation points p₁ and p₂, p₁ and p₂ are added to an accumulation point set denoted as Points;

residual accumulation points are selected according to a following maximum and minimum formula;

23. :

The clustering method, as recited in claim 15, wherein in the step 4, on an initial condition, two most dissimilar documents, i.e., with a minimum Proximity(i,j), are selected for serving as two initial accumulation points p₁ and p₂, p₁ and p₂ are added to an accumulation point set denoted as Points;

residual accumulation points are selected according to a following maximum and minimum formula;

24. :

The clustering method, as recited in claim 16, wherein in the step 4, on an initial condition, two most dissimilar documents, i.e., with a minimum Proximity(i,j), are selected for serving as two initial accumulation points p₁ and p₂, p₁ and p₂ are added to an accumulation point set denoted as Points;

residual accumulation points are selected according to following maximum and minimum formula;

25. :

The clustering method, as recited in claim 12, wherein in the step 5, N represents a total number of documents participating in clustering, M represents a total number of accumulation points selected;

in the beginning, M documents serve as accumulation points of the clustering, residual N−

M documents are added in the M clusters;

Cluster(p_r), r=1, 2, . . . , M represents a set of each cluster;

in the beginning, each set only has one documents serving as the accumulation points;

for a document i not participating in the clusters, a most similar cluster is calculated according to a following expression;

26. :

The clustering method, as recited in claim 13, wherein in the step 5, N represents a total number of documents participating in clustering, M represents a total number of accumulation points selected;

in the beginning, M documents serve as accumulation points of the clustering, residual N−

M documents are added in the M clusters;

Cluster(p_r), r=1, 2, . . . , M represents a set of each cluster;

in the beginning, each set only has one documents serving as the accumulation points;

for a document i not participating in the clusters, a most similar cluster is calculated according to a following expression;

27. :

The clustering method, as recited in claim 14, wherein in the step 5, N represents a total number of documents participating in clustering, M represents a total number of accumulation points selected;

in the beginning, M documents serve as accumulation points of the clustering, residual N−

M documents are added in the M clusters;

Cluster(p_r), r=1, 2, . . . , M represents a set of each cluster;

in the beginning, each set only has one document serving as the accumulation points;

for a document i not participating in the clusters, a most similar cluster is calculated according to a following expression;

28. :

The clustering method, as recited in claim 15, wherein in the step 5, N represents a total number of documents participating in clustering, M represents a total number of accumulation points selected;

in the beginning, M documents serve as accumulation points of the clustering, residual N−

M documents are added in the M clusters;

Cluster(p_r), r=1, 2, . . . , M represents a set of each cluster;

in the beginning, each set only has one documents serving as the accumulation points;

for a document i not participating in the clusters, a most similar cluster is calculated according to a following expression;

29. :

The clustering method, as recited in claim 24, wherein in the step 5, N represents a total number of documents participating in clustering, M represents a total number of accumulation points selected;

in the beginning, M documents serve as accumulation points of the clustering, residual N−

M documents are added in the M clusters;

Cluster(p_r), r=1, 2, . . . , M represents a set of each cluster;

in the beginning, each set only has one documents serving as the accumulation points;

for a document i not participating in the clusters, a most similar cluster is calculated according to following expression;

30. :

The clustering method as recited in claim 12, wherein the step 6 comprises a step of disposing M clusters in the circular ring structure, in such a manner that clusters having more similar characteristics are distributed closer, and clusters having more dissimilar characteristics are distributed farther;

wherein in an initial condition, two clusters are randomly selected to be added to the circular ring structure, and residual M−

2 clusters are added to the circular ring structure in sequence according to a following formula;

31. :

The clustering method as recited in claim 29, wherein in the step 6, M clusters are disposed in the circular ring structure, in such a manner that clusters having more similar characteristics are distributed closer, and clusters having more dissimilar characteristics are distributed farther;

wherein in an initial condition, two clusters are randomly selected to be added to the circular ring structure, and residual M−

2 clusters are added to the circular ring structure in sequence according to a following formula;