(57)【要約】  本発明はクラスタリング方法、装置および端末装置が提供される。該方法においては、近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在することが判断されて、アクセスすべきオブジェクトがコアオブジェクトとして判断される。アクセスすべきオブジェクトは、第１のグループにクラスタリングされ、およびアクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して、拡張クラスタリングが実行される。直接的に密度可到達の近隣オブジェクトがコアオブジェクトではない場合、該拡張クラスタリングは停止されて、アクセスすべき全てのオブジェクトがクラスタリングされるまで、アクセスすべき次のオブジェクトが判断される。複数の隣接するドメインは、アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するのに用いられるため、走査半径の制限と、含まれるドットの最小数とが低減される。したがって、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度は低下し、クラスタリング結果の精度は向上する。
2016520896.tif 000002
【特許請求の範囲】
【請求項１】
アクセスすべきオブジェクトの各近隣オブジェクトを取得することと、
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することであって、前記アクセスすべきオブジェクトが、複数の隣接するドメインを有することと、
前記近隣オブジェクトの数が前記所定値以上であると判断された場合に、前記アクセスすべきオブジェクトを第１のグループにクラスタリングすることと、
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することと、
を備えるクラスタリング方法。
【請求項２】
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することは、
近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を取得することと、
前記複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上であるか否かを判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されているか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの全てが判断されていない場合に、前記複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上であるか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトをコアオブジェクトではないと判断することと、
を備える請求項１に記載のクラスタリング方法。
【請求項３】
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することは、
近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を取得することと、
距離に対応する重み係数を取得することであって、前記重み係数が前記距離に関連付けられていることと、
前記距離と、前記対応する重み係数とに従って、第１の隣接するドメイン内の前記近隣オブジェクトの数を計算することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が、前記複数の隣接するドメインの走査半径の昇順で前記所定値以上であるか否かを判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されているか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの全てが判断されていない場合に、前記複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の前記近隣オブジェクトの数が所定値以上であるか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトをコアオブジェクトではないと判断することと、
を備える請求項１に記載のクラスタリング方法。
【請求項４】
前記距離に関連付けられた対応する重み係数を取得することは、
前記近隣オブジェクトからの距離と前記アクセスすべきオブジェクトとの対応性と、前記近隣オブジェクトが、前記アクセスすべきオブジェクトと同じであるか否かの確率とを取得することと、
前記対応性を問い合わせることにより、近隣オブジェクトが、前記距離に対応する、前記アクセスすべきオブジェクトと同じであるか否かの確率を取得することと、
前記距離に前記確率を掛けることにより、前記距離に関連付けられた対応する重み係数を取得することであって、前記重み係数は、前記確率と正の相関関係にあることと、
を備える請求項３に記載のクラスタリング方法。
【請求項５】
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することは、
前記アクセスすべきオブジェクトの前記所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得することであって、前記所定の隣接するドメインの走査半径は、前記複数の隣接するドメインの最大走査半径よりも小さいことと、
各直接的に密度可到達の近隣オブジェクトが、コア近隣であるであるか否かを１つずつ判断することと、
前記直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合に、前記所定の隣接するドメイン内に前記近隣オブジェクトを追加することであって、前記第１のグループに入る近隣オブジェクトがなくなるまで、前記直接的に密度可到達の近隣オブジェクトは前記第１のグループに入ることと、
を備える請求項１〜請求項４のいずれか一項に記載のクラスタリング方法。
【請求項６】
各直接的に密度可到達の近隣オブジェクトがコアオブジェクトであるか否かを１つずつ判断することは、
前記近隣オブジェクトの数が前記所定値以上である少なくとも１つの隣接するドメインが、前記直接的に密度可到達の近隣オブジェクトの前記複数の隣接するドメイン内に存在するか否かを判断することと、
前記近隣オブジェクトの数が前記所定値以上である場合に、前記直接的に密度可到達の近隣オブジェクトを前記コアオブジェクトとして判断することと、
前記直接的に密度可到達の近隣オブジェクトの前記複数の隣接するドメインの各々における前記近隣オブジェクトの数が前記所定値未満である場合に、前記直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断することと、
を備える請求項５に記載のクラスタリング方法。
【請求項７】
前記複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の前記近隣オブジェクトの数が、前記所定値以上であるか否かを判断することは、
各近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を順序付けることおよび前記距離の順序を取得することと、
前記距離の順序に従って、前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数を計数することと、
前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数が前記所定値以上であるか否かを判断することと、
を備える請求項２に記載のクラスタリング方法。
【請求項８】
アクセスすべきオブジェクトの各近隣オブジェクトを取得するように構成された第１の取得ユニットと、
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断するように構成された第１の判定ユニットであって、前記アクセスすべきオブジェクトが複数の隣接するドメインを有する第１の判定ユニットと、
前記近隣オブジェクトの数が前記所定値以上である前記少なくとも１つの隣接するドメインが存在すると判断された場合に、前記アクセスすべきオブジェクトを第１のグループにクラスタリングするように構成されたクラスタリングユニットと、
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように構成された拡張クラスタリングユニットと、
を備えるクラスタリング装置。
【請求項９】
前記第１の判定ユニットは、
近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を取得するように構成された第１の取得サブユニットと、
前記複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上であるか否かを判断するように構成された第１の判定サブユニットと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成された第１の判断サブユニットと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されているか否かを判断するように、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの全てが判断されていない場合には、前記複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の前記近隣オブジェクトの数が所定値以上であるか否かを判断するように前記第１の判定サブユニットを実行させるように構成された第２の判定サブユニットと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトを前記コアオブジェクトではないと判断するように構成された第２の判断サブユニットと、
を備える請求項８に記載のクラスタリング装置。
【請求項１０】
前記第１の判定ユニットは、
近隣オブジェクトと、アクセスすべきオブジェクトとの距離を取得するように構成された第２の取得サブユニットと、
前記距離に対応する重み係数を取得するように構成された第３の取得サブユニットであって、前記重み係数が前記距離に関連付けられている第３の取得サブユニットと、
前記距離および対応する重み係数に従って、第１の隣接するドメイン内の近隣オブジェクトの数を計算するように構成された計算サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が、前記複数の隣接するドメインの走査半径の昇順で所定値以上であるか否かを判断するように構成された第３の判定サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成された第３の判断サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断するように、前記アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合には、前記距離および対応する重み係数に従って、第２の隣接するドメイン内の近隣オブジェクトの数を計算するように計算サブユニットを実行させるように構成された第４の判定サブユニットと、
前記アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトをコアオブジェクトではないと判断するように構成された第４の判断サブユニットと、
を備える、請求項８に記載のクラスタリング装置。
【請求項１１】
前記第３の取得サブユニットは、
前記近隣オブジェクトから、前記アクセスすべきオブジェクトまで距離と、前記近隣オブジェクトが、前記アクセスすべきオブジェクトと同じであるか否かの確率との対応性を取得するように構成された計数サブユニットと、
前記近隣オブジェクトが、前記距離に対応する、前記アクセスすべきオブジェクトと同じであるか否かの確率を取得するために、前記対応性を問い合わせるように構成された問い合わせサブユニットと、
前記距離に前記確率を掛けることにより、前記距離に関連付けられた対応する重み係数を取得するように構成された第４の取得ユニットであって、前記重み係数が、前記確率と正の相関関係にある第４の取得ユニットと、
を備える、請求項１０に記載のクラスタリング装置。
【請求項１２】
前記拡張クラスタリングユニットは、
前記アクセスすべきオブジェクトの所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得するように構成された第５の取得サブユニットであって、所定の隣接するドメインの走査半径は、複数の隣接するドメインの最大走査半径よりも小さい第５の取得サブユニットと、
各直接的に密度可到達の近隣オブジェクトが、コア近隣であるであるか否かを１つずつ判断するように構成された第５の判定サブユニットと、
直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合に、所定の隣接するドメイン内に前記近隣オブジェクトを追加するように構成された拡張クラスタリングサブユニットであって、前記第１のグループに入る近隣オブジェクトがなくなるまで、前記直接的に密度可到達の近隣オブジェクトは前記第１のグループに入る拡張クラスタリングサブユニットと、
を備える、請求項８〜請求項１１のいずれか一項に記載のクラスタリング装置。
【請求項１３】
前記第５の判定サブユニットは、
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、前記直接的に密度可到達の近隣オブジェクトの複数の隣接するドメイン内に存在するか否かを判断するように構成された第６の判定サブユニットと、
前記近隣オブジェクトの数が前記所定値以上である場合に、前記直接的に密度可到達の近隣オブジェクトをコアオブジェクトとして判断するように構成された第５の判断サブユニットと、
前記直接的に密度可到達の近隣オブジェクトの前記複数の隣接するドメインの各々における前記近隣オブジェクトの数が前記所定値未満である場合に、前記直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断するように構成された第６の判断サブユニットと、
を備える請求項１２に記載のクラスタリング装置。
【請求項１４】
前記第１の判定サブユニットは、
各近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を順序付けし、および前記距離の順序を取得するように構成された順序付けユニットと、
前記距離の順序に従って、前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数を計数するように構成された第２の計数サブユニットと、
前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数が前記所定値以上であるか否かを判断するように構成された第７の判定サブユニットと、
を備える、請求項９に記載のクラスタリング装置。
【請求項１５】
プロセッサと、
実行可能な命令を前記プロセッサによって格納するように構成された記憶装置であって、前記プロセッサは、
アクセスすべきオブジェクトの各近隣オブジェクトを取得するように、
前記アクセスすべきオブジェクトは複数の隣接するドメインを有し、前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断するように、
前記近隣オブジェクトの数が所定値以上である前記少なくとも１つの隣接するドメインが、前記アクセスすべきオブジェクトの前記複数の隣接するドメイン内に存在していると判断された場合に、前記アクセスすべきオブジェクトを第１のグループにクラスタリングするように、および
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように、
構成される記憶装置と、
を備える端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、２０１４年２月２８日に中国知識産権局に出願された中国特許出願第２０１４１００７３４９６．５号の優先権および利益を主張するものであり、その開示内容全体は参考として本願明細書で援用されるものとする。
【０００２】
本願は、一般に、コンピュータ技術に関し、より具体的には、クラスタリング方法、装置および端末装置に関する。
【背景技術】
【０００３】
クラスタリングは、物理的または抽象的なオブジェクトから成るセットを、類似のオブジェクトから成る複数のグループに分類するためのプロセス、すなわち、該オブジェクトを異なるグループまたはクラスターに分類するためのプロセスであり、この場合、同じグループのオブジェクトは多くの類似性を有し、また、異なるグループのオブジェクトは、多くの相違点を有する。
【０００４】
クラスタリング手法には多くの種類があるが、密度に基づくクラスタリング手法と、その他のクラスタリング手法との違いについては、密度に基づくクラスタリング手法は、さまざまな距離の代わりに密度に基づいており、およびドメイン内のドットの密度が所定の閾値よりも大きい限り、該ドメインは同様のグループに追加されるということである。したがって、距離に基づくクラスタリング手法が「準円」群しか見つけることができないというクラスタリングの欠点は、克服することができる。例えば、ＤＢＳＣＡＮ（Ｄｅｎｓｉｔｙ−Ｂａｓｅｄ  Ｓｐａｔｉａｌ  Ｃｌｕｓｔｅｒｉｎｇ  ｏｆ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｗｉｔｈ  Ｎｏｉｓｅ）アルゴリズムは、密度に基づくクラスタリング手法の典型的なアルゴリズムである。ＤＢＳＣＡＮアルゴリズムは、クラスターを、関連する密度を有するドットの最大セットとして定義し、それにより、十分に高い密度を有するドメインをクラスターに分類して、ノイズの空間データベース内で、どのような形状のクラスターも見つけることができる。ＤＢＳＣＡＮアルゴリズムは、コアオブジェクトという概念と、２つの初期パラメータＥｐｓ（走査半径）およびＭｉｎＰｔｓ（含まれるドットの最小数）とを取り入れている。特定のオブジェクト周辺のＥｐｓの範囲内のオブジェクトの数がＭｉｎＰｔｓ以上である場合、該特定のオブジェクトはコアオブジェクトである。コアオブジェクト周辺のＥｐｓの範囲内のコアオブジェクトおよび近隣オブジェクトは、クラスターを構成する。クラスター内に複数のコアオブジェクトがある場合、それらのオブジェクトを中心とするクラスターは、一緒にまとめるべきである。しかし、このクラスタリング手法のクラスタリング結果は、パラメータＥｐｓおよびＭｉｎＰｔｓの値に非常に敏感であり、すなわち、ＥｐｓおよびＭｉｎＰｔｓの異なる値により、異なるクラスタリング結果が生じる可能性があり、その結果、該クラスタリング結果の不確定性が生じる可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
関連技術における問題を克服するために、クラスタリング方法、装置および端末装置は、本開示の実施形態によって提供される。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、本開示の実施形態は、以下の技術的解決策を提供する。
【０００７】
本開示の第１の態様の実施形態は、
アクセスすべきオブジェクトの各近隣オブジェクトを取得することと、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することであって、アクセスすべき該オブジェクトは、複数の隣接するドメインを有することと、該近隣オブジェクトの数が該所定値以上であると判断された場合に、該アクセスすべきオブジェクトを第１のグループにクラスタリングすることと、
該第１のグループに入れることができる近隣オブジェクトがなくなるまで、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することと、
を含むクラスタリング方法を提供する。
【０００８】
第１の態様に関して、第１の態様の第１の可能な実施形態において、該近隣オブジェクトの数が該所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することは、
近隣オブジェクトと、該アクセスすべきオブジェクトとの距離を取得することと、
該複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の該近隣オブジェクトの数が該所定値以上であるか否かを判断することと、
該第１の隣接するドメイン内の近隣オブジェクトの数が該所定値以上である場合に、該アクセスすべきオブジェクトをコアオブジェクトとして判断することと、
該第１の隣接するドメイン内の近隣オブジェクトの数が該所定値未満である場合に、該アクセスすべきオブジェクトの複数の隣接するドメインの各々が、既に判断されているか否かを判断することと、
該アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合に、該複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断することと、
該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、該アクセスすべきオブジェクトをコアオブジェクトではないと判断することと、
を含む。
【０００９】
第１の態様に関して、第１の態様の第２の可能な実施形態において、該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することは、
近隣オブジェクトと、アクセスすべきオブジェクトとの距離を取得することと、
距離に対応する重み係数を取得することであって、該重み係数が該距離に関連付けられていることと、
該距離と、該対応する重み係数とに従って、第１の隣接するドメイン内の近隣オブジェクトの数を計算することと、
該第１の隣接するドメイン内の近隣オブジェクトの数が、複数の隣接するドメインの走査半径の昇順で所定値以上であるか否かを判断することと、
該第１の隣接するドメイン内の近隣オブジェクトの数が該所定値以上である場合に、該アクセスすべきオブジェクトをコアオブジェクトとして判断することと、
該第１の隣接するドメイン内の近隣オブジェクトの数が該所定値未満である場合に、該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断することと、
該アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合に、該複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断することと、
該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、該アクセスすべきオブジェクトをコアオブジェクトではないと判断することと、
を含む。
【００１０】
第１の態様の第２の可能な実施形態に関して、第１の態様の第３の可能な実施形態において、該距離に関連付けられた対応する重み係数を取得することは、
該近隣オブジェクトからの距離と、アクセスすべきオブジェクトとの対応性と、該近隣オブジェクトが、アクセスすべきオブジェクトと同じであるか否かの確率とを取得することと、
該対応性を問い合わせることにより、該近隣オブジェクトが、該距離に対応する、該アクセスすべきオブジェクトと同じであるか否かの確率を取得することと、
該距離に該確率を掛けることにより、該距離に関連付けられた対応する重み係数を取得することであって、該重み係数は、該確率と正の相関関係にあることと、
を含む。
【００１１】
第１の態様、または、第１の態様の第１の実施形態から第３の実施形態のうちのいずれか１つに関して、第１の態様の第４の可能な実施形態において、該第１のグループに入れることができる近隣オブジェクトがなくなるまで、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することは、
該アクセスすべきオブジェクトの所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得することであって、所定の隣接するドメインの走査半径は、複数の隣接するドメインの最大走査半径よりも小さいことと、
各直接的に密度可到達の近隣オブジェクトが、コア近隣であるであるか否かを１つずつ判断することと、
直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合に、所定の隣接するドメイン内に該近隣オブジェクトを追加することであって、該第１のグループに入る近隣オブジェクトがなくなるまで、該直接的に密度可到達の近隣オブジェクトは該第１のグループに入ることと、
を含む。
【００１２】
第１の態様の第４の可能な実施形態に関して、第１の態様の第５の可能な実施形態において、各直接的に密度可到達の近隣オブジェクトがコアオブジェクトであるか否かを１つずつ判断することは、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、直接的に密度可到達の近隣オブジェクトの複数の隣接するドメイン内に存在するか否かを判断することと、
該近隣オブジェクトの数が所定値以上である場合に、該直接的に密度可到達の近隣オブジェクトをコアオブジェクトとして判断することと、
該直接的に密度可到達の近隣オブジェクトの複数の隣接するドメインの各々における近隣オブジェクトの数が所定値未満である場合に、該直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断することと、
を含む。
【００１３】
第１の態様の第１の可能な実施形態に関して、第１の態様の第６の可能な実施形態において、複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の近隣オブジェクトの数が、所定値以上であるか否かを判断することは、
各近隣オブジェクトと、アクセスすべきオブジェクトとの距離を順序付けることおよび該距離の順序を取得することと、
該距離の順序に従って、該隣接するドメインの走査半径未満のアクセスすべきオブジェクトに関する距離を有する近隣オブジェクトの数を計数することと、
該隣接するドメインの走査半径未満のアクセスすべきオブジェクトに関する距離を有する近隣オブジェクトの数が所定値以下であるか否かを判断することと、
を含む。
【００１４】
本開示の第２の態様の実施形態は、アクセスすべきオブジェクトの各近隣オブジェクトを取得するように構成された第１の取得ユニットと、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断するように構成された第１の判定ユニットであって、該アクセスすべきオブジェクトが複数の隣接するドメインを有する第１の判定ユニットと、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在すると判断された場合に、該アクセスすべきオブジェクトを第１のグループにクラスタリングするように構成されたクラスタリングユニットと、
該第１のグループに入れることができる近隣オブジェクトがなくなるまで、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように構成された拡張クラスタリングユニットと、
を含むクラスタリング装置を提供する。
【００１５】
第２の態様に関して、第２の態様の第１の可能な実施形態において、該第１の判定ユニットは、
近隣オブジェクトと、アクセスすべきオブジェクトとの距離を取得するように構成された第１の取得サブユニットと、
複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断するように構成された第１の判定サブユニットと、
該第１の隣接するドメイン内の該近隣オブジェクトの数が所定値以上である場合に、該アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成された第１の判断サブユニットと、
該第１の隣接するドメイン内の近隣オブジェクトの数が所定値未満である場合に、該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断するように、該アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合には、複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断するように該第１の判定サブユニットを実行させるように構成された第２の判定サブユニットと、
該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、該アクセスすべきオブジェクトをコアオブジェクトではないと判断するように構成された第２の判断サブユニットと、
を含む。
【００１６】
第２の態様に関して、第２の態様の第２の可能な実施形態において、該第１の判定ユニットは、
近隣オブジェクトと、アクセスすべきオブジェクトとの距離を取得するように構成された第２の取得サブユニットと、
該距離に対応する重み係数を取得するように構成された第３の取得サブユニットであって、該重み係数が該距離に関連付けられている第３の取得サブユニットと、
該距離および対応する重み係数に従って、第１の隣接するドメイン内の近隣オブジェクトの数を計算するように構成された計算サブユニットと、
該第１の隣接するドメイン内の近隣オブジェクトの数が、複数の隣接するドメインの走査半径の昇順で所定値以上であるか否かを判断するように構成された第３の判定サブユニットと、
該第１の隣接するドメイン内の近隣オブジェクトの数が該所定値以上である場合に、該アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成された第３の判断サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が所定値未満である場合に、該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断するように、該アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合には、該距離および対応する重み係数に従って、第２の隣接するドメイン内の近隣オブジェクトの数を計算するように計算サブユニットを実行させるように構成された第４の判定サブユニットと、
該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、該アクセスすべきオブジェクトをコアオブジェクトではないと判断するように構成された第４の判断サブユニットと、
を含む。
【００１７】
第２の態様の第２の可能な実施形態に関して、第２の態様の第３の可能な実施形態において、該第３の取得サブユニットは、
該近隣オブジェクトからの距離と、該アクセスすべきオブジェクトとの対応性と、該近隣オブジェクトが、該アクセスすべきオブジェクトと同じであるか否かの確率とを取得するように構成された計数サブユニットと、
該近隣オブジェクトが、該距離に対応する、アクセスすべきオブジェクトと同じであるか否かの確率を取得するために該対応性を問い合わせるように構成された問い合わせサブユニットと、
該距離に該確率を掛けることにより、該距離に関連付けられた対応する重み係数を取得するように構成された第４の取得ユニットであって、該重み係数が、該確率と正の相関関係にある第４の取得ユニットと、
を含む。
【００１８】
第２の態様、または、第２の態様の第１の実施形態から第３の実施形態のうちのいずれか１つに関して、第２の態様の第４の可能な実施形態において、該拡張クラスタリングユニットは、
該アクセスすべきオブジェクトの所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得するように構成された第５の取得サブユニットであって、所定の隣接するドメインの走査半径は、複数の隣接するドメインの最大走査半径よりも小さい第５の取得サブユニットと、
各直接的に密度可到達の近隣オブジェクトが、コア近隣であるであるか否かを１つずつ判断するように構成された第５の判定サブユニットと、
直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合に、所定の隣接するドメイン内に該近隣オブジェクトを追加するように構成された拡張クラスタリングサブユニットであって、該第１のグループに入る近隣オブジェクトがなくなるまで、該直接的に密度可到達の近隣オブジェクトは該第１のグループに入る拡張クラスタリングサブユニットと、
を含む。
【００１９】
第２の態様の第４の可能な実施形態に関して、第２の態様の第５の可能な実施形態において、該第５の判定サブユニットは、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、直接的に密度可到達の近隣オブジェクトの複数の隣接するドメイン内に存在するか否かを判断するように構成された第６の判定サブユニットと、
該近隣オブジェクトの数が所定値以上である場合に、該直接的に密度可到達の近隣オブジェクトをコアオブジェクトとして判断するように構成された第５の判断サブユニットと、
該直接的に密度可到達の近隣オブジェクトの複数の隣接するドメインの各々における近隣オブジェクトの数が所定値未満である場合に、該直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断するように構成された第６の判断サブユニットと、
を含む。
【００２０】
第２の態様の第１の可能な実施形態に関して、第２の態様の第６の可能な実施形態において、該第１の判定サブユニットは、
各近隣オブジェクトと、アクセスすべきオブジェクトとの距離を順序付けし、および該距離の順序を取得するように構成された順序付けユニットと、
該距離の順序に従って、該隣接するドメインの走査半径未満のアクセスすべきオブジェクトに関する距離を有する近隣オブジェクトの数を計数するように構成された第２の計数サブユニットと、
該隣接するドメインの走査半径未満のアクセスすべきオブジェクトに関する距離を有する近隣オブジェクトの数が所定値以上であるか否かを判断するように構成された第７の判定サブユニットと、
を含む。
【００２１】
本開示の第３の態様の実施形態は、
プロセッサと、
実行可能な命令を該プロセッサによって格納するように構成された記憶装置であって、該プロセッサは、
アクセスすべきオブジェクトの各近隣オブジェクトを取得するように、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断するように、この場合、該アクセスすべきオブジェクトは複数の隣接するドメインを有し、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、該アクセスすべきオブジェクトの複数の隣接するドメイン内に存在していると判断された場合に、該アクセスすべきオブジェクトを第１のグループにクラスタリングするように、および
該第１のグループに入れることができる近隣オブジェクトがなくなるまで、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように、
構成される記憶装置と、
を含む端末装置を提供する。
【００２２】
本開示の実施形態によってもたらされる技術的解決策には、次の有利な効果がある。該クラスタリング方法に従って、該アクセスすべきオブジェクトの各近隣オブジェクトが取得され、該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在することが判断されて、該アクセスすべきオブジェクトがコアオブジェクトとして判断される。該アクセスすべきオブジェクトは、第１のグループにクラスタリングされ、拡張クラスタリングが、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して実行される。該直接的に密度可到達の近隣オブジェクトがコアオブジェクトではない場合、該拡張クラスタリングは停止され、その後、アクセスすべき全てのオブジェクトがクラスタリングされるまで、アクセスすべき次のオブジェクトが判断される。該複数の隣接するドメインは、該クラスタリング方法において、アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するのに用いられるため、Ｅｐｓ（走査半径）およびＭｉｎＰｔｓ（含まれるドットの最小数）に関する制約は低減される。したがって、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度は低下し、およびクラスタリング結果の精度が向上する。
【００２３】
上記の概要および以下の詳細な説明はともに例示的で説明のためのものであり、およびクレームされているように、本開示を制限するものではないことを理解すべきである。
【図面の簡単な説明】
【００２４】
【図１】本開示の例示的な実施形態によるクラスタリング方法のフローチャートである。
【図２】本開示の例示的な実施形態によるオブジェクト分布の概略図である。
【図３】本開示の例示的な実施形態による隣接するドメインの分布の概略図である。
【図４】本開示の例示的な実施形態によるステップＳ４００のフローチャートである。
【図５】本開示の例示的な実施形態によるステップＳ２００のフローチャートである。
【図６】本開示の別の例示的な実施形態によるステップＳ２００のフローチャートである。
【図７】本開示の例示的な実施形態による重み係数の取得のフローチャートである。
【図８】本開示の例示的な実施形態によるクラスタリング装置の概略図である。
【図９】本開示の例示的な実施形態による装置のブロック図である。
【発明を実施するための形態】
【００２５】
この明細書に組み込まれ、該明細書の一部を構成する添付図面は、本開示と一致する実施形態を示しており、該説明とともに、本開示の原理を説明するのに役立つものである。
【００２６】
上記の図面を用いて、本開示によって開示されている実施形態が提示されており、詳細な説明が以下に記載されている。これらの図面は、本開示の範囲を多少なりとも限定しようとするものではなく、特定の実施形態を参照することにより、当業者のために、本開示のアイデアを説明するものである。
【００２７】
次に、例示的な実施形態を詳細に説明するが、それらの実施例は、添付図面に図示されている。以下の説明は、添付図面を参照し、異なる図における同じ数字は、説明のない限り、同じまたは同様の要素を示すものとする。例示的な実施形態の以下の説明に記載されている実施態様は、本開示に一致する全ての実施態様を示すものではない。むしろ、それらの実施態様は、単に、添付クレームに列挙されているような本開示に関連する態様に一致する装置および方法の実施例である。
【００２８】
本開示の実施形態の詳細な説明の前に、まず、本願明細書の以下の用語の概念を紹介する。
【００２９】
Ｅ隣接ドメイン：特定のオブジェクトを中心とし、および走査半径Ｅを有するドメインを、オブジェクトのＥ隣接ドメインという。
コアオブジェクト：オブジェクトＰのＥドメイン内の近隣オブジェクトの数がオブジェクト閾値ＭｉｎＰｔｓに含まれる最小値以上である場合、該オブジェクトをコアオブジェクトという。
近隣オブジェクト：オブジェクトＰに直接接続することができるオブジェクトを、オブジェクトＰの近隣オブジェクトという。
直接的に密度可到達：サンプルセットに対して、近隣オブジェクトＱが、オブジェクトＰのＥ隣接ドメイン内にあり、オブジェクトＰがコアオブジェクトである場合、オブジェクトＱは、オブジェクトＰ、すなわち、Ｅ隣接ドメイン内のオブジェクトＰの近隣オブジェクトから直接的に密度可到達である。
【００３０】
図１は、本開示の例示的な実施形態によるクラスタリング方法のフローチャートである。図１に示すように、該方法は、以下のステップを含む。
【００３１】
ステップＳ１００において、オブジェクトの各近隣オブジェクトが取得される。
【００３２】
本開示のクラスタリング方法におけるオブジェクトは、顔画像とすることができ、および同一人物に属する画像は、１つのクラスターにクラスタリングされる。顔画像の特徴は、ベクトルのセットに変換され、そのため、２つのオブジェクト間の距離は、それらのベクトル間の距離である。本開示の実施形態によるクラスタリング方法は、確かに、画像以外の他のデータにも適用することができる。
【００３３】
処理すべきオブジェクトのセットに対して、該セット内の各オブジェクトが、アクセスすべきオブジェクトとして処理されて、該アクセスすべきオブジェクトの各近隣オブジェクトが取得される。図２に示すように、オブジェクト５は、オブジェクト４，６および７と直接接続されており、したがって、オブジェクト４，６および７は、オブジェクト５の近隣オブジェクトである。
【００３４】
アクセス識別が、各オブジェクトのために設定される。あるオブジェクトがアクセスされた場合、該オブジェクトのアクセス識別は、アクセスされたとマークされる。例えば、あるオブジェクトがアクセスされていない場合、対応するアクセス識別は、「０」であり、あるオブジェクトがアクセスされている場合は、対応するアクセス識別は、「１」である。該オブジェクトが、該オブジェクトのアクセス識別に従ったアクセスすべきオブジェクトであるか否かが識別される。該オブジェクトが、該オブジェクトのアクセス識別に従ったアクセスすべきオブジェクトであるか否かが判断される。
【００３５】
ステップＳ２００において、該アクセスすべきオブジェクトは、複数の隣接するドメインを有し、該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かが判断される。このステップは、主に、該アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するために用いられる。肯定の場合、ステップＳ３００が実行され、否定の場合には、該アクセスすべきオブジェクトは、ノイズドットとしてマークされ、アクセスすべきオブジェクトが存在しなくなるまで、該アクセスすべきオブジェクトの次の判断を実行するために、ステップＳ１００が実行される。
【００３６】
図３に示すように、該アクセスすべきオブジェクトに関する３つの隣接するドメインは、Ｅ１隣接ドメイン、Ｅ２隣接ドメインおよびＥ３隣接ドメインである。Ｅ１隣接ドメインの走査半径はＥ１であり、Ｅ２隣接ドメインの走査半径はＥ２であり、Ｅ３隣接ドメインの走査半径はＥ３であり、この場合、Ｅ１＜Ｅ２＜Ｅ３である。まず、アクセスすべきオブジェクトＰのＥ１隣接ドメイン内の近隣オブジェクトの数Ｐｓｔ１がＭｉｎＰｓｔ１以上であるか否かが判断され、Ｐｓｔ１≧ＭｉｎＰｓｔ１である場合、アクセスすべきオブジェクトＰはコアオブジェクトであると判断され、そうでない場合は、さらに、Ｅ２隣接ドメイン内のアクセスすべきオブジェクトＰの近隣オブジェクトの数Ｐｓｔ２がＭｉｎＰｓｔ２以上であるか否かが判断され、Ｐｓｔ２≧ＭｉｎＰｓｔ２である場合、アクセスすべきオブジェクトＰはコアオブジェクトであると判断され、そうでない場合は、さらに、アクセスすべきオブジェクトＰのＥ３隣接ドメイン内の近隣オブジェクトの数Ｐｓｔ３がＭｉｎＰｓｔ３以上であるか否かが判断され、Ｐｓｔ３≧ＭｉｎＰｓｔ３である場合は、アクセスすべきオブジェクトＰはコアオブジェクトであると判断され、そうでない場合は、アクセスすべきオブジェクトＰは、コアオブジェクトではないと判断される。該走査半径は、該オブジェクトのデータタイプの異なる特徴に従って設定することができる。
【００３７】
ステップＳ３００において、アクセスすべきオブジェクトは、第１のグループにクラスタリングされ、すなわち、該アクセスすべきオブジェクトは、第１のグループとして処理される。
【００３８】
グループ番号Ｃが、該オブジェクトに対して設定される。初期状態において、グループ番号Ｃはゼロである。１つのグループが追加される度に、その追加されたグループに対応するグループ番号が１つ増える。例えば、オブジェクトＰがコアオブジェクトである場合、オブジェクトＰは第１のグループにクラスタリングされ、第１のグループに対応するグループ番号は、１になるように更新される。オブジェクトＰがある第１のグループに属していないコアオブジェクトＱが見つけられた場合、コアオブジェクトＱは、第２のグループにクラスタリングされ、第２のグループに対応するグループ番号が２になるように更新される。このようにして、追加されたグループのグループ番号は、現在のグループのグループ番号に基づいて１つ増える。
【００３９】
ステップＳ４００においては、第１のグループに入れることができる近隣オブジェクトがなくなるまで、アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して、拡張クラスタリングが実行される。
【００４０】
該所定の隣接するドメインは、アクセスすべきオブジェクトの複数の隣接するドメインのうちの１つ以上とすることができる。例えば、図３に示すように、隣接するドメインの走査半径が大きくなるほど、隣接するドメインの信頼性は低くなり、および該拡張クラスタリングは、高い信頼性を有する隣接するドメイン内のオブジェクトに対してのみ実行してもよい。例えば、図３に示すような本開示の例示的な実施形態において、該拡張クラスタリングは、アクセスすべきオブジェクトのＥ１隣接ドメインおよびＥ２隣接ドメイン内の近隣オブジェクトに対してのみ実行してもよい。該複数の隣接するドメインの各々が高い信頼性を有している場合、該拡張クラスタリングは、該複数の隣接するドメインの各々における近隣オブジェクトに対して実行することができる。
【００４１】
図４に示すような本開示の例示的な実施形態において、ステップＳ４００は、以下のステップを含む。
【００４２】
ステップＳ４０１において、アクセスすべきオブジェクトの所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトが取得され、この場合、該所定の隣接するドメインの走査半径は、該複数の隣接するドメインの最大走査半径未満である。
【００４３】
該走査半径が大きくなるほど、ノイズドットの状態に至る確率が大きくなるであろう。したがって、該所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトは、アクセスすべきオブジェクトが中にある第１のグループに追加される。
【００４４】
アクセスすべきオブジェクトＰの所定の隣接するドメイン内の全ての近隣オブジェクトのキューＮｅｉｇｈｂｏｒＰｔｓが取得されて、アクセスすべきオブジェクトＰと、オブジェクトＰの近隣オブジェクトとの距離が直接計算される。次いで、その距離が、所定のドメインの走査半径と比較される。該距離が該走査半径以上である場合、該近隣オブジェクトは、キューＮｅｉｇｈｂｏｒＰｔｓ内のオブジェクトであることを示している。該距離は、コサイン類似度またはユークリッド距離であってもよい。本願明細書において、２つのオブジェクト間のコサイン類似度が、２つのオブジェクト間の距離関係を示すのに用いられる場合、１とコサイン類似度との距離（１−ｃｏｓθ）は、その２つのオブジェクト間の距離を表すのに用いられ、この場合、２つのオブジェクト間の距離が短くなるほど、それら２つのオブジェクト間の類似度は高くなることに留意すべきである。
【００４５】
別法として、各近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得された後、該距離は、各距離のサイズに従って順序付けされる。このようにして、取得された距離の順序付けに従って、隣接するドメイン内のオブジェクトの数を判断する場合、該アクセスすべきオブジェクトに対する距離が、所定の隣接するドメインの走査半径未満である近隣オブジェクトは、キューＮｅｉｇｈｂｏｒＰｔｓを形成するようにカウントされる。
【００４６】
ステップＳ４０２においては、各直接的に密度可到達の近隣オブジェクトがコアオブジェクトであるか否かが１つずつ判断される。
【００４７】
キューＮｅｉｇｈｂｏｒＰｔｓ内のオブジェクトＰｉが詳しく検討されて、オブジェクトＰｉがコアオブジェクトであるか否かが判断され、この場合、アクセスすべきオブジェクトの直接的に密度可到達の近隣オブジェクトがコアオブジェクトであるか否かを判断する処理は、ステップＳ２００での処理と同じである。
【００４８】
各直接的に密度可到達の近隣オブジェクトに対して、該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、該直接的に密度可到達の近隣オブジェクトの複数の隣接するドメイン内に存在するか否かが判断される。該近隣オブジェクトの数が該所定値以上である場合、該直接的に密度可到達の近隣オブジェクトは、コアオブジェクトとして判断される。該直接的に密度可到達の近隣オブジェクトの複数の隣接するドメインの各々における近隣オブジェクトの数が該所定値未満である場合には、該直接的に密度可到達の近隣オブジェクトは、コアオブジェクトとして判断されない。
【００４９】
ステップＳ４０３においては、該直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合、直接的に密度可到達の近隣オブジェクトがその中にある該所定の隣接するドメイン内の近隣オブジェクトは、第１のグループに入れることができる近隣オブジェクトがなくなるまで、第１のグループに追加される。
【００５０】
拡張クラスタリングの実行中には、アクセスすべきオブジェクトを格納するためにキューが生成される。例えば、該拡張クラスタリングを、アクセスすべきオブジェクトＰに対して実行する場合、まず、キューが生成されて、該アクセスすべきオブジェクトＰの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトが該キューに追加され、例えば、該キューは、｛Ｐ１，Ｐ２，Ｐ３，Ｐ４｝である。最初に、Ｐ１がコアオブジェクトであるか否かが判断される。肯定の場合、Ｐ１の所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトが、Ｐがその中にある第１のグループに追加され、およびＰ１の所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトは、該キュー（スタックデータ構造）に追加される。該キュー内の次のオブジェクト（例えば、Ｐ２）がアクセスされて、オブジェクト（Ｐ２）がアクセスされたとマークされ、該オブジェクトがコアオブジェクトであるか否かが判断される。該オブジェクトがコアオブジェクトではない場合は、該オブジェクトが別のグループのメンバーであるか否かが判断される。該オブジェクトが、他のグループのメンバーではない場合、該オブジェクトは、オブジェクトＰがその中にある第１のグループに追加される。該キュー内のオブジェクトがなくなるまで、該キュー内の次のオブジェクトがアクセスされる。
【００５１】
ステップＳ４０４において、直接的に密度可到達の近隣オブジェクトがコアオブジェクトではない場合、各直接的に密度可到達の近隣オブジェクトが既に判断されているか否かが判断される。全ての直接的に密度可到達の近隣オブジェクトが判断されていない場合、ステップＳ４０２が実行されて、次の直接的に密度可到達の近隣オブジェクトがコアオブジェクトであるか否かが判断される。各直接的に密度可到達の近隣オブジェクトが既に判断されている場合には、この拡張クラスタリングが終了する。
【００５２】
本開示の実施形態によるクラスタリング方法を用いて、アクセスすべきオブジェクトの各近隣オブジェクトが取得されて、近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かが判断され、そして、該アクセスすべきオブジェクトがコアオブジェクトとして判断される。該アクセスすべきオブジェクトは、第１のグループにクラスタリングされ、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して、該拡張クラスタリングが実行される。該直接的に密度可到達の近隣オブジェクトがコアオブジェクトではない場合、該拡張クラスタリングが停止され、アクセスすべき全てのオブジェクトがクラスタリングされるまで、アクセスすべき次のオブジェクトが判断される。該クラスタリング方法においては、複数の隣接するドメインは、アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するのに用いられるため、Ｅｐｓ（走査半径）およびＭｉｎＰｔｓ（含まれるドットの最小数）に関する制約が低減される。したがって、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度は低下し、クラスタリング結果の精度が向上する。
【００５３】
図５に示すような例示的な実施形態において、図１のステップＳ２００は、次のステップを含む。
【００５４】
ステップＳ２１０において、近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得される。その距離は、コサイン類似度またはユークリッド距離であってもよい。
【００５５】
本願明細書においては、２つのオブジェクト間のコサイン類似度が、２つのオブジェクト間の距離関係を示し、１とコサイン類似度との差（１−ｃｏｓθ）は、２つのオブジェクト間の距離を表すのに用いられ、この場合、２つのオブジェクト間の距離が短くなるほど、それら２つのオブジェクト間の類似度は高くなることに留意すべきである。
【００５６】
ステップＳ２２０において、複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かが判断される。第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上である場合、ステップＳ２３０が実行され、第１の隣接するドメイン内の近隣オブジェクトの数が所定値未満である場合には、ステップＳ２４０が実行される。
【００５７】
別法として、各近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得された後、該距離は、各距離のサイズに従って順序付けされる。このようにして、取得された距離の順序付けに従って、隣接するドメイン内のオブジェクトの数を判断する場合、該アクセスすべきオブジェクトに対する距離が、隣接するドメインの走査半径未満である近隣オブジェクトの数がカウントされる。そして、該近隣オブジェクトの数が、対応する所定の閾値以上であるか否かが判断される。
【００５８】
例えば、図３に示すように、まず、Ｅ１隣接ドメイン内のオブジェクトの数が判断される。Ｅ１隣接ドメイン内のオブジェクトと、オブジェクトＰとの距離は、距離の順序付けを取得するために各距離のサイズに従って順序付けされる。まず、該距離の順序付けにおいて、走査半径Ｅ１に最も近い距離を、探索法（例えば、２進チョップ）に従って判断してもよく、また、Ｅ１隣接ドメイン内のオブジェクトの数を判断するために、該距離の順序付けにおいて、走査半径Ｅ１に最も近い距離未満の距離の数がカウントされ、それによって、判断効率が向上する。
【００５９】
さらに、Ｅ２隣接ドメイン内の近隣オブジェクトの数を判断し続ける必要がある場合、該距離の順序付けを探索することにより、オブジェクトＰに対する距離が、走査半径Ｅ２未満で、かつ走査半径Ｅ１超である近隣オブジェクトの数Ｐｔｓ２１がカウントされ、Ｐｔｓ２１をＰｔｓ１に追加することによって、Ｅ２隣接ドメイン内の近隣オブジェクトの数が取得される。同様に、該距離の順序付けを探索することにより、オブジェクトＰに対する距離が、走査半径Ｅ３未満であり、かつ走査半径Ｅ２超である近隣オブジェクトの数Ｐｔｓ３２がカウントされ、Ｐｔｓ３２を、Ｐｔｓ２１とＰｔｓ１の合計に加えることにより、Ｅ３隣接ドメイン内の近隣オブジェクトの数が取得される。これ以上の隣接するドメインがある場合、他の隣接するドメイン内の近隣オブジェクトの数は、このようにして取得することができる。
【００６０】
アクセスすべきオブジェクトＰの複数の隣接するドメインにおいて、該近隣オブジェクトの数は、該複数の隣接するドメインの走査半径の昇順で判断されることに留意すべきである。ある隣接するドメイン内の近隣オブジェクトの数が所定値以上であると判断された場合、後の隣接するドメイン内の近隣オブジェクトの数を判断し続けることは必要ない。
【００６１】
ステップＳ２３０において、アクセスすべきオブジェクトは、コアオブジェクトとして判断される。
【００６２】
ステップＳ２４０において、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かが判断される。該アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合、ステップＳ２２０が実行され、さらに、該複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かが判断され、および該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合には、ステップＳ２５０が実行される。
【００６３】
例えば、その最初の値がゼロである変数ｉを設定することができる。第１の隣接するドメインを判断する場合、変数ｉは、１つずつ増加する（すなわち、ｉ＝ｉ＋１）。変数ｉと、該アクセスすべきオブジェクトの複数の隣接するドメインの数を比較することにより、該アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断することができる。
【００６４】
ステップＳ２５０においては、該アクセスすべきオブジェクトがコアオブジェクトではないと判断される。
【００６５】
アクセスすべきオブジェクトＰがコアオブジェクトではないと判断された場合、オブジェクトＰはノイズドットであり、アクセスすべきオブジェクトがなくなるまで、アクセスすべき次のオブジェクトの各近隣オブジェクトを取得するステップが実行される。
【００６６】
本開示の実施形態による、該オブジェクトがコアオブジェクトであるか否かを判断するための方法を用いて、隣接するドメイン内の近隣オブジェクトの数が、該近隣オブジェクトと、アクセスすべきオブジェクトとの距離に従って直接判断される。アクセスすべきオブジェクトの複数の隣接するドメインの特定の隣接するドメイン内の近隣オブジェクトの数が所定の閾値以上である場合、該アクセスすべきオブジェクトはコアオブジェクトである。換言すれば、Ｅｐｓ（走査半径）およびＭｉｎＰｔｓ（含まれるドットの最小数）に関する制約は低減される。したがって、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度は低下し、およびクラスタリング結果の精度が向上する。
【００６７】
図６に示すような本開示の別の例示的な実施形態においては、図１のステップＳ２００は、次のステップを含む。
【００６８】
ステップＳ２１１において、近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得される。その距離は、コサイン類似度またはユークリッド距離であってもよい。
【００６９】
本願明細書においては、２つのオブジェクト間のコサイン類似度が、２つのオブジェクト間の距離関係を示し、１とコサイン類似度との差（１−ｃｏｓθ）は、２つのオブジェクト間の距離を表すのに用いられ、この場合、２つのオブジェクト間の距離が短くなるほど、それら２つのオブジェクト間の類似度は高くなることに留意すべきである。
【００７０】
ステップＳ２２１においては、該距離に対応する重み係数が取得され、この場合、該重み係数は、該距離と、２つのオブジェクト間の類似度とに関連付けられている。
【００７１】
該重み係数は、２つのオブジェクト間の距離と、２つのオブジェクト間の類似度との関係を反映することが可能である。例えば、該距離が長くなるほど、類似度は低くなり、対応する重み係数は小さくなる。対照的に、該距離が短くなるほど、類似度は高くなり、対応する重み係数は大きくなる。
【００７２】
本開示の例示的な実施形態において、該重み係数は、２つのオブジェクト間の距離と、該２つのオブジェクトが互いに同一であるか否かの確率とによって判断してもよい。図７に示すように、該重み係数は、次のステップによって取得される。
【００７３】
ステップＳ２２１１においては、サンプルオブジェクト統計に従って、近隣オブジェクトからの距離と、アクセスすべきオブジェクトとの対応性と、該近隣オブジェクトが該アクセスすべきオブジェクトと同じであるか否かの確率とが取得される。
【００７４】
２つのオブジェクト間の距離（例えば、コサイン類似度またはユークリッド距離）が取得される。該２つのオブジェクトを、それぞれＡおよびＢであると仮定すると、該２つのオブジェクト間のコサイン類似度は、式（１）に従って計算することができる。
【００７５】
【数１】
2016520896.tif 000003
ただし、Ａ・Ｂは、ベクトルＡとベクトルＢの内積であり、｜Ａ｜は、ベクトルＡの長さであり、｜Ｂ｜は、ベクトルＢの長さである。
【００７６】
例えば、顔認識において、高次元の特徴に従って計算された２つの顔画像のコサイン類似度ｃｏｓθは、［０，１］の範囲内にある。大量の顔画像統計データによれば、コサイン類似度が［０．４，１］の範囲内にある場合、２つのオブジェクトが互いに同一であるか否かの確率は９８％であり、コサイン類似度が［０．３５，０．４］の範囲内にある場合、２つのオブジェクトが互いに同一であるか否かの確率は９０％であり、コサイン類似度が［０．３，０．３５］の範囲内にある場合、２つのオブジェクトが互いに同一であるか否かの確率は７０％であり、コサイン類似度が［０．２５，０．３］の範囲内にある場合、２つのオブジェクトが互いに同一であるか否かの確率は４０％であり、コサイン類似度が［０，０．２５］の範囲内にある場合、２つのオブジェクトが互いに同一であるか否かの確率は１０％である。
【００７７】
上記の統計結果によれば、２つのオブジェクト間の距離と、該２つのオブジェクトが互いに同一であるか否かの確率との関係を得ることができる。その関係は、テーブルに、または他の形式で格納することができる。
【００７８】
ステップＳ２２１２においては、該対応性を問い合わせることにより、近隣オブジェクトが、該距離に一致するアクセスすべきオブジェクトと同じであるか否かの確率を取得する。
【００７９】
ステップＳ２２１３においては、該距離に該確率を掛けることにより、その距離に関連付けられた対応する重み係数が取得され、この場合、該重み係数は該確率と正の相関関係にある。
【００８０】
ステップＳ２２１１における統計結果によれば、該重み係数と、コサイン類似度との関係は、式（２）として示すことができる。
【００８１】
【数２】
2016520896.tif 000004
【００８２】
式（２）は、コサイン類似度と、２つのオブジェクトが同一人物であるか否かの確率との関係を表す。他の種類の距離の場合、関係式は、該距離と、対応する確率との関係に従ってまとめて推論することができるが、本願明細書においては省略する。
【００８３】
重み係数は、該重み係数が、２つのオブジェクト間の距離と、２つのオブジェクト間の類似度との関係を表すことができる限り、他の手段によって確実に取得することができる。
【００８４】
ステップＳ２３１において、指定され隣接するドメイン内の近隣オブジェクトの数は、該重み係数および該距離に従って計算される。
【００８５】
別法として、各近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得された後、該距離は、各距離のサイズに従って順序付けされる。このようにして、隣接するドメイン内のオブジェクトの数を判断する場合、該アクセスすべきオブジェクトに対する距離が、隣接するドメインの走査半径未満である近隣オブジェクトの数が、該距離の順序付けに従ってカウントされる。そして、指定された隣接するドメイン内の近隣オブジェクトと、アクセスすべきオブジェクトとの距離と、対応する重み係数とに従って、Ｅ隣接ドメイン内の近隣オブジェクトの数が取得される。
【００８６】
指定された隣接するドメインは、アクセスすべきオブジェクトの複数の隣接するドメインのうちのいずれか１つとすることができ、および該複数の隣接するドメインの走査半径の昇順で変えてもよい。
【００８７】
式（２）における重み係数に従って、近隣オブジェクトの数は、式（３）として表すことができる。
【００８８】
【数３】
2016520896.tif 000005
【００８９】
式（３）は、Ｅ隣接するドメイン内の全てのオブジェクトの総数を表す。実際には、各オブジェクトの数は、１から、該オブジェクトと、アクセスすべきオブジェクトとの距離に対応する重み係数Ｗ（ｄｉ）に変えられる。換言すれば、Ｅ隣接ドメイン内のオブジェクトの数を計算するだけではなく、オブジェクトが中心点に近づくほど、該オブジェクトの数の変換割合が大きくなり、対照的に、オブジェクトが中心点から離れるほど、該オブジェクトの数の変換割合は小さくなるということが取得される。
【００９０】
ステップＳ２４１においては、アクセスすべきオブジェクトの隣接するドメイン内の近隣オブジェクトの数が、対応する所定の閾値以上であるか否かが判断される。肯定の場合、ステップＳ２５１が実行され、否定の場合は、ステップＳ２６１が実行される。
【００９１】
図５における所定の閾値とは異なる所定の閾値は、重み係数により調節することができる。さらに、本開示の例示的な実施形態における所定の閾値は、図５における所定の閾値よりも小さい。
【００９２】
各隣接するドメイン内のオブジェクトの数が、走査半径に従って順に、対応する閾値要件を満たすか否かが判断される。肯定の場合、次の隣接するドメイン内のオブジェクトの数が判断されることになる。
【００９３】
ステップＳ２５１において、隣接するドメイン内の近隣オブジェクトの数が所定の閾値以上である場合に、アクセスすべきオブジェクトは、コアオブジェクトとして判断される。
【００９４】
ステップＳ２６１においては、隣接するドメイン内の近隣オブジェクトの数が所定の閾値未満である場合には、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かが判断される。肯定の場合、ステップＳ２７１が実行され、否定の場合には、ステップＳ２３１が実行されて、アクセスすべきオブジェクトの次の隣接するドメイン内の近隣オブジェクトの数が、該重み係数および該距離に従って計算される。
【００９５】
例えば、その最初の値がゼロである変数ｉを設定することができる。第１の隣接するドメインが判断されると、変数ｉは、１つ増加する（すなわち、ｉ＝ｉ＋１）。変数ｉと、アクセスすべきオブジェクトの複数の隣接するドメインの数とを比較することにより、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断することができ、この場合、ｉ番目の隣接するドメインの走査半径は、（ｉ＋１）番目の隣接するドメインの走査半径よりも小さい。
【００９６】
アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合、該アクセスすべきオブジェクトは、コアオブジェクトとして判断されない。
【００９７】
アクセスすべきオブジェクトＰがコアオブジェクトではないと判断された場合、オブジェクトＰはノイズドットであり、該アクセスすべきオブジェクトは、アクセスされたとマークされ、アクセスすべきオブジェクトがなくなるまで、アクセスすべき次のオブジェクトの各近隣オブジェクトを取得するステップが実行される。
【００９８】
アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するための方法を用いて、中心点に近い近隣オブジェクトが、該数の大きな変換割合を有し、および隣接するドメイン内の近隣オブジェクトの数に対する大きな寄与を有するように、近隣オブジェクトの数が、近隣オブジェクトと、アクセスすべきオブジェクトとの距離に対応する重み係数に従って変換され、対照的に、中心点から遠く離れている近隣オブジェクトは、該数の低い変換割合を有し、および隣接するドメイン内の近隣オブジェクトの数に対する小さな寄与を有し、それに伴って、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度がさらに低減され、およびクラスタリング結果の精度が向上する。
【００９９】
図８は、本開示の例示的な実施形態によるクラスタリング装置の概略図である。図８を参照すると、該装置は、第１の取得ユニット１００と、第１の判定ユニット２００と、クラスタリングユニット３００と、拡張クラスタリングユニット４００とを含む。
【０１００】
第１の取得ユニット１００は、アクセスすべきオブジェクトの各近隣オブジェクトを取得するように構成されている。
【０１０１】
第１の判定ユニット２００は、近隣オブジェクトの数が所定値以上である、少なくとも１つの隣接するドメインが存在するか否かが判断され、この場合、アクセスすべきオブジェクトは、複数の隣接するドメインを有する。
【０１０２】
図３の隣接するドメイン分布の概略図を参照して、第１の判定ユニット２００は、まず、アクセスすべきオブジェクトＰのＥ１隣接ドメイン内の近隣オブジェクトの数Ｐｓｔ１がＭｉｎＰｓｔ１以上であるか否かを判断し、Ｐｓｔ１≧ＭｉｎＰｓｔ１の場合、第１の判定ユニット２００は、アクセスすべきオブジェクトＰがコアオブジェクトであると判断し、そうでない場合は、アクセスすべきオブジェクトＰのＥ２隣接ドメイン内の近隣オブジェクトの数Ｐｓｔ２がＭｉｎＰｓｔ２以上であるか否かを判断し、Ｐｓｔ２≧ＭｉｎＰｓｔ２である場合、第１の判定ユニット２００は、アクセスすべきオブジェクトＰがコアオブジェクトであると判断し、そうでない場合は、第１の判定ユニット２００は、さらに、Ｅ３隣接ドメイン内のアクセスすべきオブジェクトＰの近隣オブジェクトの数Ｐｓｔ３がＭｉｎＰｓｔ３以上であるか否かを判断し、Ｐｓｔ３≧ＭｉｎＰｓｔ３である場合、第１の判定ユニット２００は、アクセスすべきオブジェクトＰはコアオブジェクトであると判断し、そうでない場合は、第１の判定ユニット２００は、コアオブジェクトではないと判断する。
【０１０３】
クラスタリングユニット３００は、近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かが判断される場合に、アクセスすべきオブジェクトを第１のグループにクラスタリングするように構成されている。
【０１０４】
拡張クラスタリングユニット４００は、第１のグループに入れられる近隣オブジェクトがなくなるまで、アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように構成されている。
【０１０５】
本開示の例示的な実施形態において、該拡張クラスタリングユニットは、第５の取得サブユニットと、第５の判定サブユニットと、拡張クラスタリングサブユニットとを含むことができる。
【０１０６】
第５の取得サブユニットは、アクセスすべきオブジェクトの所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得するように構成され、この場合、該所定の隣接するドメインの走査半径は、複数の隣接するドメインの最大走査半径よりも小さい。
【０１０７】
走査半径が大きくなるほど、ノイズドットの状態に至る確率が大きくなるであろう。したがって、該所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトは、アクセスすべきオブジェクトが中にある第１のグループに追加される。
【０１０８】
第５の判定サブユニットは、各直接的に密度可到達の近隣オブジェクトがコア近隣であるか否かを１つずつ判断するように構成されている。
【０１０９】
拡張クラスタリングサブユニットは、所定の隣接するドメイン内の近隣オブジェクトを追加するように構成され、この場合、直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断されると、第１のグループに入れることができる近隣オブジェクトがなくなるまで、該直接的に密度可到達の近隣オブジェクトは、第１のグループに入れられる。
【０１１０】
本開示の例示的な実施形態において、第５の判定サブユニットは、第６の判定サブユニットと、第５の判断サブユニットと、第６の判断サブユニットとを含むことができる。
【０１１１】
第６の判定サブユニットは、近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、直接的に密度可到達の近隣オブジェクトの複数の隣接するドメイン内に存在するか否かを判断するように構成されている。
【０１１２】
第５の判断サブユニットは、近隣オブジェクトの数が所定値以上である場合に、該直接的に密度可到達の近隣オブジェクトをコアオブジェクトとして判断するように構成されている。
【０１１３】
第６の判断サブユニットは、直接的に密度可到達の近隣オブジェクトの複数の隣接するドメインの各々における近隣オブジェクトの数が所定値未満である場合に、該直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断するように構成されている。
【０１１４】
本開示の実施形態によるクラスタリング装置を用いて、第１の判定ユニットは、近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断し、すなわち、第１の判定ユニットは、アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断し、該アクセスすべきオブジェクトがコアオブジェクトである場合、該クラスタリングユニットは、該アクセスすべきオブジェクトを第１のグループにクラスタリングし、該拡張クラスタリングユニットは、アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行し、該直接的に密度可到達の近隣オブジェクトがコアオブジェクトである場合、該直接的に密度可到達の近隣オブジェクトがその中にある所定の隣接するドメイン内の近隣オブジェクトは、第１のグループに追加され、該直接的に密度可到達の近隣オブジェクトがコアオブジェクトではない場合、該拡張クラスタリングは停止される。そして、第１のグループに入れることができる近隣オブジェクトがなくなるまで、アクセスすべき次のオブジェクトが判断される。該クラスタリング装置においては、複数の隣接するドメインが、アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するのに用いられるため、Ｅｐｓ（走査半径）およびＭｉｎＰｔｓ（含まれるドットの最小数）に関する制約が低減される。したがって、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度は低下し、クラスタリング結果の精度が向上する。
【０１１５】
図７に示すような本開示の例示的な実施形態において、第１の判定ユニットは、第１の取得サブユニットと、第１の判定サブユニットと、第１の判断サブユニットと、第２の判定サブユニットと、第２の判断サブユニットとを含む。
【０１１６】
第１の取得サブユニットは、近隣オブジェクトとアクセスすべきオブジェクトとの距離を取得するように構成されている。
【０１１７】
第１の判定サブユニットは、複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断するように構成されている。
【０１１８】
別法として、各近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得された後、各距離のサイズに従って該距離が順序付けされる。このようにして、隣接するドメイン内のオブジェクトの数が、得られた距離の順序付けに従って判断される場合、アクセスすべきオブジェクトに関する距離が、隣接するドメインの走査半径未満である近隣オブジェクトの数がカウントされる。そして、近隣オブジェクトの数が、対応する所定の閾値以上であるか否かが判断される。
【０１１９】
第１の判断サブユニットは、第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上である場合に、アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成されている。
【０１２０】
第２の判定サブユニットは、第１の隣接するドメイン内の近隣オブジェクトの数が所定値未満である場合に、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断するように、アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合には、複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断するように第１の判定サブユニットを実行させるように構成されている。
【０１２１】
第２の判断サブユニットは、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、該アクセスすべきオブジェクトをコアオブジェクトではないと判断して、該アクセスすべきオブジェクトをマークし、およびアクセスすべき次のオブジェクトの各近隣オブジェクトを取得するように、第１の取得ユニットを制御するように構成されている。
【０１２２】
本開示の実施形態による第１の判定ユニットを用いて、隣接するドメイン内の近隣オブジェクトの数は、該近隣オブジェクトと、アクセスすべきオブジェクトとの距離に従って直接判断される、アクセスすべきオブジェクトの複数の隣接するドメインのうちの特定の１つにおける近隣オブジェクトの数が所定の閾値以上である場合、該アクセスすべきオブジェクトは、コアオブジェクトである。換言すれば、Ｅｐｓ（走査半径）およびＭｉｎＰｔｓ（含まれるドットの最小数）に関する制約は低減される。したがって、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度は低下し、およびクラスタリング結果の精度が向上する。
【０１２３】
本開示の例示的な実施形態においては、判断効率を向上させるために、第１の判定サブユニットは、順序付けユニットと、第２の計数サブユニットと、第７の判定サブユニットとを含む。
【０１２４】
順序付けユニットは、各近隣オブジェクトと、アクセスすべきオブジェクトとの距離を順序付けして、該距離の順序を得るように構成されている。
【０１２５】
第２の計数サブユニットは、アクセスすべきオブジェクトに関して、隣接するドメインの走査半径未満の距離を有する近隣オブジェクトの数を、該距離の順序付けに従って計数するように構成されている。
【０１２６】
第７の判定サブユニットは、アクセスすべきオブジェクトに関して、隣接するドメインの走査半径未満の距離を有する近隣オブジェクトの数が所定値以上であるか否かを判断するように構成されている。
【０１２７】
本開示の実施形態による第１の判定サブユニットを用いて、順序付けユニットは、特定の隣接するドメイン内の各オブジェクトと、アクセスすべきオブジェクトとの距離を順序付けして、該距離の順序付けを得る。そして、該距離の順序付けにおける走査半径に最も近い距離が、探索法（例えば、２進チョップ）に従って判断され、特定の隣接するドメイン内のオブジェクトの数を判断するために、該走査半径に最も近い距離未満の距離の数がカウントされ、それによって、判断効率が向上する。
【０１２８】
図７に示すような本開示の別の例示的な実施形態においては、第１の判定ユニット２００は、第２の取得サブユニットと、第３の取得サブユニットと、計算サブユニットと、第３の判定サブユニットと、第３の判断サブユニットと、第４の判定サブユニットと、第４の判断サブユニットとを含む。
【０１２９】
第２の取得サブユニットは、近隣オブジェクトと、アクセスすべきオブジェクトとの距離を取得するように構成されている。
【０１３０】
第３の取得サブユニットは、該距離に対応する重み係数を取得するように構成され、この場合、該重み係数は該距離に関連付けられる。
【０１３１】
該重み係数は、２つのオブジェクト間の距離と、２つのオブジェクト間の類似度との関係を反映することが可能である。例えば、該距離が長くなるほど、類似度は低くなり、および対応する重み係数は小さくなる。対照的に、該距離が短くなるほど、類似度は高くなり、対応する重み係数は大きくなる。
【０１３２】
本開示の例示的な実施形態において、第３の取得サブユニットは、計数サブユニットと、問い合わせサブユニットと、第４の取得ユニットとを含む。
【０１３３】
該計数サブユニットは、近隣オブジェクトおよびアクセスすべきオブジェクトからの距離と、該近隣オブジェクトが、該アクセスすべきオブジェクトが同じであるか否かの確率との対応性を得るように構成されている。
【０１３４】
該問い合わせサブユニットは、該対応性を問い合わせて、近隣オブジェクトが、該距離に対応するアクセスすべきオブジェクトと同じであるか否かの確率を取得するように構成されている。
【０１３５】
第４の取得ユニットは、該距離に該確率を掛けることによって、該距離に関連付けられた対応する重み係数を得るように構成され、この場合、該重み係数は、該確率と正の相関関係にある。
【０１３６】
該計算サブユニットは、該重み係数と、該距離とに従って、隣接するドメイン内の近隣オブジェクトの数を計算するように構成されている。別法として、各近隣オブジェクトと、アクセスすべきオブジェクトとの距離が取得された後、該距離は、各距離のサイズに従って順序付けされる。このようにして、隣接するドメイン内のオブジェクトの数の場合、該距離の順序付けに従って、該アクセスすべきオブジェクトに対する距離が、隣接するドメインの走査半径未満である近隣オブジェクトの数がカウントされる。そして、指定された隣接するドメイン内の近隣オブジェクトと、アクセスすべきオブジェクトとの距離と、対応する重み係数とに従って、Ｅ隣接ドメイン内の近隣オブジェクトの数が取得される。
【０１３７】
第３の判定サブユニットは、複数の隣接するドメインの走査半径の昇順で、第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上であるか否かを判断するように構成されている。
【０１３８】
第３の判断サブユニットは、第１の隣接するドメイン内の近隣オブジェクトの数が所定値以上である場合に、該アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成されている。
【０１３９】
第４の判定サブユニットは、第１の隣接するドメイン内の近隣オブジェクトの数が所定値未満である場合に、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断するように、アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合には、該距離および該対応する重み係数に従って、第２の隣接するドメイン内の近隣オブジェクトの数を計算するように該計算サブユニットを実行させ、さらに、第３の判定サブユニットは、第２の隣接するドメイン内の近隣オブジェクトの数が所定値以上であることを判断する。
【０１４０】
第４の判断サブユニットは、アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、該アクセスすべきオブジェクトをコアオブジェクトではないと判断して、該アクセスすべきオブジェクトをアクセスされたとマークし、およびアクセスすべき次のオブジェクトの各近隣オブジェクトを取得するように、第１の取得ユニットを制御するように構成されている。
【０１４１】
アクセスすべきオブジェクトがコアオブジェクトであるか否かを判断するための方法を用いて、中心点に近い近隣オブジェクトが、該数の大きな変換割合を有し、および隣接するドメイン内の近隣オブジェクトの数に対する大きな寄与を有するように、近隣オブジェクトの数が、近隣オブジェクトと、アクセスすべきオブジェクトとの距離に対応する重み係数に従って変換され、対照的に、中心点から遠く離れている近隣オブジェクトは、該数の低い変換割合を有し、および隣接するドメイン内の近隣オブジェクトの数に対する小さな寄与を有し、それに伴って、ＥｐｓおよびＭｉｎＰｔｓに対するクラスタリング結果の感度がさらに低減され、およびクラスタリング結果の精度が向上する。
【０１４２】
上記の実施形態における装置に関しては、動作を実行する各ユニットのモードが、関連する方法の実施形態において詳細に記載されており、本願明細書においては省略されている。
【０１４３】
図９は、例示的な実施形態によるクラスタリング装置８００のブロック図である。例えば、装置８００は、携帯電話、コンピュータ、ディジタル放送端末、メッセージング装置、ゲーム機、タブレット、医療装置、運動器具、携帯情報端末等とすることができる。
【０１４４】
図９を参照すると、装置８００は、次のコンポーネント、すなわち、処理コンポーネント８０２、記憶装置８０４、電力コンポーネント８０６、マルチメディアコンポーネント８０８、オーディオコンポーネント８１０、入力／出力（Ｉ／Ｏ）インタフェース８１２、センサコンポーネント８１４および通信コンポーネント８１６のうちの１つ以上を含んでもよい。
【０１４５】
処理コンポーネント８０２は、典型的には、ディスプレイ、電話の発呼・着呼、データ通信、カメラ操作および記録動作に関連する動作等の装置８００の全体の動作を制御する。処理コンポーネント８０２は、上述した方法におけるステップの全てまたは一部を行うための命令を実行する１つ以上のプロセッサ８２０を含んでもよい。さらに、処理コンポーネント８０２は、処理コンポーネント８０２と、その他のコンポーネントとの相互作用を容易にする１つ以上のモジュールを含んでもよい。例えば、処理コンポーネント８０２は、マルチメディアコンポーネント８０８と処理コンポーネント８０２との相互作用を容易にするマルチメディアモジュールを含んでもよい。
【０１４６】
記憶装置８０４は、装置８００の動作をサポートするための様々な種類のデータを格納するように構成されている。このようなデータの実例は、装置８００上で機能される何らかのアプリケーションまたは方法のための命令、接触データ、電話帳データ、メッセージ、写真、ビデオ等を含む。記憶装置８０４は、スタティックランダムアクセスメモリ（ＳＲＡＭ）、電気的消去可能読取専用メモリ（ＥＥＰＲＯＭ）、消去可能プログラム可能読取専用メモリ（ＥＰＲＯＭ）、プログラム可能読取専用メモリ（ＰＲＯＭ）、読取専用メモリ（ＲＯＭ）、磁気メモリ、フラッシュメモリ、磁気または光ディスク等の何らかのタイプの揮発性または不揮発性メモリデバイス、またはそれらの組合せを用いて実施することができる。
【０１４７】
電力コンポーネント８０６は、装置８００のさまざまなコンポーネントに電力を供給する。電力コンポーネント８０６は、電力管理システムと、１つ以上の電源と、装置８００における電力の生成、管理および配電に関連する他の何らかのコンポーネントとを含むことができる。
【０１４８】
マルチメディアコンポーネント８０８は、装置８００とユーザとの間の出力インタフェースを形成するスクリーンを含む。いくつかの実施形態において、該スクリーンは、液晶ディスプレイ（ＬＣＤ）およびタッチパネル（ＴＰ）を含むことができる。該スクリーンがタッチパネルを含む場合、該スクリーンは、ユーザからの入力信号を受け取るタッチスクリーンとして実施してもよい。該タッチパネルは、該タッチパネルへの接触、スワイプおよびジェスチャーを感知する１つ以上のタッチセンサを含む。該タッチセンサは、接触またはスワイプ動作の境界を感知するだけではなく、接触またはスワイプ動作に関連する周期および圧力も感知することができる。いくつかの実施形態において、マルチメディアコンポーネント８０８は、前方カメラおよび／または後方カメラを含む。該前方カメラおよび後方カメラは、装置８００が、撮影モードまたはビデオモード等の動作モードになっている間、外部マルチメディアデータを受け取ることができる。該前方カメラおよび後方カメラの各々は、固定光学レンズシステムであってもよく、および焦点および光学ズーム性能を有することができる。
【０１４９】
オーディオコンポーネント８１０は、オーディオ信号を出力および／または入力するように構成されている。例えば、オーディオコンポーネント８１０は、装置８００が、発呼モード、記録モードおよび音声認識モード等の動作モードになっているときに、外部音声信号を受け取るように構成されたマイクロフォン（ＭＩＣ）を含む。受け取ったオーディオ信号は、さらにメモリ８０４に格納してもよく、または、通信コンポーネント８１６を介して送信してもよい。いくつかの実施形態において、オーディオコンポーネント８１０はさらに、オーディオ信号を出力するスピーカーを含む。
【０１５０】
Ｉ／Ｏインタフェース８１２は、処理コンポーネント８０２と、キーボード、クリックホイール、ボタン等の周辺インタフェースモジュールとの間のインタフェースを形成する。該ボタンは、限定するものではないが、ホームボタン、ボリュームボタン、スタートボタンおよびロッキングボタンを含んでもよい。
【０１５１】
センサコンポーネント８１４は、装置８００のさまざまな様子に関する状態評価を実行できる１つ以上のセンサを含む。例えば、センサコンポーネント８１４は、装置８００の開／閉状態、装置８００のコンポーネント、例えば、ディスプレイおよびキーボードの相対的位置、装置８００または装置８００のコンポーネントの位置の変化、装置８００と接触するユーザの存在の有無、装置８００の方向性または加速／減速、および装置８００の温度の変化を検出してもよい。センサコンポーネント８１４は、何らかの物理的接触を伴うことなく、すぐ近くのオブジェクトの存在を検出するように構成された近接センサを含んでもよい。また、センサコンポーネント８１４は、撮像用途に用いるための、ＣＭＯＳまたはＣＣＤ等の光センサも含んでもよい。いくつかの実施形態においては、センサコンポーネント８１４は、加速度計、ジャイロスコープセンサ、磁気センサ、圧力センサまたは温度センサも含んでもよい。
【０１５２】
通信コンポーネント８１６は、装置８００と他の装置との有線または無線の通信を容易にするように構成されている。装置８００は、ＷｉＦｉ，２Ｇまたは３Ｇ、またはこれらの組合せ等の通信規格に基づいて無線ネットワークにアクセスすることができる。１つの実施例において、通信コンポーネント８１６は、放送チャネルを介して外部放送管理システムからの放送信号または放送関連情報を受信する。１つの例示的な実施形態において、通信コンポーネント８１６は、近距離通信を容易にするために、近距離無線通信（ＮＦＣ）モジュールをさらに含む。例えば、ＮＦＣモジュールは、無線自動識別（ＲＦＩＤ）技術、赤外線通信（ＩｒＤＡ）技術、超広帯域（ＵＷＢ）技術、ブルートゥース（ＢＴ）技術およびその他の技術に基づいて実施することができる。
【０１５３】
例示的な実施形態において、装置８００は、１つ以上の特定用途向け集積回路（ＡＳＩＣ）、ディジタル信号プロセッサ（ＤＳＰ）、ディジタル信号処理装置（ＤＳＰＤ）、プログラム可能論理素子（ＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、制御装置、マイクロコントローラ、マイクロプロセッサ、または、上述した方法を実行するための他の電子コンポーネントを用いて実施することができる。
【０１５４】
例示的な実施形態においては、上述した方法を実行するための、装置８００のプロセッサ８２０によって実行可能な、例えば、記憶装置８０４に含まれる命令を含む、非持続性コンピュータ可読記憶媒体も設けられている。例えば、該非持続性コンピュータ可読記憶媒体は、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ記憶装置等であってもよい。
【０１５５】
該記憶媒体内の命令が、携帯端末のプロセッサによって実行される場合に、該携帯端末が、
アクセスすべきオブジェクトの各近隣オブジェクトを取得することと、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することであって、該アクセスすべきオブジェクトが複数の隣接するドメインを有することと、
該近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在する場合に、該アクセスすべきオブジェクトを第１のグループにクラスタリングすることと、
第１のグループに入れることができる近隣オブジェクトがなくなるまで、該アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することと、
を含むクラスタリング方法を実行することができる非持続性コンピュータ可読記憶媒体が設けられる。
【０１５６】
本開示が、上述され、および添付図面に図示されている正確な構成に限定されないこと、および本発明の範囲から逸脱することなく、さまざまな変更および変形が実行可能であることは正しく認識されるであろう。本開示の範囲は、添付クレームによってのみ限定されることが意図されている。
【０１５７】
「第１の」および「第２の」等の本願明細書における関連する用語は、単に存在物または動作と別の存在物または動作を区別することが意図され、それらの存在物または動作間の何らかの関係または順序をほのめかすことは意図されていないことに留意すべきである。さらに、「含む」、「備える」またはその他の変形等の用語は、非排他的な意味をカバーするように意図され、そのため、一連の要素を含むプロセス、方法、オブジェクトまたは装置は、明確に概説されていない他の要素をさらに含んでもよく、または、該プロセス、方法、オブジェクトまたは装置の固有の要素を含んでもよい。
【０１５８】
上記は、単に本開示の実施形態であり、および当業者が本開示を理解または実施するのに役に立つように意図されている。それらの実施形態のさまざまな変更は、当業者には明らかであり、また、本願明細書で定義されている一般的原理は、本開示の趣旨および範囲から逸脱することなく、他の実施形態において実行することができる。したがって、本開示は、本願明細書のそれらの実施形態に限定されないが、本開示の原理および新規な特徴に適合する最も広い範囲を請求する。
【図１】
2016520896.tif 000006
【図２】
2016520896.tif 000007
【図３】
2016520896.tif 000008
【図４】
2016520896.tif 000009
【図５】
2016520896.tif 000010
【図６】
2016520896.tif 000011
【図７】
2016520896.tif 000012
【図８】
2016520896.tif 000013
【図９】
2016520896.tif 000014
【手続補正書】
【提出日】平成27年3月2日(2015.3.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
アクセスすべきオブジェクトの各近隣オブジェクトを取得することと、
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することであって、前記アクセスすべきオブジェクトが、複数の隣接するドメインを有することと、
前記近隣オブジェクトの数が前記所定値以上であると判断された場合に、前記アクセスすべきオブジェクトを第１のグループにクラスタリングすることと、
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することと、
を備えるクラスタリング方法。
【請求項２】
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することは、
近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を取得することと、
前記複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上であるか否かを判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されているか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの全てが判断されていない場合に、前記複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上であるか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトをコアオブジェクトではないと判断することと、
を備える請求項１に記載のクラスタリング方法。
【請求項３】
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断することは、
近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を取得することと、
距離に対応する重み係数を取得することであって、前記重み係数が前記距離に関連付けられていることと、
前記距離と、前記対応する重み係数とに従って、第１の隣接するドメイン内の前記近隣オブジェクトの数を計算することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が、前記複数の隣接するドメインの走査半径の昇順で前記所定値以上であるか否かを判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断することと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されているか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの全てが判断されていない場合に、前記複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の前記近隣オブジェクトの数が所定値以上であるか否かを判断することと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトをコアオブジェクトではないと判断することと、
を備える請求項１に記載のクラスタリング方法。
【請求項４】
前記距離に関連付けられた対応する重み係数を取得することは、
前記近隣オブジェクトからの距離と前記アクセスすべきオブジェクトとの対応性と、前記近隣オブジェクトが、前記アクセスすべきオブジェクトと同じであるか否かの確率とを取得することと、
前記対応性を問い合わせることにより、近隣オブジェクトが、前記距離に対応する、前記アクセスすべきオブジェクトと同じであるか否かの確率を取得することと、
前記距離に前記確率を掛けることにより、前記距離に関連付けられた対応する重み係数を取得することであって、前記重み係数は、前記確率と正の相関関係にあることと、
を備える請求項３に記載のクラスタリング方法。
【請求項５】
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行することは、
前記アクセスすべきオブジェクトの前記所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得することであって、前記所定の隣接するドメインの走査半径は、前記複数の隣接するドメインの最大走査半径よりも小さいことと、
各直接的に密度可到達の近隣オブジェクトが、コア近隣であるであるか否かを１つずつ判断することと、
前記直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合に、前記所定の隣接するドメイン内に前記近隣オブジェクトを追加することであって、前記第１のグループに入る近隣オブジェクトがなくなるまで、前記直接的に密度可到達の近隣オブジェクトは前記第１のグループに入ることと、
を備える請求項１〜請求項４のいずれか一項に記載のクラスタリング方法。
【請求項６】
各直接的に密度可到達の近隣オブジェクトがコアオブジェクトであるか否かを１つずつ判断することは、
前記近隣オブジェクトの数が前記所定値以上である少なくとも１つの隣接するドメインが、前記直接的に密度可到達の近隣オブジェクトの前記複数の隣接するドメイン内に存在するか否かを判断することと、
前記近隣オブジェクトの数が前記所定値以上である場合に、前記直接的に密度可到達の近隣オブジェクトを前記コアオブジェクトとして判断することと、
前記直接的に密度可到達の近隣オブジェクトの前記複数の隣接するドメインの各々における前記近隣オブジェクトの数が前記所定値未満である場合に、前記直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断することと、
を備える請求項５に記載のクラスタリング方法。
【請求項７】
前記複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の前記近隣オブジェクトの数が、前記所定値以上であるか否かを判断することは、
各近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を順序付けることおよび前記距離の順序を取得することと、
前記距離の順序に従って、前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数を計数することと、
前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数が前記所定値以上であるか否かを判断することと、
を備える請求項２に記載のクラスタリング方法。
【請求項８】
アクセスすべきオブジェクトの各近隣オブジェクトを取得するように構成された第１の取得ユニットと、
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断するように構成された第１の判定ユニットであって、前記アクセスすべきオブジェクトが複数の隣接するドメインを有する第１の判定ユニットと、
前記近隣オブジェクトの数が前記所定値以上である前記少なくとも１つの隣接するドメインが存在すると判断された場合に、前記アクセスすべきオブジェクトを第１のグループにクラスタリングするように構成されたクラスタリングユニットと、
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように構成された拡張クラスタリングユニットと、
を備えるクラスタリング装置。
【請求項９】
前記第１の判定ユニットは、
近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を取得するように構成された第１の取得サブユニットと、
前記複数の隣接するドメインの走査半径の昇順の距離に従って、第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上であるか否かを判断するように構成された第１の判定サブユニットと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成された第１の判断サブユニットと、
前記第１の隣接するドメイン内の前記近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されているか否かを判断するように、前記アクセスすべきオブジェクトの前記複数の隣接するドメインの全てが判断されていない場合には、前記複数の隣接するドメインの走査半径の昇順の距離に従って、第２の隣接するドメイン内の前記近隣オブジェクトの数が所定値以上であるか否かを判断するように前記第１の判定サブユニットを実行させるように構成された第２の判定サブユニットと、
前記アクセスすべきオブジェクトの前記複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトを前記コアオブジェクトではないと判断するように構成された第２の判断サブユニットと、
を備える請求項８に記載のクラスタリング装置。
【請求項１０】
前記第１の判定ユニットは、
近隣オブジェクトと、アクセスすべきオブジェクトとの距離を取得するように構成された第２の取得サブユニットと、
前記距離に対応する重み係数を取得するように構成された第３の取得サブユニットであって、前記重み係数が前記距離に関連付けられている第３の取得サブユニットと、
前記距離および対応する重み係数に従って、第１の隣接するドメイン内の近隣オブジェクトの数を計算するように構成された計算サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が、前記複数の隣接するドメインの走査半径の昇順で所定値以上であるか否かを判断するように構成された第３の判定サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が前記所定値以上である場合に、前記アクセスすべきオブジェクトをコアオブジェクトとして判断するように構成された第３の判断サブユニットと、
前記第１の隣接するドメイン内の近隣オブジェクトの数が前記所定値未満である場合に、前記アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されているか否かを判断するように、前記アクセスすべきオブジェクトの複数の隣接するドメインの全てが判断されていない場合には、前記距離および対応する重み係数に従って、第２の隣接するドメイン内の近隣オブジェクトの数を計算するように計算サブユニットを実行させるように構成された第４の判定サブユニットと、
前記アクセスすべきオブジェクトの複数の隣接するドメインの各々が既に判断されている場合に、前記アクセスすべきオブジェクトをコアオブジェクトではないと判断するように構成された第４の判断サブユニットと、
を備える、請求項８に記載のクラスタリング装置。
【請求項１１】
前記第３の取得サブユニットは、
前記近隣オブジェクトから、前記アクセスすべきオブジェクトまで距離と、前記近隣オブジェクトが、前記アクセスすべきオブジェクトと同じであるか否かの確率との対応性を取得するように構成された計数サブユニットと、
前記近隣オブジェクトが、前記距離に対応する、前記アクセスすべきオブジェクトと同じであるか否かの確率を取得するために、前記対応性を問い合わせるように構成された問い合わせサブユニットと、
前記距離に前記確率を掛けることにより、前記距離に関連付けられた対応する重み係数を取得するように構成された第４の取得ユニットであって、前記重み係数が、前記確率と正の相関関係にある第４の取得ユニットと、
を備える、請求項１０に記載のクラスタリング装置。
【請求項１２】
前記拡張クラスタリングユニットは、
前記アクセスすべきオブジェクトの所定の隣接するドメイン内の各直接的に密度可到達の近隣オブジェクトを取得するように構成された第５の取得サブユニットであって、所定の隣接するドメインの走査半径は、複数の隣接するドメインの最大走査半径よりも小さい第５の取得サブユニットと、
各直接的に密度可到達の近隣オブジェクトが、コア近隣であるであるか否かを１つずつ判断するように構成された第５の判定サブユニットと、
直接的に密度可到達の近隣オブジェクトがコアオブジェクトであると判断された場合に、所定の隣接するドメイン内に前記近隣オブジェクトを追加するように構成された拡張クラスタリングサブユニットであって、前記第１のグループに入る近隣オブジェクトがなくなるまで、前記直接的に密度可到達の近隣オブジェクトは前記第１のグループに入る拡張クラスタリングサブユニットと、
を備える、請求項８〜請求項１１のいずれか一項に記載のクラスタリング装置。
【請求項１３】
前記第５の判定サブユニットは、
前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが、前記直接的に密度可到達の近隣オブジェクトの複数の隣接するドメイン内に存在するか否かを判断するように構成された第６の判定サブユニットと、
前記近隣オブジェクトの数が前記所定値以上である場合に、前記直接的に密度可到達の近隣オブジェクトをコアオブジェクトとして判断するように構成された第５の判断サブユニットと、
前記直接的に密度可到達の近隣オブジェクトの前記複数の隣接するドメインの各々における前記近隣オブジェクトの数が前記所定値未満である場合に、前記直接的に密度可到達の近隣オブジェクトをコアオブジェクトではないと判断するように構成された第６の判断サブユニットと、
を備える請求項１２に記載のクラスタリング装置。
【請求項１４】
前記第１の判定サブユニットは、
各近隣オブジェクトと、前記アクセスすべきオブジェクトとの距離を順序付けし、および前記距離の順序を取得するように構成された順序付けユニットと、
前記距離の順序に従って、前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数を計数するように構成された第２の計数サブユニットと、
前記隣接するドメインの走査半径未満の前記アクセスすべきオブジェクトに関する前記距離を有する前記近隣オブジェクトの数が前記所定値以上であるか否かを判断するように構成された第７の判定サブユニットと、
を備える、請求項９に記載のクラスタリング装置。
【請求項１５】
プロセッサと、
実行可能な命令を前記プロセッサによって格納するように構成された記憶装置であって、前記プロセッサは、
アクセスすべきオブジェクトの各近隣オブジェクトを取得するように、
前記アクセスすべきオブジェクトは複数の隣接するドメインを有し、前記近隣オブジェクトの数が所定値以上である少なくとも１つの隣接するドメインが存在するか否かを判断するように、
前記近隣オブジェクトの数が所定値以上である前記少なくとも１つの隣接するドメインが、前記アクセスすべきオブジェクトの前記複数の隣接するドメイン内に存在していると判断された場合に、前記アクセスすべきオブジェクトを第１のグループにクラスタリングするように、および
前記第１のグループに入れることができる近隣オブジェクトがなくなるまで、前記アクセスすべきオブジェクトの所定の隣接するドメイン内の直接的に密度可到達の近隣オブジェクトに対して拡張クラスタリングを実行するように、
構成される記憶装置と、
を備える端末装置。
【請求項１６】
コンピュータの稼働する時、請求項１から７のいずれか１項に記載のクラスタリング方法を実行させるコンピュータプログラム。
【請求項１７】
請求項１６に記載のコンピュータプログラムを含む、コンピュータ読み取り可能な記録媒体。
【国際調査報告】
2016520896.tif 000015
2016520896.tif 000016
2016520896.tif 000017
2016520896.tif 000018