JP4789814B2 - Cluster generation apparatus and cluster generation method - Google Patents
Cluster generation apparatus and cluster generation method Download PDFInfo
- Publication number
- JP4789814B2 JP4789814B2 JP2007014194A JP2007014194A JP4789814B2 JP 4789814 B2 JP4789814 B2 JP 4789814B2 JP 2007014194 A JP2007014194 A JP 2007014194A JP 2007014194 A JP2007014194 A JP 2007014194A JP 4789814 B2 JP4789814 B2 JP 4789814B2
- Authority
- JP
- Japan
- Prior art keywords
- node
- cluster
- score
- graph
- arc
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
本発明は、グラフのクラスタを生成するクラスタ生成装置およびクラスタ生成方法に関するものである。 The present invention relates to a cluster generation device and a cluster generation method for generating a cluster of graphs.
インスタンスをもつノード間がアークによって接続されたグラフまたはそのサブグラフを分割したものをクラスタといい、クラスタは、その中ではノードのインスタンス同士が類似し、クラスタが異なればノードのインスタンス同士が類似しないように生成される。 A graph in which nodes with instances are connected by arcs or a subgraph divided is called a cluster. In a cluster, node instances are similar to each other, and if the clusters are different, node instances are not similar to each other. Is generated.
この出願の発明に関連する先行技術文献情報としては下記のものがある。 Prior art document information relating to the invention of this application includes the following.
非特許文献1では、サブグラフを検索する技術を開示している。グラフはRDFで表現され、検索にはクエリが使用される。
Non-Patent
非特許文献2では、クラスタを生成する技術を開示している。クラスタ生成には、エッジの密度の差異が用いられる。
Non-Patent
非特許文献3では、サブグラフを検索する技術を開示している。ここでは、グラフは重み付きグラフであり、ノードのオーソリティ値とハブ値をHITSアルゴリズムで計算する。そして、複数の情報のそれぞれをもつノード間にあるパスで、しかもそのパスを構成するノードについて計算された値がしきい値以上のものを検索する。
Non-Patent
非特許文献4では、指定されたシードのウェブページと周辺のウェブページを収集し、それらのグラフを生成する。そして、そのグラフのノードのオーソリティ値とハブ値をHITSアルゴリズムで計算し、その値が上位のウェブページがグラフの中心的なノード(コア)であることとする。
非特許文献1に記載の技術では、1つのサブグラフを検索するだけなので、複数の情報の関連性を示せない。また、グラフ構造の知識が必要である。
In the technique described in
非特許文献2に記載の技術では、クラスタを生成できるが、複数の情報の関連性を示せない。また、関心の対象が考慮されない。
In the technique described in Non-Patent
非特許文献3に記載の技術では、検索できるのはパスなので、複数の情報の関連性を十分に示せない。
In the technique described in
非特許文献4に記載の技術では、生成されるのは、シードを中心とした1つのグラフ(クラスタ)だけなので、複数の情報の関連性を示せない。また、関心の対象が考慮されない。 In the technique described in Non-Patent Document 4, since only one graph (cluster) centered on a seed is generated, the relevance of a plurality of information cannot be shown. Also, the object of interest is not considered.
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、グラフからそのノード間の関連性を示せるクラスタを生成できるクラスタ生成装置およびクラスタ生成方法を提供することにある。 The present invention has been made in view of the above problems, and an object of the present invention is to provide a cluster generation device and a cluster generation method capable of generating a cluster that can show the relationship between the nodes from a graph. .
上記の課題を解決するために、本発明では、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフまたはそのサブグラフのアークに、指定された関心度に応じたアークスコアを設定し、そのアークスコアを基にして、グラフなどのノードについてのノードスコアを計算し、計算されたノードスコアを基にして、グラフなどのクラスタを生成する。 In order to solve the above problem, in the present invention, an arc score corresponding to a specified degree of interest is set to an arc of a graph or a subgraph thereof in which nodes having instances are connected by an arc having a label, A node score for a node such as a graph is calculated based on the arc score, and a cluster such as a graph is generated based on the calculated node score.
本発明によれば、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。 According to the present invention, since the node score calculated based on the arc score for the arc between the nodes is used, it is possible to generate a cluster that can indicate the relationship between the nodes.
以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。 Hereinafter, embodiments of the present invention will be described with reference to the drawings. In addition, the same code | symbol is provided to the same thing and duplication description is abbreviate | omitted.
[第1の実施の形態]
図1は、第1の実施の形態に係るクラスタ生成装置1Aの構成図である。
[First Embodiment]
FIG. 1 is a configuration diagram of a
クラスタ生成装置1Aは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。
The
クラスタ生成装置1Aは、有向グラフであるグラフGを表示するためのデータ群が記憶されたグラフデータベース11と、ユーザ端末2で入力操作をさせるための入力用インタフェースを生成する入力用インタフェース生成部12と、ユーザ端末2のユーザの関心の対象として想定された項目(関心項目という)に対応づけて、その関心項目に関連するラベルを記憶したラベル記憶部13と、グラフGのアークにスコア(アークスコアという)を設定するアークスコア設定部14と、そのグラフGのノードについてスコア(ノードスコアという)を計算するノードスコア計算部15と、そのグラフGからクラスタを生成するクラスタ生成部16と、データベースインタフェース17と、処理結果を伝えるための出力用インタフェースを生成する出力用インタフェース生成部18とを備える。
The
クラスタは、グラフGの一部を分割して得られた各部分と同じものである。分割して得られるものなので、クラスタ同士では重複がない。また、サブグラフ内では分離している部分がないから、クラスタ内でも同様である。クラスタは、その中ではノードのインスタンス同士が類似し、クラスタが異なればノードのインスタンス同士が類似しないように生成される。 The cluster is the same as each part obtained by dividing a part of the graph G. Since it is obtained by dividing, there is no overlap between clusters. Further, since there is no separated part in the subgraph, the same applies to the cluster. The clusters are generated so that the node instances are similar to each other, and if the clusters are different, the node instances are not similar to each other.
クラスタ生成装置1Aは、各部(データベース含む)でデータの送受信(受け渡し)が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをクラスタ生成装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。他の実施の形態でも同様である。
The
図2は、グラフデータベース11に記憶されたデータ群を全て使って表示できるグラフGの一部を例示した図である。
FIG. 2 is a diagram illustrating a part of a graph G that can be displayed using all data groups stored in the
グラフデータベース11に記憶されたデータ群を全て使って、図2に一部を例示したグラフG、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフG、を表示することができる。逆にいえば、グラフGを表示するための過不足ないデータ群がグラフデータベース11に記憶されている。以下、そのデータ群を便宜的にグラフGという。また、なんらかのグラフ、サブグラフ(なんらかのグラフそのものまたはそれに含まれるグラフ)、パス(分岐および閉ループをもたないグラフ)などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。
Using all the data groups stored in the
グラフGでは、例えば、「XML」や「Bプロジェクト」などのインスタンスをもつノードが、「rm:技術キーワード」や「rm:著者」などのラベルをもつアークで接続される。また、グラフGでは、ノードにそのインスタンス「Person:山田太郎」などの概念であるクラス「Person:人」などが定義される。 In the graph G, for example, nodes having instances such as “XML” and “B project” are connected by arcs having labels such as “rm: technical keyword” and “rm: author”. Further, in the graph G, a class “Person: person” or the like that is a concept such as an instance “Person: Taro Yamada” is defined in a node.
図3は、グラフデータベース11に記憶されたデータ群の一部を例示した図である。
FIG. 3 is a diagram illustrating a part of a data group stored in the
例えば、最初のデータ「<org:Dプロジェクト><rm:技術キーワード>”XML”」は、インスタンス「org:Dプロジェクト」をもつノードからインスタンス「XML」のノードへ向かうアークがラベル「rm:技術キーワード」をもつことを示している。また、例えば、最後のデータ「<person:鈴木花子><rdf:type><Person:人>」は、インスタンス「person:鈴木花子」をもつノードのクラスが「person:人」であることを示している。 For example, in the first data “<org: D project> <rm: technical keyword>“ XML ””, an arc from the node having the instance “org: D project” to the node of the instance “XML” is labeled “rm: technique”. It has shown that it has a keyword. For example, the last data “<person: Hanako Suzuki> <rdf: type> <Person: person>” indicates that the class of the node having the instance “person: Hanako Suzuki” is “person: person”. ing.
なお、各データは、実際にはRDF(以下の文献に記載)で表現されている。 Each data is actually expressed in RDF (described in the following document).
「Resource Description Framework(RDF)Model and Syntax Specification」, Ora Lassia, Ralph R.Swick編,[online], インターネット<URL:http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/>
「RDF Vocabulary Description Language 1.0: RDF Schema」, Dan Brickley, R.V.Guha編,[online], インターネット<URL:http://www.w3.org/TR/rdf-schema/>
図4は、ラベル記憶部13の記憶内容を示す図である。
"Resource Description Framework (RDF) Model and Syntax Specification", Ora Lassia, Ralph R. Swick, [online], Internet <URL: http://www.w3.org/TR/1999/REC-rdf-syntax- 19990222 />
“RDF Vocabulary Description Language 1.0: RDF Schema”, Dan Brickley, RVGuha, [online], Internet <URL: http://www.w3.org/TR/rdf-schema/>
FIG. 4 is a diagram showing the contents stored in the
例えば、関心項目「所属」には、ラベル「person:所属」、ラベル「rm:学会KW」、ラベル「rm:会員」が対応づけられている。 For example, a label “person: affiliation”, a label “rm: academic society KW”, and a label “rm: member” are associated with the interest item “affiliation”.
また、関心項目「学術論文」には、ラベル「rm:著者」、ラベル「rm:著者KW」が対応づけられている。 Further, the label “rm: author” and the label “rm: author KW” are associated with the item of interest “scientific paper”.
また、関心項目「サービス開発」には、ラベル「ms:KW」、ラベル「ms:担当者」、ラベル「ms:参考文献」、ラベル「ms:著者」が対応づけられている。 The item of interest “service development” is associated with a label “ms: KW”, a label “ms: person in charge”, a label “ms: reference”, and a label “ms: author”.
かかるラベルは、対応する関心項目に関連するものとして、グラフGのラベルから選択されたものである。 Such a label is selected from the labels of the graph G as related to the corresponding item of interest.
(第1の実施の形態の動作)
図5は、第1の実施の形態のシーケンス図である。
(Operation of the first embodiment)
FIG. 5 is a sequence diagram of the first embodiment.
クラスタ生成装置1Aでは、入力用インタフェース生成部12が、入力用インタフェースを生成し、それをユーザ端末2に送信して(S1)、図6に示したように表示させる(S3)。ここでの操作により特定された1以上のキーワードKWと1以上のクラスCLの一方または両方、各関心項目の関心度(大、中、小のいずれか)の組合せ、並びに、しきい値THをユーザ端末2がクラスタ生成装置1Aに送信する(S5)。しきい値THは、これを例えば低く設定して、ノードを多く含むクラスタを表示させるためのものである。なお、これらのキーワードKWなどは、クラスタ生成装置1Aに記憶しておき、それを適宜読み出して使用してもよい。
In the
(アークスコア設定)
クラスタ生成装置1Aは、アークスコア設定部14が、グラフGのアークにアークスコアを設定する(S11)。具体的には、アークスコアを含むクエリをデータベースインタフェース17に送信する(S111)ことで、アークスコアが設定されたグラフGを取得する(S112)。
(Arc score setting)
In the
例えば、関心項目「所属」にラベル記憶部13で対応づけられたラベル「person:所属」、ラベル「rm:学会KW」、ラベル「rm:会員」に対し、関心項目「所属」の関心度に応じたアークスコアを設定する。
For example, for the label “person: affiliation”, the label “rm: academic society KW”, and the label “rm: member” associated with the interest item “affiliation” in the
また、関心項目「学術論文」にラベル記憶部13で対応づけられたラベル「rm:著者」、ラベル「rm:著者KW」に対し、関心項目「学術論文」の関心度に応じたアークスコアを設定する。
Further, an arc score corresponding to the interest level of the interest item “scholarly paper” is given to the label “rm: author” and the label “rm: author KW” associated with the interest item “scholarly paper” in the
また、関心項目「サービス開発」にラベル記憶部13で対応づけられたラベル「ms:KW」、ラベル「ms:担当者」、ラベル「ms:参考文献」、ラベル「ms:著者」に対し、関心項目「サービス開発」の関心度に応じたアークスコアを設定する。
In addition, for the label “ms: KW”, the label “ms: person in charge”, the label “ms: reference”, and the label “ms: author” associated with the item of interest “service development” in the
例えば、関心度が「大」の場合はアークスコア「1.0」を設定し、関心度が「中」の場合はアークスコア「0.1」を設定し、関心度が「小」の場合はアークスコア「0.01」を設定する。なお、関心度を数値とし、その数値である関心度に相関するアークスコアを設定してもよい。 For example, when the degree of interest is “large”, the arc score “1.0” is set, when the degree of interest is “medium”, the arc score “0.1” is set, and when the degree of interest is “small”. Sets the arc score "0.01". Note that the degree of interest may be a numerical value, and an arc score that correlates with the numerical value of interest may be set.
そのグラフGの各ノードのインスタンスをそのノードのクラスに置き換え、同一のインスタンス(クラス)をもつノードではその中の1つのみ残し、そのようにしてなるグラフに上記の各アークスコアを当てはめると、その一部は、例えば図7のようになる。 Replacing the instance of each node in the graph G with the class of the node, leaving only one of the nodes having the same instance (class), and applying the above arc scores to the graph thus formed, A part of it is as shown in FIG. 7, for example.
(ノードスコア計算)
次に、クラスタ生成装置1Aは、ノードスコア計算部15が、グラフGのノードのスコア(ノードスコアという)を計算する(S13)。
(Node score calculation)
Next, in the
図8は、ノードスコア計算のフローチャートを示す図である。かかる計算は、アークスコアを基にしたものであり、リンク解析ともいう。 FIG. 8 is a diagram showing a flowchart of node score calculation. Such calculation is based on the arc score and is also called link analysis.
ノードスコア計算部15は、まず、グラフGのノードに、その重要度を示すこととなる、ノードスコアの初期値「1」を設定する(S101)。
The node
次に、各ノードにつき、例えば、PageRankのアルゴリズムを用いた、図9の式により、ノードスコアを計算する(S103)。 Next, for each node, for example, a node score is calculated by the equation of FIG. 9 using the PageRank algorithm (S103).
そして、このノードスコアで、グラフGに設定されたノードスコアの初期値を更新する(S105)。このような計算更新を、ノードスコアが収束するまで、再帰的に行う。これにより、ノードスコアが重要度を示すこととなる。 Then, the initial value of the node score set in the graph G is updated with this node score (S105). Such calculation update is performed recursively until the node score converges. As a result, the node score indicates the importance.
グラフGに各アークスコアを当てはめたグラフの一部が、例えば図10に示すようなものであった場合、同図に示すように、例えば、インスタンス「XML」をもつノードのノードスコアは0.4となる。インスタンス「Person:電々三郎」をもつノードのノードスコアは0.9となる。インスタンス「org:H3G」をもつノードのノードスコアは0.6となる。 If a part of the graph in which each arc score is applied to the graph G is as shown in FIG. 10, for example, the node score of the node having the instance “XML” is 0. 4 The node score of the node having the instance “Person: Dentsu Saburo” is 0.9. The node score of the node having the instance “org: H3G” is 0.6.
次に、クラスタ生成装置1Aは、クラスタ生成部16が、グラフGからクラスタを生成する(S15)。ここでは、グラフGでキーワードKWに等しいインスタンスをもつノードまたはグラフGでクラスCLが定義されたノードである各ノードにつき、そのノード(キーノードという)を含むクラスタを生成する。キーノードと同数のクラスタが生成される。
Next, in the
図11は、1つのクラスタを生成するフローチャートを示す図であり、このフローチャートによるクラスタ生成が各キーノードについて同時に行われる。 FIG. 11 is a diagram showing a flowchart for generating one cluster, and cluster generation according to this flowchart is simultaneously performed for each key node.
まず、クラスタ生成部16は、グラフGから所定条件を満たさないノードを除外する(S201)。ここでは、キーノードを起点とし、起点に単一のアークで接続されたノードであり且つしきい値以下のノードスコアをもつノードを除外する(S201)。次に、除外されなかったノードを候補としてこれををクラスタに含める又は除外する処理を1候補づつ行うのだが、まず、未処理である1つの候補が、他のクラスタ生成でも候補になっているか否かを判定する(S203)。NOと判定された場合は、候補を本クラスタ生成に係るクラスタに含める(S205)。一方、YESと判定された場合は、候補と本クラスタ生成に係るキーノードとの間のアーク数、候補と他のクラスタ生成に係るキーノードとの間のアーク数を計算し、それらの中で本クラスタ生成に係るアーク数が最大であるか否かを判定する(S207)。NOと判定された場合は、候補を本クラスタ生成の候補から除外する(S209)。YESと判定された場合は、候補と他のクラスタ生成に係るキーノードとの間のアーク数の中で、候補と本クラスタ生成に係るキーノードとの間のアーク数と同数のものがあるか否かを判定する(S211)。つまり、他にもアーク数が最大のものがあるか否かを判定する(S211)。NOと判定された場合は、候補を本クラスタ生成に係るクラスタに含める(S205)。YESと判定された場合は、候補のノードスコアとその候補の本クラスタ生成に係る起点のノードスコアとの差分、候補のノードスコアとその候補の他のクラスタ生成に係る起点のノードスコアとの差分を計算し、その中で本クラスタ生成に係る差分が最小か否かを判定する(S213)。NOと判定された場合は、候補を本クラスタ生成に係るクラスタに含め候補から除外する(S209)。YESと判定された場合は、候補を本クラスタ生成に係るクラスタに含める(S205)。
First, the
ステップS205、S205を行ったら、次に、未処理の候補があるか否かを判定する(S215)。YESと判定された場合は、ステップS203に戻る。NOと判定された場合は、クラスタに含められたノードの1つを新たな起点とし(S217)、ステップS201に戻る。そのステップS201では、その新たな起点に単一のアークで接続されたノードであり且つしきい値以下のノードスコアをもつノードを除外する(S201)。 After performing steps S205 and S205, it is next determined whether or not there is an unprocessed candidate (S215). When it determines with YES, it returns to step S203. When it is determined NO, one of the nodes included in the cluster is set as a new starting point (S217), and the process returns to step S201. In step S201, nodes that are connected to the new starting point by a single arc and have a node score equal to or lower than the threshold value are excluded (S201).
なお、ある起点に単一のアークで接続されたノードからクラスタに含ませられたものが複数あり(便宜的にノードn11,n12という)、その中の1つ(ノードn11とする)が新たな起点となって、その起点に単一のアークで接続されたノード(ノードn111という)がクラスタに含ませられた場合は、ノードn111よりもノードn12が先に起点となる。 There are a plurality of nodes included in the cluster from nodes connected to a starting point by a single arc (referred to as nodes n11 and n12 for convenience), and one of them (referred to as node n11) is a new one. When a node connected to the starting point by a single arc (referred to as node n111) is included in the cluster, node n12 is the starting point before node n111.
図12は、2つのクラスタが生成された様子を示す図であり、アークの矢印とラベル、ノードのインスタンスについては、記載省略している。 FIG. 12 is a diagram illustrating a state in which two clusters are generated, and descriptions of arc arrows, labels, and node instances are omitted.
同図に示すように、ノードI1とキーノードKI1との間のアーク数は「3」であり、ノードI1とキーノードKI2との間のアーク数は「2」であるから、ノードI1は、キーノードKI1を含むクラスタC1でなく、キーノードKI2を含むクラスタC2に含められる。 As shown in the figure, since the number of arcs between the node I1 and the key node KI1 is “3” and the number of arcs between the node I1 and the key node KI2 is “2”, the node I1 is the key node KI1. Is included in the cluster C2 including the key node KI2.
また、同図に示すように、ノードI2とキーノードKI1との間のアーク数は「2」であり、ノードI2とキーノードKI2との間のアーク数は「2」である。また、ノードI2のノードスコア「0.6」とクラスタC1に係る起点I3のノードスコア「0.9」との差分は「0.3」であり、ノードI2のノードスコア「0.6」とクラスタC2に係る起点I4のノードスコア「0.8」との差分は「0.2」であるから、ノードI2はクラスタC2に含められる。 As shown in the figure, the number of arcs between the node I2 and the key node KI1 is “2”, and the number of arcs between the node I2 and the key node KI2 is “2”. Further, the difference between the node score “0.6” of the node I2 and the node score “0.9” of the starting point I3 related to the cluster C1 is “0.3”, and the node score “0.6” of the node I2 is Since the difference from the node score “0.8” of the starting point I4 related to the cluster C2 is “0.2”, the node I2 is included in the cluster C2.
次に、図5に戻り、出力用インタフェース生成部18が、生成された各クラスタの出力用インタフェースを生成し、これをユーザ端末2に送信し(S19)、各クラスタを表示させる(S21)。
Next, returning to FIG. 5, the output
第1の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフGのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(アークスコア設定部14)と、そのアークスコアを基にして、グラフGのノードについてのノードスコアを計算するノードスコア計算手段(ノードスコア計算部15)と、その計算されたノードスコアを基にして、グラフGのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段(クラスタ生成部16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。 According to the first embodiment, the arc score setting means (arc score) that sets an arc score according to the designated degree of interest in the arc of the graph G in which nodes having instances are connected by an arc having a label. A setting unit 14), a node score calculation means (node score calculation unit 15) for calculating a node score for a node of the graph G based on the arc score, and a graph based on the calculated node score Cluster generation means (cluster generation unit 16) for generating a cluster that is a subgraph of G and is a subgraph that does not overlap with the rest, and a node score calculated based on an arc score for arcs between nodes Is used, it is possible to generate a cluster that can show the relationship between nodes.
また、キーノード以外のノード(中間ノード)についてのノードスコアを用いられるので、ノード間の関連性を示せるクラスタを生成することができる。 In addition, since the node score for nodes other than the key nodes (intermediate nodes) is used, a cluster that can show the relationship between the nodes can be generated.
また、図11のステップS207、S211、S213を行うので、ノード間の関連性を示せるクラスタを生成することができる。 Further, since steps S207, S211, and S213 in FIG. 11 are performed, a cluster that can indicate the relationship between the nodes can be generated.
また、関心度に応じたアークスコアを設定するので、関心度に適したクラスタを生成することができる。 In addition, since an arc score corresponding to the degree of interest is set, a cluster suitable for the degree of interest can be generated.
また、ラベル記憶部13において、関心項目に対応づけて予めラベルを記憶させ、指定された関心度に対応する関心項目に対応づけられたラベルをもつアークに、当該関心度に応じたアークスコアを設定するので、関心度に応じたクラスタを生成することができる。[第2の実施の形態]
図13は、第2の実施の形態に係るクラスタ生成装置1Bの構成図である。
In the
FIG. 13 is a configuration diagram of the
クラスタ生成装置1Bは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。
The
クラスタ生成装置1Bは、グラフデータベース11と、入力用インタフェース生成部12と、ノードスコア記憶部13Aと、ノードスコア設定部14Aと、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18とを備える。
The
本実施の形態では、予め関心度の組合せのそれぞれにつき、図10に示したようなノードスコアが計算され、ノードスコア記憶部13Aが、組合せに対応づけてノードスコアを記憶している。
In this embodiment, a node score as shown in FIG. 10 is calculated in advance for each combination of interest levels, and the node
(第2の実施の形態の動作)
図14は、第2の実施の形態のシーケンス図である。
(Operation of Second Embodiment)
FIG. 14 is a sequence diagram of the second embodiment.
ステップS5までは、第1の実施の形態と同様である。 Up to step S5 is the same as in the first embodiment.
続いて、ノードスコア設定部14Aは、ユーザ端末2から送信された関心度の組合せに対応するノードスコアを選択し(S11A)、それをグラフGのノードに設定する(S11B)。具体的には、ノードスコアを含むクエリをデータベースインタフェース17に送信する(S115)ことで、ノードスコアが設定されたグラフを取得する(S116)。
Subsequently, the node
そして、第1の実施の形態と同様に、そのノードスコアを設定したグラフからクラスタを生成する(S15)。以降も、第1の実施の形態と同様である。 Then, as in the first embodiment, a cluster is generated from the graph in which the node score is set (S15). The subsequent steps are the same as in the first embodiment.
第2の実施の形態によれば、グラフGのアークに、指定される関心度に応じたアークスコアが設定され、そのアークスコアを基にして、グラフGのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段(ノードスコア記憶部13A)と、指定された関心度に対応づけてノードスコア記憶手段(13A)に記憶されたノードスコアをグラフGに設定するノードスコア設定手段(ノードスコア設定部14A)と、設定されたノードスコアを基にして、グラフGのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
According to the second embodiment, an arc score corresponding to the specified degree of interest is set for the arc of the graph G, and the node score for the node of the graph G is calculated based on the arc score. The node score storage means (node
また、関心度の組合せに対応するノードスコアを選択するので、関心度の組合せに適したクラスタを生成することができる。 Moreover, since the node score corresponding to the combination of interest levels is selected, a cluster suitable for the combination of interest levels can be generated.
[第3の実施の形態]
図15は、第3の実施の形態に係るクラスタ生成装置1Cの構成図である。
[Third Embodiment]
FIG. 15 is a configuration diagram of the
クラスタ生成装置1Cは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。
The
クラスタ生成装置1Cは、グラフデータベース11と、入力用インタフェース生成部12と、ラベル記憶部13と、アークスコア設定部14と、ノードスコア計算部15と、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18と、グラフ処理部19とを備える。
The
図16は、第3の実施の形態のシーケンス図である。 FIG. 16 is a sequence diagram of the third embodiment.
予めクラスタ生成装置1Cにしきい値THSが設定される。しきい値THSは、経験的にしきい値THより低くなるように設定される。
A threshold value THS is set in advance in the
ステップS13までは、第1の実施の形態と同様である。 Up to step S13 is the same as in the first embodiment.
続いて、グラフ処理部19が、そのグラフの一部を削除する(S14A)。ここでは、いずれかのキーノードに少なくとも1つのアークで接続され且つしきい値THSより大きいノードスコアをもつノードを検出し、それ以外のノードとそのノードに接続されたアークを削除する。
Subsequently, the
そして、そのグラフについてステップS13と同様のノードスコア計算を行う(S14B)。以降も、第1の実施の形態と同様である。 And the node score calculation similar to step S13 is performed about the graph (S14B). The subsequent steps are the same as in the first embodiment.
第3の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフGのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(14)と、そのアークスコアを基にして、グラフGのノードについてのノードスコアを計算する第1のノードスコア計算手段(ステップS13が該当する)と、そのノードスコアを基にして、グラフGの一部を削除するグラフ処理手段(グラフ処理部19)と、一部を削除されたグラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算する第2のノードスコア計算手段(ステップS14Bが該当する)と、そのノードスコアを基にして、グラフGのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。 According to the third embodiment, the arc score setting means (14) for setting an arc score corresponding to the designated degree of interest in the arc of the graph G in which nodes having instances are connected by arcs having labels. And a first node score calculation means for calculating a node score for a node of the graph G based on the arc score (corresponding to step S13), and a part of the graph G based on the node score. And a graph processing means (graph processing unit 19) for deleting the second and a new node score for the node of the graph based on the arc score set for the arc of the partially deleted graph Node score calculating means (corresponding to step S14B) and cluster generating means for generating a cluster of the graph G based on the node score 16) and provided with a so calculated node score is used based on the arc score for arc located between nodes, it is possible to generate a cluster can show the relationship between nodes.
また、キーノードを含む部分以外を削除した後のグラフでノードスコアを計算するので、キーノードを含む部分でのノード間の関連性を示せるクラスタを生成することができる。 Further, since the node score is calculated from the graph after deleting the part other than the part including the key node, it is possible to generate a cluster that can show the relationship between the nodes in the part including the key node.
[第4の実施の形態]
図17は、第4の実施の形態に係るクラスタ生成装置1Dの構成図である。
[Fourth Embodiment]
FIG. 17 is a configuration diagram of a
クラスタ生成装置1Dは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。
The
クラスタ生成装置1Dは、グラフデータベース11と、入力用インタフェース生成部12と、ラベル記憶部13と、ノードスコア記憶部13Aと、アークスコア設定部14、ノードスコア設定部14Aと、ノードスコア計算部15と、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18と、グラフ処理部19とを備える。
The
(第4の実施の形態の動作)
第4の実施の形態では、クラスタ生成装置1Dに、しきい値THより低くなるようにしきい値THSが予め設定される。
(Operation of the fourth embodiment)
In the fourth embodiment, threshold value THS is preset in
図18は、第4の実施の形態のシーケンス図である。 FIG. 18 is a sequence diagram of the fourth embodiment.
ステップS11Bまでは、第2の実施の形態と同様である。 Steps up to step S11B are the same as in the second embodiment.
続いて、グラフ処理部19が、第3の実施の形態と同様なしきい値THSを用いた判定により、そのグラフの一部を削除する(S14A)。そして、一部を削除したグラフについて、第1の実施の形態のステップS11と同様なアークスコア設定を行い(S12)、続いて、当該グラフについて、第1の実施の形態のステップS13と同様なノードスコア計算を行う(S14B)。以降も、第1の実施の形態と同様である。
Subsequently, the
第4の実施の形態によれば、グラフGのアークに、指定される関心度に応じたアークスコアが設定され、そのアークスコアを基にして、グラフGのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段(13A)と、指定された関心度に対応づけてノードスコア記憶手段(13A)に記憶されたノードスコアをグラフGに設定するノードスコア設定手段(14A)と、その設定されたノードスコアを基にして、グラフの一部を削除するグラフ処理手段(19)と、一部を削除されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(14)と、一部を削除されたグラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算するノードスコア計算手段(15)と、そのノードスコアを基にして、グラフGのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。 According to the fourth embodiment, an arc score corresponding to the designated degree of interest is set for the arc of the graph G, and the node score for the node of the graph G is calculated based on the arc score. The node score stored in the node score storage means (13A) is stored in advance in association with the corresponding degree of interest, and the node score storage means (13A) is stored in the node score storage means (13A) in association with the designated degree of interest. A node score setting means (14A) for setting a graph G, a graph processing means (19) for deleting a part of the graph based on the set node score, and an arc of the graph from which a part is deleted Based on the arc score setting means (14) for setting the arc score according to the specified degree of interest, and the arc score set for the arc of the partially deleted graph A node score calculation means (15) for calculating a new node score for the node of the graph, and a cluster generation means (16) for generating a cluster of the graph G based on the node score. Since the node score calculated based on the arc score for the arc in between is used, a cluster that can show the relationship between the nodes can be generated.
また、関心度の組合せに対応するノードスコアを選択するので、関心度の組合せに適したクラスタを生成することができる。 Moreover, since the node score corresponding to the combination of interest levels is selected, a cluster suitable for the combination of interest levels can be generated.
また、キーノードを含む部分以外を削除した後のグラフでノードスコアを計算するので、キーノードを含む部分でのノード間の関連性を示せるクラスタを生成することができる。 Further, since the node score is calculated from the graph after deleting the part other than the part including the key node, it is possible to generate a cluster that can show the relationship between the nodes in the part including the key node.
[第5の実施の形態]
図19は、第5の実施の形態に係るクラスタ生成装置1Eの構成図である。
[Fifth Embodiment]
FIG. 19 is a configuration diagram of a
グラフ検索装置1Eは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。
The
クラスタ生成装置1Eは、グラフデータベース11と、パターンデータベース11Aと、入力用インタフェース生成部12と、ラベル記憶部13と、アークスコア設定部14と、パターン検索部14Bと、ノードスコア計算部15と、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18とを備える。
The
パターンデータベース11Aには、グラフGからサブグラフを検索するためのパターンが記憶される。
The
(パターンの説明)
ここでパターンについて説明する。
(Description of pattern)
Here, the pattern will be described.
パターンは、グラフデータベース11に記憶されるデータ群(グラフG)の一部をなすデータ群と同様なものであり、それを図20のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。パスパターンはパスを検索するパターンであり、サブグラフパターンはサブグラフを検索するものである。
The pattern is the same as the data group forming a part of the data group (graph G) stored in the
パスパターンは、例えば、同図のようなグラフ(パス)である。 The path pattern is, for example, a graph (path) as shown in FIG.
パターンはグラフと同様に、実際にはデータ群であるが、それを逐一説明するのは冗長であるから、パターンの説明はグラフ化されたもので行う。 Like a graph, a pattern is actually a data group, but since it is redundant to explain each pattern, the pattern is explained in a graph.
一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、同図に示すように、?とそれに後続する単語からなる。 In general, in a pattern, some nodes and arcs have instances and labels, and the rest do not. Variables are set for nodes and arcs that do not have instances or labels. As shown in the figure, the variables are Followed by a word.
また、一般的にパターンでは、必要があれば、変数が設定された一部のノードに、そのパターンにより検索されるグラフにおける、同位置のノードがもつインスタンスの上位概念を示すクラスが予め定義される。 In general, in a pattern, if necessary, a class indicating a high-level concept of an instance of a node at the same position in a graph searched by the pattern is defined in advance for some nodes set with variables. The
同図のパスパターンでは、キーワードKW「セマンティックweb」がインスタンスであるノードを一方端とすると、他方端のノードにクラスCL「Person:人」が定義されている。 In the path pattern shown in the figure, when a node having the keyword KW “semantic web” as an instance is one end, a class CL “Person: person” is defined in the other end node.
このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。 A subgraph retrieved from a certain graph by such a pattern has the following conditions.
つまり、検索されるのは、(1)そのグラフまたはそのサブグラフであって、(2)パターンの構造を過不足なく有し、(3)パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、(4)場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。 In other words, what is searched is (1) the graph or its subgraph, (2) having a pattern structure without excess or deficiency, (3) having instances or labels within the pattern without deficiency, In other words, nodes and arcs at positions equal to the positions of nodes and arcs with instances and labels in the pattern have instances and labels equal to the instances, and (4) in some cases, classes included in the pattern are defined A node at a position equal to the position of the node has an instance that is a subordinate concept of the class.
なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。 Note that searching for a subgraph in this way by pattern is referred to as searching for a subgraph that matches the pattern.
図21は、第5の実施の形態のシーケンス図である。 FIG. 21 is a sequence diagram of the fifth embodiment.
ステップS5までは、第1の実施の形態と同様である。 Up to step S5 is the same as in the first embodiment.
次に、キーワードKWに等しいインスタンスをもつノードをもつパターンや、グラフGでクラスCLが定義されたノードのインスタンスに等しいインスタンスをもつノードをもつパターンや、その両方をもつパターンを検索する(S11C)。 Next, a pattern having a node having an instance equal to the keyword KW, a pattern having a node having an instance equal to an instance of a node whose class CL is defined in the graph G, and a pattern having both are searched (S11C). .
次に、アークスコア設定部14が、グラフGでそのパターンにマッチするサブグラフにおけるアークに対し、第1の実施の形態のステップS11と同様に、アークスコアを設定する(S12)。具体的には、パターンの内容やアークスコアを含むクエリをデータベースインタフェース17に送信する(S12A)ことで、グラフGでそのパターンにマッチするサブグラフであってアークスコアが設定されたグラフを取得する(S12B)。
Next, the arc
そして、そのグラフについて、第1の実施の形態と同様のノードスコア計算を行う(S13)。以降も、第1の実施の形態と同様である。 And the node score calculation similar to 1st Embodiment is performed about the graph (S13). The subsequent steps are the same as in the first embodiment.
第5の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフGのサブグラフを検索する際に用いられるパターンが記憶されるパターンデータベース11Aと、指定された条件にマッチするパターンを検索するパターン検索手段(パターン検索部14B)と、検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(14)と、そのアークスコアを基にして、サブグラフのノードについてのノードスコアを計算するノードスコア計算手段(15)と、そのノードスコアを基にして、サブグラフのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。
According to the fifth embodiment, the
1A、1B、1C、1D、1E:クラスタ生成装置
11 グラフデータベース
11A パターンデータベース
13 ラベル記憶部
13A ノードスコア記憶部
14 アークスコア設定部
14A ノードスコア設定部
15 ノードスコア計算部
16 クラスタ生成部
19 グラフ処理部
1A, 1B, 1C, 1D, 1E:
Claims (11)
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算するノードスコア計算手段と、
前記計算されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成装置。 An arc score setting means for setting an arc score corresponding to a specified degree of interest in an arc of a graph in which nodes having instances are connected by an arc having a label;
Node score calculation means for calculating a node score for a node of the graph based on the arc score;
Cluster generation means for generating a cluster that is a subgraph of the graph and is a subgraph that does not overlap with the rest based on the calculated node score ;
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定するノードスコア設定手段と、
前記設定されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成装置。 An arc score corresponding to a specified degree of interest is set to an arc of a graph in which nodes having instances are connected by an arc having a label. Based on the arc score, a node score for the node of the graph is determined based on the arc score. A node score storage means in which the calculated node score is stored in advance in association with the corresponding degree of interest;
Node score setting means for setting the node score stored in the node score storage means in association with the designated degree of interest in the graph;
Cluster generating means for generating a cluster that is a sub-graph of the graph based on the set node score and is a sub-graph that does not overlap with the rest , and
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算する第1のノードスコア計算手段と、
前記ノードスコアを基にして、前記グラフの一部を削除するグラフ処理手段と、
一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算する第2のノードスコア計算手段と、
当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成装置。 An arc score setting means for setting an arc score corresponding to a specified degree of interest in an arc of a graph in which nodes having instances are connected by an arc having a label;
First node score calculation means for calculating a node score for a node of the graph based on the arc score;
Graph processing means for deleting a part of the graph based on the node score;
Second node score calculation means for calculating a new node score for a node of the graph based on the arc score set for the arc of the graph from which a part has been deleted;
Cluster generating means for generating a cluster that is a sub-graph of the graph based on the node score and does not overlap with the rest , and
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定するノードスコア設定手段と、
前記設定されたノードスコアを基にして、前記グラフの一部を削除するグラフ処理手段と、
一部を削除された前記グラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算するノードスコア計算手段と、
当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成装置。 An arc score corresponding to a specified degree of interest is set to an arc of a graph in which nodes having instances are connected by an arc having a label. Based on the arc score, a node score for the node of the graph is determined based on the arc score. A node score storage means in which the calculated node score is stored in advance in association with the corresponding degree of interest;
Node score setting means for setting the node score stored in the node score storage means in association with the designated degree of interest in the graph;
Graph processing means for deleting a part of the graph based on the set node score;
Arc score setting means for setting an arc score according to the specified degree of interest in the arc of the graph from which a part has been deleted;
Node score calculation means for calculating a new node score for a node of the graph based on the arc score set for the arc of the graph from which a part has been deleted;
Cluster generating means for generating a cluster that is a sub-graph of the graph based on the node score and does not overlap with the rest , and
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
指定された条件にマッチするパターンを検索するパターン検索手段と、
検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記サブグラフのノードについてのノードスコアを計算するノードスコア計算手段と、
前記ノードスコアを基にして、前記サブグラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成装置。 A pattern database that stores patterns used to search subgraphs of a graph in which nodes having instances are connected by arcs having labels;
A pattern search means for searching for a pattern that matches a specified condition;
Arc score setting means for setting an arc score according to the specified degree of interest to the arc of the subgraph that matches the searched pattern;
Node score calculating means for calculating a node score for the node of the subgraph based on the arc score;
Based on the node score, and a cluster generation means for generating a cluster which is non-overlapping sub-graph of a subgraph and is and the remaining part of the subgraph,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
前記アークスコア設定手段は、指定された関心度に対応する関心項目に前記ラベル記憶手段で対応づけられたラベルをもつアークに、当該指定された関心度に応じたアークスコアを設定する
ことを特徴とする請求項1、3、4、5のいずれかに記載のクラスタ生成装置。 Label storage means for storing a label in advance in association with an item of interest corresponding to the specified degree of interest;
The arc score setting means sets an arc score corresponding to the designated degree of interest for an arc having a label associated with the item of interest corresponding to the designated degree of interest by the label storage means. The cluster generation device according to any one of claims 1, 3, 4, and 5 .
当該クラスタ生成装置の前記ノードスコア計算手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置の前記クラスタ生成手段が、前記計算されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。 The arc score setting means of the cluster generation device according to claim 1 sets an arc score corresponding to a designated degree of interest in the arc of the graph,
The node score calculation means of the cluster generation device calculates a node score for a node of the graph based on the arc score,
When the cluster generation unit of the cluster generation device generates a cluster that is a sub-graph of the graph and a sub-graph with no overlap with the rest based on the calculated node score ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
当該クラスタ生成装置のクラスタ生成手段が、前記設定されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。 The node score setting unit of the cluster generation device according to claim 2 sets a node score stored in the node score storage unit in association with a designated degree of interest in the graph,
When the cluster generation unit of the cluster generation device generates a cluster that is a sub-graph of the graph and a sub-graph that does not overlap with the rest based on the set node score ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
当該クラスタ生成装置の第1のノードスコア計算手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置のグラフ処理手段が、前記ノードスコアを基にして、前記グラフの一部を削除し、
当該クラスタ生成装置の第2のノードスコア計算手段が、一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。 The arc score setting means of the cluster generation device according to claim 3 sets an arc score corresponding to a designated degree of interest in the arc of the graph,
The first node score calculation means of the cluster generation device calculates a node score for the node of the graph based on the arc score,
The graph processing means of the cluster generation device deletes a part of the graph based on the node score,
The second node score calculation means of the cluster generation device calculates a new node score for the node of the graph based on the arc score set for the arc of the graph from which a part has been deleted,
When the cluster generation means of the cluster generation device generates a cluster that is a subgraph of the graph and a subgraph that does not overlap with the rest, based on the node score ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
当該クラスタ生成装置のグラフ処理手段が、前記設定されたノードスコアを基にして、前記グラフの一部を削除し、
当該クラスタ生成装置のアークスコア設定手段が、一部を削除された前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置のノードスコア計算手段が、一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。 The node score setting unit of the cluster generation device according to claim 4 sets a node score stored in the node score storage unit in association with a designated degree of interest in the graph,
The graph processing means of the cluster generation device deletes a part of the graph based on the set node score,
The arc score setting means of the cluster generation device sets an arc score corresponding to the designated degree of interest in the arc of the graph from which a part has been deleted,
The node score calculation means of the cluster generation device calculates a new node score for the node of the graph based on the arc score set for the arc of the graph from which a part has been deleted,
Based on the node score, the cluster generation unit of the cluster generation device generates a cluster that is a subgraph of the graph and has no overlap with the remaining portion.
When
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
当該クラスタ生成装置のアークスコア設定手段が、検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置のノードスコア計算手段が、前記アークスコアを基にして、前記サブグラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、前記ノードスコアを基にして、前記サブグラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。 The pattern search unit of the cluster generation device according to claim 5 searches the pattern database for a pattern that matches a specified condition,
The arc score setting means of the cluster generation device sets an arc score corresponding to the specified degree of interest in the arc of the subgraph that matches the searched pattern,
The node score calculation means of the cluster generation device calculates a node score for the node of the subgraph based on the arc score,
When the cluster generation means of the cluster generation device generates a cluster that is a subgraph of the subgraph based on the node score and is a subgraph that does not overlap with the remaining portion ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2007014194A JP4789814B2 (en) | 2007-01-24 | 2007-01-24 | Cluster generation apparatus and cluster generation method |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2007014194A JP4789814B2 (en) | 2007-01-24 | 2007-01-24 | Cluster generation apparatus and cluster generation method |
Publications (2)
Publication Number | Publication Date |
---|---|
JP2008181333A JP2008181333A (en) | 2008-08-07 |
JP4789814B2 true JP4789814B2 (en) | 2011-10-12 |
Family
ID=39725190
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2007014194A Active JP4789814B2 (en) | 2007-01-24 | 2007-01-24 | Cluster generation apparatus and cluster generation method |
Country Status (1)
Country | Link |
---|---|
JP (1) | JP4789814B2 (en) |
Families Citing this family (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP5126786B2 (en) | 2008-07-11 | 2013-01-23 | 曙ブレーキ工業株式会社 | Pad clip for disc brake device |
JP5353523B2 (en) * | 2009-07-23 | 2013-11-27 | 日本電気株式会社 | Graph analysis apparatus, graph analysis method, and graph analysis program |
JP5277111B2 (en) * | 2009-08-12 | 2013-08-28 | 日本電信電話株式会社 | Pattern classification apparatus and pattern classification method |
JP5855594B2 (en) * | 2013-02-19 | 2016-02-09 | 日本電信電話株式会社 | Clustering apparatus, clustering processing method and program thereof |
CN113515672A (en) | 2020-12-31 | 2021-10-19 | 腾讯科技(深圳)有限公司 | Data processing method and device, computer readable medium and electronic equipment |
Family Cites Families (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JPH0475169A (en) * | 1990-07-18 | 1992-03-10 | Ricoh Co Ltd | Intellectual activity assisting device |
JP2000181936A (en) * | 1998-12-17 | 2000-06-30 | Nippon Telegr & Teleph Corp <Ntt> | Document feature extracting device and document classifying device |
JP2002215676A (en) * | 2001-01-12 | 2002-08-02 | Hitachi Tohoku Software Ltd | Related information retrieval method, related information storage method, related information retrieval device and recording medium for related information retrieval |
JP4547300B2 (en) * | 2005-05-09 | 2010-09-22 | 日本電信電話株式会社 | Common query graph pattern generation device, generation method, generation program, and common subgraph search device, search method, and search program using the same |
US7958120B2 (en) * | 2005-05-10 | 2011-06-07 | Netseer, Inc. | Method and apparatus for distributed community finding |
-
2007
- 2007-01-24 JP JP2007014194A patent/JP4789814B2/en active Active
Also Published As
Publication number | Publication date |
---|---|
JP2008181333A (en) | 2008-08-07 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
Färber et al. | Citation recommendation: approaches and datasets | |
US11822918B2 (en) | Code search and code navigation | |
Shvaiko et al. | Ontology matching: state of the art and future challenges | |
US9740685B2 (en) | Generation of natural language processing model for an information domain | |
US8001106B2 (en) | Systems and methods for tokenizing and interpreting uniform resource locators | |
US20100145902A1 (en) | Methods and systems to train models to extract and integrate information from data sources | |
US20090070322A1 (en) | Browsing knowledge on the basis of semantic relations | |
WO2014160379A1 (en) | Dimensional articulation and cognium organization for information retrieval systems | |
US11928140B2 (en) | Methods and systems for modifying a search result | |
JP4789814B2 (en) | Cluster generation apparatus and cluster generation method | |
JP4200933B2 (en) | Information retrieval device | |
Karim et al. | A step towards information extraction: Named entity recognition in Bangla using deep learning | |
Abhishek et al. | An intelligent approach for mining knowledge graphs of online news | |
US20180046704A1 (en) | Systems and Methods for Selection-Based Contextual Help Retrieval | |
US20160188595A1 (en) | Semantic Network Establishing System and Establishing Method Thereof | |
Vinutha et al. | Insights into search engine optimization using natural language processing and machine learning | |
JP7412307B2 (en) | Creation support device, creation support method, and creation support program | |
Rodríguez-Ferreiro et al. | Semantic domain and grammatical class effects in the picture–word interference paradigm | |
Mengoni et al. | Empowering covid-19 fact-checking with extended knowledge graphs | |
JP5277111B2 (en) | Pattern classification apparatus and pattern classification method | |
JP2008140204A (en) | Data retrieval system and program | |
Adhiya et al. | AN EFFICIENT AND NOVEL APPROACH FOR WEB SEARCH PERSONALIZATION USING WEB USAGE MINING. | |
JP4698619B2 (en) | Centrality value calculation apparatus and centrality value calculation method | |
Giannini et al. | A Logic-based approach to Named-Entity Disambiguation in the Web of Data | |
Svetashova et al. | Pay-as-you-go Population of an Automotive Signal Knowledge Graph |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20101109 |
|
A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20101124 |
|
A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20110120 |
|
A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20110329 |
|
A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20110520 |
|
TRDD | Decision of grant or rejection written | ||
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20110712 |
|
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20110719 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140729 Year of fee payment: 3 |
|
R150 | Certificate of patent or registration of utility model |
Ref document number: 4789814 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |