직교 배열
Orthogonal array수학에서 직교 배열은 "표"(배열)이며, 그 항목은 고정된 유한한 기호 집합(일반적으로 {1,2,...,n})에서 나온 것으로, 표의 t 열을 선택할 때마다 이러한 열에 제한된 각 행의 항목들을 취함으로써 형성된 기호들의 순서가 모두 t-t-tuple인 방식으로 배열된다.같은 횟수만큼 삐삐를 반복하다 숫자 t를 직교 배열의 강도라고 한다. 다음은 기호 집합 {1,2} 및 강도 2가 있는 직교 배열의 간단한 예:
1 1 1 2 2 1 1 2 2 2 1 2
첫 번째와 세 번째 열에 제한되는 행, 즉 (1,1), (2,1), (1,2), (2,2)에 의해 형성된 네 개의 순서 쌍은 모두 두 요소 집합의 가능한 순서 쌍이며 각각 한 번씩 정확하게 나타난다. 두 번째와 세 번째 열에는 각각 한 번씩 나타나는 (1,1), (2,1), (2,2) 및 (1,2)가 표시된다. 다시 말하지만, 가능한 모든 순서 쌍은 각각 한 번씩 나타난다. 첫 번째 열과 두 번째 열을 사용했다면 같은 문구가 들어 있을 것이다. 따라서 이것은 강도 2의 직교 배열이다.
직교 배열은 표 형식에서 상호 직교 라틴 사각형의 개념을 일반화한다. 이러한 배열은 다른 조합 설계에 많은 연결을 가지며 실험, 코딩 이론, 암호 및 다양한 유형의 소프트웨어 시험의 통계 설계에 응용된다.
정의
t-(v,k,csv) 직교 배열(t ≤ k)은 λvt × k 배열로, 이 배열의 t 열의 모든 부분 집합에서 X 포인트의 모든 t-투플이 정확히 λ 행에 나타나도록 v 포인트가 있는 세트 X에서 항목이 선택된다.
이 공식 정의에서 t-tuple의 반복에 대한 제공(required is number of repeat)이 이루어지며 행의 수는 다른 파라미터에 의해 결정된다.
많은 애플리케이션에서 이러한 매개변수에는 다음과 같은 이름이 부여된다.
- v는 수준 수입니다.
- k는 요인 수입니다.
- λv는t 실험 런 수입니다.
- t는 힘이고,
- λ은 지수다.
직교 배열은 반복되는 행을 포함하지 않으면 단순하다.
직교 배열은 X가 순서 q의 유한한 필드q F(primary power)이고 배열의 행이 벡터 공간(Fq)의 하위 공간을 형성하는 경우 선형이다.k[1]
모든 선형 직교 배열은 간단하다.
예
2-(4, 5, 1) 직교 배열의 예: 16개의 런이 있는 지수 1의 강도 2, 4 레벨 설계.
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 | 3 |
| 1 | 4 | 4 | 4 | 4 |
| 2 | 1 | 4 | 2 | 3 |
| 2 | 2 | 3 | 1 | 4 |
| 2 | 3 | 2 | 4 | 1 |
| 2 | 4 | 1 | 3 | 2 |
| 3 | 1 | 2 | 3 | 4 |
| 3 | 2 | 1 | 4 | 3 |
| 3 | 3 | 4 | 1 | 2 |
| 3 | 4 | 3 | 2 | 1 |
| 4 | 1 | 3 | 4 | 2 |
| 4 | 2 | 4 | 3 | 1 |
| 4 | 3 | 1 | 2 | 4 |
| 4 | 4 | 2 | 1 | 3 |
2-(3,5,3) 직교 배열의 예([2]보기 쉽도록 전치형으로 작성됨):
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
| 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 0 |
| 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 |
사소한 예
모든 t-(v, t, λ) 직교 배열은 v-set λ 시간의 모든 t-tule을 나열하는 것만으로 쉽게 구성되기 때문에 사소한 것으로 간주될 수 있다.
상호직교 라틴 사각형
2-(v,k,1) 직교 배열은 순서 v의 k - 2 상호 직교 라틴 제곱의 집합과 동일하다.
지수 1, 강도 2 직교 배열은 통계 문헌에서 하이퍼 그레이코 라틴 정사각형 설계로도 알려져 있다.
자연 숫자 {1,...,v} 집합으로 식별된 원소의 v-set에 대해 A를 강도 2, 인덱스 1 직교 어레이로 설정하십시오. 인덱싱 열이라고 하는 A의 두 열을 순서대로 선택하고 수정하십시오. 1 ≤ i, j ≤ v와 함께 순서가 지정된 모든 쌍(i, j)은 인덱싱 열의 행에 정확히 한 번 나타난다. A의 다른 열을 선택하고, A의 인덱싱 열에 (i,j)가 포함된 행에서 이 열에 있는 A의 항목(i,j)인 사각 배열을 만드십시오. 결과 제곱은 순서 v의 라틴 제곱이다. 예를 들어, 2-(3,4,1) 직교 배열을 고려한다.
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 |
| 2 | 1 | 2 | 3 |
| 2 | 2 | 3 | 1 |
| 2 | 3 | 1 | 2 |
| 3 | 1 | 3 | 2 |
| 3 | 2 | 1 | 3 |
| 3 | 3 | 2 | 1 |
(그 순서대로) 3열과 4열을 색인화 열로 선택함으로써, 첫 번째 열은 라틴 사각형을 생성한다.
| 1 | 2 | 3 |
| 3 | 1 | 2 |
| 2 | 3 | 1 |
두 번째 열은 라틴어 사각형을 생성하는 동안,
| 1 | 3 | 2 |
| 3 | 2 | 1 |
| 2 | 1 | 3 |
직교 배열에서 이러한 방식으로 생성된 라틴 사각형은 직교 라틴 사각형이므로 색인 기둥 이외의 k - 2 열은 k - 2 상호 직교 라틴 사각형 세트를 생성한다.
이 구조는 완전히 되돌릴 수 있으므로 강도 2, 지수 1 직교 배열을 상호 직교 라틴어 정사각형 집합에서 구성할 수 있다.[3]
라틴 사각형, 라틴 큐브 및 라틴 하이퍼큐브
직교 배열은 실험의 통계적 설계에 관심이 있는 이러한 다양한 객체를 설명할 수 있는 균일한 방법을 제공한다.
라틴 네모
앞의 절에서 언급한 바와 같이, 순서 n의 라틴 사각형은 2-(n, 3, 1) 직교 배열로 생각할 수 있다. 실제로 직교 배열은 순서 쌍의 구별되는 열을 인덱싱 열로 사용할 수 있기 때문에 6개의 라틴 사각형으로 이어질 수 있다. 그러나 이것들은 모두 동위원소로서 동등하다고 간주된다. 구체성을 위해 우리는 항상 자연 순서의 처음 두 열이 색인 열로 사용된다고 가정해야 한다.
라틴 큐브
통계를 볼 때 그 문헌에서, 라틴어의 큐브는 n×n× n3차원 매트릭스 n층들로 구성되어, 각 각 모든 n고유 요소를 나타나는 큐브의 반대쪽 얼굴의 3쌍의 각 층 평행에 표시되는 n고유 요소를n2번, 정리 반복됩니다와 행과 n기둥 같은. each는 그 층에서 정확히 n번 반복된다.[4]
이 정의에서 라틴 큐브 층은 라틴 사각형이 될 필요가 없다는 점에 유의하십시오. 실제로 행, 열 또는 파일(다른 층에서 특정 위치의 셀)은 n 기호의 순열이 될 필요가 없다.[5]
순서 n의 라틴 큐브는 2-(n, 4, n) 직교 배열과 동일하다.[2]
두 개의 라틴어 큐브 n 순서는 직교하며, 만약 두 큐브의 해당 셀에서 선택한3 n 쌍의 원소 중에서 각각 구별되는 순서의 쌍이 정확히 n번 발생하는 경우.
순서 n의 k - 3 상호 직교 라틴 큐브 세트는 2-(n, k, n) 직교 배열과 동일하다.[2]
순서 3의 상호 직교 라틴 큐브 쌍의 예는 위의 예제에서 2-(3,5,3) 직교 배열은 2-(3,5,3)이다.
제약조건이 없는 라틴 사각형의 경우와 달리, 라틴 큐브의 직교 배열 표현에 대한 색인 열은 3-(n,3,1) 직교 배열을 형성하도록 선택해야 한다.
라틴어 하이퍼큐브
r번째 클래스의 순서 n의 m차원 라틴어 하이퍼큐브는 n × n × ...이다. 각각 n개의rm − r 구별되는 원소가 n번 반복되며, 각 원소가 n개의 평행(m - 1)차원 선형 서브스페이스(또는 " "")의 각 m 세트에서 정확히 n번 발생하는 ×n m차원 매트릭스. 동일한 순서의 n과 r등급의 두 개의 라틴어 하이퍼큐브는 다른 하나에 중첩될 때 한 개의 모든 요소가 다른 원소와 정확히 n번 발생하며m − 2r 직교한다고 한다.[6]
순서 n의 k - m 상호 직교 m-차원 라틴 하이퍼큐브 세트는 2-(n, k, nm − 2) 직교 배열과 동등하며, 여기서 색인화 열이 m-(n, m, 1) 직교 배열을 형성한다.
역사
라틴 사각형과 상호 직교 라틴 사각형의 개념은 키센(1942)에 의해 라틴 큐브와 하이퍼큐브, 직교 라틴 큐브와 하이퍼큐브로 일반화되었다.[7] Rao(1946)는 이러한 결과를 강도 t로 일반화했다. C. R. R. Rao로 인해 이러한 사상의 일반화로서 직교 배열의 현재 개념은 Rao(1947년)에 나타난다.[8]
기타 구성
하다마드 행렬
순서 4m의 Hadamard 행렬이 존재하는 경우, 2-(2, 4m - 1, m) 직교 배열도 존재한다.
H를 표준화된 형태로 순서 4m의 Hadamard 행렬로 한다(첫 번째 행과 열 항목은 모두 +1이다). 원하는 직교 배열을 얻으려면 첫 번째 행을 삭제하고 전치물을 취하십시오.[9]
아래 순서 8 표준화된 Hadamard 행렬(부호로만 표시되는 ±1 항목)
| + | + | + | + | + | + | + | + |
| + | + | + | + | − | − | − | − |
| + | + | − | − | + | + | − | − |
| + | + | − | − | − | − | + | + |
| + | − | + | − | + | − | + | − |
| + | − | + | − | − | + | − | + |
| + | − | − | + | + | − | − | + |
| + | − | − | + | − | + | + | − |
2-(2,7,2) 직교 배열 생성:[10]
| + | + | + | + | + | + | + |
| + | + | + | − | − | − | − |
| + | − | − | + | + | − | − |
| + | − | − | − | − | + | + |
| − | + | − | + | − | + | − |
| − | + | − | − | + | − | + |
| − | − | + | + | − | − | + |
| − | − | + | − | + | + | − |
1, 2, 4열은 인덱싱 열로 사용하여 나머지 열은 순서 2의 서로 직교하는 네 개의 라틴 큐브를 생성한다.
코드
C d (Fq)n를 최소 거리 d를 갖는 치수 m의 선형 코드가 되도록 한다. 그⊥ 다음 C(벡터 서브공간 C의 직교보완물)는 (선형) (d - 1)-(q, n, λ) 직교배열로, 여기서
λ = qn − m − d + 1.[11]
적용들
임계값 구성표
비밀 공유(비밀 나누기라고도 함)는 참가자 그룹 사이에 비밀을 분배하는 방법으로 구성되며, 각 그룹에는 비밀의 몫이 할당된다. 비밀은 서로 다른 유형의 충분한 주식을 결합해야만 재구성할 수 있다. 개별 주식은 그 자체로 아무 쓸모가 없다. 비밀 공유 체계는 비밀 획득 기준을 충족하지 못하는 모든 참가자가 비밀이 무엇인지에 대한 추가 지식이 없는 경우 공유가 없는 개인이 하는 것보다 완벽하다.
한 종류의 비밀 공유 계획에는 한 명의 딜러와 n명의 플레이어가 있다. 딜러는 선수들에게 비밀의 몫을 주지만 구체적인 조건이 충족돼야 선수들이 비밀을 재구성할 수 있다. 딜러는 t(임계점용) 이상의 플레이어가 함께 비밀을 재구성할 수 있지만 t 플레이어보다 적은 그룹도 이를 재구성할 수 없는 방식으로 각 플레이어에 공유를 부여함으로써 이를 달성한다. 그러한 시스템을 (t, n)-임계(streshold) 체계라고 한다.
t-(v, n + 1, 1) 직교 배열을 사용하여 완벽한 (t, n)-임계 구조를 구성할 수 있다.[12]
- A를 직교 배열로 두십시오. 첫 번째 n개의 컬럼은 선수들에게 공유를 제공하는 데 사용되며, 마지막 컬럼은 공유할 비밀을 나타낸다. 딜러가 비밀 S를 공유하고자 하는 경우, 마지막 항목이 S인 A의 행만 이 계획에 사용된다. 딜러는 이러한 행 중 하나를 무작위로 선택하고, i열의 이 행에 있는 엔트리를 공유로 플레이어 i에게 나눠준다.
요인 설계
요인 실험은 여러 요인(수위, 항생제, 비료 등)을 다양한(하지만 적분) 수준(높음, 낮음 또는 다양한 중간 수준)에서 각 실험 단위에 적용하는 통계적으로 구조화된 실험이다.[13] 완전 요인 실험에서는 요인 수준의 모든 조합을 테스트해야 하지만 교란 요인에 영향을 최소화하기 위해 모든 실험 런에서 수준을 변경해야 한다.
강도 2의 직교 배열을 사용하여 요인 실험을 설계할 수 있다. 열은 다양한 요인을 나타내며 항목은 요인을 적용할 수 있는 수준(모든 요인을 동일한 수준 수로 적용할 수 있다고 가정)이다. 실험 런은 직교 배열의 행으로, 즉 행에 나타나는 수준에서 해당 요인을 적용한다. 이러한 설계 중 하나를 사용할 때는 설계가 허용하는 한 처리 단위와 시행 순서를 랜덤화해야 한다. 예를 들어 적절한 크기의 직교 배열을 사용 가능한 배열에서 랜덤하게 선택한 다음 런 순서를 랜덤화하는 것이 권장된다.
품질관리
직교 배열은 1950년대 초 인도 통계 연구소를 방문했을 때 일어난 다구치 게니치의 타구치 방법 개발에 중심적인 역할을 했다. 그의 방식은 일본과 인도 산업에서 성공적으로 적용되고 채택되었으며, 그 후 미국 산업에서도 일부 유보적인 태도를 보이기도 했다.
테스트
직교 배열 시험은 체계적이고 통계적인 소프트웨어 시험 방법인 블랙박스 시험 기법이다.[14][15] 시스템에 대한 입력의 수가 상대적으로 작지만 너무 커서 시스템에 대한 모든 입력의 전체 시험을 수행할 수 없을 때 사용된다.[14] 특히 컴퓨터 소프트웨어 시스템 내에서 오류 논리학 관련 오류를 찾아내는 데 효과적이다.[14] 직교 배열은 사용자 인터페이스 테스트, 시스템 테스트, 회귀 테스트 및 성능 테스트에 적용할 수 있다. 단일 치료로 구성된 요인 수준의 순열은 반응과 상관관계가 없으므로 각 치료는 고유한 정보를 제공한다. 그러한 치료에서 실험을 조직하는 것의 순효과는 동일한 정보가 최소 실험 횟수에 수집된다는 것이다.
참고 항목
메모들
- ^ Stinson 2003, 페이지 225
- ^ a b c Dénes & Keedwell 1974, 페이지 191
- ^ Stinson 2003, 페이지 140–141, 섹션 6.5.1
- ^ Dénes & Keedwell 1974, 페이지 187은 그 정의를 키센(1950, 페이지 21)에게 돌렸다.
- ^ 조합자가 선호하는 정의에서 각 행, 열, 파일에는 기호의 순열이 포함되지만 이는 순열 큐브라고 하는 특수한 유형의 라틴 큐브일 뿐이다.
- ^ Dénes & Keedwell 1974, 페이지 189
- ^ 라그하바라오 1988, 페이지 9
- ^ 라그하바라오 1988, 페이지 10
- ^ Stinson 2003, 페이지 225, 정리 10.2
- ^ Stinson 2003, 페이지 226, 예 10.3
- ^ Stinson 2003, 페이지 231, 정리 10.17
- ^ Stinson 2003, 페이지 262, 정리 11.5
- ^ 거리 & 거리 1987, 페이지 194, 섹션 9.2
- ^ a b c Pressman, Roger S (2005). Software Engineering: A Practitioner's Approach (6th ed.). McGraw–Hill. ISBN 0-07-285318-2.
- ^ Phadke, Madhav S. "Planning Efficient Software Tests". Phadke Associates, Inc.
Numerous articles on utilizing Orthogonal Arrays for Software and System Testing.
참조
- Box, G. E. P.; Hunter, W. G.; Hunter, J. S. (1978). Statistics for Experimenters: An Introduction to Design, Data Analysis, and Model Building. John Wiley and Sons.
- Dénes, J.; Keedwell, A. D. (1974), Latin squares and their applications, New York-London: Academic Press, ISBN 0-12-209350-X, MR 0351850
- Hedayat, A.S.; Sloane, N.J.A.; Stufken, J. (1999), Orthogonal arrays, theory and applications, New York: Springer
- Kishen, K. (1942), "On latin and hyper-graeco cubes and hypercubes", Current Science, 11: 98–99
- Kishen, K. (1950), "On the construction of latin and hyper-graeco-latin cubes and hypercubes", J. Indian Soc. Agric. Statistics, 2: 20–48
- Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (corrected reprint of the 1971 Wiley ed.). New York: Dover.
- Raghavarao, Damaraju and Padgett, L.V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific.
{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크) - Rao, C.R. (1946), "Hypercubes of strength ''d'' leading to confounded designs in factorial experiments", Bulletin of the Calcutta Mathematical Society, 38: 67–78
- Rao, C.R. (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", Supplement to the Journal of the Royal Statistical Society, 9 (1): 128–139, doi:10.2307/2983576, JSTOR 2983576
- Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2
- Street, Anne Penfold & Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. ISBN 0-19-853256-3.
외부 링크
- 하이퍼 그레이코라틴 사각형 설계
- PROC PRATEX를 사용한 SAS 예제
- 쿠펠드, 워렌 F. "직교 배열" SAS 연구소 SAS는 117,000개 이상의 직교 어레이 카탈로그를 제공한다.
이 글은 국립표준기술원 웹사이트 https://www.nist.gov의 공공 도메인 자료를 통합한 것이다.
