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