(57)【要約】  1つまたは複数のモバイルデバイスは、パスに沿って移動しながら測定値を得る。各測定値は、ワイヤレス送信機の識別子の特定のグループと、対応するワイヤレス信号の強度とを含むことができる。測定値のセットはパスに沿って系列内に得られ、測定値のサブセットは、サブセットに含まれる測定値の類似性の尺度の値に関するテストに合格するために識別される。上記で説明した測定値のサブセットを追加測定値の類似のサブセットと(たとえばクラスタリングによって)比較することによって、新しい関連場所が識別される。あるいは、上記で説明した測定値のサブセットをあらかじめ計算された測定値のモデルと比較することによって、既知の関連場所(たとえばラベルを有する)が識別される。同様に、上記で説明した測定値のサブセットを別のパスの測定値の対応するサブセットと比較して、たとえば、その中の共通部分を識別することができる。
2014532353.tif 000002
【特許請求の範囲】
【請求項１】
関連場所を発見する方法であって、
ワイヤレス信号の測定値のセットをコンピューティングデバイスによって受信するステップと、
1つまたは複数の場所を前記コンピューティングデバイスによって識別するステップであって、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有する、識別するステップと、
2つの重心の比較に基づいて、前記2つの重心を有する対応する2つの場所が類似しているかどうかを前記コンピューティングデバイスによって判断するステップと、
前記対応する2つの場所が類似していると判断されたことに基づいて、前記対応する2つの場所を含む関連場所を前記コンピューティングデバイスによって非一時的なメモリに記憶するステップと
を含む方法。
【請求項２】
前記識別するステップが、各測定値が得られた時間とは無関係に実行される、
請求項1に記載の方法。
【請求項３】
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信するステップと、
前記対応する2つの場所に関連付けられた2つのラベルを前記コンピューティングデバイスによって比較し、前記2つのラベルが類似しているかどうかチェックするステップと
をさらに含み、
前記記憶するステップがさらに、前記2つのラベルが類似していると判断されたことに基づいて実行される、
請求項2に記載の方法。
【請求項４】
前記1つまたは複数のラベルが少なくとも2人の異なるユーザから取得される、
請求項3に記載の方法。
【請求項５】
前記1つまたは複数のラベルの第1のセットがパブリックと指定され、
前記1つまたは複数のラベルの第2のセットが、前記少なくとも2人の異なるユーザのうち少なくとも1人のユーザに対して、プライベートと指定される、
請求項4に記載の方法。
【請求項６】
前記識別するステップが、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項1に記載の方法。
【請求項７】
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックするステップ
をさらに含む、請求項6に記載の方法。
【請求項８】
前記類似性の尺度が、少なくとも、類似度関数を実行して前記測定値を前記サブセット内の測定値の重心と比較することによって取得される、
請求項7に記載の方法。
【請求項９】
前記測定値が、ワイヤレス信号の送信機の対応するグループの識別子のグループと、ワイヤレス信号の強度とを含み、
前記重心が、前記ワイヤレス信号の送信機の対応するグループの平均値のグループを含み、
前記測定値を得る際に、各平均値が、測定された前記送信機の対応するワイヤレス信号の複数の強度を求めて各送信機に対して計算される、
請求項8に記載の方法。
【請求項１０】
前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成するステップをさらに含み、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項6に記載の方法。
【請求項１１】
前記ワイヤレス信号の測定値のセット内の複数のサブセットを、追加測定値のサブセットと比較して、新しい関連場所を識別するステップ
をさらに含む、請求項10に記載の方法。
【請求項１２】
前記ワイヤレス信号の測定値のセット内の複数のサブセットを、測定値の別のセット内のサブセットと比較して、既知の関連場所を識別するステップ
をさらに含む、請求項6に記載の方法。
【請求項１３】
前記判断するステップが地理情報とは無関係に実行される、
請求項1に記載の方法。
【請求項１４】
測定値を処理するためのデバイスであって、
ワイヤレス送受信機と、
前記ワイヤレス送受信機に動作可能に結合された1つまたは複数のプロセッサと、
前記1つまたは複数のプロセッサに動作可能に結合された非一時的なメモリと、
前記非一時的なメモリ内に保持されたソフトウェアであって、前記1つまたは複数のプロセッサ内で実行されると、前記1つまたは複数のプロセッサに、
ワイヤレス信号の測定値のセットを受信させ、
1つまたは複数の場所を識別させ、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有し、
2つの重心の比較に基づいて、前記2つの重心を有する対応する2つの場所が類似しているかどうかを判断させ、
前記対応する2つの場所が類似していると判断されたことに基づいて、前記対応する2つの場所を含む関連場所を前記非一時的なメモリに記憶させる、ソフトウェアと
を備えるデバイス。
【請求項１５】
前記1つまたは複数の場所の識別が、各測定値が得られた時間とは無関係である、
請求項14に記載のデバイス。
【請求項１６】
前記ソフトウェアが、前記1つまたは複数のプロセッサに、さらに、
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信させ、
前記対応する2つの場所に関連付けられた2つのラベルを比較させ、前記2つのラベルが類似しているかどうかチェックさせ、
前記非一時的なメモリ内での前記関連場所の記憶が、前記2つのラベルが類似していると判断されたことにさらに基づく、
請求項15に記載のデバイス。
【請求項１７】
前記1つまたは複数のラベルが少なくとも2人の異なるユーザから取得される、
請求項16に記載のデバイス。
【請求項１８】
前記1つまたは複数の場所の識別が、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項14に記載のデバイス。
【請求項１９】
前記ソフトウェアが、前記1つまたは複数のプロセッサに、さらに、
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックさせる、
請求項18に記載のデバイス。
【請求項２０】
前記類似性の尺度が、少なくとも、類似度関数を実行して前記測定値を前記サブセット内の測定値の重心と比較することによって取得される、
請求項19に記載のデバイス。
【請求項２１】
前記ソフトウェアが、前記1つまたは複数のプロセッサに、さらに、前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成させ、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項18に記載のデバイス。
【請求項２２】
前記対応する2つの場所の類似性の判断が地理情報とは無関係である、
請求項14に記載のデバイス。
【請求項２３】
少なくとも1つのプロセッサによって実行されるべきソフトウェアを備える非一時的なコンピュータ可読記憶媒体であって、前記ソフトウェアが、
ワイヤレス信号の測定値のセットを受信する命令と、
1つまたは複数の場所を識別する命令であって、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有する、命令と、
2つの重心の比較に基づいて、前記2つの重心を有する対応する2つの場所が類似しているかどうかを判断する命令と、
前記対応する2つの場所が類似していると判断されたことに基づいて、前記対応する2つの場所を備える関連場所を非一時的なメモリに記憶する命令と
を備える、非一時的なコンピュータ可読記憶媒体。
【請求項２４】
前記命令が、各測定値が得られた時間とは無関係である、
請求項23に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２５】
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信する命令と、
前記対応する2つの場所に関連付けられた2つのラベルを比較して、前記2つのラベルが類似しているかどうかチェックする命令と
をさらに備え、
前記非一時的なメモリ内での前記関連場所の記憶が、前記2つのラベルが類似していると判断されたことにさらに基づく、
請求項24に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２６】
前記1つまたは複数の場所の識別が、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項23に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２７】
前記ソフトウェアが、
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックする命令
をさらに備える、請求項26に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２８】
前記類似性の尺度が、少なくとも、類似度関数を実行して前記測定値を前記サブセット内の測定値の重心と比較することによって取得される、
請求項27に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２９】
前記ソフトウェアが、前記少なくとも1つのプロセッサに、さらに、前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成させ、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項26に記載の非一時的なコンピュータ可読記憶媒体。
【請求項３０】
前記対応する2つの場所の類似性の判断が地理情報とは無関係である、
請求項23に記載の非一時的なコンピュータ可読記憶媒体。
【請求項３１】
メモリに結合されたプロセッサとワイヤレス受信機とを備えるシステムであって、
ワイヤレス信号の測定値のセットを取得するための手段と、
1つまたは複数の場所を識別するための手段であって、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有する、識別するための手段と、
2つの重心の比較に基づいて、前記2つの重心を有する対応する2つの場所が類似しているかどうかを判断するための手段と、
前記対応する2つの場所が類似していると判断されたことに基づいて、前記対応する2つの場所を含む関連場所を非一時的なメモリに記憶するための手段と
を備えるシステム。
【請求項３２】
前記判断が、各測定値が得られた時間とは無関係に実行される、
請求項31に記載のシステム。
【請求項３３】
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信するための手段と、
前記対応する2つの場所に関連付けられた2つのラベルを比較して、前記2つのラベルが類似しているかどうかチェックするための手段と
をさらに備え、
前記記憶するための手段がさらに、前記2つのラベルが類似していると判断されたことに基づく、
請求項32に記載のシステム。
【請求項３４】
前記識別するための手段が、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項31に記載のシステム。
【請求項３５】
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックするための手段
をさらに備える、請求項34に記載のシステム。
【請求項３６】
前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成するための手段をさらに備え、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項34に記載のシステム。
【請求項３７】
拡張された関連場所を発見するための装置であって、
少なくとも1つのプロセッサと、
コンピュータ可読命令を記憶する非一時的なメモリであって、前記コンピュータ可読命令が、前記少なくとも1つのプロセッサによって実行されると、前記装置に、
ワイヤレス信号の測定値のセットを取得させ、
1つまたは複数の場所を識別させ、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有し、
2つの重心の比較に基づいて、前記2つの重心を有する対応する2つの場所が類似しているかどうかを判断させ、
前記対応する2つの場所が類似していると判断されたことに基づいて、前記対応する2つの場所を含む関連場所を前記非一時的なメモリに記憶させる、非一時的なメモリと
を備える装置。
【請求項３８】
前記対応する2つの場所の類似性の判断が地理情報とは無関係である、
請求項37に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
優先出願の相互参照
本出願は、参照によりその全体が本明細書に組み込まれている、2011年9月28日に出願した「Discovering and Automatically Sizing Places of Relevance」という名称の米国仮出願第61/540,426号の利益および優先権を主張するものである。本出願はまた、参照によりその全体が本明細書に組み込まれている、2012年9月26日に出願した「Discovering and Automatically Sizing A Place of Relevance」という名称の米国特許出願第13/627,823号の利益および優先権も主張する。
【０００２】
本開示の態様は、通信技術、コンピューティング技術、および/またはロケーションベース技術に関する。より詳細には、本開示の態様は、関連場所(place of relevance)を発見するおよび/または自動的にサイズを調整するための方法、装置、システム、およびコンピュータ可読媒体に関する。いくつかの実施形態では、ユーザに関連のある場所に関連するパス(たとえば、その場所から出発するパス、その場所で終わるパス、またはその場所を通過するパス)に沿って1つまたは複数のモバイルデバイスが移動する間にそのモバイルデバイスによって得られる測定値に基づいて、その場所を発見する。
【背景技術】
【０００３】
関連場所(POR)は、ある人物にとって重要な何らかの物理的なロケーションおよび/またはエリアであってよく、この人は、たとえば、モバイルコンピューティングデバイス(たとえば、ワイヤレスハンドセット、携帯電話、スマートフォン、携帯情報端末(PDA)など)のユーザであってよい。ある特定の場所がユーザにとって重要であるかどうかは、ユーザがその特定の場所に対応する物理的ロケーションおよび/またはエリアで費やす期間によって決まるおよび/またはこの期間によって測定することができる。したがって、コンピューティングデバイスのユーザ(それに対応して、コンピューティングデバイス自体)がある特定の場所で十分に長い期間静止しているおよび/または費やす場合、そのコンピューティングデバイスは、その特定の場所がPORであると判断することができる。
【０００４】
ユーザがラベルを供給する従来技術では、ユーザに関連のある場所を識別することも知られている。たとえば、測定の第1のセットは、モバイルデバイスが静止しているときに、そのモバイルデバイスによって得ることができる。その後、ユーザは、これらの測定値が得られた場所に「オフィス」というラベルを付けることができる。同様に、測定値の第2のセットは、モバイルデバイスが別のロケーションで静止しているときに得ることができ、その後、そのロケーションには、ユーザによって「自宅」というラベルを付けることができる。したがって、測定値の第1のセットおよび第2のセットが得られたエリアは、ユーザに関連のある2つの場所を構成する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、モバイルデバイスが静止しているときに得られる測定値に基づくだけでなく、モバイルデバイスが静止していないときに得られる測定値、すなわちモバイルデバイスが移動しているときに得られる測定値にも基づいて、上記で説明した種類の関連場所を識別することが必要とされている。発明者らが認識している1つの課題は、モバイルデバイスが店舗(デパート、たとえばJ.C. PennyまたはMacy'sなど)内のパスに沿ってユーザにより移動させられるときに生じる。店舗では、ユーザは1つの地点で数分静止せず、代わりに、一般にユーザは店舗内を歩き回っている。したがって、モバイルデバイスが移動しているときに得られる測定値を使用して、以下で説明するように関連場所を識別することが必要とされている。
【課題を解決するための手段】
【０００６】
本開示の態様は、1つまたは複数の関連場所(POR)の発見および/または自動的なサイズ調整に関する。たとえば、いくつかのPORは、単一の特定の地点(または、ワイヤレス信号の測定値が得られた位置)を表すように定義されないことがあり、代わりに、複数の地点を含む、現実世界におけるパスを表すように定義されてよい。さらに他のPORは、現実世界における隣接しているおよび/または連続している地点のセットを表すように定義されてもよい。本開示の1つまたは複数の態様を実施することによって、コンピューティングデバイス(および/または、その上で実行されるソフトウェア)は、ロケーション固有の提供(たとえば、近くの店舗、レストランなどのクーポン)、ロケーション固有の広告、他のロケーションベースの特徴、および/またはロケーションに関連する情報などの拡張された機能をユーザに提供することを可能とすることができる。
【０００７】
1つまたは複数の態様によれば、1つまたは複数の拡張された関連場所を発見する際に、複数の関連場所を識別することができる。複数の関連場所のうち1つまたは複数の関連場所に関連付けるべき1つまたは複数のラベルを指定するユーザ入力を受信することができる。その後、受信したユーザ入力に基づいて、複数の関連場所のうち少なくとも2つの関連場所が1つまたは複数のラベルのうち第1のラベルに関連付けられるかどうかを判断することができる。次いで、(重心間の相違を示す)1つまたは複数の距離メトリックに基づいて、少なくとも2つの関連場所が隣接しているかどうかを判断することができる。その後、少なくとも2つの関連場所が第1のラベルに関連付けられると判断したことを受けて、および少なくとも2つの関連場所が隣接していると判断したことを受けて、少なくとも2つの関連場所が拡張された関連場所を定義すると判断することができる。
【０００８】
少なくとも1つの構成では、1つまたは複数のラベルは、少なくとも2人の異なるユーザから取得することができる。1つまたは複数の追加構成では、1つまたは複数のラベルの第1のセットはパブリックと指定することができ、1つまたは複数のラベルの第2のセットは、少なくとも2人の異なるユーザのうち少なくとも1人のユーザに対して、プライベートと指定することができる。さらに1つまたは複数の追加構成では、第1のラベルは、第1のセットに含めることができる。
【０００９】
1つまたは複数の追加態様および/または代替態様によれば、1つまたは複数のパスベースの関連場所を発見する際に、複数の位置値を受信することができる。その後、1つまたは複数の連続的な歩行区間を複数の位置値に基づいて識別することができる。次いで、少なくとも2つの識別された連続的な歩行区間に対して、この少なくとも2つの識別された連続的な歩行区間の各々に対応する重心のツリーを生成することができる。その後、生成された重心のツリーに基づいて、この少なくとも2つの識別された連続的な歩行区間が第1のパスに一致するかどうか判断することができる。
【００１０】
少なくとも1つの構成では、生成された重心のツリーの各々は、複数のレベルを含むことができる。1つまたは複数の追加構成では、少なくとも2つの識別された連続的な歩行区間が第1のパスに一致するかどうかを判断することは、生成された重心のツリーの対応するレベルを再帰的に比較することを含むことができる。さらに1つまたは複数の追加構成では、少なくとも2つの識別された連続的な歩行区間が第1のパスに一致するかどうかを判断することは、生成された重心のツリーの対応するレベルを個別にクラスタ化することを含むことができる。
【００１１】
いくつかの実施形態では、モバイルデバイスは、パスに沿って歩行しているユーザによって持ち歩かれながら、ワイヤレス信号の測定値を得る。各測定値は、ワイヤレス送信機の識別子の特定のグループと、対応するワイヤレス信号の強度とを含むことができる。測定値のセットは、ユーザのパスに沿って時系列的に得られ、これらの測定値のサブセットは、たとえばサブセットに含まれる測定値の類似性の尺度に関する、1つまたは複数の所定のテストに合格するために識別される。たとえば、上記で説明した測定値のサブセットの重心(および/またはラベルなどの他の属性)を追加測定値の類似のサブセットの重心(および/またはラベルなどの他の属性)と(たとえばクラスタリングによって)比較することによって、新しい関連場所が識別される。あるいは、上記で説明した測定値のサブセットをあらかじめ計算された測定値のモデルと比較することによって、既知の関連場所(たとえばラベルを有する)が識別される。同様に、上記で説明した測定値のサブセットを別のパスの測定値の対応するサブセットと比較して、たとえば、その中の共通部分を識別することができる。
【図面の簡単な説明】
【００１２】
【図１Ａ】本開示におけるいくつかの実施形態の1つまたは複数の例示的態様により1つまたは複数の拡張された関連場所を発見するおよび/または自動的にサイズを調整する1つの例示的な方法を示す図である。
【図１Ｂ】本開示におけるいくつかの実施形態の1つまたは複数の例示的態様による、概念的に示された例示的な拡張された関連場所を屋内地図上に示した図である。
【図２Ａ】本開示におけるいくつかの実施形態の1つまたは複数の例示的態様により1つまたは複数のパスベースの関連場所を発見するおよび/または自動的にサイズを調整する1つの例示的な方法を示す図である。
【図２Ｂ】本開示におけるいくつかの実施形態の1つまたは複数の例示的態様による、概念的に示されたパスベースの関連場所を屋内地図上に示した図である。
【図３Ａ】本明細書で説明するいくつかの実施形態において、パスに沿って移動しながらワイヤレス信号の測定値を得るためにモバイルデバイス120によって実行される動作(act)を高水準流れ図で示した図である。
【図３Ｂ】経時的に得られた測定値間の類似性をY軸(たとえば0〜1の範囲で)上に、X軸(たとえば0〜10分の範囲で)に沿った測定の時刻の関数として示すプロットを二次元グラフで示した図である。
【図３Ｃ】説明する実施形態のうちのいくつかにおける、図5Aのモバイルデバイス120のプロセッサ100によって実行される動作を高水準流れ図で示した図である。
【図４Ａ】いくつかの実施形態のモバイルデバイス120を高水準ブロック図で示した図である。
【図４Ｂ】図4Aの発見システム130において使用される1つまたは複数のパラメータを表で示したものである。
【図４Ｃ】説明する実施形態のいくつかにおいて、最初に測定の時刻(たとえば、タイムスタンプによって示される)に基づいてWiFi測定をクラスタ化し、続いて外れ値を除外するためのクラスタのマージ、続いて徒歩以外の移動中に得られた測定値を除外するための持続時間フィルタリング、続いて関連場所(POR)を識別するための類似性クラスタリングによって、図4Aの発見システム130の動作を一例として示した図である。
【図５Ａ】時間順データのクラスタリングを実行するいくつかの実施形態の時間的クラスタリングモジュールを擬似コードで示した図である。
【図５Ｂ】クラスタをマージし、それによって外れ値を除外するいくつかの実施形態のクラスタマージングモジュールを擬似コードで示した図である。
【図５Ｃ】徒歩以外の移動中に得られた測定値、たとえば自転車または車などの移動している乗り物に乗っている間に得られた測定値を除外するいくつかの実施形態の持続時間フィルタリングモジュールを擬似コードで示した図である。
【図５Ｄ】訪問の流れおよび既知の関連場所のセットに基づいて新しい関連場所を識別する、いくつかの実施形態のPOR抽出モジュールを擬似コードで示した図である。
【図５Ｅ】訪問の流れおよび既知の関連場所のセットに基づいて既知の関連場所にユーザが存在することを識別する、いくつかの実施形態のPOR認識モジュールを擬似コードで示した図である。
【図６Ａ】説明する実施形態のうちのいくつかにおける、図4Aのコンピュータシステム120のプロセッサ100によって実行される追加の動作を高水準流れ図で示した図である。
【図６Ｂ】間仕切りされた区画(cubicle)601から始まりオフィス600を通過して休憩室602で終わるパス「A」に沿ってユーザが歩いている間のコンピュータシステム120による測定を示した図である。
【図６Ｃ】図4Aのコンピュータシステム120のメモリ110における測定値A1…AI…AN、ならびにこれらの測定値に対する重心C1A、ならびにAIの類似性属性(または類似性尺度)を示した図である。
【図６Ｄ】図6Bのパスのためのメモリ110内のルートノード621を示した図である。
【図６Ｅ】メモリ110における、図6BのパスAの2つの部分を、測定値の2つのサブセットすなわち測定値A1〜AIおよび測定値AJ〜ANそれぞれを形成するための類似性尺度の使用によって形成されるサブパスALおよびARとして示した図である。
【図６Ｆ】図6Eに示される2つのサブセットA1〜AIおよびAJ〜ANに基づいてルートノード621ならびにその子ノード622および623によって形成されたツリー620を示した図である。
【図６Ｇ】メモリ110における、図6BのパスAの6つの部分を、図6Eに示される2つのサブセットA1〜AIおよびAJ〜ANの各々に含まれる測定値の3つのサブセットを形成するための類似性尺度の使用によって形成されるサブサブパスALL、ALM、ALR、ARL、ARM、およびARRとして示した図である。
【図６Ｈ】図6Gに示される6つの部分(およびしたがって6つのサブセット)のためのノードを含むようにこの時点で強化(augment)された図6Fのツリー620を示した図である。
【図７】いくつかの実施形態において図6Eおよび図6Gに示される種類の測定値のサブセットを追加測定値のサブセットと比較して、新しい関連場所を識別するためにいくつかの実施形態で実行される動作を流れ図で示した図である。
【図８Ａ】あるパスの測定値のサブセットを別のパスと比較するために、図5Aのモバイルデバイス120のプロセッサ100によって実行される追加の動作を高水準流れ図で示した図である。
【図８Ｂ】2つの間仕切りされた区画からオフィス600を通過して始まり両方とも休憩室で終わる2つのパス「A」および「B」に沿った測定値を示した図である。
【図８Ｃ】図5Aのモバイルデバイス120のメモリ110における、複数のサブセットに細分され次いで比較される図8Bの2つのパスに沿った測定値を示した図である。
【図８Ｄ】図8Bのうち2つのパス上での測定値のサブセットのマッチングを示した図である。
【図９Ａ】本開示におけるいくつかの実施形態の1つまたは複数の例示的態様により、関連場所(POR)を自動的にサイズ調整する一例を屋内地図上に示した図である。
【図９Ｂ】本開示のいくつかの実施形態の1つまたは複数の例示的態様における、拡張されたPOR910を自動的にサイズ調整するために使用される測定値(双方向矢印921〜926として示されている)間の相違を示すペアワイズ距離を、訪問911〜914(ハッチングの付いた円として示されている)間の、図9Aの拡張されたPOR910内に示した図である。
【図９Ｃ】dsize=μ+aσ(たとえば、a=3、しかし実施形態に応じて、aは2、2.99、4などの何らかの定数値であってよい)のとき、サイズ調整で使用するために拡張されたPOR内での訪問間のペアワイズ距離(x軸に沿って)の発生の頻度(y軸に沿って)をグラフで示した図である。
【図９Ｄ】本開示のいくつかの実施形態の1つまたは複数の例示的態様における、新しい拡張されたPOR930を取得するための、拡張されたPOR910の訪問911〜914への新しい訪問931の追加を示した図である。
【図９Ｅ】本開示のいくつかの実施形態の1つまたは複数の例示的態様において、関連場所を自動的にサイズ調整するためにいくつかの実施形態において実行される動作を流れ図で示した図である。
【図９Ｆ】訪問CV1が、拡張されたPORの中心から距離dsize/bの範囲内にあるか、または訪問CV2が、拡張されたPORの中心から距離dsizeとdsize/bとの間にあるかに応じて、それぞれ拡大または縮小された拡張されたPORを示した図である(たとえば、b=2、しかし実施形態に応じて、bは1、1.99、3などの何らかの定数値であってよい)。
【図９Ｇ】説明する実施形態のいくつかの態様における、プロセッサ100によって実行される動作を高水準流れ図で示した図である。
【発明を実施するための形態】
【００１３】
以下の説明におけるいくつかの実施形態は、関連場所を、ユーザが十分長い期間(たとえば10秒とあらかじめ決められた)とどまる固定の場所に関連する場所、すなわちユーザにとって意味上の関連を有する固定の場所とのみ考えるシステムを、以下の2つの拡張機能、すなわち、(A)パスベースの関連場所および(B)拡張された関連場所のうち少なくとも1つを有するように拡張する。
【００１４】
第1の種類の関連場所(パスベースの関連場所と呼ばれる)は、ユーザが多くの場合に歩いて通る、またはユーザが多くの場合にその中を長期間(たとえば10分)歩き回る傾向がある、エリアである。そのような関連場所(「POR」)は、以下ではパスと呼ぶこともある。パスベースのPORは、従来の軌跡というよりもむしろ、ユーザの歩行が行われる現実世界の領域を表すように、より漠然と定義されることがある。例としては、スーパーマーケットまたは商店街があり得る。これらの場所では、ユーザは1つの地点で必ずしも数分を費やすとは限らないが、一般に店舗内を歩き回っている可能性がある。
【００１５】
第2の種類の関連場所(拡張された関連場所と呼ばれる)は、多数の隣接するまたは連続している発見された固定関連場所がユーザによって同じ関連場所であると意味的に考えられ得るエリアである。例としては、カフェテリアまたは講堂または劇場が含まれ得る。これらは、ユーザの観点から、異なる座席が同じ場所であると意味的に考えられ得るが、従来のアルゴリズムでは、複数の固定関連場所と識別することができる。この第2の種類の関連場所への各訪問は、同じ場所の一部であると見なされることがあるが、本明細書で説明するいくつかの実施形態では、その場所の異なる部分に対応する複数の訪問を同じ意味論的関連場所であると識別する。
【００１６】
いくつかの実施形態では、拡張された関連場所の方法は、ユーザが所定の期間(たとえば10秒)静止している訪問中に信号測定値を生成し、それらの測定値をクラスタ化して場所を形成する(たとえば、以下で図4Aを参照して説明する)固定POR方法の出力を消費する。いくつかの実施形態では、たとえば1つまたは複数のユーザから受信されたラベルの入力(文字列など)に基づいて、固定POR方法によって出力される場所に、ラベルまたは注釈(ラベルとの関連によって)が付けられる。いくつかの実施形態における拡張された関連場所の方法では、ラベルを受信して(重心の比較に加えて)自動的に比較し、ラベルが(所定の閾値に従って)同一または十分に類似しているとき、それぞれの場所を、拡張された場所に含まれると自動的にマークする。ラベルの比較は、コンピューティングデバイスによって実施形態に応じて何らかの形で実行することができ、たとえばハミング距離≦2を持つラベルは類似していると見なすことができる。
【００１７】
いくつかの実施形態では、上記で説明した拡張された関連場所の方法は再帰的に実行され、したがって、何らかの数の場所は、拡張されたPORに含めることができる。上記で説明した拡張された関連場所の方法は、測定値が得られた時刻を使用しない(および、これとは無関係である)(たとえば測定値のタイムスタンプは使用されない)ことに留意されたい。対照的に、パスベースの関連場所の方法では、測定値の時系列(測定の時刻に従って互いに順序づけられた測定値)を使用して、場所の重心および/またはクラスタ化するべき測定値を識別する。たとえば、ある場所へのユーザによる訪問の特定の系列が数回繰り返されるとき、これは、パスベースの関連場所の方法を実行する際にコンピュータシステム120によって学習される。したがって、いくつかの実施形態では、パスベースの関連場所の方法において、POR方法を全体として使用せず、代わりに、その中でいくつかのステップを使用する。このステップは、本明細書で図4A〜図4Cを参照して説明するように、実施形態に応じて様々なやり方で実行される。
【００１８】
拡張された関連場所は、コンピューティングデバイスのいくつかの実施形態では、次のように形成することができる。(1)同じ(または十分に類似した)ラベルを異なる固定関連場所に適用するためのユーザ入力、(2)固定関連場所を発見するために使用される距離メトリック(測定値間の相違を示す)は複数の固定関連場所が隣接するまたは連続していることを自動的に判断するために使用することが可能である。条件1および条件2(たとえば、上記の2つの条件)を満たす固定関連場所のすべては、次いで、より大きい拡張された関連場所と関連付けることができる。この方法を用いた結果、現実世界ではたとえばカフェテリアおよび劇場であり得る場所を、拡張された関連場所として正しく発見する(たとえば自動識別)ことができる。さらに、コンピューティングデバイスは、複数の場所をマージしないように構成することができ、固定関連場所が条件2(たとえば、上記の第2の条件)を満たさない場合、ユーザは、この複数の場所を職場として選択して、拡張された関連場所を形成することができる。
【００１９】
この方法を応用して、ラベルが複数のユーザから得られるときに拡張された関連場所を自動的に発見するため、ラベルを注意深く選定することが必要な場合がある。たとえば、2人の従業員が固定関連場所にオフィスまたは私のオフィスとラベルを付け、この2人が、隣接するオフィスを有する場合、これらの関連場所を(たとえばサーバコンピュータによって)マージして単一の拡張された関連場所にすることはしない。いくつかの構成では、サーバコンピュータの中に、各ラベルに対して、そのラベルを「パブリック」または「プライベート」と定義する有効範囲が存在する場合がある。固定関連場所のマージというこの問題を回避するために、拡張された関連場所の発見は、コンピューティングデバイスによって、パブリックラベルを持つ場合のみ行われ、パーソナル/プライベートラベルを持つ場合には行われなくてもよい。ラベルの有効範囲は、あらかじめ知られていてもよいし、ユーザによって設定されてもよい。後者の場合、複数のユーザが同じラベルに対して異なる有効範囲を選定したときに、競合解消の手段(たとえば、競合解消方法)が必要とされることがある。
【００２０】
図1Aは、本開示の1つまたは複数の例示的態様により1つまたは複数の拡張された関連場所を発見するおよび/または自動的にサイズを調整する1つの例示的な方法を示す。1つまたは複数の態様によれば、図1Aに示される例示的な方法のうちのステップのいずれかおよび/またはすべては、1つまたは複数のコンピューティングデバイス(たとえば、コンピュータシステム120)内で実施されるおよび/またはこれによって実行されることが可能であり、このコンピューティングデバイスは、実施形態に応じて移動中および/または静止していることができる。これに加えて、またはこの代わりに、図1Aに示される例示的な方法のステップのいずれかおよび/またはすべては、実行されると1つまたは複数のコンピューティングデバイスに例示的な方法を実行させることが可能なコンピュータ実行可能命令として、コンピュータ可読媒体内に記憶することができる。
【００２１】
ステップ101(図1A)では、複数の関連場所を識別することができる。たとえば、ステップ101では、コンピューティングデバイス(たとえば、コンピュータシステム120)は、コンピューティングデバイスによって入手される位置データに基づいて複数の関連場所を識別することができる。そのような位置データには、WiFi(登録商標)信号の1つまたは複数の測定値(WiFiトレースと呼ばれる)、モーションの分類、ステップカウント、方向情報、音紋、および/または他の位置データなどが含まれ得る。そのような位置データを使用して、コンピューティングデバイスは、たとえば、ユーザ(および/またはコンピューティングデバイス)が十分に長い期間特定のエリアまたはロケーションで静止しているおよび/または静止していた場合(たとえば、ユーザが特定のエリアまたはロケーションで費やす時間が10秒などの閾値を超える場合)、その特定のエリアまたはロケーション(位置データの1つまたは複数の項目に対応することができる)が関連場所であると判断することができる。いくつかの構成では、これに加えて、またはこの代わりに、他の方法および/またはステップを使用して、複数の関連場所を識別することができる。
【００２２】
ステップ102では、1つまたは複数のラベルを指定するユーザ入力を受信することができる。たとえば、ステップ102では、コンピューティングデバイスは、ユーザによる1つまたは複数のラベル(たとえば、意味タグ)の1つまたは複数の関連場所への割り当てに相当するユーザ入力を(たとえば、1つまたは複数のユーザインターフェースを介して)受信することができる。たとえば、あるユーザは、1つの関連場所に「私のオフィス」とラベルを付けることができ、このユーザは、別の関連場所に「ショッピングモール」とラベルを付けることができる。同様に、1つまたは複数の他のラベルが、ユーザによって割り当てられるおよび/またはコンピューティングデバイスによって受信されることが可能である。
【００２３】
ステップ103では、同じラベルが少なくとも2つの関連場所に割り当てられているかどうか判断することができる。たとえば、ステップ103では、コンピューティングデバイスは、ステップ102で受信したユーザ入力に基づいて、たとえば、複数の関連場所のうち少なくとも2つの関連場所に同じラベルが割り当てられているかどうか判断することができる。たとえば、コンピューティングデバイスのユーザが、ある関連場所に「モアハウスマーケット」とラベルを付け、おそらく近くにある別の関連場所にも「モアハウスマーケット」とラベルを付けることがある。これに加えて、またはこの代わりに、他の方法および/またはステップを使用して、同じラベルが少なくとも2つの関連場所に割り当てられているかどうか判断することができる。
【００２４】
たとえば、いくつかの構成では、ラベルが異なるユーザによって割り当てられることが可能である。上記の例では、たとえば、第1のユーザが第1の関連場所に「モアハウスマーケット」とラベルを付けることがあり、第2のユーザ(第1のユーザと異なる)も、おそらく近くにある第2の関連場所に同様に「モアハウスマーケット」とラベルを付けることがある。これに加えて、またはこの代わりに、ユーザは、関連場所に適用されるラベルがパブリックであるかプライベートであるかを指定することが可能な場合がある。パブリックラベルは、たとえば、他のユーザによって見られることができ、および/または、本明細書で説明するように拡張された関連場所を発見する際にシステムによって使用することができる。一方、プライベートラベルは、たとえば、他のユーザによって見えなくてもよく、および/または拡張された関連場所を発見する際にシステムによって使用されなくてもよい。
【００２５】
ステップ103において、同じラベルが少なくとも2つの関連場所に割り当てられていないと判断された場合、方法は終了することができる。一方、ステップ103において、少なくとも2つの関連場所に同じラベルが割り当てられている(または類似のラベルが割り当てられている)と判断された場合、ステップ104では、1つまたは複数の距離メトリック(測定値間の相違を示す)に基づいて、たとえば、少なくとも2つの関連場所が隣接しているおよび/または連続しているかどうか判断することができる。1つまたは複数の態様によれば、2つの場所が互いから一定の距離の範囲内にある(たとえば、相違を示す距離が0と1との間にあるとき、距離が0.1未満である)ことを示すテストに合格する場合、これらの場所は隣接しているおよび/または連続していると考えることができる。これに加えて、またはこの代わりに、他の方法および/またはステップを使用して、少なくとも2つの関連場所が隣接しているおよび/または連続しているかどうか判断することができる。
【００２６】
したがって、上記で説明した例を継続すると、コンピューティングデバイスは、ステップ104で、1つまたは複数の距離メトリックに基づいて、少なくとも2つの関連場所、たとえばラベル(「モアハウスマーケット」)を有する少なくとも2つの関連場所が隣接している(たとえば、相違に関して、互いから一定の距離の範囲内にある)かどうか判断することができる。たとえば、コンピューティングデバイスは、上記で説明した位置データを使用して、たとえば、少なくとも2つの関連場所における測定値間の距離(相違を示す)を計算することができる。たとえば、いくつかの実施形態のコンピューティングデバイスは、ステップ104で、少なくとも2つの重心の比較に基づいて、対応する2つの場所が互いに類似しているかどうか判断することができる。
【００２７】
その後、ステップ104において、少なくとも2つの関連場所が隣接していないおよび/または連続していないと判断された場合、方法は終了することができる。一方、ステップ104において、少なくとも2つの関連場所が隣接しているおよび/または連続していると判断された場合、ステップ105では、少なくとも2つの関連場所は拡張された関連場所を定義すると判断することができる。たとえば、コンピューティングデバイスが、上記で説明した例の少なくとも2つの関連場所(たとえば、「モアハウスマーケット」というラベルが付けられた関連場所)が隣接しているおよび/または連続していると判断した場合、ステップ105では、コンピューティングデバイスは、少なくとも2つの関連場所は拡張された関連場所を定義すると判断することができる。したがって、そのような実施形態では、コンピューティングデバイスは、メモリ110に(たとえば、図4AのPOR場所モデル135のセットに)、少なくともこれらの2つの場所を含む拡張された関連場所を(たとえば、実施形態に応じて、リストまたはデータベースに)記憶する。
【００２８】
図1Bは、本開示の1つまたは複数の例示的態様による、概念的に示された例示的な拡張された関連場所を屋内地図上に示す。図1Bに見られるように、ある企業のオフィスビル201は、受付エリア202、廊下203、第1のオフィス204、第2のオフィス205、カフェテリア206、および階段吹抜け207などの様々な部屋、オフィス、空間、および/または他のエリアを含むことができる。1つまたは複数の態様によれば、これらの部屋、オフィス、空間、および/または他のエリアの各々は、まとめて1つの関連場所と考えることができるが、これらの部屋、オフィス、空間、および/または他のエリアは、本明細書で説明するコンピューティングデバイスによって、1つの拡張された関連場所と定義することができる。いくつかの実施形態では、コンピューティングデバイスは、主に測定値に基づいて、図1Bに示される種類の1つまたは複数の建物のレイアウトを使用することなく、拡張されたPORを定義する。しかしながら、他の実施形態では、相互に接続された1つまたは複数の建物のレイアウト、屋内地図、間取り図、および/または他の地理情報を、測定値と組み合わせて使用する。
【００２９】
いくつかの実施形態では、関連場所(POR)は、中心点の周囲で一定の距離の範囲内にある(および、追加の基準のセットを満たす)十分に多い数のWiFi測定値によって定義することができる。この時点で、新しい種類の関連場所である「パス」は、連続的な歩行区間によって得られると定義することができる。「歩行」は、(a)モーション分類機の出力、および/または(b)WiFi信号の測定値の連続的な変化、によって定義することができる。「連続的」は、(a)t_minよりも長い全体的な持続時間、(b)i_maxよりも長い中断がない、によって定義することができる。上記の定義から、信号レベルに関して、パスは、ある期間にわたって収集されるWiFi測定値(信号強度の値、および信号識別子)の系列であることを理解することができる。モーションと連動する場合、コンピュータシステム120はまた、ステップカウントおよび方向(たとえば、直接的な変化の系列)に関する情報を有することができる。
【００３０】
したがって、本明細書で説明する種類の数多くの方法は、軌跡を認識して区間に分ける。以下の説明では、パスについて説明し、(a)図1Aおよび図1Bを参照して上記で説明した場所方法の拡張とすることができる、(b)WiFiトレースのみで開始することができるが、モーションの分類、ステップカウント、方向情報、音紋などを容易に採用することができる、(c)正確な軌跡の記述ではなく、広く定義されたパス(たとえば、スーパーマーケット、商店街の特定の一部、またはカフェテリアにつながるホールなどの特定のエリア内での歩行)の再発生の認識の問題に重点を置くことができる、(d)計算の複雑性を低くして実施することができる、(e)パスの重複を異なる空間規模で考えることができる、方法に注目する。したがって、いくつかの適用例では、人物が特定の建物または大型スーパーマーケットの中を歩行していることを知ることに関心がある場合がある。したがって、同じ比較的広いエリア内にある2つのパスはマッチングと考えることができる。他の適用例では、特定の廊下に(たとえば、カフェテリアまたは会議室への進入路として)注目することがある。
【００３１】
図2Aは、本開示の1つまたは複数の例示的態様により1つまたは複数のパスベースの関連場所を発見するおよび/または自動的にサイズを調整する1つの例示的な方法を示す。1つまたは複数の態様によれば、図2Aに示される例示的な方法のうちのステップのいずれかおよび/またはすべては、1つまたは複数のコンピューティングデバイス(たとえば、コンピュータシステム120)内で実施されるおよび/またはこれによって実行されることが可能である。これに加えて、またはこの代わりに、図2Aに示される例示的な方法のステップのいずれかおよび/またはすべては、実行されると1つまたは複数のコンピューティングデバイスに例示的な方法を実行させることが可能なコンピュータ実行可能命令として、コンピュータ可読媒体内に記憶することができる。
【００３２】
ステップ221では、複数の位置値を受信することができる。たとえば、ステップ221では、コンピューティングデバイス(たとえば、コンピュータシステム120)が、複数の位置値を受信することができる。そのような位置値は、上記で説明した位置データに類似した位置データを含むおよび/またはそれからなることができる。たとえば、位置データには、1つまたは複数のWiFiトレース、モーションの分類、ステップカウント、方向情報、音紋、および/または他の位置データなどが含まれ得る。
【００３３】
ステップ222では、1つまたは複数の連続的な歩行区間を識別することができる。1つまたは複数の態様によれば、「歩行」とは、以下でさらに説明するように、モーション分類機の出力によって測定されるモーションおよび/またはWiFi測定値の連続的な変化を指すことができ、「連続的」とは、第1の閾値(たとえば、t_min)よりも長い全体的な持続時間を有する、および/または第2の閾値(たとえば、i_max)よりも長い中断のない、モーションを指すことができる。したがって、上記で説明した例を継続すると、コンピューティングデバイスは、たとえば、受信した複数の位置値に基づいて、1つまたは複数の連続的な歩行区間を識別することができる。
【００３４】
ステップ223では、測定値の重心の1つまたは複数のツリーを生成することができる。たとえば、ステップ223では、コンピューティングデバイスは、第1の識別された連続的な歩行区間上で得られた測定値に対する重心の第1のツリーと、第2の識別された連続的な歩行区間上で得られた測定値に対する重心の第2のツリーを生成することができる。1つまたは複数の構成では、重心の各ツリーは、複数のレベルを含むことができる。重心の1つまたは複数のツリーを生成する方法および/またはステップについては、以下でさらに説明する。これらに加えて、またはこれらの代わりに、重心の1つまたは複数のツリーを生成する際に、他の方法および/またはステップを使用することができる。
【００３５】
ステップ224では、生成した重心のツリーを比較して、1つまたは複数の識別された連続的な歩行区間が同じパスに一致するかどうか判断することができる。たとえば、ステップ224では、コンピューティングデバイスは、以下でさらに説明するように、パスマッチング(たとえば、生成した測定値の重心のツリーの対応するレベルを再帰的に比較することを必要とすることがある)を実行することができる。これに加えて、またはこの代わりに、コンピューティングデバイスは、以下でさらに説明するように、たとえば、類似性クラスタリング(たとえば、生成した重心のツリーの対応するレベルを個別にクラスタ化することを必要とすることがある)を実行することができる。
【００３６】
図2Bは、本開示の1つまたは複数の例示的態様による、概念的に示されたパスベースの関連場所を屋内地図上に示す。図2Bに見られるように、ショッピングモール241は、第1の店舗242、歩道243、第2の店舗244、第3の店舗245、レストラン246、および第4の店舗247など、様々な店舗、レストラン、歩道、および/または他のエリアを含むことができる。ショッピングモール241を歩き回るとき、異なる人間が異なるパスを通ることができる。たとえば、第1の人物がパス250(図2B)に沿って歩くことができ、第2の人物がパス251(図2B)に沿って歩くことができる。第1の人物の軌跡と第2の人物の軌跡はいくつかの点で異なることがあるが、第1の人物と第2の人物の両方はショッピングモール241を歩き回っている。したがって、ショッピングモール241は、歩行が行われる大まかに定義された領域と考えることができ、したがって、パス250およびパス251は、パスベースの関連場所を定義することができる。
【００３７】
いくつかの説明する実施形態では、ユーザが歩いている間、モバイルデバイス(スマートフォンなど)の形態的要素をとるコンピュータシステム120がユーザによって持ち歩かれる。したがって、コンピュータシステム120は、ユーザがエリアを通って歩くパスに沿って移動する。そのような移動中に、コンピュータシステム120は、動作301(図3A)において、ワイヤレスアクセスポイント(WAP)によって送信されたワイヤレス信号などの1つまたは複数の信号を測定し、動作302に進む。動作302では、コンピュータシステム120は、現在のWiFi測定値に関するタプル(たとえば、測定されている信号の識別子(情報源のアドレスなど)、特定のWAPのWiFi信号の強度)を記憶し、次いで動作303に進む。動作303では、コンピュータシステム120は、既知であり測定値に関して識別されたすべてのWiFi信号が測定されたかどうかチェックし、現在の測定値を形成する。この段階で、現在の測定値に対してすべての信号が測定されていない場合、動作301に戻ることによって、コンピュータシステム120は、追加測定値を得て、追加WAPのタプルを形成することができる。
【００３８】
現在の測定値のすべての信号が測定されているとき、コンピュータシステム120は動作304に進み、現在の測定値のすべてのタプルを出力し、さらに、たとえばコンピュータシステム120内でソフトウェア(アプリケーション、オペレーティングシステム、ドライバ、またはオペレーティングシステムより下位の専用ソフトウェアなど)が使用するために、またはコンピュータシステム120が結合されたサーバコンピュータ内のソフトウェアが使用するために、現在の時刻のタイムスタンプを出力する。動作304で出力される測定値の例が、図6Bおよび図6Cに、(たとえば、ユーザが、図6Bの間仕切りされた区画601から始まってオフィス600を通って休憩室602で終わるパス「A」に沿って歩いている間)図6Cに示されるように1分ごとに、たとえばそれぞれ午前9時00分、午前9時01分、および午前9時02分に、次々に連続して得られた測定値の時系列A1...I...ANとして示されている。
【００３９】
いくつかの実施形態では、コンピュータシステム120は、現在の測定値(またはWiFiトレース)に基づいて、ベクトル(「特徴ベクトル」とも呼ばれる)を作成するようにプログラムされる。そのようなベクトルの次元数は、測定されているWiFi信号の情報源の数に基づいて、コンピュータシステム120によって自動的に選択することができ、各信号の受信信号強度(RSSI)値は、ベクトル内の次元の値として使用される。そのような実施形態では、測定されるべきWiFi信号が検知されないとき、コンピュータシステム120は、ベクトル内の対応する要素を可能な最小のRSSI値(すなわち、RSSI値の範囲の最小値)に設定するようにプログラムすることができる。
【００４０】
いくつかの実施形態では、動作304における測定値の出力の後(および/またはベクトルの生成の後)、コンピュータシステム120は動作305に進む。動作305では、いくつかの実施形態のコンピュータシステム120は、次いで、(A)測定された信号の変化、または(B)所定の期間(たとえば、1分に1回)、または(C)これらの2つの条件(A)と(B)の組合せを待つ。動作305における条件(A)のいくつかの例では、コンピュータシステム120は、類似度関数を実行して、類似性尺度または相違の距離を取得し、測定値に基づいて(上記で説明したように)形成されたベクトルを比較し、変化があるかどうか判断することができる。
【００４１】
図6Cに示される例では、ワイヤレス信号の測定値は定期的に、たとえば1分ごとに1回得られるが、容易に明らかであるように、そのような測定値は、15秒ごと、または5分ごとなどの他の時間間隔で得られてもよく、そのような時間間隔は、いくつかの実施形態では、たとえば測定値を得るときにコンピュータシステム120が利用可能なバッテリ電力に基づいて変化することができる。いくつかの実施形態では、複数の測定値間で変化が検出されないとき、動作305では、(図6Cに示されるように)複数の測定値を使用して、重心を取得することができ、この重心は、本明細書で説明するように場所を識別する際に使用することができる。
【００４２】
測定値間で変化が検出されるとき、コンピュータシステム120は、たとえば類似性に関する閾値(たとえば図4B参照)を使用して変化が著しいかどうか評価し、変化が著しい場合、コンピュータシステム120は(上記で説明した)動作301に戻る。図4Bに示される種類の閾値は、いくつかの適用例では、あらかじめ定義することができる(たとえば、実験データに基づいて設定することができる定数)。他の実施形態では、図4Bの閾値は動的とすることができ(たとえば、最良の結果を取得するために最適化に基づいて導出される)、したがって、閾値はコンピュータシステム120内のアプリケーションによって異なってよい。たとえば、コンピュータシステム120のいくつかの実施形態では、信号/測定値のノイズ(たとえば、経時的なノイズ)が低い(たとえば、別の定数を下回る)とき、信号の変化を検出するために使用される、類似性に関する動的な閾値(たとえば図4B参照)は、最適化方法を使用して緩和することができる。動的な閾値の使用には、計算および/または測定値を必要とすることがあり、これはコンピュータシステム120のバッテリを消耗させるという欠点を有する。
【００４３】
いくつかの実施形態では、ある地点(「中心点」)の周囲で類似しており、さらに、類似のラベルおよび/または時系列内での発生などの追加基準のセットを満たす十分に大きい数の測定値を見つけるに際して、関連場所がプロセッサ100によって識別される。いくつかの実施形態では、ワイヤレスアクセスポイント(WAPS)の受信信号強度(RSSI)の測定値を使用して、以下の意味で類似性値を決定する。すなわち、測定値のセットを仮定して、これらの測定値がどのくらい互いに類似しているか、である。類似性は現実世界における非線形空間の全域で(たとえば、建物の中の1つまたは複数の壁の全域で)定義可能であるので、上記で説明した類似性値は、現実世界における物理的距離よりも汎用的であることに留意されたい。
【００４４】
前述のように、いくつかの実施形態では、WiFi信号の測定値を使用して、n個の要素のベクトルを作成し、各要素(「次元」とも呼ばれる)は(たとえば、図6Cに示されるように)WiFi信号のRSSIを表し、次いで、これらのベクトルを、たとえば類似度関数を使用して比較する。いくつかの実施形態でそのようなベクトルに含まれ得る追加基準の一例は、WiFi信号の情報源すなわちワイヤレスアクセスポイント(WAP)の応答率、たとえば、すべてのWAPが互いに類似した応答信頼性で応答するかどうか、に基づく。したがって、これに加えて、またはこの代わりに、いくつかの実施形態では、以下で説明するように、パスの区間(「歩行区間」と呼ばれる)内で、ユーザが止まらずに歩くとき得られる測定値に基づく、「パス」PORと呼ばれる新しい種類の関連場所(POR)を使用する。
【００４５】
図3Aを参照すると、説明した動作304における現在の測定値の出力が、プロセッサ100によって実行される動作311で受信される。したがって、プロセッサ100のいくつかの実施形態は、ユーザのパス内の連続的な歩行区間に対応する一連の連続的に変化する信号の測定値を関連場所(POR)のモデルとして使用する機構を実施する。いくつかの実施形態のプロセッサ100のうち1つまたは複数は、コンピュータシステム120内に含めることができ、実施形態によっては、いくつかのプロセッサ100は、コンピュータシステム120が結合されるサーバコンピュータ内に含めることができる。
【００４６】
図3Aに示される種類のいくつかの実施形態では、動作304における出力は1つのソフトウェア(すなわち「アプリケーション」)の実行によって行われ、動作311における受信は別のソフトウェアの実行によって行われ、これらのソフトウェアの両方は単一のプロセッサ100によって実行されるが、前述のように、他の実施形態では、そのようなソフトウェアは異なるプロセッサ100によって実行されてよい。動作311で現在の測定値を受信すると、プロセッサ100は、特定のあらかじめ定義された条件が満たされるかどうかチェックし、条件が満たされることは、コンピュータシステム120を持ち歩くユーザが実際にパスに沿って歩いていることを示す。
【００４７】
チェックされるあらかじめ定義された条件は実施形態に応じて異なってよいが、いくつかの実施形態では、図3Bに示されるように、時間的に連続して次々に得られる測定値の類似性についてチェックする。具体的には、図3Bは、縦のY軸が連続するWiFi測定値の類似性を表し、水平のX軸が時間を表すグラフを示す。図3Bでは、時間間隔306A中に時間的に連続して得られた測定値のグループは、互いに対して、時間間隔307A内の測定値などの他の測定値に対して、高い類似性を有する。したがって、そのような実施形態では、連続する測定値間の高い類似性に基づいて、時間間隔306A中にユーザが単一の場所にいる(その中を動き回っているが)という判断が、コンピュータシステム120によって行われる。他の時間間隔307A、307B、307C、および307D(図3B参照)では、コンピュータシステム120は、連続する測定値間の類似性が低すぎることに基づいて、ユーザが場所間を移動していると判断する。したがって、いくつかの実施形態では、本明細書で説明するように、関連場所(POR)を自動的に発見するまたは認識する際に、各測定値が得られた時刻がコンピュータシステム120によって使用される。
【００４８】
図3Bでは、4つの時間間隔306A、306B、306C、および306Dが示されており、これらの時間間隔は、(空間に関する)高い類似性を持つ測定値を有する。したがって、これらの4つの時間間隔306A〜306Dは、コンピュータシステム120によって、ユーザによる4つの訪問と表される。たとえば、時間間隔306A中の第1の訪問において互いに対して時間的に順次得られる測定値の第1のサブセットは、ユーザの自宅においてであってよく、時間間隔306B中の第2の訪問において互いに対して時間的に順次得られる測定値の第2のサブセットは、自宅から職場に行く途中のコーヒーショップにおいてであってよく、時間間隔306C中の第3の訪問において互いに対して時間的に順次得られる測定値の第3のサブセットは、ユーザのオフィスにおいてであってよく、時間間隔306D中の第4の訪問において互いに対して時間的に順次得られる測定値の第4のサブセットは、レストランにおいてであってよい。
【００４９】
前の段落で説明した種類の各訪問は、いくつかの実施形態のコンピュータシステム120のメモリ110(図4A)において、訪問場所モデル(VPM)としてモデル化される。いくつかの実施形態では、訪問場所モデルを構築すると、ノイズが減少する。したがって、コンピュータシステム120のいくつかの実施形態では、クラスタ化され、それによってノイズを減少させるのは、これらの訪問場所モデル(VPM)である(他の実施形態では、WiFi測定値自体をクラスタ化することがあるが)。訪問場所モデルの使用は、いくつかの実施形態では、PORの抽出中に影響を受け、コンピュータシステム120が、たとえば互いに隣接する2つのオフィスを区別することを可能にする。したがって、本明細書で説明する訪問場所モデルの使用により、2つのステップ、すなわちVPMの構築という第1のステップと、このVPMに対する類似性クラスタリングという第2のステップからなるプロセスの優れた性能が実現される。
【００５０】
図3Cを参照すると、プロセッサ100のいくつかの実施形態は、現在の測定値と前の測定値との間の時間差がi_maxよりも大きいどうかを(動作312に従って)チェックするようにプログラムされ、この時間差がi_maxよりも大きくない場合、動作319に進んで現在のパスに現在の測定値を記憶し、次いで動作311に戻る。動作312での答えがyesの場合、プロセッサ100は動作313に進み、現在のパスの全体的な持続時間がt_minよりも長いかどうかチェックし、t_minよりも長くない場合は、現在のパスをヌルに再初期化するだけの動作318に進み、動作311に戻る。動作313は、いくつかの実施形態では、ユーザの歩行が無視できるほど小さく、解析する価値がないときに、(以下で説明する動作314における)識別が実行されないように実行される。
【００５１】
したがって、いくつかの実施形態では、測定値のサブセットの時系列内の第1の測定値と最後の測定値との間で測定されるユーザの歩行区間の全体的な持続時間がt_minよりも長く続くこと、および何らかの2つの連続的に得られた測定値間にi_maxよりも長い中断がないことに基づいて、ユーザが歩いていると判断する。前述のように、上記で説明した条件は、いくつかの実施形態では、図3Cの動作312および313によって示されるように、現在の測定値を受信するプロセッサ100によってチェックされる。
【００５２】
動作313での答えがyesであるとき、プロセッサ100は動作314を実行して、たとえばユーザが歩いている可能性があるパスの区間に沿って測定される、互いに対して時間的に順次発生する測定値のサブセット(またはグループ)を識別し、それによって、連続的な歩行区間を識別する。サブセット内の測定値は、少なくとも、サブセット内に含まれるすべての測定値の類似性の尺度の値に関するテストに合格するために、動作314において識別される。プロセッサ100のいくつかの実施形態では、各測定値AI(図6C)および(パスAに関するA1...AI...ANの時系列の測定値の)重心C1Aに対する類似度関数180の実行によって取得される値を類似性の尺度(または類似性属性)として使用し、測定値A1...AI...ANを、サブセットを形成すると識別することができる。
【００５３】
具体的には、いくつかの実施形態では、各測定値AIの、重心C1Aに対する類似性の尺度の値は所定の閾値(最小類似性)に対してテストされ、各測定値AIは、テストに合格したときにのみサブセット内に含まれる。類似度関数180(図4A)の例は、Tanimoto、Dice、Jaccardなどである。いくつかの実施形態では、相違を示す距離メトリックを使用し、この距離は次のように1-類似性として取得される。したがって、本明細書で説明する種類のいくつかの方法では、重心を有する場所の識別は、測定値、たとえば図4Cに示され以下で説明するように互いに対して時間的に順次得られる測定値の時刻に基づいて特定の測定値のみをサブセット内に含むことに基づいて実行される。
【００５４】
次いで、動作314に従って識別された測定値のサブセットを非一時的なメモリ110に動作315で記憶し、すべてのサブセットが識別されたかどうかチェックする動作316が続き、すべてのサブセットが識別されていない場合、制御は(上記で説明した)動作312に戻る。類似性の尺度の値に関するテストに合格するすべてのサブセットが識別されるとき、動作316での答えはyesであり、このサブセットを使用する制御は動作317に移る。いくつかの実施形態では、動作317において、動作314から生じた測定値の各サブセットを、追加測定値のサブセットと(たとえば、図5Aおよび図5Dに示されるクラスタリングによって)比較し、新しい関連場所を識別する。いくつかの実施形態では、動作317において、動作314から生じた測定値の各サブセットを、(たとえば、図5Eに示される)あらかじめ計算した測定値のモデルと比較し、既知の関連場所を識別する。いくつかの実施形態では、動作317において、動作314から生じた測定値の各サブセットを、追加パスで得られた追加測定値と比較し、たとえば、2つのパスが互いに交差する場所を識別する。したがって、(たとえば、パスベースの関連場所を識別するための)動作317における測定値のサブセットの具体的な使用法は実施形態によって決まり、そのような使用の後、制御は(上記で説明した)動作318に移る。
【００５５】
動作314において測定値のサブセットを識別する際に、プロセッサ100のいくつかの実施形態では、パスのモデルを構築する最小の規模として最小半径dminを使用する。いくつかの実施形態では、動作314は、パスに沿って測定され互いに類似している測定値のセットから始まり、そのセットを反復して(および、いくつかの実施形態では、再帰的に)サブセットに細分し、ついには、隣接するサブセット内の測定値がdmin未満によって分離されるとき、細分が停止する段階に到達する。他の実施形態では、各新しい測定値を受信すると、動作314が反復して呼び出され、さらに、(上記で説明した)動作314に従って類似性テストに合格するために識別された、メモリ110に現在記憶されている測定値のサブセットに新しい測定値を追加するべきかどうか判断する。
【００５６】
動作314において識別された測定値のサブセットは、経時的に収集されるWiFiトレースの系列を構成する。プロセッサ100のいくつかの実施形態におけるサブセットの収集の期間は、所定の閾値t_minよりも大きいように設計される。実施形態によっては、WiFiトレースの代わりに、またはこれに加えて、コンピュータシステム120は、内蔵モーションセンサを使用して、ステップカウントおよび方向(方向変化の系列)に関する情報を取得することができる。したがって、いくつかの実施形態では、ユーザのパスに沿って得られた特定の測定値(WiFiトレースなど)を認識し、区間化するが、他の実施形態では、モーションの分類、ステップカウント、方向情報、音紋などの他の測定法を採用する。
【００５７】
いくつかの実施形態では、ソフトウェアを実行して(上記で説明した)動作312を実行する1つまたは複数のプロセッサ100は、パスに沿って互いに対して順次発生する測定値のサブセットをパスの中で移動しながらモバイルデバイスによって得られた測定値のセットの中から反復して識別するための手段を構成し、サブセット内の測定値は、少なくとも、サブセットに含まれるすべての測定値の類似性の尺度の値に関するテストに合格するために識別される。その上、そのような実施形態では、ソフトウェアを実行して(上記で説明した)動作315を実行する1つまたは複数のプロセッサ100は、少なくとも反復して識別するための手段によって識別された各サブセットを非一時的なメモリに記憶するための手段を構成する。
【００５８】
本明細書で説明するタイプのいくつかの実施形態では、動作314において識別された測定値のサブセットは、関連場所(POR)へのユーザの訪問を識別するためにコンピュータシステム120によって使用される。場所は物理的ロケーションを表し、現実世界の空間内の拡張(たとえば、円または正方形として)は、ある建物内の部屋、たとえばオフィス(図1B)の事務室204、または自宅の居間、または店舗244(図2B)の区画、の寸法の建物の部屋、を有する。そのような場所を、(たとえばWiFiトレースの)1つまたは複数の測定値を使用してコンピュータシステム120によって識別して、ユーザが同じ場所にいるかどうか判断することができる。
【００５９】
いくつかの実施形態のコンピュータシステム120は、測定値が互いと十分に類似しているとき、たとえば(Tanimotoなど類似度関数180を実行することによって取得される)距離メトリックが、測定値間の相違に関するテストに合格したこと、たとえば0.1未満の距離(または0.9よりも大きい類似性)を示すとき、何らかの種類の地図またはレイアウトまたは他の地理情報を使用せずにユーザが同じ場所にいると判断する。コンピュータシステム120は、次いで、重心(たとえば重心C1A)を計算することによって、類似した測定値(たとえば、図6Cの測定値A1...AI...AN)を集約することができる。図6Aに示される例示的な例では、単一の場所は、各WAPに対して、複数の測定値の信号強度を平均することによって(この算術平均を取ることによって)取得される重心C1Aを有すると識別される。
【００６０】
前述のように、本明細書で説明する種類のいくつかの実施形態では、地図またはレイアウトまたは間取り図または何らかの他のそのような地理情報を使用せずに、特定の場所をコンピュータメモリ内で識別する。この特定の場所は、これらの実施形態では、測定値間の距離を(測定空間とも呼ばれる、測定値のみが定義される空間における相違メトリックとして)取得するために、類似度関数を使用したワイヤレス信号(および/または、その重心)の測定値の比較によってのみ識別される。例示的な例では、測定されるワイヤレス信号は、鉄道の駅で通常聞こえる音(たとえば、電車が鳴らす警笛)などの音である。上記で説明した例では、(音の空間における)測定空間内の場所を鉄道の駅と自動的に識別する、および/または(音の空間における)2つの場所を類似していると判断するいくつかの実施形態では、鉄道の駅についての地理情報(地図、レイアウト、または間取り図など)は使用されない。上記で説明した例のいくつかの実施形態では、(音空間において識別された)そのような場所をリストに記憶し、類似度関数を使用して音響測定値(異なる周波数における音声信号の強度のベクトル)を比較することによって、拡張された場所を鉄道の駅と定義する。代替実施形態では、そのようなワイヤレス信号測定値と組み合わせて(たとえば、都市の街路のレベルにおける)屋外地図ならびに/または屋内地図(またはレイアウト)ならびに/または何らかの他の地理情報および/もしくは位置(たとえばGPSからの緯度および経度)を使用して、現実世界では異なる物理的ロケーションに存在する、たとえば廊下またはトイレからユーザのオフィスを分離する壁の両側にある、場所を識別する。
【００６１】
いくつかの実施形態における訪問は、ユーザが連続的に同じ場所にいる(すなわち、重心から(測定値の相違を示す)所定の距離内にいる)時間の間隔と定義されるが、ユーザは、静止していなくてもよく、代わりに、同じ場所と識別される空間の中を歩き回っていることがある。したがって、いくつかの実施形態では、関連場所(POR)は、ユーザが少なくともTminVisit回(たとえば2回)訪問し、それらのTminVisitの訪問の各々が時間TminVTime(たとえば5分)の最小持続時間を超えた場所(たとえば測定値の重心および測定値間の相違の距離)であると定義される。
【００６２】
実施形態によっては、場所がコンピュータシステム120によってPORと分類される前に、ユーザがTminVisit回よりも多く場所を訪問しなければならないことがある。これは、訪問の1つまたは複数が時間TminVTimeの最小持続時間を超えない場合に当てはまる。両方の閾値は、使用するケース(use case)に応じて調整可能である。いくつかの実施形態では、再訪問は、コンピュータシステム120によって、既知のPOR(たとえば、以前に訪問した場所)へのユーザによる訪問であると判断される。いくつかの実施形態における再訪問の定義は、再訪問を構成するために、ユーザの訪問が何らかの最小持続時間行われることを必要としない(そのような実施形態では、最小持続時間は、最初にユーザの訪問を自動的に発見するために必要とされるとしても)ことに留意されたい。
【００６３】
本明細書で説明する種類のいくつかの実施形態では、メモリ110(図4A)内でコンピュータシステム120によって作成される場所モデルは、場所の特定の所定の特性をとらえる。具体的には、1つまたは複数の特性(たとえば重心)は、場所を識別するために使用されるWiFi測定値からコンピュータシステム120のいくつかの実施形態によって抽出され、その後、これらの特性を使用して、ユーザによる再訪問中にその同じ場所を認識する。コンピュータシステム120のいくつかの実施形態では、次のような3つの種類の場所、すなわち、関連場所(POR場所モデル)、以前に訪問された場所(訪問場所モデル)、および複数の測定値を使用して識別された場所(即時(instantaneous)場所モデル)をモデル化する。具体的には、いくつかのそのような実施形態では、POR場所モデル(PPM)は、PORを特徴づけるためにコンピュータシステム120によって使用される。いくつかの実施形態では、訪問場所モデル(VPM)は、ユーザの訪問を特徴づけるためにコンピュータシステム120によって使用される。即時場所モデル(IPM)は、コンピュータシステム120のいくつかの実施形態では、即座に収集されたWiFi測定値から導出され、ユーザの現在のロケーションの特性をとらえる。しかしながら、技術的観点から、これらの3つの場所モデルは、場所がなぜどのようにコンピュータシステム120によってモデル化されているかという点で類似している。
【００６４】
いくつかの実施形態では、コンピュータシステム120内のプロセッサ100は、所定のソフトウェアを実行して、コンピュータシステム120内の発見システム130(図4A)を実施し、WiFi測定値などの未加工のセンサデータのストリームを分析するだけで新しい場所を監視されずに識別する。多数の実施形態の発見システム130は、屋内地図、またはレイアウト、または間取り図上での場所の地理ロケーションまたは場所の空間的拡張のサイズに関する既存の知識を使用しない。その上、いくつかの実施形態では、そのような未加工のセンサデータは、区間に分けられず、発見システム130への入力に対して注釈が付けられず、場所および訪問に関するグランドトルース(ground truth)(たとえば地図データ)は発見システム130では利用できない。そのような実施形態の発見システム130は、大部分は、フィルタ139(図4A)によって誤差を除去するようにフィルタリングすることができる未加工のセンサデータに対して動作する。いくつかの実施形態の発見システム130の出力は、関連付けられたPOR場所モデルを有する関連場所のセットである。次いで、これらのPOR場所モデルは、認識システム150(図4A参照)によって入力として使用される。
【００６５】
いくつかの実施形態では、発見システム130(図4A)は、次のように2つのステップからなるプロセスを実行するモジュール131と132とを含む。プロセスの第1のステップでは、発見システム130のモジュール131は、訪問場所モデルを含む時間TminVTimeの最小持続時間を持つすべての訪問を抽出する。プロセスの第2のステップでは、発見システム130(図4A)のモジュール132は、以前に抽出された訪問場所モデルをクラスタ化することによってPORを抽出する。クラスタを別のモジュール133によって分析し、TminVisitよりも多い訪問場所モデルを含む各クラスタ(それぞれの訪問)には、POR、たとえば上記で説明したように拡張されたPORまたはパスベースのPORとラベルが付けられる。このようにして、発見システム130は、POR場所モデル135(図4A)のセットを生成する。いくつかの実施形態では、発見システム130は、本明細書で説明するPORの定義に基づいて、訪問の持続時間およびクラスタ内の訪問場所モデルの数に関する制約を実施する。POR場所モデル135のセットは、一般的には、発見システム130によって受信される測定値が多くなるにつれて経時的に成長し、より多くの場所がPORとして発見されることになる。
【００６６】
発見システム130(図4A)によるクラスタリングの実装形態を、説明した2つのステップに分割することによって、いくつかの利点が得られる。2つのステップからなるクラスタリングプロセスの第1のステップは、時間的クラスタリングに基づいており、訪問ならびに対応する訪問場所モデル(VPM)を抽出する。2つのステップからなるプロセスの第2のステップは、第1のステップから受信した訪問場所モデル(VPM)を類似性に基づいてクラスタ化し、関連場所(POR)を判断する。2つのステップからなるクラスタリングプロセスは、誤差を生成し得る未加工のWiFi測定値に対して類似性クラスタリングを直接行うことができる単一のステップからなるプロセスに対する改善と考えられる。2つの隣接するオフィスを訪問する一例では、未加工の測定値(たとえばWiFiトレース)は、両方のオフィスの領域全体にわたって均等に分散される。この例では、単一のステップからなるクラスタリングプロセスは、2つのオフィスからの測定値を1つのクラスタにマージし、(両方のオフィスを合わせた)1つの場所を識別することができる。この誤差は、空間的な特徴、たとえばロケーション特徴(緯度および経度)のみに基づいて、単一ステップでクラスタリングを実行することから生じる。
【００６７】
しかしながら、発見システム130(図4A)による上記で説明した2つのステップからなるクラスタリングプロセスは、第1のステップにおいてVPMを識別する時間的クラスタリング、続いて第2のステップにおいてPORを識別する類似性クラスタリングを持ち、WiFi測定値から抽出される特定の追加情報を使用する。具体的には、発見システム130(図4A)は、各WiFi測定値の収集の時刻を、時間的クラスタリングの第1のステップにおける追加情報として使用する。したがって、いくつかの実施形態の発見システム130は、空間と時間の両方において類似した2つのWiFi測定値を、単一の訪問中に収集されているとして第1のステップで処理し、次いで、これらの2つのWiFi測定値を一緒にクラスタ化するだけで、単一のVPMを生成する。次いで、クラスタリングの第2のステップで複数のVPMを互いに比較し、この複数のVPMが異なる(たとえば、2つの隣接するオフィスが別個のPORであると発見された)場合はマージしない。
【００６８】
いくつかの実施形態の発見システム130は、以下の3つの特徴のうち1つまたは複数を実施する。第1に、場所pは、コンピュータシステム120のいくつかの実施形態では、場所pによって表される現実世界で入手されるデータポイント(またはWiFi測定値)に含まれる特性情報を得る場所モデルpmpによって識別される。第2に、場所モデルpmpは、いくつかの実施形態では、コンピュータシステム120内に構築され、未加工のデータポイント(またはWiFi測定値)に基づいて更新される。第3に、類似度関数fsim(pmp1,pmp2)は、いくつかの実施形態のコンピュータシステム120において、2つの場所モデルの類似性を評価するために使用される。これらの3つの特徴を使用することによって、いくつかの実施形態の発見システム130は、以下で説明するように、拡張されたPOR、パスベースのPORを発見し、また、再訪問も認識する。
【００６９】
いくつかの実施形態では、発見システム130(図4A)は、図4Bに示される種類の1つまたは複数の閾値を使用する。具体的には、発見システム130は、パラメータを2つの部分、すなわち場所発見パラメータおよび場所認識パラメータに分類する。これらのパラメータのいくつかは、関連場所(POR)をモデル化するために発見システム130によって使用される。より具体的には、関連場所の発見は、発見システム130によって2つのステップに分解される。すなわち、第1のステップは、訪問および対応する訪問場所モデル(VPM)を抽出し、第2のステップは、訪問場所モデル(VPM)をクラスタ化し、PORおよび対応するPOR場所モデルを抽出する。これらの2つのステップについて、以下で図4Cに示される例を参照して説明する。
【００７０】
図4Cの例では、ユーザは、次のようなグランドトルースラベル、すなわち、自宅410、通勤420、職場430、通勤440、次いで自宅450に戻る、によって示される系列をたどる。理想的には、発見システム130は、訪問抽出という第1のステップの一部として3つの訪問(たとえば自宅410、職場430、および自宅450)を、POR抽出という第2のステップの一部として2つのPOR(たとえば自宅410、450、および職場430)を抽出する。この例では、いくつかのWiFi測定値411、412、413、414、415、416、417、418、421、422、423、424、431、432、433、434、441、442、451、452、453、454、455、456が、その中で測定値タイムスタンプによって識別されるように、通信サブシステム122(図4A)から時間的順序で発見システム130によって受信される。
【００７１】
発見システム130は、これらの測定値をいくつかのレベル460、470、480、および490(図4C)で処理する。具体的には、測定値411〜414は、これらのノードが時間的に順次発生し、(測定値が互いに類似しているので)すべてが同じ場所に属するので、時間的クラスタリングの1つのレベル460に伝搬され、ノード461にマージされる。次いで、ノード461が、クラスタをマージするより高いレベル470にノード471Aとして伝播される。同様に、レベル470におけるノード471Aおよび471が(重心が互いに類似しているので)マージされ、持続時間ベースのフィルタリングというさらにより高いレベル480にノード481として伝搬される。レベル480におけるノード481、486、および489は、十分な持続時間があり(たとえば、5秒よりも長い)、したがって、類似性クラスタリングというさらにより高いレベル490に、それぞれノード491、496、および499として伝搬される。ノード491および499は(たとえば同じラベル「自宅」を有することに基づいて)マージされ、ノード401を形成し、次いで(都市内のツリーの規模で地図を使用するいくつかの実施形態では)ノード401を屋外地図上で識別することができるが、ノード496は(たとえば異なるラベル「職場」を有することに基づいて)マージされず、その屋外地図上のノード402になる。したがって、この段階では、2つのノード401および402が関連場所と識別されている(少数の実施形態では、屋外地図たとえば街路レベルの地図にマッピングされる)。ノードが伝搬されマージされる様式は実施形態によって決まり、いくつかのそのような実施形態について以下で説明する。図4Cでは、ノードのサイズは、ノードによって表されるデータポイント(またはWiFi測定値)の数を示す。図4Cのノード間の矢印はデータの流れを示す。
【００７２】
いくつかの実施形態の発見システム130は、時間的クラスタリングモジュール131をクラスタマージモジュール132および持続時間フィルタリングモジュール133(図4A)と組み合わせて使用して、即時場所モデルから訪問場所モデルを抽出する。具体的には、図5Aの擬似コードによって示されるように、時間的クラスタリングモジュール131は、データポイント(またはWiFi測定値)から訪問を抽出する。時間的クラスタリングモジュール131は、一次元空間における時間のすべてのデータポイントを表す。このクラスタリング技法は、多次元データが一次元空間(テーブル)に表されるデータベースインデックス理論で使用されるクラスタリング技法である線形クラスタリングに基づく。この一般的なアイデアは、発見システム130によって適用され、時間次元に沿ってクラスタリングを実行する。
【００７３】
いくつかの実施形態の発見システム130は、以下の制約、すなわち、2つのデータポイント(またはWiFi測定値)は、十分な類似性(類似度関数および類似性閾値TtempClustに関して)を共有する場合およびその場合のみ、かつこの2つのデータポイント間にあるデータポイントのすべて(時間に関して)もこの同じノードに割り当てられる場合、同じノードにクラスタ化されるように、モジュール131で時間的クラスタリングを実行する。その結果、いくつかの実施形態では、ノードは、間隔の持続時間にわたるデータポイントの少なくとも大部分(すなわち>50%)が少なくともある程度の類似性(異なるデータポイントがフィルタ除去される、または除外される)を共有する時間の間隔を表す。したがって、この領域では、各時間間隔は訪問を構成する。
【００７４】
図4Cのレベル460は、時間的クラスタリングモジュール131の動作を示す。具体的には、データポイント(またはWiFi測定値)は、レベル460の現在のノードに類似しているかどうかに関して時間順序で評価される。たとえば、図4Cでは、初期測定値411のデータはレベル460に伝搬されて、新しいノード461Aを形成し、次いで次のデータポイント412がノード461Aへの類似性についてチェックされる。図4Cを参照して以下で説明するように、データポイントが(閾値TtempClustに関して)十分に類似していることがわかると、ノードとデータポイントがクラスタ化され、他の場合は新しいノードが開始される。
【００７５】
具体的には、図4Cに示されるように、レベル460の第1のノード461Aは第2のデータポイント412に類似していることがわかり、したがって第1のノード461Aと第2のデータポイント412がクラスタ化されてノード461Bを形成し、ノード461Bは第1のノード461Aおよび第2のデータポイント412より大きく示され、ノード461Bは現時点で2つの測定値を表していることを示す。次いで、ノード461Bの重心(たとえば2つの測定値のWiFiトレースのベクトル平均)を第3のデータポイント413と比較すると、類似している(たとえば、互いから相違の所定の距離の範囲内にある)ことがわかり、そのため、ノード461Bと第3のデータポイント413がクラスタ化されてノード461Cを形成する。次いで、ノード461Cの重心を第4のデータポイント414と比較すると、類似していることがわかり、したがって、ノード461Cと第4のデータポイント414がクラスタ化されてノード461を形成する。次に、同様に、ノード461の重心を第5のデータポイント415と比較すると、異なることがわかり、そのため、ノード461と第5のデータポイント415はクラスタ化されない。代わりに、第2のノード462が第5のデータポイント415に基づいてレベル460で開始される。
【００７６】
ノード461A〜461Cは、(3つの時間的により早い時点における)同じノード461の3つのバージョンであり、したがって、この段階では、レベル460に2つのノード461および462がある。次に、ノード462を第6のデータポイント416と比較すると、異なることがわかり、そのため、ノード462と第6のデータポイント416はクラスタ化されない。代わりに、第3のノード463Aが、第6のデータポイント416に基づいてレベル460で開始される。次に、ノード463Aを第7のデータポイント417と比較すると、類似していることがわかり、したがって、ノード463Aと第7のデータポイント417がクラスタ化されてノード463Bを形成する。次いで、ノード463Bの重心を第8のデータポイント418と比較すると、類似していることがわかり、したがって、ノード463Bと第8のデータポイント418とがクラスタ化されてノード463を形成する。次に、ノード463の重心を第9のデータポイント421と比較すると、異なることがわかり、そのため、ノード463と第9のデータポイント421はクラスタ化されない。代わりに、第4のノード464が第9のデータポイント421に基づいてレベル460で開始される。
【００７７】
したがって、時間的クラスタリングモジュール131(図4A)が上記で説明した様式でWiFi測定値411〜418、421〜424、431〜434、441〜442、451〜456を処理すると、レベル460はメモリ110に合計11のノードを有する。したがって、時間的クラスタリングにより、レベル460における11のノードは、11の訪問を示す(それらのうちのいくつかは、通勤中に得られた測定値を表すノード464など、ごく短時間の訪問とすることができる)。図4Cの例では、これらの11のノードは、クラスタマージモジュール132によって処理され、クラスタマージモジュール132は、連続するデータポイントに対する相違により訪問を潜在的に分割し得る外れ値を除外する。具体的には、WiFi測定値の外れ値によって提示される問題は、外れ値があることによって、時間的クラスタリングモジュール131が訪問に人工的な分割を導入するということである。これは、外れ値が直接の隣接要素(neighbor)(時間の次元における隣接要素)と十分な類似性を共有しないことが原因である。
【００７８】
たとえば、図4Cは、そのすべてが自宅410で得られるWiFi測定値411〜418がレベル460で3つのノード461、462、および463にクラスタ化されていることを示し、ノード461、462、および463は3つの訪問を表すが、ユーザはたった1つの場所(自宅410)にいる。これは、ノード471の重心と第5のデータポイント415との間の相違が原因である。第5のデータポイント415は(グランドトルースに従って)自宅410で収集されたので、第5のデータポイント415は、外れ値として適切に識別されるべきであった。しかしながら、この外れ値415は、グランドトルースを知ることなく発見システム130によって除去される必要があり、これは、図5Bの擬似コードによって示されるように、クラスタマージモジュール132によって実施される。
【００７９】
いくつかの実施形態では、クラスタマージモジュール132は、類似性が閾値TmergeSimよりも小さく、(訪問を表す)レベル460の何らかの2つのノードの間の時間ギャップが閾値TmergeTimeよりも小さい場合かつその場合のみ、これらのノードを結合する。その結果、外れ値により以前に分割された訪問は、単一の訪問に融合する。図4Cに示される例では、クラスタマージモジュール132は、最初にノード461をレベル470に伝搬させてノード471Aを形成し、次いで、このノード471の重心をレベル460でノード462の重心と比較する。ノード461と462があまりにも異なり、そのためにノード462が最初に時間的クラスタリングモジュール131によって開始され、これを行うとき、自宅410における訪問を分割することを想起されたい。
【００８０】
一致がないことがわかると、この段階では、クラスタマージモジュール132は、レベル460でノード471Aの重心を第3のノード463の重心と比較する。この例は、レベル460でのノード461および463が空間内で類似していることがわかり(基礎となる測定値411〜414、416〜418が同じ場所すなわち自宅で得られたので、ノード461と463は類似している)、また、互いに時間的に近いこともわかるので(これらの測定値411〜414、416〜418はすべて同じ場所への単一の訪問で得られたので)、クラスタマージモジュール132が一致を見つける。したがって、一致を見つけたことを受けて、クラスタマージモジュール132は、レベル460の第3のノード463をノード471Aとマージして、レベル470のノード471を取得する。ノード471は測定値415からの寄与を含まず、したがって、発見システム130によって外れ値として効果的にフィルタ除去されることに留意されたい。
【００８１】
次に、ノード471の重心をノード464と比較すると、異なることがわかり、そのため、ノード471とノード464はクラスタ化されない。代わりに、クラスタマージモジュール132が、ノード464のデータを伝搬させてレベル470でノード472を形成する。次いで、ノード472を、レベル460のノード464の後ろのノード(ラベルは付けられていない)と比較すると、一致が見つからず、そのため、クラスタマージモジュール132はデータを伝搬させて、レベル470でノード473を形成する。このようにして、追加ノード474、475、476、477、478、479がレベル470で形成される。したがって、クラスタマージモジュール132(図4A)がレベル460の11のノードの処理を完了すると、図4Cに示されるように、合計9つのノード471〜479がレベル470に存在し、次いで、これらの9つのノードがレベル480に伝搬される。
【００８２】
いくつかの実施形態の発見システム130は、持続時間として指定された閾値を適用して、あまりにも短時間であるまたは別の点で関連場所と識別するのに適格でない訪問を除外する持続時間フィルタリングモジュール133を含む。持続時間フィルタリングモジュール133のいくつかの実施形態では、時間TminVTimeという最小持続時間を超える訪問に基づいてPORの定義を実施する。具体的には、持続時間フィルタリングモジュール133は、図5Cの擬似コードによって示されるように、レベル480の(訪問を示す)ノードを持続時間に基づいてフィルタリングし、したがって、すべて残りの訪問は時間TminVTimeという最小持続時間を超える。図4Cの例では、訪問482は、通勤中に得られた測定値から生じるので、あまりにも短時間である。したがって、モジュール133がその処理を完了すると、ノード481、486、および489のみが残っており、レベル480のノードの残りはフィルタ除去される。したがって、これらの3つのノード481、486、および489のデータは、次のレベル490に伝搬されて、ノード491、496、および499を形成する。
【００８３】
いくつかの実施形態の発見システム130はまた、関連場所を識別するために、類似度関数180を使用して、この時点では測定値の時刻とは無関係にレベル490のノードを互いに比較するPOR抽出モジュール134(図4A)も含む。上記で説明したようにモジュール131、132、および133を使用した後でPOR抽出モジュール134を使用することによって、他の設計におけるいくつかの欠点を克服する。たとえば、未加工のデータポイントに対する直接的な類似性クラスタリングによって、訪問の持続時間に関する情報は露出されない。未加工のデータに対する類似性クラスタリングによって、各場所に対するクラスタおよび各クラスタ内のデータポイントの数が識別される。均等なサンプリングを仮定すると、データポイントの数は、各クラスタまたはそれぞれの場所で費やされた累積時間に比例する。しかしながら、各場所でどれほどの時間が累積されているかは不明であり、したがって使用されない。データポイントに対する類似性クラスタリングによって、ユーザが時間を費やす場所(クラスタ)が露出されるが、ユーザが連続的に(たとえば職場で)時間を費やすのかまたは複数のごく短時間の訪問(たとえば職場に向かう途中の交通信号)にわたって大量の時間を蓄積しているのかに関する情報を露出することはない。
【００８４】
前の段落で説明した種類の問題は、時間的クラスタリングモジュール131の後にPOR抽出モジュール134を使用して対処される。その上、前述のように、レベル490のすべてのノードは、持続時間フィルタリングモジュール133によってすでに処理されており、したがって、これらのノードは、PORの定義によって必要とされる最小持続時間を超える訪問を表す。したがって、POR抽出モジュール134によるレベル490におけるノードからのPORの抽出は、図5Dの擬似コードによって示されるように、持続時間フィルタリングモジュール133によって識別されるすべての訪問場所モデルに対する類似性クラスタリングに基づく。
【００８５】
いくつかの実施形態の発見システム130では、閾値TsimClustを使用して類似性クラスタリングを再帰的に実行する。このクラスタリング手法は、クラスタまたはノードの数は与えられないが、閾値は与えられていると仮定する。具体的には、発見システム130によって識別されるクラスタまたはノードの数は、データポイントまたはWiFi測定値によって左右される。この手法の利点は、クラスタリングプロセス全体を再実行することなく発見システム130によってクラスタを動的に追加可能であるということである。概念的には、ユーザによる訪問を表すノードは、最も類似しているどのノード(またはクラスタ)ともクラスタ化される(または結合される)が、閾値TsimClustを(類似度関数180を使用して生成される)類似性尺度が超えないときのみである。閾値TsimClustを超えない場合は、新しいノードまたはクラスタがPOR抽出モジュール134によって開始される。上記で説明した類似性クラスタリングの完了の後、結果として生じるすべてのノード(またはクラスタ)を、PORとして適格であるかどうかに関して分析する。少なくともTminVisitの訪問を含むクラスタはPORを表す(TminVisitはPORの定義におけるパラメータによって決定される)。図4Cに示される例では、閾値TminVisit=1、したがってPOR抽出モジュール134は、3つの訪問場所モデル(自宅491、職場496、自宅499)をクラスタ化し、2つのPOR401および402を出力する。
【００８６】
いくつかの実施形態のコンピュータシステム120はまた、発見システム130と同時に使用する認識システム150(図4A)も含む。認識システム150は、再訪問が行われたかどうか判断する。図5Eの擬似コードに示されるように、起動時の認識システム150への入力は、POR場所モデルによって表されるPORのセットである。このセットは随時更新することが可能であり、この更新は、更新が実行された後に次の認識ステップが開始されたときから有効になる。認識システム150の各認識ステップでの入力は、WiFi測定値から訪問を抽出するクラスタマージモジュール132から出力される現在の訪問である。現在の訪問に基づいて、認識システム150は、PORのうち1つへの再訪問が存在するかどうか判断する。再訪問の場合は、認識システム150はPORの識別子を出力し、再訪問でない場合は、認識システム150は再訪問が認識されていないことを示す。いくつかの実施形態では、認識システム150は、認識決定の信頼度を表す信頼度値を計算する。
【００８７】
いくつかの実施形態の認識システム150では、内部状態変数を維持することによって時間ステップごとに(完全な訪問が識別されるのを待つ代わりに)現在の訪問についてのクラスタマージモジュール132からの増分情報を使用し、この内部状態変数は、2つの状態すなわち「入る」または「出る」のうち1つとすることができる。「入る」という内部状態は進行中の再訪問を示し、「出る」という内部状態は、再訪問が認識されない(または、以前の再訪問が終了しており、新しい再訪問が開始されていない)ことを示す。認識システム150は、2つの条件に当てはまる場合、「出る」という状態から「入る」という状態に遷移する。この2つの条件とは、進行中の訪問は時間閾値TrecogEnterを超えなければならないこと、および類似性によって、訪問を既知のPORへの訪問と識別しなければならないことである。
【００８８】
したがって、いくつかの実施形態の認識システム150は発見システム130の中間結果を監視し、2つの条件が真になると、再訪問には、検出されたというマークがメモリ110内で付けられる。認識システム150が「入る」という状態に遷移した後、認識システム150は、各認識ステップでPORの識別子を返すことによって再訪問を報告する。遷移が発生し、認識システム150が「入る」という状態になった後、認識システム150は、遷移を引き起こした訪問を監視する。外れ値がなく、ユーザが同じロケーションにとどまると仮定すると、監視される訪問は、各認識ステップとともに時間的に成長する。再訪問は、いくつかの実施形態では、終了条件を満たしたときに終了する。その終了条件とは、監視される訪問と現在の時刻との間の持続時間が所定の時間閾値TrecogExitを超えることである。この終了条件は、認識システム150が外れ値に基づいてドロップインしドロップアウトする(dropping in and out)ことを防止する。たとえば、現在のデータポイントまたは測定値が外れ値である場合、認識システム150は、再訪問がないことを示す-1を出力しない。
【００８９】
したがって、いくつかの実施形態の認識システム150は、監視されるべき訪問の持続時間が時間閾値TrecogExitを超えない限り、外れ値を許容し、PORインジケータを報告する。いくつかの実施形態では、認識システム150は、時間閾値TrecogEnterとTrecogExitの両方を使用して、再訪問に入ったことと出たことを報告する。そのような閾値を使用することによって、潜伏時間(latency)と正確さとの間の内在的なトレードオフがもたらされる。時間閾値が大きいほど、外れ値による誤分類の可能性が低くなる。しかしながら、潜伏時間が増加するにつれて、再訪問に入ることおよび出ることが検出される。
【００９０】
いくつかの実施形態の認識システム150は、認識決定を表す信頼度値を提供する。信頼度値の計算は、次のように、2つの最も類似した場所の間の差に基づく。
【００９１】
【数１】
2014532353.tif 000003
【００９２】
式中、pm1およびpm2は2つの最も類似したPORのPOR場所モデルであり、pmvは監視される訪問の訪問場所モデルである。
【００９３】
いくつかの実施形態のコンピュータシステム120は、認識システム150または発見システム130のいずれかまたは両方によって使用される類似度関数180を含む。類似度関数180は、実施形態に応じて多数の異なる方法で実施することが可能である。いくつかの実施形態では、類似度関数180は、実験においてその優れた性能を発揮したことにより、Tanimoto類似性を実施する。Tanimoto類似性は、次のように、2つの特徴ベクトル(fvaおよびfvb)間の類似性を測定する。
【００９４】
【数２】
2014532353.tif 000004
【００９５】
特徴ベクトルは、コンピュータシステム120によって場所モデルのRSSI値から計算される。場所
【００９６】
【数３】
2014532353.tif 000005
【００９７】
の場所モデルpmxがワイヤレスアクセスポイントapiの平均RSSI値を示すと仮定する。その場合、Tanimoto類似性は次のように計算される。
【００９８】
【数４】
2014532353.tif 000006
【００９９】
式中、
【０１００】
【数５】
2014532353.tif 000007
【０１０１】
である。RSSI値が-101であるときに各特徴の長さをゼロにするために、RSSI値が[-101,0]の空間から[0,101]の空間に変換されることに留意されたい。ワイヤレスアクセスポイントapjが2つの場所モデルのうち1つのみに含まれると仮定すると、他の場所モデルpm0に追加され、次いで
【０１０２】
【数６】
2014532353.tif 000008
【０１０３】
を設定することができる。
【０１０４】
プロセッサ100の様々な実施形態は、ユーザがスーパーマーケット、商店街の特定の一部、またはカフェテリアにつながるホールなどの特定のエリア内を歩行したことから生じるパスまたは歩行区間の再発生をWiFi測定値内で認識するようにプログラムされる。プロセッサ100の多数の実施形態は、パスの重複を異なる空間的規模で識別するようにプログラムされる。いくつかの適用例では、本明細書で説明する種類の実施形態は、ユーザが特定の建物または大型スーパーマーケットの中を歩行したと判断する。いくつかのそのような実施形態では、共通の比較的広いエリア(たとえばカフェテリア)内にある2つのパスは、プロセッサ100によってマッチングと識別される。他の適用例では、プロセッサ100のいくつかの実施形態は、パスに沿ったWiFi測定値から特定の廊下を(たとえば、カフェテリアまたは会議室への進入路として)識別する。
【０１０５】
したがって、いくつかのそのような実施形態では、プロセッサ100は、重心のツリーによって表されるレベルの階層構造を生成するようにプログラムされ、図6Aに示され、以下でステップ1、2、および3を参照して説明するように、各重心は前のレベルの半径の2倍である半径に割り当てられる(他の実施形態では、倍増以外のものを使用する)。ステップ1(図6Aの動作611参照)では、プロセッサ100は、WiFiトレースのベクトル平均を見つけ、パスに沿った測定値を含むために、どのくらい大きい半径が必要であるか(これは、レベル1の重心C1と呼ばれることがある)判断するようにプログラムされる。図6A〜図6Hを参照して本明細書で説明するように識別される半径は、図9A〜図9Fを参照して本明細書で説明するように、後で変更する(すなわち、サイズを再調整する)ことができる。
【０１０６】
いくつかの実施形態では、各測定値は、(前述のように)ベクトルによって表され、したがって、ベクトル平均は、(測定値の)ベクトル全体の各次元の値を平均することによって得られる。より具体的には、前述のように、各測定値は、ワイヤレス信号の送信機の識別子の特定のグループと、この特定のグループ内の識別された送信機から受信したワイヤレス信号の強度とを含む。いくつかの実施形態では、重心C1Aは、図6Cに示されるようにオレンジ色、青色、緑色、および赤色という名の送信機などの、特定のグループ内の識別されたワイヤレス送信機に対応する平均値のグループを含むようにプロセッサ100によって形成される。
【０１０７】
前の段落で説明した各平均値は、測定値を得る際に測定された各ワイヤレス送信機からの対応するワイヤレス信号の強度全体にわたって、特定のグループ内の識別された各ワイヤレス送信機に対してプロセッサ100によって計算される。たとえば、オレンジ色という名の送信機の場合、値52、54、および56を使用して、算術平均すなわち54を得て、次いで、この算術平均を重心C1Aのベクトルの第1の項として使用する。同様に、赤色という名の送信機の場合、値68、66、および68を使用して、算術平均すなわち67.3を得て、次いで、この算術平均を重心C1Aのベクトルの最後の項として使用する。重心C1Aによって表される訪問の開始時刻午前9時00分および終了時刻午前9時02分は、このサブセットに含まれる測定値の最も早い時刻および最も遅い時刻からプロセッサ100によって自動的にまとめられることに留意されたい。
【０１０８】
この段階では、プロセッサ100は、実際の半径を記憶し、同時にまた、比較メトリックとして使用するためにC1を次に大きい重心にセットすることができる。いくつかの実施形態では、類似性尺度は、たとえば各測定値と重心(図6B参照)との間の差の逆数として決定され、すべての測定値の中の最小の類似性尺度は、パスAのルートノード621に対する最小の類似性(図6D参照、パスAに対する0.18の類似性尺度)として記憶される。いくつかの実施形態では、そのような類似性尺度を使用して、場所を定義するために使用される拡張を表すことができる。
【０１０９】
ステップ2(図6Aの動作612参照)では、いくつかのそのような実施形態では、次に小さい重心の半径(たとえば現在の半径の半分に等しい)を新しい半径として使用し、現在のレベル番号を1に増加させ、開始点を歩行区間の第1の地点に設定し、レベル1の重心の数をn=1に設定する。類似性尺度を使用する実施形態では、ルートノードに対して記憶される値を2倍にする(図6F参照、図6Eに示されるサブパスALおよびARに対する値0.36)。このステップ2に巻き付くように、いくつかの実施形態では、次いで、次のようにステップ2a、2b、および2c(図6A参照)を実行する。
【０１１０】
ステップ2a(図6Aの動作613参照)では、これらの実施形態は、すべての地点(次の地点を含む)を包含するために必要な半径が新しい半径を超える段階に到達するまで(および、これが起こるとき、その次の地点は含まれない)、1地点ずつ平均を更新する。図6Dおよび図6Eの例を参照されたい。これらの例では、0.36という最小の類似性を使用して地点A1〜AIのサブセットを形成し、それによって、パスA内のすべての地点A1〜ANの中からサブパスARを識別する。
【０１１１】
次に、ステップ2b(図6Aの動作614参照)では、そのような実施形態は、次いで、Cl,nとして重心を記憶する(たとえば、このレベルに対応する重心によって半径が与えられるので、平均を記憶する)。次に、ステップ2c(図6Aの動作615参照)では、そのような実施形態は、パス内にまだ残っている地点があるかどうかをチェックし、まだ残っている地点がある場合、新しい開始点をパス内の次の地点に設定し、nを増加させ、ステップ2a(図6Aの動作613参照)に戻る。ステップ3(図6Aの動作616参照)では、いくつかのそのような実施形態は、半径がdminに到達したかどうかチェックし、dminに到達していない場合、ステップ2を繰り返す。
【０１１２】
上記で説明したステップ1〜3の手順によって、重心のツリーが、図6Hに示される種類のパスモデルとして生成され、それにより、図6BのパスAを図6Gの6つのサブサブパスALL、ALM、ALR、ARL、ARM、およびARRに分割する。実施形態によっては、上記で説明した手順に、当業者には容易に明らかであろう多数の改良がある。たとえば、1つのそのような改良では、図6Hに示される種類のツリー620内の重心に対する各ノードは、ステップカウント、方向、または音紋などの追加情報を含む。
【０１１３】
それぞれ図6Gに示される種類の重心のツリー620によって表されるパスのセットを仮定すると、いくつかの実施形態のコンピュータシステム120は、場合によってはいくつかのパラメータだけを調整して、固定関連場所に対する類似性クラスタリングのように、各ツリーレベルを個別にクラスタ化することによって開始することができる。その結果、いくつかの実施形態のシステムは、3つの種類のクラスタ、すなわち、(A)最上位レベル重心のクラスタ(たとえば図5D参照)、(B)最小重心のレベルのクラスタ(たとえば図5Aおよび図5B参照)、および(C)中間レベル重心のクラスタ(たとえば図5C参照)、を取得することができる。
【０１１４】
図7の動作701によって示されるように、コンピュータシステム120のいくつかの実施形態は、ツリー620の最上位レベル重心のクラスタを形成する。最上位レベル重心のクラスタは、2つのパスが同じ関心エリア内にあることを意味することができる。たいていの場合、このエリアは、モバイルデバイスのユーザが静止することなく(立ったり座ったりせずに)特定の範囲内にとどまる、特定の建物、スーパーマーケット、商店街などであってよい。システム120のいくつかの実施形態は、そのようなパスのデータベースを最初に構築する。本質的に、コンピュータシステム120が、いくつかの最上位レベル重心によってモデル化された場所へのある人物による十分な数の訪問を検出すると、システムは、それを、現在のパスが以前に観測したパスと同じパスである(データベース内でのその存在に基づいて)という認識に基づいて、関心エリアと定義することができる。要約すると、システム120が特定の最上位レベル重心への十分な数の訪問を検出した後、システム120は、メモリ110内に(図7の動作702に従って)このノードが関連エリアであるというマークを付ける。
【０１１５】
図7の動作703によって示されるように、プロセッサ100のいくつかの実施形態では、ツリー620(図6H)の最下位レベルノードによって表される最小重心のレベルにクラスタを形成する。いくつかの実施形態では、プロセッサ100は、2つのパスが、共通の小規模エリアを表す単一の最下位レベルノードを通過する(すなわち、パスが互いに交差する)と判断し、このエリアのサイズは、最小半径dminによって、モデルが構築される最小規模と判断される。
【０１１６】
ある建物(最上位レベル重心によって識別される)内の複数のパスが(図7の動作704に従って)1つのそのような小さい重心内に一致を有する場合、プロセッサ100は、(図7の動作705に従って)この重心に、建物の入口または中心点などの建物内の多数のユーザによって一般的に使用されるエリア(たとえばエレベータ)に対応するとマークを付ける。
【０１１７】
プロセッサ100が、(図7の動作706に従って)連続する最小半径の重心の系列において、2つまたはそれ以上のパスが互いに部分的に一致することを見つけると、プロセッサ100は、(図7の動作707に従って)これらのパスにサブパスを共有するとマークを付ける。そのような一例では、1つのパスは廊下であり、別のパスは、廊下に面するあるオフィスから別のオフィスへの通路である。別の例はカフェテリアであり、カフェテリアの異なるロケーションで始まり異なるテーブルで終わるパスには、プロセッサ100によって、(動作707に従って)共通サブパスを有するとマークが付けられる。その上、プロセッサ100は、2つまたはそれ以上のパスがすべての最小レベルの重心で完全に一致する場合、これらのパスは互いに同一であると判断する。いくつかの実施形態では、プロセッサ100は、最小レベルの重心に対して確率モデルを使用して、同一のパスを識別するようにプログラムされる。厳しい閾値を使用して、尺度がPOR(最小の重心)内にあるかどうか判断する代わりに、他の実施形態では、ガウスモデルを使用してノイズをモデル化し、このガウスモデルに基づく意思決定を推進する。
【０１１８】
図7の動作708によって示されるように、プロセッサ100のいくつかの実施形態は、中間レベル重心にクラスタを形成する。そのような一致は、上記で説明したレベルのうち1つで一致することがすでにわかっているパスの場合に発生することがあるが、状況によっては、パスは、中間レベルの単一の重心の中でのみ一致する。したがって、いくつかの実施形態では、プロセッサ100は、最上位レベル重心で一致するパスが中間レベル重心でも一致するかどうか(動作708および709に従って)チェックするようにプログラムされ、一致する場合は、プロセッサ100は、(動作710に従って)2つのパスが特に近接する特定の領域があるとメモリ内でマークを付ける。プロセッサ100は、これらのパスに共通サブパスを有するとマークを付けず、代わりに、プロセッサ100は、そのユーザは中間レベルノードによって識別される特定の限定されたエリアを多くの場合に通過する傾向があるとメモリ内でマークを付けることに留意されたい。
【０１１９】
1つの例示的な例では、プロセッサ100は、追加情報(たとえばユーザ入力)から、最上位レベル重心がスーパーマーケットに対応すると判断する。この例では、プロセッサ100は、この追加情報を動作710で使用して、そのような中間レベル重心に、ユーザが必ずしも同じパスを歩いて通るとは限らないものの常に訪問する特定の部門に対応するとマークを付ける。別のそのような例では、プロセッサ100は、中間ノードに(動作710で)、ユーザが購入する食品を選択する、および/またはユーザがその食品の代金を支払うカフェテリアのエリアを表すとマークを付ける。したがって、いくつかの実施形態の動作710でマークが付けられたそのような中間重心は、プロセッサ100によって、スーパーマーケットまたはカフェテリアのような場所を検出し、ユーザの「自宅」のような複雑な関連場所を識別する助けとなるために使用される。
【０１２０】
動作708および709を実行するとき、プロセッサ100が、パスが中間レベル重心で一致し、他のレベルでは一致しないことを見つけた場合、プロセッサ100は、(図7の動作711に従って)その中間レベルノードに、2つの関連エリアの共通領域を表すとマークを付ける。そのような一例では、動作711で識別される中間レベルノードは、ショッピングセンター内の2つの店の間の駐車場である。
【０１２１】
ツリー620(図6H)のあらゆるレベルに対して、いくつかの実施形態のプロセッサ100によって実行される類似性クラスタリング(たとえば図5D参照)は、重心のリストを生成する。これらの重心は、そのような実施形態のプロセッサ100の認識モジュール(たとえば図5E参照)でマッチングのために使用される。したがって、プロセッサ100のいくつかの実施形態では、同じまたは異なる訪問における隣接するまたは近くの場所へのユーザの訪問に基づく関連場所(POR)に対して発見システム130(図4A)を実施し、対応するPORを、共通ラベル(たとえば、固定PORに以前に使用したラベル)を持つ同じ意味論的場所であると記録する。
【０１２２】
プロセッサ100のいくつかの実施形態は、図8Aに示される1つまたは複数の動作を実行することによって、図8Bに示される2つのパスAおよびBに関して上記で説明した種類のツリーを一致させる。いくつかの実施形態のプロセッサ100は、ツリー(図8Dに示される)を横断することによって2つのパスAおよびB上の測定値のサブセット(図8Cに示される)を再帰的に比較するようにプログラムされ、この比較は、レベルごと、重心ごとに行われる。最初に、プロセッサ100は、パスAおよびBの最上位レベル(「ルートノード」とも呼ばれる)重心C1AおよびC1Bが同じレベルにある(たとえば、オフィスビルの重心など、同じサイズの重心の中に含まれる)かどうかチェックすることによって開始する。一方のパスが大きく、他方のパスが小さい場合、プロセッサ100は、はるかに大きい重心に適合するよう要求した可能性がある。あるパス(すなわちパスA)が、より大きい重心に対応する場合、プロセッサ100は、パスBの最上位レベル重心と同じレベルにあるパスAのすべての重心を収集し、それらの重心の各々に対して以下で説明する手順を繰り返すだけである。
【０１２３】
パスマッチングの第1のステップでは、プロセッサ100は、2つの重心が重複を有するかどうかを、動作811に従ってチェックする。以下の3つの可能性がある。(a)重心は重複しない。この場合、プロセッサ100は、動作812に従って、2つのパスに、これらの重心の中で独立している(disjoint)とマークを付ける。(b)動作811では、その答えがyesの場合、プロセッサ100は動作813に進み、重心の平均(平均値)は同一であると見なすのに十分なほど互いに対して近い(たとえば、所定の閾値の範囲内にある)かどうかチェックする。この(b)の場合、プロセッサ100が、動作813での答えがyesである、すなわちパスが、対応するレベル上のこれらの重心の中で一致するとわかっている場合、重心には、動作814に従って、マッチングとマークが付けられる。この(b)の場合、クラスタリングが行われた場合は、重心をプロセッサ100によって結合することができ、特定のパスが訪問された回数のカウンタを増加させることができる。動作813において、答えがnoである場合、プロセッサ100は、(c)重心は適切な量の重複を有する、と判断する。いくつかの実施形態では、プロセッサ100は、「適切な重複」を、dminによって定義される最小重心程度の大きさの重複と判断し、この見解には、動作817を実行することによって、いくつかの実施形態におけるプロセッサ100によってマークが付けられる。
【０１２４】
パスマッチングの別のステップでは、プロセッサ100は、現在の重心が最小の重心のレベルにあるかどうかを、動作815に従ってチェックし、最小の重心のレベルにある場合は停止する。動作815には、図8Aに示すように、動作814および817から到達する。パスマッチング手順に関して上記で説明した可能性(a)(重複のない可能性)の場合も同様であり、動作812の後、プロセッサ100は停止する。他の場合には、動作815での答えがnoの場合、上記の(b)および(c)の場合は、動作816に従って重複領域内にある次のレベルの重心の各ペア(各パスから1つ)に対して、パスマッチング手順(ステップ1すなわち動作811に進む)が繰り返される。いくつかの実施形態では、パスマッチングにおいて、幅優先探索がプロセッサ100によって実行される。
【０１２５】
上記で説明したパスマッチング手順が終了するとき、その結果は、図8Dに示されるようにパスがマッチングであるとわかった重心のリストである。リスト内の重心は異なるレベルにあってよい(これは、これらの重心が、異なる半径を持つ重心に対応することを意味する)ことに留意されたい。したがって、たとえば、リスト上のある重心は全体としてオフィスビル201(図1B)に対応することがあり、別の重心(より大きな重心に含まれる)は、この同じオフィスビル201のエリア203であることがある。2つのパスAとB(図8D)が所与のレベル(すなわち、ルートノードレベルまたはルートノードレベルの下の第1のレベル)の重心の中で一致するということは、これらのパスが後続のレベル(たとえば図6Hに示される最下位レベル)の重心のいずれの中でも一致することを意味しない。たとえば、すべてが同じオフィスビル内にあるが、それぞれがそのビルの異なるエリアにある一群のパスが存在することがある。しかしながら、ある重心のペア(たとえば図8Dの重心ALLおよびBLL)が最も低いレベルで一致するとき、このペアを使用して、パスベースの関連場所(POR)にメモリ110内でマークを付ける。
【０１２６】
いくつかの実施形態では、場所の再訪問の分布に基づいて、経時的に関連場所(POR)のサイズを適応的に決定する。たとえば、建物内部のある人物のオフィスなどの狭い場所への複数の再訪問中、その人物は、通常、その場所内の同じロケーションで時間のほとんどを費やす(たとえば、その人物は、通常、自分の机の同じ椅子に座る)。したがって、いくつかの実施形態では、たとえば以下で図9A〜図9Dを参照して説明するように、関連場所のサイズが(複数の場所の再訪問にわたって)徐々に小さくなると判断する、すなわち相違を示すペアワイズ距離を使用してPORのサイズを縮小するのに十分なほど高い(たとえば、分散が所定の閾値を下回る)、複数の場所の再訪問にわたる信号測定値において類似性を使用する(たとえば、Tanimoto関数を実行する)。
【０１２７】
同様に、建物内のカフェテリアなどの広い場所への複数の再訪問中、ある人物は、通常、その広い場所内の異なるロケーションで時間を費やす(たとえば、その人物は、日によって異なるテーブルに座ってよい)。したがって、いくつかの実施形態では、たとえば以下で図9Eおよび図9Fを参照して説明するように、遠いが、にもかかわらず同じ関連場所の中にある複数の場所の再訪問全体にわたる信号測定値を使用して、PORのサイズを拡大し、所定の最大サイズに到達するまで(複数の場所の再訪問にわたって)PORのサイズを徐々に大きくする。
【０１２８】
図9Aは、ある建物内の一組のオフィス(office suite)900を示し、この一組のオフィス900は、受付エリア901と、2つのオフィス902および903と、会議室904とを含む。図9Aはまた、オフィス903の中に、4つの関連場所911〜914を組み合わせることによって、たとえば上記で図1Aを参照して説明した動作105を実行することによって、形成された拡張された関連場所910も示す。関連場所910(図9B)を形成する際、コンピュータシステム120は、4つの場所911、912、913、および914の重心間のペアワイズ距離921〜926(図9B)を計算する(たとえば、Tanimoto関数を実行することによって得られる)。次いで、コンピュータシステム120は、たとえば図9Cに示される、ペアワイズ距離921、922、923、924、925、および926の平均μおよび標準偏差σを計算し、続いて、拡張されたPOR910のサイズを次のように計算する。dsize=μ+3σ
【０１２９】
この状態において、新しい関連場所931が拡張されたPOR910に十分に近いことがわかった場合、拡張されたPOR910を、図9Dに示される新しい拡張されたPOR930に変更することができる。これを行うために、コンピュータシステム120は、追加ペアワイズ距離932、933、934、および935を計算し、これらのペアワイズ距離を使用して、ペアワイズ距離921〜926および932〜935の新しい平均μnおよび新しい標準偏差σnを計算し、続いて拡張されたPOR930のサイズを次のように計算する。dnsize=μn+3σn
【０１３０】
新しい場所への訪問CVtが決定されると、いくつかの実施形態のコンピュータシステム120は、次のように、図9Eに示される種類の方法を実行する。具体的には、動作941では、コンピュータシステム120は、場所への訪問CVtを使用して、既知の場所モデル135(図4A)の中から、場所への訪問CVtに最も近い関連場所PORtを見つけ、次いで動作942に進む。動作942では、コンピュータシステム120は、2つの場所CVtとPORtとの間の距離(dist(CVt,PORt)と示す)が関連場所PORtの現在のサイズdsizeよりも小さいかどうかチェックする。
【０１３１】
動作942での答えがnoのとき、コンピュータシステム120は、動作943を実行して、新しい関連場所PORnewを作成し、そのサイズdnewsizeを所定の距離たとえばddefaultSizeに設定する。動作942での答えがyesのとき、コンピュータシステム120は、動作944において場所CVtを既存の関連場所PORtに含めることによってPORtを更新し、次いで動作945に進む。動作945では、コンピュータシステム120は、既存の関連場所PORtのサイズを再計算してRdsizeとするが、動作945を実施する具体的な方法は、後述のように、実施形態に応じて異なる。動作945の完了時に、Rdsizeが所定の最小値dminSizeよりも小さいまたはこれに等しい(動作946参照)場合、現在のサイズdsizeは最小値dminSizeに変更される(動作947参照)。そして、Rdsizeが所定の最大値dmaxSizeよりも大きいまたはこれに等しい(動作948参照)場合、現在のサイズdsizeは最大値dmaxSizeに変更される(動作949参照)。最後に、動作946と948の両方の答えがnoのとき、動作950において、現在のサイズdsizeはRdsizeに変更される。
【０１３２】
上記で図9A〜図9Dを参照して説明した第1の例では、図9Eの動作945において、上記で説明したようにRdsizeを計算する、具体的にはRdsize=μ+3σである。第2の例では、既存の関連場所PORtは、本明細書で説明するように、動作945において拡張可能であり、いくつかの実施形態では、所定の係数k≧1を用いて類似の式を使用して拡張し、したがってRdsize=k(μ+3σ)であるが、μおよびσは、訪問と既存の関連場所PORtとの間の距離である(そして、上記で説明した第1の例でμおよびσを計算するために使用されるペアワイズ距離ではない)ことに留意されたい。第3の例では、Rdsize=dsize+α*(dist(CVt,PORt)-dsize/2)であり、式中、0≦α≦1であり、αは所定の定数である。dist=1-類似性であり、ここで、類似性はTanimotoなどの類似度関数の実行によって得られることに留意されたい。
【０１３３】
POR960に含める新しい場所961が、動作951(図9E)において、十分に小さい距離(dist(CV1,PORt)である、たとえばPOR960の半径の半分すなわちdsize/2よりも小さいことがわかったとき、いくつかの実施形態の動作952において、拡張されたPOR960(図9F)は(たとえば、上記で説明したいずれかの式を使用して)縮小される。同じ拡張されたPOR960(図9F)は、POR960に含める別の新しい場所962が、動作953において、十分に大きい距離(dist(CV2,PORt)である、たとえばPOR960の半径の半分すなわちdsize/2よりも大きいが、POR960の半径dsizよりも小さいことがわかったとき、いくつかの実施形態の動作954において(たとえば、上記で説明したいずれかの式を使用して)拡張される。
【０１３４】
したがって、この詳細な説明では、関連場所(POR)を発見するおよび/または自動的にサイズを調整するための方法、装置、システム、および非一時的なコンピュータ可読媒体が提示される。いくつかの態様では、1つまたは複数の関連場所を発見する際に、図9Gの動作971によって示されるように、モバイルデバイスによって、またはサーバによって、またはこれらの組合せによって、ワイヤレス信号の測定値のセットを受信するまたは別の方法で取得することができる。次いで、図9Gの動作972によって示されるように、1つまたは複数の場所を(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)識別することができる。
【０１３５】
識別された各場所は、測定値のセットの中のサブセット内の1つまたは複数の測定値を使用して取得される重心を有することができる。いくつかの態様では、場所の識別は、972A(図9G)に従って、時間的に順次得られた測定値に基づいてよい。そのような識別は、ハードウェアによって、またはソフトウェアを実行するプロセッサによって、または「自分は同じ場所にいるのか?」という質問に答える他の手段によって、測定値の類似性に基づいてよく、その場合、972に戻って、現在識別されている場所の重心を計算する際に測定値を含める。
【０１３６】
いくつかの態様では、2つのそのような場所を動作972Aで使用して、これらの場所がパスに沿って順次発生するかどうか(たとえば、これらの場所の測定値が時間的に連続しているかどうか)判断し、これらの場所が互いに十分に類似した重心を有する(たとえばTanimoto距離が0.1よりも小さい)かどうか判断し、両方の条件が満たされるとき、動作973(図9G)を実行する。いくつかの態様では、2つの場所は、動作972Bにおいて、類似しているまたは同一であると判断されたラベルの比較に基づいて、および互いに十分に類似していると判断された重心に基づいて、測定値が得られた時刻とは無関係に識別され、両方の条件が満たされるとき、動作973(以下で説明する)を再実行する。
【０１３７】
動作973では、2つの重心を比較することに基づいて、この2つの重心を有する対応する2つの場所が類似しているかどうか(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)判断することができる。次いで、動作974では、動作973で使用された対応する2つの場所が類似していると(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)判断されたことに基づいて、たとえばこの対応する2つの場所を含むリストとして、関連場所を記憶することができる。
【０１３８】
いくつかの態様では、複数の関連場所のうち1つまたは複数の関連場所に関連付けられるべき1つまたは複数のラベルを指定するユーザ入力を(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)受信することができる。その後、受信したユーザ入力に基づいて、複数の関連場所のうち少なくとも2つの関連場所が1つまたは複数のラベルの共通のラベルに、または類似していると判断されたラベルに関連付けられるかどうか(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)判断することができる。さらに、前述のように、(相違を示す)1つまたは複数の距離メトリックに基づいて、この少なくとも2つの関連場所が類似しているかどうか(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)判断することができる。その後、この少なくとも2つの関連場所が類似のラベル(または同じラベル)に関連付けられていると判断したことを受けて、およびこの少なくとも2つの関連場所が類似していると判断したことを受けて、この少なくとも2つの関連場所は拡張された関連場所を定義すると(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)判断することができる。
【０１３９】
いくつかの態様では、測定値は、互いに対して時間的に順次測定されたために各サブセットに含めることができ、各場所の識別は、そのようなサブセットに基づくことができる。各測定値は、たとえば、(たとえばサブセットの重心に対する)測定値が類似性の尺度に関するテストに合格するかどうか(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)チェックすることに基づいて、測定値のサブセットに含めることができる。類似性の尺度は、たとえば、ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは類似度関数を実行して各測定値をサブセット内の測定値の重心と比較する他の手段によって、取得することができる。各測定値は、ワイヤレス信号の送信機の識別子のグループと、このグループ内の識別された送信機から受信したワイヤレス信号の強度とを含む。各重心は、特定のグループ内の識別されたワイヤレス送信機に対応する平均値のグループを含むことができる。各平均値は、測定値を得る際に測定された各ワイヤレス送信機からの対応するワイヤレス信号の強度全体にわたって、特定のグループ内の識別された各ワイヤレス送信機に対して(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)計算される。
【０１４０】
いくつかの態様では、ツリーのルートノードは、測定値のセットに基づいて(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)作成することができ、このツリー内の複数の子ノードは、このルートノードに接続することができ、少なくとも1つの子ノードは、セット内の測定値のサブセットに基づいて作成される。前述のように、測定値は、互いに対して時間的に順次測定されたために、および類似性の尺度に関するテストに合格したために、各サブセットに含めることができる。測定値のセット内の複数のサブセットを、追加測定値のサブセットと(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)比較して、新しい関連場所を識別することができる。これに加えて、またはこの代わりに、測定値のセット内の複数のサブセットを、測定値の別のセットと(ハードウェアによって、またはソフトウェアを実行するプロセッサ、もしくは他の手段によって)比較して、既知の関連場所を識別することができる。
【０１４１】
いくつかの実施形態のコンピュータシステム120は、画面上に表示されている現実世界の物体のビデオのフレームを生成するカメラ1019(図4A)を含むスマートフォンなどのモバイルデバイスである。前述のように、コンピュータシステム120は、加速度計、ジャイロスコープ、コンパスなどの、実際の動きを示す測定値を提供する様々なセンサ1003をさらに含むことができる。コンピュータシステム120は、加速度計およびコンパスおよび/または他のセンサを使用して、通常の方法で傾斜および/または回転を感知し、プロセッサ100が地面に対するそれ自体の方向および位置を判断するのを助けることができる。センサ1003の代わりに、またはこれに加えて、コンピュータシステム120は、カメラ1019からの画像を使用して、プロセッサ100がそれ自体の方向および位置を判断するのを助けることができる。また、コンピュータシステム120は、通常の方法で使用されるグラフィックスエンジン1004と画像処理プロセッサ1005とをさらに含むことができる。コンピュータシステム120は、任意選択で、拡張現実(AR)機能をサポートする様々なモジュールを含むことができる。
【０１４２】
メモリ110に加えて、コンピュータシステム120は、フラッシュメモリ(またはSDカード)などの1つまたは複数の他の種類のメモリと、ならびに/またはメモリ110(「主記憶装置」とも呼ばれる)にロードするために、および/もしくはプロセッサ100が使用するために、データおよび/またはソフトウェアを記憶するハードディスクおよび/または光ディスク(「補助記憶装置」とも呼ばれる)1008とを含むことができる。コンピュータシステム120は、送受信機1010内のワイヤレス送信機および受信機および/または何らかの他の通信インターフェースをさらに含むことができる。コンピュータシステム120は、セルラー式通信デバイスまたは他のワイヤレス通信デバイス、パーソナル移動通信システム(PCS)デバイス、パーソナルナビゲーションデバイス(PND)、パーソナルインフォメーションマネージャ(PIM)、携帯情報端末(PDA)、ラップトップ、カメラ、スマートフォン、タブレット(Apple Inc.から入手可能なiPadなど)、または拡張現実(AR)環境を作成することが可能な他の適切なモバイルプラットフォームなどの、何らかの携帯型電子デバイスであってよいことを理解されたい。
【０１４３】
上記で説明した種類のコンピュータシステム120は、「コンピュータビジョン」技法を使用する物体認識などの、他の位置判断方法を含むことができる。コンピュータシステム120は、マイクロホンとスピーカとをユーザインターフェースにさらに含むことができる。当然のことながら、コンピュータシステム120は、プロセッサ100が使用するためのファームウェアを記憶するために使用可能な読み出し専用メモリ1007など、本開示に関連しない他の要素を含むことができる。
【０１４４】
コンピュータシステム120のいくつかの実施形態では、上記で説明したモジュールは、コンピュータシステム120のメモリ110にあるソフトウェアの命令を実行する1つまたは複数のプロセッサ100によって実施されるが、他の実施形態では、何らかの1つまたは複数のモジュールは、コンピュータシステム120内のハードウェア回路および/またはファームウェアおよび/またはソフトウェアの何らかの組合せで実施される。したがって、実施形態に応じて、本明細書で説明する種類の様々な機能は、(1つまたは複数の処理ユニットまたはプロセッサコアによって実行される)ソフトウェアで、または専用ハードウェア回路で、またはファームウェアで、またはこれらの何らかの組合せで、実施することができる。
【０１４５】
プロセッサ100は、コンピュータシステム120内の1つまたは複数の処理ユニットによって実施される機能を実行する。ハードウェア実装形態では、プロセッサ100の1つまたは複数の処理ユニットは、1つまたは複数のマイクロプロセッサ、埋込み型プロセッサ、コントローラ、特定用途向け集積回路(ASIC)、デジタル信号プロセッサ(DSP)、デジタル信号処理デバイス(DSPD)、プログラマブルロジックデバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、本明細書で説明する機能を実行するように設計された他の電子ユニット、またはこれらの組合せの中で実施され得る。ファームウェアおよび/またはソフトウェアの実装形態では、方法は、本明細書で説明された機能を実行するモジュール(たとえば、手順、関数など)で実施され得る。
【０１４６】
その上、本明細書で使用されるとき、「メモリ」という用語は、長期メモリ、短期メモリ、またはモバイルプラットフォームに関連付けられるその他のメモリを含む、非一時的である何らかの種類のコンピュータ記憶媒体を指し、何らかの特定の種類のメモリ、またはメモリの数、またメモリが格納される媒体の種類に限定されない。したがって、本明細書で説明する方法は、適用例に応じて様々な手段によって実施され得る。たとえば、これらの方法は、ファームウェア(図4A)、またはソフトウェア、またはハードウェア、またはこれらの何らかの組合せで実施されることがある。
【０１４７】
コンピュータ命令を有形に実施する何らかの機械可読媒体は、本明細書で説明された方法の実施において使用され得る。たとえば、ソフトウェア(図4A)は、メモリ110に記憶されプロセッサ100によって実行されるプログラムコードを含むことができる。メモリは、プロセッサ100の内部に実装されてもよいし、プロセッサ100の外部に実装されてもよい。ファームウェアおよび/またはソフトウェアで実装する場合、機能は、1つまたは複数のコンピュータ命令またはコードとしてコンピュータ可読媒体上に記憶され得る。例としては、データ構造(所定の動きの系列など)で符号化された非一時的なコンピュータ可読媒体と、コンピュータプログラム(上記で説明した方法を実行するように実行可能なソフトウェアなど)を用いて符号化された非一時的なコンピュータ可読媒体がある。
【０１４８】
いくつかの例示的な実施形態について、本発明の一部を形成する添付の図面を参照して説明する。本開示の1つまたは複数の態様を実施することができる特定の実施形態について説明しているが、他の実施形態を使用してよく、本開示の範囲または添付の特許請求の範囲の趣旨から逸脱することなく様々な変更を加えることができる。
【０１４９】
本開示は、特定の実施形態に関して示されているが、実施形態はそれらに限定されない。したがって、いくつかの実施形態における項目120はモバイルデバイスであるが、他の実施形態では、項目120は、異なる形態的要素を使用して実施され、たとえば、いくつかの他の実施形態では、項目120はモバイルプラットフォーム(タブレット、たとえばApple, Inc.から入手可能なiPad)であり、さらに他の実施形態では、項目120は何らかの電子デバイスまたはコンピュータシステムである。そのような電子デバイスまたはシステム120の例示的な実施形態は、1つまたは複数のワイヤレスリンクを介して通信するラップトップコンピュータ、デスクトップコンピュータ、またはサーバコンピュータなどの固定されたコンピュータの一部分であるプロセッサおよびメモリなどワイヤレスで相互に通信する複数の物理的部品を含むことができ、センサおよびユーザ入力回路は、手の中に保持するのに十分なほど小さいハウジングに入れられる。
【０１５０】
図4Aは、本開示の1つまたは複数の態様を実施することができる例示的なコンピューティングシステムを示す。たとえば、図4Aに示されるコンピュータシステムは、本明細書で説明する特徴、方法、および/または方法ステップのいずれかおよび/またはすべてを実施し得るおよび/または実行し得るコンピューティングデバイスの一部として組み込まれてもよい。たとえば、コンピュータシステム120は、ハンドヘルドデバイスの構成要素のうちのいくつかを表すことがある。ハンドヘルドデバイスは、カメラおよび/またはディスプレイユニットなどの入力感知ユニットを有する何らかのコンピューティングデバイスであってよい。ハンドヘルドデバイスの例としては、限定するものではないが、ビデオゲームコンソール、タブレット、スマートフォン、およびモバイルデバイスがある。
【０１５１】
図4Aは、本明細書で説明する様々な他の実施形態によって提供される方法を実行することが可能かつ/またはホストコンピュータシステム、リモートキオスク/端末、販売時点情報管理デバイス、モバイルデバイス、セットトップボックス、および/もしくはコンピュータシステムとして機能することが可能なコンピュータシステム120の一実施形態の概略図を提供する。図4Aは、様々な構成要素の一般化された例示を提供することを意図するにすぎず、これらの構成要素のいずれかおよび/またはすべては、必要に応じて利用され得る。したがって、図4Aは、比較的に分離された様式で、または比較的により統合された様式で、個々のシステム要素がどのように実施され得るかを広く示す。
【０１５２】
バス1015を介して電気的に結合することができる(または、必要に応じて、別の方法で通信することができる)ハードウェア要素を備えるコンピュータシステム120が示されている。このハードウェア要素としては、限定するものではないが、1つまたは複数の汎用プロセッサおよび/または1つまたは複数の専用プロセッサ(デジタル信号処理チップ、グラフィックスアクセラレーションプロセッサなど)を含む1つまたは複数のプロセッサ100、限定するものではないが、カメラ、マウス、キーボードなどを含むことができる1つまたは複数の入力デバイス115、ならびにディスプレイユニット、プリンタなどを含むことができる1つまたは複数の出力デバイス121があり得る。
【０１５３】
コンピュータシステム120は、1つまたは複数の非一時的な記憶デバイス125をさらに含む(および/またはこれと通信する)ことができ、非一時的な記憶デバイス125は、限定するものではないが、ローカルストレージおよび/もしくはネットワークアクセス可能ストレージを備えることができ、かつ/または限定するものではないが、ディスクドライブ、ドライブアレイ、光記憶デバイス、プログラム可能、フラッシュ更新可能などとすることが可能なランダムアクセスメモリ(「RAM」)および/または読み出し専用メモリ(「ROM」)などのソリッドステート記憶デバイスを含むことができる。そのような記憶デバイスは、限定するものではないが、様々なファイルシステム、データベース構造などを含む何らかの適切なデータストレージを実施するように構成されてよい。
【０１５４】
コンピュータシステム120はまた、通信サブシステム122も含むことができ、通信サブシステム122は、限定するものではないが、モデム、ネットワークカード(ワイヤレスまたは有線)、赤外線通信デバイス、ワイヤレス通信デバイス、および/またはチップセット(Bluetooth(登録商標)デバイス、802.11デバイス、WiFiデバイス、WiMax(登録商標)デバイス、セルラー式通信設備など)などを含むことができる。通信サブシステム122は、ネットワーク(一例を挙げるために以下で説明するネットワークなど)、他のコンピュータシステム、および/または本明細書で説明する何らかの他のデバイスを用いてデータを交換することを可能にすることができる。コンピュータシステム120は、非一時的なメモリ110をさらに備えることができ、非一時的なメモリ110は、上記で説明したように、RAMデバイスまたはROMデバイスを含むことができる。
【０１５５】
コンピュータシステム120はまた、現在メモリ110内にあるとして示されるソフトウェア要素を備えることができ、ソフトウェア要素としては、オペレーティングシステム140、デバイスドライバ、実行ファイルライブラリ、および/または1つまたは複数のアプリケーションプログラム145などの他のコードがあり、これらは、様々な実施形態によって提供されるコンピュータプログラムを備え得る、かつ/または本明細書で説明するように、他の実施形態によって提供される方法を実施する、および/もしくは他の実施形態によって提供されるシステムを構成するように設計され得る。単に例として、上記で説明した方法に関して説明した1つまたは複数の手順は、コンピュータ(および/またはコンピュータ内のプロセッサ)によって実行可能なコードおよび/または命令として実施されてもよい。一態様では、次いで、そのようなコードおよび/または命令は、説明した方法による1つまたは複数の動作を実行するように汎用コンピュータ(または他のデバイス)を構成するおよび/または適合させるために使用され得る。
【０１５６】
これらの命令および/またはコードのセットは、上記で説明した記憶デバイス125などのコンピュータ可読記憶媒体上に記憶されてもよい。場合によっては、この記憶媒体は、コンピュータシステム120などのコンピュータシステム内に内蔵されてもよい。他の実施形態では、この記憶媒体は、その上に記憶された命令/コードを用いて汎用コンピュータをプログラムする、構成する、および/または適合させるために使用することができるように、コンピュータシステムから分離されてもよいし(たとえば、コンパクトディスクなどの着脱可能な媒体)、および/またはインストールパッケージの形で提供されてもよい。これらの命令は、コンピュータシステム120によって実行可能な実行可能コードの形態をとってもよいし、ならびに/または(たとえば、様々な一般に入手可能なコンパイラ、インストールプログラム、圧縮/解凍ユーティリティなどのいずれかを使用して)コンピュータシステム120上でのコンパイル時および/またはインストール時に実行可能コードの形態をとるソースコードおよび/もしくはインストール可能なコードの形態をとってもよい。
【０１５７】
固有の要求事項に従って、大幅な変形を加えてもよい。たとえば、カスタマイズしたハードウェアも使用してよいし、および/または特定の要素をハードウェア、ソフトウェア(アプレットなどの高移植性ソフトウェアを含む)、もしくはハードウェアとソフトウェアの両方として実施してもよい。さらに、ネットワーク入出力デバイスなどの他のコンピューティングデバイスへの接続を用いてもよい。
【０１５８】
いくつかの実施形態では、コンピュータシステム(コンピュータシステム120など)を用いて、本開示による方法を実行することができる。たとえば、説明した方法の手順のうちのいくつかまたはすべては、メモリ110に含まれる1つまたは複数の命令の1つまたは複数の系列(オペレーティングシステム140および/またはアプリケーションプログラム145などの他のコードに組み込むことができる)を実行するプロセッサ100に応答するコンピュータシステム120によって実行することができる。そのような命令は、記憶デバイス125のうち1つまたは複数などの別のコンピュータ可読媒体からメモリ110に読み込むことができる。単に例として、ワーキングメモリ110に含まれる命令の系列を実行すると、プロセッサ100は、本明細書で説明する方法の1つまたは複数の手順を実行することができる。
【０１５９】
いくつかの実施形態のアプリケーションプログラム145は、認識システム150によるPORの認識を使用して、情報をユーザに表示することができ、その情報は、認識されたPORに基づいて選択される。表示される情報は実施形態によって決まり、たとえばユーザがレストランのそばを歩いているとき、広告またはクーポンが、コンピュータシステム120(モバイルデバイスであってよい)の画面などの出力デバイス121に表示されてよい。
【０１６０】
いくつかの実施形態のコンピュータシステム120は、認識システム150からの場所訪問情報に基づいてユーザプロファイルを構築し、次いで、このユーザプロファイルを使用して、いくつかの質問に回答する。第1の例として、ある場所に何回訪問したか、および1週間に平均してどのくらいの時間を費やしたか(たとえば、自宅、職場)?第2の例として、思い出せない場所への最後の訪問はいつか?(たとえば、タイヤ交換)。さらに、コンピュータシステム120のいくつかの実施形態では、ユーザの行動パターンを抽出して、それをユーザプロファイルに記憶する(たとえば、どの種類の場所に頻繁に行ったか、ジムまたは店?、食料雑貨店に行ったのは主にいつか?)。そのようなユーザのオフラインプロファイルは、その後、ユーザの行動についての理解を深めるために、ならびに適切なマーケティングターゲットおよびマーケティング戦略を決定するために、いくつかの実施形態のアプリケーションプログラム145によって使用される。
【０１６１】
いくつかの実施形態のコンピュータシステム120は、そのようなユーザプロファイルを使用して、ユーザの行動を予測する。場所訪問の時間的パターンに基づいて、いくつかの実施形態のアプリケーションプログラム145は、ユーザの次回の訪問を予測し、この予測を使用して様々なアクションを実行する。たとえば、発見システム130が、1つのパターンはユーザが映画館を訪問した後でレストランに行くことであると識別すると、アプリケーションプログラム145は、このパターンを使用して、そのエリアに存在しユーザにとって魅力的な可能性があるレストランのクーポンを取得して表示する。コンピュータシステム120によるそのような予測に基づく広告は、実際の購入が発生する直前にユーザに届き、ユーザの行動に影響を与える、たとえばユーザを異なるレストランに案内する。
【０１６２】
「機械可読媒体」および「コンピュータ可読媒体」という用語は、本明細書で使用されるとき、機械に特別な方法で動作させるデータを提供することに関与する何らかの非一時的な媒体を指す。コンピュータシステム120を使用して実施される一実施形態では、様々なコンピュータ可読媒体は、実行するためにプロセッサ100に命令/コードを提供することに関与してもよいし、かつ/またはそのような命令/コードを(たとえば信号として)記憶するおよび/または運ぶために使用されてもよい。多数の実装形態では、コンピュータ可読媒体は、物理的なおよび/または有形の記憶媒体である。そのような非一時的な媒体は、限定するものではないが、不揮発性媒体および揮発性媒体を含む、多数の形態をとることができる。不揮発性媒体としては、たとえば、記憶デバイス125などの、光ディスクおよび/または磁気ディスクがある。揮発性媒体としては、限定するものではないが、メモリ110などのダイナミックメモリがある。
【０１６３】
非一時的なコンピュータ可読媒体としては、物理的なおよび/または有形のコンピュータ可読記憶媒体がある。記憶媒体は、コンピュータによってアクセスすることができる何らかの利用可能な非一時的な媒体であってよい。限定ではなく、例として、そのようなコンピュータ可読媒体は、パンチカード、紙テープ、RAM、ROM、PROM、EPROM、EEPROM、フラッシュメモリ、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置もしくは他の磁気記憶デバイス、またはソフトウェア命令(「プロセッサ命令」または「コンピュータ命令」とも呼ばれる)もしくはデータ構造の形態でプログラムコードを記憶するために使用することができ、コンピュータによってアクセスすることができる他の何らかの非一時的な媒体を備えることができる。ディスク(diskおよび/またはdisc)は、フレキシブルディスク(flexible disk)、ハードディスク(hard disk)、コンパクトディスク(compact disc)(CD)、レーザディスク(laser disc)、光ディスク(optical disc)、デジタル多用途ディスク(digital versatile disc)(DVD)、フロッピー(登録商標)ディスク(floppy disk)、およびブルーレイディスク(blu-ray disc)を含み、ここでディスク(disk)は通常、磁気的にデータを再生するが、ディスク(disc)はレーザを用いて光学的にデータを再生する。上記の組合せも、コンピュータ可読媒体の範囲内に含めるべきである。
【０１６４】
非一時的なコンピュータ可読媒体の様々な形態は、実行のために1つまたは複数の命令の1つまたは複数の系列をプロセッサ100に運ぶことに関係してもよい。単に例として、命令は、最初はリモートコンピュータの磁気ディスクおよび/または光ディスクに収容されてもよい。リモートコンピュータは、命令をそのダイナミックメモリにロードして、命令を信号として伝送媒体を介して送り、コンピュータシステム120によって受信させるおよび/または実行させてもよい。これらの信号は、電磁信号、音響信号、光信号などの形態をとってよく、本明細書で説明する種類のいくつかの実施形態により命令を符号化することができる搬送波のすべての例である。
【０１６５】
通信サブシステム122(および/またはその構成要素)が、一般に、信号を受信し、次いで、バス1015が信号(および/または信号によって運ばれるデータ、命令など)をメモリ110に運ぶことができ、プロセッサ100がメモリ110から命令を取り出して実行する。メモリ110によって受信される命令は、任意選択で、プロセッサ100による実行の前または後のいずれかに、非一時的な記憶デバイス125に記憶されてもよい。
【０１６６】
上記で説明した方法、システム、およびデバイスは例である。様々な実施形態は、必要に応じて、省略してもよいし、置き換えてもよいし、または様々な手順もしくは構成要素/構成部品を追加してもよい。たとえば、代替構成では、説明した方法は、説明した順序とは異なる順序で実行されてよく、かつ/または様々な段階を追加してもよいし、省略してもよいし、および/または組み合わせてもよい。また、いくつかの実施形態に関して説明した特徴を様々な他の実施形態で組み合わせてもよい。同様に、実施形態の異なる態様および要素を組み合わせてもよい。また、技術は進化し、したがって、要素の多くは、それらの具体的な例に本開示の範囲を限定しない例である。
【０１６７】
実施形態の完全な理解を提供するために、説明において、具体的な詳細が記載されている。しかしながら、実施形態は、これらの具体的な詳細がなくても実施され得る。たとえば、実施形態が不明瞭になることを避けるために、よく知られている回路、プロセス、アルゴリズム、構造、および技法は、不必要な詳細を記載せずに示されている。本明細書は、例示的な実施形態のみを提供し、本明細書で説明する種類の実施形態の範囲、適用可能性、または構成を限定することを意図するものではない。むしろ、実施形態の前述の説明は、実施形態を実施するための権能を付与する記載を当業者に提供する。本開示の趣旨および範囲から逸脱することなく、要素の機能および構成に様々な変更を加えてもよい。
【０１６８】
また、いくつかの実施形態について、流れ図またはブロック図として示されるプロセスとして説明した。それぞれが動作を逐次プロセスとして説明することがあるが、動作の多くは、並列にまたは同時に実行することができる。さらに、動作の順序を並べ替えてもよい。プロセスは、図に含まれない追加のステップを有してもよい。その上、方法の実施形態は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、またはこれらの何らかの組合せによって実施され得る。関連するタスクを実行するためのプログラムコードまたはコードセグメントは、ソフトウェア、ファームウェア、ミドルウェア、またはマイクロコードにおいて実施されるとき、記憶媒体などのコンピュータ可読媒体に記憶することができる。プロセッサは、この関連するタスクを実行することができる。
【０１６９】
いくつかの実施形態を説明してきたが、本開示の趣旨から逸脱することなく、様々な修正形態、代替構造、および等価物を使用することができる。たとえば、上記の要素は、単に、より大規模なシステムの構成要素であってもよく、このより大規模なシステムでは、他のルールが、本明細書で説明する種類の実施形態の適用よりも優先してもよいし、または場合によっては本明細書で説明する種類の実施形態の適用を修正してもよい。また、上記の要素の前、その間、またはその後に始めることができるいくつかのステップが考えられる。したがって、上記の説明は、実施形態の範囲を限定するものではない。
【０１７０】
本開示の範囲から逸脱することなく、様々な適合および修正を加えることができる。したがって、添付の特許請求の範囲の趣旨および範囲は、前述の説明に限定されるべきではない。様々な態様を例として示し説明する本明細書の説明から、実施形態のいくつかの他の態様が当業者には容易に明らかになるであろうことを理解されたい。図面および詳細な説明は、限定としてではなく、本質的に例示として見なされるべきである。
【符号の説明】
【０１７１】
100  プロセッサ
105  動作、バス
110  ワーキングメモリ
115  入力デバイス
120  コンピュータシステム、項目
121  出力デバイス
122  通信サブシステム
125  記憶デバイス
130  発見システム
131  時間的クラスタリングモジュール
132  クラスタマージモジュール
133  持続時間フィルタリングモジュール
134  POR抽出モジュール
135  POR場所モデル
139  フィルタ
140  オペレーティングシステム
145  アプリケーションプログラム
150  認識システム
180  類似度関数
201  オフィスビル
202  受付エリア
203  廊下、エリア
204  第1のオフィス、事務室
205  第2のオフィス
206  カフェテリア
207  階段吹抜け
241  ショッピングモール
242  第1の店舗
243  歩道
244  第2の店舗
245  第3の店舗
246  レストラン
247  第4の店舗
250  パス
251  パス
301  動作
302  動作
303  動作
304  動作
305  動作
【図１Ａ】
2014532353.tif 000009
【図１Ｂ】
2014532353.tif 000010
【図２Ａ】
2014532353.tif 000011
【図２Ｂ】
2014532353.tif 000012
【図３Ａ】
2014532353.tif 000013
【図３Ｃ】
2014532353.tif 000014
【図４Ａ】
2014532353.tif 000015
【図４Ｂ】
2014532353.tif 000016
【図５Ａ】
2014532353.tif 000017
【図５Ｂ】
2014532353.tif 000018
【図５Ｃ】
2014532353.tif 000019
【図５Ｄ】
2014532353.tif 000020
【図５Ｅ】
2014532353.tif 000021
【図６Ａ】
2014532353.tif 000022
【図６Ｂ】
2014532353.tif 000023
【図６Ｃ】
2014532353.tif 000024
【図６Ｄ】
2014532353.tif 000025
【図６Ｅ】
2014532353.tif 000026
【図６Ｆ】
2014532353.tif 000027
【図６Ｇ】
2014532353.tif 000028
【図６Ｈ】
2014532353.tif 000029
【図７】
2014532353.tif 000030
【図８Ａ】
2014532353.tif 000031
【図８Ｂ】
2014532353.tif 000032
【図８Ｃ】
2014532353.tif 000033
【図８Ｄ】
2014532353.tif 000034
【図９Ａ】
2014532353.tif 000035
【図９Ｂ】
2014532353.tif 000036
【図９Ｃ】
2014532353.tif 000037
【図９Ｄ】
2014532353.tif 000038
【図９Ｅ】
2014532353.tif 000039
【図９Ｆ】
2014532353.tif 000040
【図９Ｇ】
2014532353.tif 000041
【図３Ｂ】
2014532353.tif 000042
【図４Ｃ】
2014532353.tif 000043
【手続補正書】
【提出日】平成25年7月26日(2013.7.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
関連場所を発見する方法であって、
ワイヤレス信号の測定値のセットをコンピューティングデバイスによって受信するステップと、
1つまたは複数の場所を前記コンピューティングデバイスによって識別するステップであって、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有する、識別するステップと、
2つの重心の比較に少なくとも基づいて、前記2つの重心を有する対応する2つの場所が新しい関連場所を識別するかどうかを前記コンピューティングデバイスによって判断するステップと、
前記対応する2つの場所に基づいて識別された前記新しい関連場所を前記コンピューティングデバイスによって非一時的なメモリに記憶するステップと
を含む方法。
【請求項２】
前記識別するステップが、各測定値が得られた時間とは無関係に実行され、
各場所が、前記サブセット内の測定値における類似性によって決定される大きさを有する、
請求項1に記載の方法。
【請求項３】
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信するステップと、
前記対応する2つの場所に関連付けられた2つのラベルを前記コンピューティングデバイスによって比較し、前記2つのラベルが類似しているかどうかチェックするステップと
をさらに含み、
前記記憶するステップがさらに、前記2つのラベルが類似していると判断されたことに基づいて実行される、
請求項2に記載の方法。
【請求項４】
前記1つまたは複数のラベルが少なくとも2人の異なるユーザから取得される、
請求項3に記載の方法。
【請求項５】
前記1つまたは複数のラベルの第1のセットがパブリックと指定され、
前記1つまたは複数のラベルの第2のセットが、前記少なくとも2人の異なるユーザのうち少なくとも1人のユーザに対して、プライベートと指定される、
請求項4に記載の方法。
【請求項６】
前記識別するステップが、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項1に記載の方法。
【請求項７】
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックするステップ
をさらに含む、請求項6に記載の方法。
【請求項８】
前記類似性の尺度が、少なくとも、類似度関数を実行して前記各測定値を前記サブセット内の測定値の重心と比較することによって取得される、
請求項7に記載の方法。
【請求項９】
前記各測定値が、送信機の対応するグループの識別子のグループと、前記送信機の対応するグループからのワイヤレス信号の強度とを含み、
前記重心が、前記送信機の対応するグループからのワイヤレス信号の強度の平均値のグループを含み、
前記測定値を得る際に、各平均値が、測定された前記送信機の対応するワイヤレス信号の複数の強度を求めて各送信機に対して計算される、
請求項8に記載の方法。
【請求項１０】
前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成するステップをさらに含み、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項6に記載の方法。
【請求項１１】
前記ワイヤレス信号の測定値のセット内の複数のサブセットを、追加測定値のサブセットと比較して、前記新しい関連場所を識別するステップ
をさらに含む、請求項10に記載の方法。
【請求項１２】
前記ワイヤレス信号の測定値のセット内の複数のサブセットを、測定値の別のセット内のサブセットと比較して、既知の関連場所を識別するステップ
をさらに含む、請求項6に記載の方法。
【請求項１３】
前記判断するステップが地理情報とは無関係に実行される、
請求項1に記載の方法。
【請求項１４】
測定値を処理するためのデバイスであって、
ワイヤレス送受信機と、
前記ワイヤレス送受信機に動作可能に結合された1つまたは複数のプロセッサと、
前記1つまたは複数のプロセッサに動作可能に結合された非一時的なメモリと、
前記非一時的なメモリ内に保持されたソフトウェアであって、前記1つまたは複数のプロセッサ内で実行されると、前記1つまたは複数のプロセッサに、
ワイヤレス信号の測定値のセットを受信させ、
1つまたは複数の場所を識別させ、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有し、
2つの重心の比較に少なくとも基づいて、前記2つの重心を有する対応する2つの場所が新しい関連場所を識別するかどうかを判断させ、
前記対応する2つの場所に基づいて識別された前記新しい関連場所を前記非一時的なメモリに記憶させる、ソフトウェアと
を備えるデバイス。
【請求項１５】
前記1つまたは複数の場所の識別が、各測定値が得られた時間とは無関係であり、
各場所が、前記サブセット内の測定値における類似性によって決定される大きさを有する、
請求項14に記載のデバイス。
【請求項１６】
前記ソフトウェアが、前記1つまたは複数のプロセッサに、さらに、
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信させ、
前記対応する2つの場所に関連付けられた2つのラベルを比較させ、前記2つのラベルが類似しているかどうかチェックさせ、
前記非一時的なメモリ内での前記関連場所の記憶が、前記2つのラベルが類似していると判断されたことにさらに基づく、
請求項15に記載のデバイス。
【請求項１７】
前記1つまたは複数のラベルが少なくとも2人の異なるユーザから取得される、
請求項16に記載のデバイス。
【請求項１８】
前記1つまたは複数の場所の識別が、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項14に記載のデバイス。
【請求項１９】
前記ソフトウェアが、前記1つまたは複数のプロセッサに、さらに、
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックさせる、
請求項18に記載のデバイス。
【請求項２０】
前記類似性の尺度が、少なくとも、類似度関数を実行して前記各測定値を前記サブセット内の測定値の重心と比較することによって取得される、
請求項19に記載のデバイス。
【請求項２１】
前記ソフトウェアが、前記1つまたは複数のプロセッサに、さらに、前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成させ、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項18に記載のデバイス。
【請求項２２】
前記対応する2つの場所に基づいて前記新しい場所を識別するための判断が地理情報とは無関係である、
請求項14に記載のデバイス。
【請求項２３】
関連場所を発見するソフトウェアを備える非一時的なコンピュータ可読記憶媒体であって、前記ソフトウェアが、プロセッサによって実行されると、
ワイヤレス信号の測定値のセットを受信するステップと、
1つまたは複数の場所を識別するステップであって、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有する、識別するステップと、
2つの重心の比較に少なくとも基づいて、前記2つの重心を有する対応する2つの場所が新しい関連場所を識別するかどうかを判断するステップと、
前記対応する2つの場所に基づいて識別された前記新しい関連場所を非一時的なメモリに記憶するステップと
を含む方法内のステップを実行する、非一時的なコンピュータ可読記憶媒体。
【請求項２４】
前記1つまたは複数の場所の識別が、各測定値が得られた時間とは無関係であり、
各場所が、前記サブセット内の測定値における類似性によって決定される大きさを有する、
請求項23に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２５】
前記方法内の前記ステップが、
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信するステップと、
前記対応する2つの場所に関連付けられた2つのラベルを比較して、前記2つのラベルが類似しているかどうかチェックするステップと
をさらに含み、
前記非一時的なメモリ内での前記関連場所の記憶が、前記2つのラベルが類似していると判断されたことにさらに基づく、
請求項24に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２６】
前記1つまたは複数の場所の識別が、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項23に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２７】
前記方法内の前記ステップが、
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックするステップ
をさらに備える、請求項26に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２８】
前記類似性の尺度が、少なくとも、類似度関数を実行して前記各測定値を前記サブセット内の測定値の重心と比較することによって取得される、
請求項27に記載の非一時的なコンピュータ可読記憶媒体。
【請求項２９】
前記方法内の前記ステップが、
前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成し、少なくとも1つの子ノードが前記サブセットに基づいて作成するステップ
をさらに備える、請求項26に記載の非一時的なコンピュータ可読記憶媒体。
【請求項３０】
前記対応する2つの場所に基づいて前記新しい場所を識別するための判断が地理情報とは無関係である、
請求項23に記載の非一時的なコンピュータ可読記憶媒体。
【請求項３１】
メモリに結合されたプロセッサとワイヤレス受信機とを備えるシステムであって、
ワイヤレス信号の測定値のセットを取得するための手段と、
1つまたは複数の場所を識別するための手段であって、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有する、識別するための手段と、
2つの重心の比較に少なくとも基づいて、前記2つの重心を有する対応する2つの場所が新しい関連場所を識別するかどうかを判断するための手段と、
前記対応する2つの場所に基づいて識別された前記新しい関連場所を非一時的なメモリに記憶するための手段と
を備えるシステム。
【請求項３２】
前記判断が、各測定値が得られた時間とは無関係に実行され、
各場所が、前記サブセット内の測定値における類似性によって決定される大きさを有する、
請求項31に記載のシステム。
【請求項３３】
それぞれ前記1つまたは複数の場所に関連付けられるべき1つまたは複数のラベルに関するユーザ入力を受信するための手段と、
前記対応する2つの場所に関連付けられた2つのラベルを比較して、前記2つのラベルが類似しているかどうかチェックするための手段と
をさらに備え、
前記記憶するための手段がさらに、前記2つのラベルが類似していると判断されたことに基づく、
請求項32に記載のシステム。
【請求項３４】
前記識別するための手段が、前記2つの重心の各々の前記サブセット内の測定値が互いに対して時間的に順次測定されることに基づく、
請求項31に記載のシステム。
【請求項３５】
類似性の尺度に関するテストに前記サブセット内の各測定値が合格するかどうかチェックするための手段
をさらに備える、請求項34に記載のシステム。
【請求項３６】
前記ワイヤレス信号の測定値のセットに基づくツリーのルートノードおよび前記ルートノードに接続された前記ツリー内の複数の子ノードを作成するための手段をさらに備え、少なくとも1つの子ノードが前記サブセットに基づいて作成される、
請求項34に記載のシステム。
【請求項３７】
拡張された関連場所を発見するための装置であって、
少なくとも1つのプロセッサと、
コンピュータ可読命令を記憶する非一時的なメモリであって、前記コンピュータ可読命令が、前記少なくとも1つのプロセッサによって実行されると、前記装置に、
ワイヤレス信号の測定値のセットを取得させ、
1つまたは複数の場所を識別させ、各場所が、前記ワイヤレス信号の測定値のセット内のサブセットを使用することによって取得される重心を有し、
2つの重心の比較に少なくとも基づいて、前記2つの重心を有する対応する2つの場所が新しい関連場所を識別するかどうかを判断させ、
前記対応する2つの場所に基づいて識別された前記新しい関連場所を前記非一時的なメモリに記憶させる、非一時的なメモリと
を備える装置。
【請求項３８】
前記対応する2つの場所に基づいて新しい場所を識別するための判断が地理情報とは無関係であり、
各場所が、前記サブセット内の測定値における類似性によって決定される大きさを有する、
請求項37に記載の装置。
【国際調査報告】
2014532353.tif 000044
2014532353.tif 000045