(57)【特許請求の範囲】
【請求項１】
併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップと、
２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断するステップと、
併合できるクラスタが存在する場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップに戻して実行し、併合後のクラスタの数と併合前のクラスタの数とが等しくなると、クラスタリング結果を取得するステップと、
サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するステップと、
前記対応関係に基づいて、前記対象間の距離と、前記確率で決められた重み係数との間のマッピング関係を決定するステップと、を含み、
前記対応関係に基づいて、前記対象間の距離と重み係数との間のマッピング関係を決定するステップにおいて、
前記対応関係をサーチし、前記対象間の距離の対応する２つの対象が同一の対象である確率を取得し、
前記確率を前記対象間の距離が対応する重み係数として決定すること
を特徴とするクラスタリング方法。
【請求項２】
前記重み付き距離は、第１のクラスタと第２のクラスタ間の重み付き距離であり、
前記併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップにおいて、
前記第１のクラスタにおける全ての対象と前記第２のクラスタにおける全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得し、
前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得し、
前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得する
ことを特徴とする請求項１に記載のクラスタリング方法。
【請求項３】
前記第１のクラスタの全ての対象と前記第２のクラスタの全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するステップにおいて、
前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得し、
前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得し、
前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得し、
前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタとの間の重み付き距離を取得し、
前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離、及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得する
ことを特徴とする請求項２に記載のクラスタリング方法。
【請求項４】
併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するための取得ユニットと、
２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断するための判断ユニットと、
併合できるクラスタが存在する場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得させるように前記取得ユニットを制御し、併合後のクラスタの数と併合前のクラスタの数とが等しくなると、クラスタリング結果を取得するための併合ユニットと、
サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するための統計ユニットと、
前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定するための決定ユニットと、を備え、
前記決定ユニットは、
前記対応関係をサーチし、前記対象間の距離の対応する２つの対象が同一人物である確率を取得するためのサーチサブユニットと、
前記確率を前記対象間の距離が対応する重み係数として決定するための決定サブユニットと、を備える
ことを特徴とするクラスタリング装置。
【請求項５】
前記重み付き距離は、第１のクラスタと第２のクラスタ間の重み付き距離であり、
前記取得ユニットは、
前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得するための第１の取得サブユニットと、
前記第１のクラスタの全ての対象に対して、前記類似性が最も大きい距離及び対応する第１の重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するための第２の取得サブユニットと、
前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得するための第３の取得サブユニットと、
前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得するための第４の取得サブユニットと、を備える
ことを特徴とする請求項４に記載のクラスタリング装置。
【請求項６】
前記第２の取得サブユニットは、
前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得するための第５の取得サブユニットと、
前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得するための第６の取得サブユニットと、
前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得するための第７の取得サブユニットと、
前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタと間の重み付き距離を取得するための第８の取得サブユニットと、
前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するための第９の取得サブユニットと、を備える
ことを特徴とする請求項５に記載のクラスタリング装置。
【請求項７】
プロセッサと、
前記プロセッサが実行できる指令を記憶するためのメモリとを含み、
前記プロセッサは、
併合しようとする全てのクラスタに対して、対象間の距離の対応する前記対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得する処理と、
２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断する処理と、
２つのクラスタが併合できる場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得する処理に戻して実行し、併合後のクラスタの数と併合前のクラスタの数とが等しくなると、クラスタリング結果を取得する処理と、
サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得する処理と、
前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定する処理と、を実行し、
前記対応関係に基づいて、前記対象間の距離と重み係数との間のマッピング関係を決定する処理において、
前記対応関係をサーチし、前記対象間の距離の対応する２つの対象が同一の対象である確率を取得し、
前記確率を前記対象間の距離が対応する重み係数として決定する
ことを特徴とする端末装置。
【請求項８】
プロセッサに実行されることにより、請求項１乃至３のいずれか１項に記載のクラスタリング方法を実現することを特徴とするプログラム。
【請求項９】
請求項８に記載のプログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出願番号が２０１４１００９６６０８．９であって、出願日が２０１４年３月１４日である中国特許出願に基づき優先権を主張し、当該中国特許出願のすべての内容を本発明に援用する。
本発明は、コンピュータ技術分野に関し、特に、クラスタリング方法、クラスタリング装置、端末装置、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
クラスタリングは、物理的対象又は抽象的対象の集合を、類似な対象からなる複数のクラスタに分ける過程、即ち対象を異なるクラスタに分類する過程であり、同一のクラスタに属する対象が大きい類似性を持ち、異なる類に属する対象が大きい相違性を持つ。階層的クラスタリング方法において、所定の終了条件を満たすまで、指定された対象を階層的に分解する。凝集型階層的クラスタリング方法は、最低層から上への策略であり、まず、各対象をそれぞれ１つのクラスタとして、そして、所定の終了条件を満たすまで、これらのクラスタを併合し、大きくなるクラスタを形成する。階層的クラスタリング方法は、クラスタ間の類似度に対する定義が異なる以外、基本的に、上記のようなものである。
【０００３】
例えば、クラスタリング方法が画像の分類に用いられ、同じ人物に属する画像を１つのクラスタに分類する場合、関連するクラスタリング方法は、クラスタとクラスタとの間の距離だけで２つの画像における人の顔の類似度を評価する。しかし、各対象間の距離が類似度評価への貢献がほぼ同じなので、このクラスタリング方法によるクラスタリング結果の正確率が比較的に低い。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術に存在する問題を解決するために提出されたものであり、本発明は、クラスタリング方法、クラスタリング装置、端末装置、プログラム及び記録媒体を提供する。
【０００５】
上記の技術問題を解決するために、本発明の実施例は、以下の技術方案を公開した。
【０００６】
本発明の実施例の第１の局面において、クラスタリング方法を提供し、前記クラスタリング方法は、併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の距離が対応する２つの対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップと、２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断するステップと、併合できるクラスタが存在する場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップに戻して実行し、併合後のクラスタの数と併合前のクラスタの数とが等しくなると、クラスタリング結果を取得するステップと、を含む。
【０００７】
第１の局面を合わせて、第１の局面の第１の実施形態において、前記方法は、さらに、サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するステップと、前記対応関係に基づいて、前記対象間の距離と、前記確率で決められた重み係数との間のマッピング関係を決定するステップと、を含む。
【０００８】
第１の局面の第１の実施形態を合わせて、第１の局面の第２の実施形態において、前記対応関係に基づいて、前記対象間の距離と重み係数との間のマッピング関係を決定するステップにおいて、前記対応関係をサーチし、前記対象間の距離の対応する２つの対象が同一の対象である確率を取得し、前記確率を前記対象間の距離が対応する重み係数として決定する。
【０００９】
第１の局面又は第１の局面の第１の実施形態を合わせて、第１の局面の第３の実施形態において、前記重み付き距離は、第１のクラスタと第２のクラスタ間の重み付き距離であり、前記併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップにおいて、前記第１のクラスタにおける全ての対象と前記第２のクラスタにおける全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得し、前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得し、前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得する。
【００１０】
第１の局面の第３の実施形態を合わせて、第１の局面の第４の実施形態において、前記第１のクラスタの全ての対象と前記第２のクラスタの全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するステップにおいて、前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得し、前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得し、前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得し、前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタとの間の重み付き距離を取得し、前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離、及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得する。
【００１１】
本発明の実施例の第２の局面において、クラスタリング装置を提供し、前記クラスタリング装置は、
【００１２】
併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の距離が対応する２つの対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するための取得ユニットと、２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断するための判断ユニットと、併合できるクラスタが存在する場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得させるように前記取得ユニットを制御し、併合後のクラスタの数と併合前のクラスタの数とが等しくなると、クラスタリング結果を取得するための併合ユニットと、を備える。
【００１３】
第２の局面を合わせて、第２の局面の第１の実施形態において、前記装置は、さらに、
サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するための統計ユニットと、
前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定するための決定ユニットと、を備える。
【００１４】
第２の局面の第１の実施形態に合わせて、第２の局面の第２の実施形態において、前記決定ユニットは、
前記対応関係をサーチし、前記対象間の距離の対応する２つの対象が同一人物である確率を取得するためのサーチサブユニットと、
前記確率を前記対象間の距離が対応する重み係数として決定するための決定サブユニットと、を備える。
【００１５】
第２の局面の第１の実施形態又は第２の局面の第２の実施形態に合わせて、第２の局面の第３の実施形態において、
前記重み付き距離は、第１のクラスタと第２のクラスタ間の重み付き距離であり、
前記取得ユニットは、
前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得するための第１の取得サブユニットと、
前記第１のクラスタの全ての対象に対して、前記類似性が最も大きい距離及び対応する第１の重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するための第２の取得サブユニットと、
前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得するための第３の取得サブユニットと、
前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得するための第４の取得サブユニットと、を備える。
【００１６】
第２の局面の第３の実施形態に合わせて、第２の局面の第４の実施形態において、前記第２の取得サブユニットは、
前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得するための第５の取得サブユニットと、
前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得するための第６の取得サブユニットと、
前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得するための第７の取得サブユニットと、
前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタと間の重み付き距離を取得するための第８の取得サブユニットと、
前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するための第９の取得サブユニットと、を備える。
【００１７】
本発明の実施例の第３の局面において、端末装置を提供し、前記端末装置は、
プロセッサと、
プロセッサが実行できる指令を記憶するためのメモリとを含み、
前記プロセッサは、
併合しようとする全てのクラスタに対して、対象間の距離の対応する前記対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得する処理と、
２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断する処理と、
２つのクラスタが併合できる場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得する処理に戻して実行し、併合後のクラスタの数と併合前のクラスタの数とが等しくなると、クラスタリング結果を取得する処理を、実行する。
本発明の実施例の第４局面において、プログラムを提供し、前記プログラムは、プロセッサに実行されることにより、前記クラスタリング方法を実現する。
本発明の実施例の第５局面において、前記プログラムが記録された記録媒体を提供する。
【００１８】
本発明の実施例の技術方案は、以下の有益な効果を有する。前記クラスタリング方法は、２つの対象の類似性で決められた重み係数に基づいて、クラスタ間の重み付き距離を取得し、即ち、対象間の距離に重みを付け、そして、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、重み付き距離が併合条件を満たすクラスタを併合し、クラスタリング結果を取得する。前記重み付き距離と２つの対象の類似性とが関連付けられるため、対象の類似性が異なり、対応するクラスタリング結果への貢献も異なり、類似性が高いほど対応する貢献が大きくなるので、クラスタリング結果の正確率が向上した。
【００１９】
上記の概略的な説明と下記の詳細な説明は、例示的なものであり、本発明の範囲を限定するためのものではないと理解すべきである。
【図面の簡単な説明】
【００２０】
ここでの図面は、本明細書の一部として、本発明に相応しい実施例を示し、明細書と合わせて本発明の原理を解釈する。
【図１】例示的な実施例に係るクラスタリング方法のフローチャートである。
【図２】例示的な実施例に係る図１におけるステップＳ１１０のフローチャートである。
【図３】例示的な実施例に係る図２におけるステップＳ１１１のフローチャートである。
【図４】例示的な実施例に係る重み係数を取得するフローチャートである。
【図５】例示的な実施例に係るクラスタリング装置を模式的に示す図である。
【図６】例示的な実施例に係る他のクラスタリング装置を模式的に示す図である。
【図７】例示的な実施例に係る端末装置のブロック図である。
【図８】例示的な実施例に係るサーバのブロック図である。  本発明について、上記図面で明確の実施例を示し、後述でより詳細に説明する。これらの図面は、何らかの方法で本発明の思想の範囲を制限するのではなく、特定な実施例を参照することで当業者に本発明のコンセプトを説明するためのものである。
【発明を実施するための形態】
【００２１】
図１は、例示的な実施例に係るクラスタリング方法のフローチャートである。前記クラスタリング方法は、図１に示すように、以下のステップを備える。
【００２２】
ステップＳ１１０：併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得する。
【００２３】
対象が人の顔の画像である場合、本発明の前記クラスタリング方法は、同一人物に属する画像を集め、１つのクラスタを形成する。人の顔の画像における特徴が１組のベクトルへ変換されるため、対象間の距離がベクトル間の距離になる。勿論、本発明のクラスタリング方法は、画像以外の他のデータに適用することもできる。
【００２４】
クラスタリングする前、まず、初期化を実行し、各対象をそれぞれ１つのクラスタに分類し、クラスタとクラスタとの間の距離、即ちクラスタに含まれた対象間の距離（例えば、コサイン類似度、ユークリッド距離等）を計算する。
【００２５】
対象間の類似性が高いほど、対応する重み係数が大きくなり、一方、対象間の類似性が低いほど、対応する重み係数が小さくなる。例えば、対象間の距離から対応する２つの対象が同一の対象である確率に基づいて、前記重み係数を決定することができる。或いは、重み付き核関数ｗ＝ｆ（ｄ）を利用して重み係数を取得することができ、ただし、ｗが重み係数であり、ｄが対象間の距離である。例えば、ｗ＝１／ｄ２の関数で重み係数を取得する。或いは、予め設定された閾値を用いて重み係数を取得することもできる。ここで、逐一説明しない。
【００２６】
本発明の一実施例において、図２に示すように、ステップＳ１１０は、以下のステップＳ１１１〜Ｓ１１３を含む。
【００２７】
ステップＳ１１１：前記第１のクラスタにおける全ての対象と前記第２のクラスタにおける全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得する。
【００２８】
本発明の一実施例において、図３に示すように、前記ステップＳ１１１は、以下のステップＳ１１１１〜Ｓ１１１５を含む。
【００２９】
ステップＳ１１１１：前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得する。
【００３０】
仮に第１のクラスタをＡとし、第２のクラスタをＢとし、クラスタＡとクラスタＢとの間の重み付き距離を計算する。まず、クラスタＡにおける任意一つの対象ＡｉとクラスタＢにおける全ての対象との間の距離ｄ（Ａｉ，Ｂ）を計算し、対象ＡｉとクラスタＢにおける全ての対象との間の類似性が最も大きい距離を取得する。本実施例において、コサイン類似度を採用するので、最大のコサイン類似度ｄｍａｘ（Ａｉ，Ｂ）が対応する対象間の類似性は、最大である。
【００３１】
本発明の例示的な一実施例において、前記重み係数は、対象間の距離から対応する２つの対象が同一の対象である確率により得られ、図４に示すように、以下のステップを含む。
【００３２】
ステップＳ１００：サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得する。
【００３３】
例えば、人の顔を認識する場合、高次元特徴に基づいて算出された２人の顔の画像のコサイン類似度ｃｏｓθの範囲が［０，１］になる。大量の人の顔の画像に対する統計データによって下記の結果を得られる。コサイン類似度が［０．４５，１］の範囲内にある場合、２つの対象が同一人物である確率は、大よそ９８％である。コサイン類似度が［０．３５，０．４５）の範囲内にある場合、２つの対象が同一人物である確率は、大よそ７０％である。コサイン類似度が［０．２５，０．３５）の範囲内にある場合、２つ対象が同一人物である確率は、大よそ４０％である。コサイン類似度が［０．１５，０．２５）の範囲内にある場合、２つの対象が同一人物である確率は、大よそ１０％である。コサイン類似度が［０，０．１５）の範囲内にある場合、２つの対象が同一人物である確率は、大よそ０．１％である。
【００３４】
上記の統計結果に基づいて、以下の式（１）を用いて、重み係数とコサイン類似度との間の関係を記述する。
【数１】
0006051336.tif 000002
【００３５】
式（１）は、コサイン類似度と２つの対象が同一人である確率との間の対応関係を示す。他の種類の距離については、距離が対応する確率間の関係から導き出されることができ、ここで、詳しく説明しない。
【００３６】
ステップＳ２００：前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定する。
【００３７】
対象間の距離を取得し、そして、前記対象間の距離が式（１）の中、どの区間内に位置するかを判断し、最終的に、式（１）を用いて前記対象間の距離と重み係数との間のマッピング関係を決定する。上記形態により取得されたｄｍａｘ（Ａｉ，Ｂ）が対応する重み係数は、Ｗ（ｄｍａｘ（Ａｉ，Ｂ））である。
【００３８】
ステップＳ１１１２：前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離（最大コサイン類似度）を得る。
【００３９】
式（２）を用いて、ＡｉとクラスタＢとの間の最小重み付き距離φｍａｘ（Ａｉ，Ｂ）を得る。
φｍａｘ（Ａｉ，Ｂ）＝Ｗ（ｄｍａｘ（Ａｉ，Ｂ））*ｄｍａｘ（Ａｉ，Ｂ）  （２）
【００４０】
ステップＳ１１１３：前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得する。
【００４１】
仮にクラスタＡにおける対象ＡｉとクラスタＢにおける対象ｂとの間の距離が最大となると、式（３）によって対象ＡｉとクラスタＢにおける対象ｂ以外の他の各対象との間の平均重み付き距離φａｖｇ（Ａｉ，Ｂ）を取得する。
【数２】
0006051336.tif 000003
【００４２】
ステップＳ１１１４：前記最小重み付き距離と前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタとの間の重み付き距離を取得する。
【００４３】
式（４）を用いて、ＡｉとクラスタＢとの間の最小重み付き距離φｍａｘ（Ａｉ，Ｂ）と平均重み付き距離φａｖｇ（Ａｉ，Ｂ）に基づいて、対象ＡｉからクラスタＢまでの重み付き距離φ（Ａｉ，Ｂ）を得る。
φ（Ａｉ，Ｂ）＝φｍａｘ（Ａｉ，Ｂ）＋φａｖｇ（Ａｉ，Ｂ）              （４）
【００４４】
ステップＳ１１１５：前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離及び前記類似性の最も大きい距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得する。
【００４５】
式（５）を用いて、クラスタＡとクラスタＢと間の第１の単方向重み付き距離Ｓ（Ａ、Ｂ）を得る。
【数３】
0006051336.tif 000004
【００４６】
式（５）において、Ｗ（ｄｍａｘ（Ａｉ，Ｂ））は、クラスタＡにおける対象ＡｉとクラスタＢにおける全ての対象との間の最大コサイン類似度（最小距離）ｄｍａｘ（Ａｉ，Ｂ）が対応する重み係数を表す。
【００４７】
ステップＳ１１２：前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得する。
【００４８】
クラスタＢからクラスタＡまでの第２の単方向重み付き距離Ｓ（Ｂ、Ａ）の算出方法は、クラスタＡからクラスタＢまでの第１の単方向重み付き距離の算出方法に類似するため、ここで、詳しく説明しない。
【００４９】
ステップＳ１１３：前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得する。
【００５０】
式（６）を用いて、クラスタＡとクラスタＢとの間の重み付き距離Ｈ（Ａ、Ｂ）を算出する。
【数４】
0006051336.tif 000005
【００５１】
ステップＳ１２０：２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断する。併合できるクラスタが存在するとき、ステップＳ１３０を実行し、併合できるクラスタが存在しないとき、ステップＳ１４０を実行する。
【００５２】
前記予め設定された距離閾値は、異なる対象のデータタイプにより設定され、更に、算出された対象間の距離のタイプ（例えば、コサイン類似度、ユークリッド距離等）により設定される。例えば、対象が人の顔の画像であり、且つ対象間の距離のタイプがコサイン類似度である場合には、距離閾値を０．３〜０．３５に設定することができる。
【００５３】
重み付き距離を計算するときに採用されるクラスタ間の距離のタイプが異なると、２つのクラスタが併合できるか否かの判断条件も異なる。
【００５４】
クラスタ間のコサイン類似度に基づいてクラスタの重み付き距離を取得する場合、２つのクラスタ間の重み付き距離が前記予め設定された距離閾値より小さいか否かを判断する。２つのクラスタ間の重み付き距離が前記予め設定された距離閾値より小さい場合、２つのクラスタの類似性が高くて併合できると表明する。
【００５５】
クラスタ間の重み付き距離がユークリッド距離又は他の距離で算出される場合、２つのクラスタ間の重み付き距離が予め設定された距離閾値より大きいか否かを判断する。２つのクラスタ間の重み付き距離が前記予め設定された距離閾値より大きくない場合、２つのクラスタの類似性が高くて併合できると表明する。
【００５６】
本発明の実施例において、重み付き距離がクラスタ間の最小重み付き距離と平均重み付き距離で得られ、このように、比較的多くの対象を有するクラスタをえこひいきすることができるとともに、少ない対象を有するクラスタも配慮でき、人の顔をクラスタリングすることに非常に適切である。このため、前記重み付き距離を用いてクラスタリングをすることで、クラスタリングの正確率を向上させることができる。
【００５７】
２つのクラスタが併合できる場合、ステップＳ１３０において、併合できるすべてのクラスタに対して、それぞれ併合する。
【００５８】
ステップＳ１４０：併合後のクラスタの数が併合前のクラスタの数より少ないか否かを判断する。ＹＥＳの場合、ステップＳ１１０へ戻して実行し、ＮＯの場合、ステップＳ１５０へ進む。
【００５９】
併合後のクラスタの数が併合前のクラスタの数より少ない場合、併合後のクラスタの数と併合前のクラスタの数が等しくなるまで、即ち併合できるクラスタが存在しなくなるまで、全ての併合しようとするクタスタに対して、対象間の距離が対応する重み係数に基づいて２つのクラスタ間の重み付き距離を取得するステップを繰り返して実行し、クラスタリング結果を取得する。
【００６０】
ステップＳ１５０：クラスタリング結果を取得する。
【００６１】
１つのクラスタにクラスタリングされた対象の類似性が高く、相違性が低い。人の顔の画像を対象とする場合、１つのクラスタにクラスタリングされた人の顔の画像が同一人物の画像である。
【００６２】
本発明の実施例に係るクラスタリング方法によれば、対象間の距離が対応する、２つの対象の類似性で決められた重み係数に基づいて、クラスタ間の重み付き距離を取得し、即ち、対象間の距離に重みを付け、そして、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、重み付き距離が併合条件を満たすクラスタを併合し、クラスタリング結果を取得する。前記重み付き距離と２つの対象の類似性とが関連付けられるため、対象の類似性が異なり、対応するクラスタリング結果への貢献も異なり、類似性が高いほど対応する貢献が大きくなるので、クラスタリング結果の正確率が向上した。
【００６３】
図５は、例示的な実施例に係るクラスタリング装置を模式的に示す図である。図５を参照し、当該装置は、取得ユニット１００と、判断ユニット２００と、併合ユニット３００とを備える。
【００６４】
前記取得ユニット１００は、併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の距離が対応する２つの対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するように構成される。
【００６５】
前記取得ユニット１００は、第１の取得サブユニットと、第２の取得サブユニットと、第３の取得サブユニットと、第４の取得サブユニットとを備える。
【００６６】
前記第１の取得サブユニットは、前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得するように構成される。
【００６７】
前記第２の取得サブユニットは、前記第１のクラスタの全ての対象に対して、前記類似性が最も大きい距離及び対応する第１の重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するように構成される。
【００６８】
本発明の一実施例において、前記第２の取得サブユニットは、さらに、第５の取得サブユニットと、第６の取得サブユニットと、第７の取得サブユニットと、第８の取得サブユニットと、第９の取得サブユニットとを備える。
【００６９】
前記第５の取得サブユニットは、前記第１のクラスタにおける任意一つの対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得するように構成される。
【００７０】
前記第６の取得サブユニットは、前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得するように構成される。
【００７１】
前記第７の取得サブユニットは、前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得するように構成される。
【００７２】
前記第８の取得サブユニットは、前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタとの間の重み付き距離を取得するように構成される。
【００７３】
前記第９の取得サブユニットは、前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するように構成される。
【００７４】
前記第３の取得サブユニットは、前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得するように構成される。
【００７５】
前記第４の取得サブユニットは、前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの間の重み付き距離を取得するように構成される。
【００７６】
前記判断ユニット２００は、２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、２つのクラスタが併合できるか否かを判断するように構成される。
【００７７】
前記併合ユニット３００は、２つのクラスタが併合できる場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、即ち併合できるクラスタがなくなるまで、前記取得ユニットに、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得させ、クラスタリング結果を取得するように構成される。
【００７８】
本発明の実施例に係るクラスタリング装置によれば、取得ユニットにより、対象間の距離が対応する、２つの対象の類似性で決められた重み係数に基づいて、クラスタ間の重み付き距離を取得し、即ち、対象間の距離に重みを付け、判断ユニットにより重み付き距離に基づいて併合可能なクラスタを判定した後、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合ユニットにより重み付き距離が併合条件を満たすクラスタを併合し、クラスタリング結果を取得する。前記重み付き距離と２つの対象の類似性とが関連付けられるため、対象の類似性が異なり、対応するクラスタリング結果への貢献も異なり、類似性が高いほど対応する貢献が大きくなるので、クラスタリング結果の正確率が向上した。
【００７９】
図６は、例示的な実施例に係る他のクラスタリング装置を模式的に示す図である。図６を参照し、前記装置は、統計ユニット４００と、決定ユニット５００と、取得ユニット１００と、判断ユニット２００と、併合ユニット３００とを備える。なお、本実施例において、名称及び符号が図５に示した実施例と同様なユニットは、同じ機能を果すため、詳しく説明しない。
【００８０】
前記統計ユニット４００は、サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するように構成される。
【００８１】
前記決定ユニット５００は、前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定するように構成される。
【００８２】
前記決定ユニットは、さらに、サーチサブユニットと、決定サブユニットとを備える。
【００８３】
前記サーチサブユニットは、前記対応関係をサーチし、前記対象間の距離が対応する２つの対象が同一人物である確率を取得するように構成される。
【００８４】
前記決定サブユニットは、前記確率を前記対象間の距離が対応する重み係数として決定するように構成される。
【００８５】
前記決定ユニット５００に接続される前記取得ユニット１００は、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得する。
【００８６】
本発明の実施例に係るクラスタリング装置によれば、まず、大量のサンプル対象から対象間の距離及び２つの対象が同一の対象である確率を取得し、対応の重み係数を決定し、そして、クラスタ間の重み付き距離を取得し、併合前後のクラスタの数が変わらなくなるまで、重み付き距離に基づいて併合可能なクラスタを判定して併合し、クラスタリング結果を取得する。前記重み付き距離と２つの対象が同一の対象である確率とが関連付けられるため、２つの対象が同一の対象である確率が対象間の距離に伴って変化する状況を考えられる。従って、異なる対象間の距離への貢献が異なり、確率値が大きいほど対応する貢献が大きくなるため、前記クラスタリング装置は、クラスタリング結果の正確率を向上させることができる。
【００８７】
上記の実施例に係る装置について、各ユニットにより実行される具体的な操作は、関連する方法の実施例において詳しく説明しため、ここで、詳しく説明しない。
【００８８】
図７は、例示的な実施例に係るクラスタリング方法を使用する端末装置８００のブロック図である。例えば、端末装置８００は、携帯電話、コンピュータ、デジタル放送端末、メッセージ送受信デバイス、ゲームコンソール、タブレットデバイス、医療機器、フィットネス機器、パーソナルデジタルアシスタント等であってもよい。
【００８９】
図７を参照して、端末装置８００は、プロセスアセンブリ８０２、メモリ８０４、電源アセンブリ８０６、マルチメディアアセンブリ８０８、オーディオアセンブリ８１０、入出力（Ｉ／Ｏ）インターフェイス８１２、センサアセンブリ８１４、及び通信アセンブリ８１６のような一つ以上のアセンブリを含んでよい。
【００９０】
プロセスアセンブリ８０２は、一般的には端末装置８００の全体の操作を制御するものであり、例えば、表示、電話呼び出し、データ通信、カメラ操作、及び記録操作と関連する操作を制御する。プロセスアセンブリ８０２は、一つ以上のプロセッサ５２０を含み、これらによって命令を実行することにより、上記の方法の全部、或は一部のステップを実現するようにしてもよい。なお、プロセスアセンブリ８０２は、一つ以上のモジュールを含み、これらによってプロセスアセンブリ８０２と他のアセンブリの間のインタラクションを容易にするようにしてもよい。例えば、プロセスアセンブリ８０２は、マルチメディアモジュールを含み、これらによってマルチメディアアセンブリ８０８とプロセスアセンブリ８０２の間のインタラクションを容易にするようにしてもよい。
【００９１】
メモリ８０４は、各種類のデータを記憶することにより端末装置８００の操作を支援するように構成される。これらのデータの例は、端末装置８００において操作されるいずれのアプリケーションプログラム又は方法の命令、連絡対象データ、電話帳データ、メッセージ、画像、ビデオ等を含む。メモリ８０４は、いずれの種類の揮発性メモリ、不揮発性メモリ記憶デバイスまたはそれらの組み合わせによって実現されてもよく、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ ＲＯＭ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、磁気メモリ、フラッシュメモリ、磁気ディスク、或いは光ディスクである。
【００９２】
電源アセンブリ８０６は、端末装置８００の多様なアセンブリに電力を供給する。電源アセンブリ８０６は、電源管理システム、一つ以上の電源、及び端末装置８００のための電力の生成、管理及び割り当てに関連する他のアセンブリを含んでもよい。
【００９３】
マルチメディアアセンブリ８０８は、前記端末装置８００とユーザの間に一つの出力インターフェイスを提供するスクリーンを含む。上記の実施例において、スクリーンは液晶モニター（ＬＣＤ）とタッチパネル（ＴＰ）を含んでもよい。スクリーンがタッチパネルを含むことにより、スクリーンはタッチスクリーンを実現することができ、ユーザからの入力信号を受信することができる。タッチパネルは一つ以上のタッチセンサを含んでおり、タッチ、スライド、及びタッチパネル上のジェスチャを検出することができる。前記タッチセンサは、タッチ、或はスライドの動作の境界だけでなく、前記のタッチ、或はスライド操作に係る継続時間及び圧力も検出できる。上記の実施例において、マルチメディアアセンブリ８０８は、一つのフロントカメラ、及び／又はリアカメラを含む。端末装置８００が、例えば撮影モード、或はビデオモード等の操作モードにある場合、フロントカメラ、及び／又はリアカメラは外部からマルチメディアデータを受信できる。フロントカメラとリアカメラのそれぞれは、一つの固定型の光レンズ系、或は可変焦点距離と光学ズーム機能を有するものであってもよい。
【００９４】
オーディオアセンブリ８１０は、オーディオ信号を入出力するように構成されてもよい。例えば、オーディオアセンブリ８１０は、一つのマイク（ＭＩＣ）を含み、端末装置８００が、例えば呼出しモード、記録モード、及び音声認識モード等の操作モードにある場合、マイクは外部のオーディオ信号を受信することができる。受信されたオーディオ信号は、さらにメモリ８０４に記憶されたり、通信アセンブリ８１６を介して送信されたりされる。上記の実施例において、オーディオアセンブリ８１０は、オーディオ信号を出力するための一つのスピーカーをさらに含む。
【００９５】
Ｉ／Ｏインターフェイス８１２は、プロセスアセンブリ８０２と周辺インターフェイスモジュールの間にインターフェイスを提供するものであり、上記周辺インターフェイスモジュールは、キーボード、クリックホイール、ボタン等であってもよい。これらのボタンは、ホームボタン、ボリュームボタン、起動ボタン、ロッキングボタンを含んでもよいが、これらに限定されない。
【００９６】
センサアセンブリ８１４は、端末装置８００に各方面の状態に対する評価を提供するための一つ以上のセンサを含む。例えば、センサアセンブリ８１４は、端末装置８００のＯＮ／ＯＦＦ状態、端末装置８００のディスプレイとキーパッドのようなアセンブリの相対的な位置決めを検出できる。また、例えば、センサアセンブリ８１４は、端末装置８００、或は端末装置８００の一つのアセンブリの位置変更、ユーザと端末装置８００とが接触しているか否か、端末装置８００の方位、又は加速／減速、端末装置８００の温度の変化を検出できる。センサアセンブリ８１４は、何れの物理的接触がない状態にて付近の物体の存在を検出するための近接センサを含んでもよい。センサアセンブリ８１４は、撮影アプリケーションに適用するため、ＣＭＯＳ（Complementary metal-oxide-semiconductor）、又はＣＣＤ（Charge-coupled device）図像センサのような光センサを含んでもよい。上記の実施例において、当該センサアセンブリ８１４は、加速度センサ、ジャイロスコープセンサ、磁気センサ、圧力センサ、及び温度センサをさらに含んでもよい。
【００９７】
通信アセンブリ８１６は、端末装置８００と他の機器の間に有線、又は無線形態の通信を提供する。端末装置８００は、例えばＷｉＦｉ（Ｗｉｒｅｌｅｓｓ Ｆｉｄｅｌｉｔｙ）、２Ｇ（第２世代移動通信システム）、３Ｇ（第３世代移動通信システム）、或はこれらの組み合わせのような、通信規格に基づいた無線ネットワークに接続されてもよい。一つの例示的な実施例において、通信アセンブリ８１６は、放送チャンネルを介して外部の放送管理システムからの放送信号、又は放送に関連する情報を受信する。一つの例示的な実施例において、前記通信アセンブリ８１６は、近距離無線通信（ＮＦＣ）モジュールをさらに含むことにより、近距離通信を推進するようにする。例えば、ＮＦＣモジュールは、ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）技術、ＩｒＤＡ（Ｉｎｆｒａｒｅｄ Ｄａｔａ Ａｓｓｏｃｉａｔｉｏｎ）技術、ＵＷＢ（Ｕｌｔｒａ  Ｗｉｄｅ Ｂａｎｄ）技術、ＢＴ（Ｂｌｕｅｔｏｏｔｈ（登録商標））技術、他の技術に基づいて実現できる。
【００９８】
例示的な実施例において、端末装置８００は、一つ以上のＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）、ＤＳＰＤ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｄｅｖｉｃｅ）、ＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）、コントローラ、マイクロコントローラ、マイクロプロセッサ、または他の電子部品によって実現されるものであり、上記方法を実行する。
【００９９】
例示的な実施例において、さらに、命令を含む非一時的なコンピュータで読み取り可能な記憶媒体、例えば命令を含むメモリ８０４を提供しており、端末装置８００のプロセッサ５２０により上記命令を実行して上記方法を実現する。例えば、前記非一時的なコンピュータで読み取り可能な記憶媒体は、ＲＯＭ、ＲＡＭ（Ｒａｎｄｏｍ−Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｃ ＲＯＭ）、磁気テープ、フロッピーディスク（登録商標）、光データ記憶デバイス等である。
【０１００】
非一時的なコンピュータで読み取り可能な記憶媒体は、前記記憶媒体における指令がモバイル端末のプロセッサで実行されると、モバイル端末にクラスタリング方法を実施させる。
【０１０１】
前記クラスタリング方法は、
併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の距離が対応する２つの対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップと、
２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断するステップと、
併合できるクラスタが存在する場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップに戻して実行し、クラスタリング結果を取得するステップと、を含む。
【０１０２】
選択的に、前記方法は、さらに、サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するステップと、前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定するステップとを含む。
【０１０３】
選択的に、前記対応関係に基づいて、前記対象間の距離と重み係数との間のマッピング関係を決定するステップは、前記対応関係をサーチし、前記対象間の距離が対応する２つの対象が同一の対象である確率を取得し、前記確率を前記対象間の距離が対応する重み係数として決定することにより実現できる。
【０１０４】
選択的に、前記重み付き距離は、第１のクラスタと第２のクラスタとの間の重み付き距離であり、前記併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップは、前記第１のクラスタにおける全ての対象と前記第２のクラスタにおける全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得し、また、前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得し、前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得することにより実現できる。
【０１０５】
選択的に、前記第１のクラスタの全ての対象と前記第２のクラスタの全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するステップは、
前記第１のクラスタにおける任意の対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得し、
前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得し、
前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得し、
前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタとの間の重み付き距離を取得し、
前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離、及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得することにより実現できる。
【０１０６】
図１３は、本発明の実施例に係るサーバの構成を模式的に示す図である。例えば、当該サーバ１９００は、スペック又は性能に応じて大きく相違する可能性があり、１つ又は１つ以上のＣＰＵ（ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔｓ）１９２２（例えば、１つ又は１つ以上のプロセッサ）、メモリ１９３２、及び１つ又は１つ以上のアプリケーション１９４２或いはデータ１９４４の記憶媒体１９３０（例えば、１つ又は１つ以上の大容量記憶装置）を含んでもよい。なお、メモリ１９３２及び記憶媒体１９３０は一時的な記憶装置又は長期記憶装置であってもよい。記憶媒体１９３０に記憶されたブログラムは、端末装置に対して一連の指令操作を実行することができる１つ又は１つ以上のモジュール（図示せず）を含んでもよい。さらに、ＣＰＵ１９２２は、記憶媒体１９３０と通信し、サーバ１９００において、記憶媒体１９３０における一連の指令操作を実行することもできる。
【０１０７】
サーバ１９００は、さらに、１つ又は１つ以上の電源１９２６、１つ又は１つ以上の有線又は無線ネットワークインターフェイス１９５０、１つ又は１つ以上の入出力インターフェイス１９５８、１つ又は１つ以上のキーボード１９５６及び／又は１つ又は１つ以上の、例えばＷｉｎｄｏｗｓ ＳｅｒｖｅｒＴＭ（登録商標）、Ｍａｃ ＯＳ ＸＴＭ（登録商標）、ＵｎｉｘＴＭ（登録商標）、ＬｉｎｕｘＴＭ（登録商標）、ＦｒｅｅＢＳＤＴＭ（登録商標）等のＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）１９４１を含むことができる。
【０１０８】
例示的な実施例において、さらに、端末装置のプロセッサ１９２２で実行されることで上記方法を実現する指令を含む非一時的なコンピュータで読み取り可能な記憶媒体を提供し、例えば、メモリ１９３２又は記憶媒体１９３０を提供する。例えば、前記非一時的なコンピュータで読み取り可能な記憶媒体は、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、光データ記憶装置等であってもよい。
【０１０９】
非一時的なコンピュータで読み取り可能な記憶媒体は、前記記憶媒体における指令がモバイル端末のプロセッサで実行されると、端末装置にクラスタリング方法を実施させる。
【０１１０】
前記クラスタリング方法は、
併合しようとする全てのクラスタに対して、対象間の距離の対応する、前記対象間の距離が対応する２つの対象間の類似性で決められた重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップと、
２つのクラスタ間の重み付き距離及び予め設定された距離閾値に基づいて、併合できるクラスタが存在するか否かを判断するステップと、
併合できるクラスタが存在する場合、併合できるすべてのクラスタに対して、それぞれ併合し、併合後のクラスタの数と併合前のクラスタの数とが等しくなるまで、併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップに戻して実行し、クラスタリング結果を取得するステップと、を含む。
【０１１１】
選択的に、前記方法は、さらに、サンプル対象に対して統計することにより、対象間の距離と２つの対象が同一の対象である確率との対応関係を取得するステップと、前記対応関係に基づいて、前記対象間の距離と前記確率で決められた重み係数との間のマッピング関係を決定するステップとを含む。
【０１１２】
選択的に、前記対応関係に基づいて、前記対象間の距離と重み係数との間のマッピング関係を決定するステップは、前記対応関係をサーチし、前記対象間の距離が対応する２つの対象が同一の対象である確率を取得し、前記確率を前記対象間の距離が対応する重み係数として決定することにより実現できる。
【０１１３】
選択的に、前記重み付き距離は、第１のクラスタと第２のクラスタとの間の重み付き距離であり、前記併合しようとする全てのクラスタに対して、対象間の距離が対応する重み係数に基づいて、２つのクラスタ間の重み付き距離を取得するステップは、前記第１のクラスタにおける全ての対象と前記第２のクラスタにおける全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得し、また、前記第２のクラスタから前記第１のクラスタまでの第２の単方向重み付き距離を取得し、前記第１の単方向重み付き距離及び前記第２の単方向重み付き距離に基づいて、前記第１のクラスタと前記第２のクラスタとの重み付き距離を取得することにより実現できる。
【０１１４】
選択的に、前記第１のクラスタの全ての対象と前記第２のクラスタの全ての対象との間の距離及び対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得するステップは、
前記第１のクラスタにおける任意の対象と前記第２のクラスタにおける全ての対象との間の類似性が最も大きい距離、及び前記類似性の最も大きい距離が対応する第１の重み係数を取得し、
前記類似性が最も大きい距離と対応する第１の重み係数との積に基づいて、前記第１のクラスタにおける対象と前記第２のクラスタの全ての対象との間の最小重み付き距離を取得し、
前記第１のクラスタにおける対象と前記第２のクラスタにおける類似性の最も大きい距離が対応する対象以外の他の対象との間の距離の平均重み付き距離を取得し、
前記最小重み付き距離及び前記平均重み付き距離に基づいて、前記第１のクラスタにおける前記対象と前記第２のクラスタとの間の重み付き距離を取得し、
前記第１のクラスタにおける全ての対象と前記第２のクラスタとの間の重み付き距離、及び前記重み付き距離が対応する重み係数に基づいて、前記第１のクラスタから前記第２のクラスタまでの第１の単方向重み付き距離を取得することにより実現できる。
【０１１５】
本発明は、上記説明また図面に示した具体的な構成に限らず、本発明の範囲を逸脱しない限り、様々な変更及び修正を行うことができると理解すべきである。本発明の範囲は、添付の特許請求の範囲により限定される。
【０１１６】
本明細書において、「第１の」と「第２の」等の関係用語は、単なる１つの部品又は操作と、別の部品又は操作とを区別するためのものであり、これらの部品又は操作の間に、実際に、このような関係又は順位が存在することを要求又は暗示するものではない。また、「含む」、「有する」などの用語又はその他の何らかの変形は、排他的な意味ではないので、一連の要素である過程、方法、物品又は機器を含むことは、これらの要素だけを含むことを意味するではなく、明示されていない他の要素、又はこのような過程、方法、物品又は機器が固有する要素も含むことを意味する。更なる限定がない場合、「１つの…を含む」により限定された要素というは、前記要素の過程、方法、物品又は機器の以外に、他の同一の要素が存在することが排除するわけではない。
【０１１７】
上記内容は、当業者に本発明を理解又は実現させる具体的な実施形態である。これらの実施例に対する様々な修正は、当業者にとって、自明なことである。明細書に定義された一般的な原理は、本発明の主旨又は範囲を脱離しない限り、他の実施例によりも実現できる。このため、本発明は、明細書に示す上記の実施例に限定されず、明細書に公開された原理及び新規特徴に一致する最大範囲を含む。
【図１】
0006051336.tif 000006
【図２】
0006051336.tif 000007
【図３】
0006051336.tif 000008
【図４】
0006051336.tif 000009
【図５】
0006051336.tif 000010
【図６】
0006051336.tif 000011
【図７】
0006051336.tif 000012
【図８】
0006051336.tif 000013